Patent Description:
Computer networks are interconnected sets of computing devices that exchange data, such as the Internet. Communication protocols such as the User Datagram Protocol (UDP) define systems of rules for exchanging data using computer networks. UDP adheres to a connectionless communication model without guaranteed delivery, ordering, or non-duplicity of datagrams. A datagram is a basic unit for communication and includes a header and a payload. The header is metadata specifying aspects of the datagram, such as a source port, a destination port, a length of the datagram, and a checksum of the datagram. The payload is the data communicated by the datagram. Computing devices communicating using UDP transmit datagrams to one another via the computer network.

Connectionless communication protocols such as UDP generally have lower overhead and latency than connection-oriented communication protocols like the Transmission Control Protocol (TCP), which establish connections between computing devices before transmitting data. However, existing connectionless communication protocols are inadequate for data transfers that require less latency than is accommodated by the existing art. For example, an augmented reality (AR) environment streaming at <NUM> frames per second (FPS) may require latency an order of magnitude lower than provided by current techniques. In such an AR environment, the frames are spaced at approximately sixteen millisecond intervals, while current network protocols typically provide latency of approximately one hundred milliseconds (or more).

As such, with existing techniques, a user does not interact with the current state of the AR environment, only a recent state. A user using a client to interact with the AR environment over a computer network may interact with an old state of AR positional data. For example, in an AR game, a player may see an AR object at an old location (e.g., where the object was <NUM> milliseconds previously), while the AR positional data in fact has a new location for the object (e.g. the AR object has been moved by another player). This latency in communication between the client and a server hosting or coordinating the AR game may lead to a frustrating user experience. This problem may be particularly acute where more than one user is participating in the AR game because the latency may cause a noticeable delay between the actions of one player showing up in other players' views of the AR environment.

<CIT> relates to augmented reality mobile edge computing. <CIT> relates to a remote message routing device and methods thereof.

Augmented reality (AR) systems supplement views of the real world with computer-generated content. Incorporating AR into a parallel-reality game may improve the integration between the real and virtual worlds. AR may also increase interactivity between players by providing opportunities for them to participate in shared gaming experiences in which they interact. For example, in a tank battle game, players might navigate virtual tanks around a real-world location, attempting to destroy each other's tanks. The movement of the tanks may be limited by real-world geography (e.g., the tanks move more slowly through rivers, move more quickly on roads, cannot move through walls, etc.).

Existing AR session techniques involve a server maintaining a master state and periodically synchronizing the local state of the environment at client devices to the master state via a network (e.g., the internet). However, synchronizing a device's local state may take a significant amount of time (e.g., ~<NUM> of milliseconds), which is detrimental to the gaming experience. The player is, in effect, interacting with a past game state rather than the current game state. This problem may be particularly acute where more than one user is participating in the AR game because the latency causes a noticeable delay between the actions of one player showing up in other players' views. For example, if one player moves an AR object in the world, other players may not see it has moved until one hundred milliseconds (or more) later, which is a human-perceptible delay. As such, another player may try to interact with the object in its previous location and be frustrated when the game corrects for the latency (e.g., by declining to implement the action requested by the player or initially implementing the action and then revoking it when the player's client device next synchronizes with the server).

This and other problems may be addressed by processing datagrams at an intermediary node (e.g., a cell tower). Latency may be reduced using a peer-to-peer (P2P) protocol that exchanges game updates between clients connected to the same edge node without routing the updates via the game server. For example, using these approaches, latency may be reduced to ~<NUM> milliseconds or less. Furthermore, this may increase bandwidth availability enabling a greater number of players to share a common AR experience.

The figures and the following description describe certain embodiments by way of illustration only. One skilled in the art will readily recognize from the following description that alternative embodiments of the structures and methods may be employed without departing from the principles described. Reference will now be made to several embodiments, examples of which are illustrated in the accompanying figures. Wherever practicable similar or like reference numbers are used in the figures to indicate similar or like functionality. Where elements share a common numeral followed by a different letter, the elements are similar or identical. The numeral alone refers to any one or any combination of such elements.

As disclosed herein, a datagram-responsive computer network protocol ("the disclosed protocol") may lower computer network latency (e.g., in one embodiment, the latency is ~<NUM> milliseconds). <FIG> illustrates a computer network that communicates using the disclosed protocol, according to one embodiment. The figure illustrates a simplified example using block figures for purposes of clarity. The computer network includes two clients 110A and 110B, a server <NUM>, and a cell tower <NUM>. In other embodiments the computer network may include fewer, additional, or other components, such as additional clients, servers <NUM>, cell towers <NUM>, or other network nodes. For example, the computer network may be a local area network (LAN) using one or more WiFi routers as network nodes rather than a cell tower <NUM>.

A client 110A or 110B is a computing device such as a personal computer, laptop, tablet computer, smartphone, or so on. Clients 110A and 110B can communicate using the disclosed protocol. The server <NUM> is similarly a computing device capable of communication via the disclosed protocol. Clients 110A and 110B may communicate with the server <NUM> using the disclosed protocol, or in some embodiments may use a different protocol. For example, clients 110A and 110B may communicate with one another using the disclosed protocol but with the server <NUM> using TCP. In an embodiment, each client 110A or 110B includes a local AR module and the server <NUM> includes a master AR module. Each local AR module communicates AR data to local AR modules upon other clients and/or the master AR module upon the server <NUM>.

The cell tower <NUM> is a network node that serves as an intermediary node for end nodes such as clients 110A and 110B. As described above, in other embodiments the computer network may include other network nodes replacing or in addition to a cell tower <NUM> but enabling similar communication. The cell tower <NUM> increases the range over which messages may be communicated. For example, a client 110A may send a message to a cell tower <NUM> which proceeds to transmit the message to a client 110B, where client 110A would not have been able to communicate with client 110B without the cell tower <NUM>.

In an embodiment, client 110A, 110B communications may be routed through the server <NUM> or peer-to-peer (P2P). Communications routed through the server <NUM> may go from a first client 110A to the server <NUM> via the cell tower <NUM> and then back through the cell tower <NUM> to a second client 110B. In contrast, P2P communication may go from the first client 110A to the cell tower <NUM> and then directly to the second client 110B. Note that in some cases, the communications may pass through other intermediary devices, such as signal boosters. As used herein, a communication is considered P2P if it is routed to the target client 110B without passing through the server <NUM>. For example, a message (e.g., a datagram) may be sent P2P if the target client 110B is connected to the same cell tower <NUM> as the sending client 110A and routed via the server <NUM> otherwise. In another embodiment, clients 110A and 110B communicate entirely using P2P. Furthermore, in some embodiments, UDP hole punching may be used to establish a connection among two or more clients.

In one embodiment, the clients 110A and 110B use a coordination service (e.g., hosted at the server and communicated with via TCP) to synchronize IP addresses. The clients 110A and 110B can then communicate (e.g., via UDP) using public facing IP addresses or a local area network (LAN). For example, a first client 110A might send a request via TCP to the coordination service to join a local AR shared environment. The coordination service may provide the first client 110A with the IP address of a second client 110B connected to the AR environment (e.g., via the same cell tower <NUM>). The coordination service may also provide the first client's IP address to the second client 110B or the first client 110A may provide it directly using the second client's IP address (as provided by the coordination service). In some embodiments, the coordination service may prompt the second client 110B to approve the first client 110A (e.g., by requesting user confirmation or checking a list of approved clients to connect with the second client 110B) before the second client's IP address is provided.

<FIG> illustrates a datagram <NUM> configured according to the disclosed protocol, according to one embodiment. The datagram <NUM> includes a payload <NUM>, which as described above is the content of the datagram <NUM>. The datagram <NUM> also includes a header <NUM>, a portion of which is a P2P flag <NUM>, also known as an indicator. The header may be similar to a UDP header plus a P2P flag <NUM>, or may contain different or additional metadata in addition to the P2P flag. The P2P flag is used to determine whether the datagram <NUM> is sent to the server <NUM> or is sent P2P to another client 110A and 110B. In other embodiments the P2P flag <NUM> is replaced with one or more other indicators within the header providing similar functionality.

The cell tower <NUM> receives <NUM> a datagram <NUM> from client 110A and determines how to route the datagram based on the P2P flag <NUM>. In one embodiment, the P2P flag <NUM> may be set by the sending client 110A to indicate that the datagram <NUM> should be sent P2P if possible. The cell tower <NUM> analyzes the datagram <NUM> and, assuming the P2P flag <NUM> indicates the datagram <NUM> should be sent P2P, determines whether the target client 110B is currently connected to the cell tower (e.g., by comparing an identifier of the target client 110B to a list of currently connected clients). If the target client 110B is connected to the cell tower <NUM>, the datagram <NUM> is sent to it without going via the server <NUM>. In contrast, if the target client 110B is not connected to the cell tower <NUM>, the datagram <NUM> is sent to the server <NUM> to be sent on to the target client 110B (e.g., via a second cell tower <NUM> to which it is currently connected). For example, the server <NUM> might maintain a database or other list of which cell towers <NUM> are currently or have been recently connected to which client devices 110A and 110B. In some embodiments, the cell tower <NUM> may send the datagram <NUM> to both the target client 110B and the server <NUM>.

In another embodiment, the P2P flag <NUM> may be an identifier of an AR session, a user, a device, a game account, or the like. The cell tower <NUM> maintains a list of P2P flags <NUM> for which the datagram <NUM> should be sent P2P (or P2P if possible). The cell tower <NUM> analyzes <NUM> the datagram <NUM> to determine whether it should be sent via the server <NUM> or P2P. If the P2P flag <NUM> includes an identifier on the list, the datagram <NUM> is a P2P message and the cell tower <NUM> sends <NUM> the datagram <NUM> to the target client. For example, if the header <NUM> of the datagram <NUM> indicates the destination port is that of client 110B, the cell tower <NUM> sends <NUM> the datagram <NUM> to client 110B. In contrast, if the P2P flag <NUM> indicates the datagram <NUM> is not a P2P message, the cell tower <NUM> sends <NUM> the P2P flag <NUM> to the server <NUM>. Alternatively, the list may indicate P2P flags <NUM> for messages that are not to be sent P2P, in which case the default behavior if the P2P flag <NUM> is not on the list is to send the corresponding datagram P2P to the target client (e.g., client 110B).

<FIG> is a block diagram illustrating one embodiment of an intermediary node. In the embodiment shown, the intermediary node is a cell tower <NUM> that includes a routing module <NUM>, a data ingest module <NUM>, an AR environment module <NUM>, a map processing module <NUM>, an authority check module <NUM>, and a local data store <NUM>. The cell tower <NUM> also includes hardware and firmware or software (not shown) for establishing connections to the server <NUM> and clients 110A and 110B for exchanging data. For example, the cell tower <NUM> may connect to the server <NUM> via a fiberoptic or other wired internet connection and clients 110A and 110B using a wireless connection (e.g., <NUM> or <NUM>). In other embodiments, the cell tower <NUM> may include different or additional components. In addition, the functions may be distributed among the elements in a different manner than described.

The routing module <NUM> receives data packets and sends those packets to one or more recipient devices. In one embodiment, the routing module <NUM> receives datagrams <NUM> from clients 110A and 110B and uses the method described with reference to <FIG> to determine where to send the received datagrams. The routing module <NUM> may also receive data packets from the server addressed to either particular clients 110A, 110B or all clients that are connected to the cell tower. The routing module <NUM> forwards the data packets to the clients 110A and 110B to which they are addressed.

The data ingest module <NUM> receives data from one or more sources that the cell tower <NUM> uses to provide a shared AR experience to players via the connected clients 110A and 110B. In one embodiment, the data ingest module <NUM> receives real-time or substantially real-time information about real-world conditions (e.g., from third party services). For example, the data ingest module <NUM> might periodically (e.g., hourly) receive weather data from a weather service indicating weather conditions in the geographic area surrounding the cell tower. As another example, the data ingest module <NUM> might retrieve opening hours for a park, museum, or other public space. As yet another example, the data ingest module <NUM> may receive traffic data indicating how many vehicles are travelling on roads in the geographic area surrounding the cell tower <NUM>. Such information about real-world conditions may be used to improve the synergy between the virtual and real worlds.

The AR environment module <NUM> manages AR environments in which players in the geographic area surrounding the cell tower <NUM> may engage in shared AR experiences. In one embodiment, a client 110A or 110B connects to the cell tower <NUM> while executing an AR game and the AR environment module <NUM> connects the client to an AR environment for the game. All players of the game who connect to the cell tower <NUM> may share a single AR environment or players may be divided among multiple AR environments. For example, there may be a maximum number of players in a particular AR environment (e.g., ten, twenty, one hundred, etc.). Where there are multiple AR environments, newly connecting clients 110A, 110B may be placed in a session randomly or the client may provide a user interface (UI) to enable the player to select which session to join. Thus, a player may elect to engage in an AR environment with friends. In some embodiments, players may establish private AR environments that are access protected (e.g., requiring a password or code to join).

In various embodiments, to enable AR objects (e.g., creatures, vehicles, etc.) to appear to interact with real world features (e.g., to jump over obstacles rather than going through them), the AR environment module <NUM> provides connected clients 110A and 110B with map data representing the real world in the proximity of the client (e.g., stored in the local data store <NUM>). The AR environment module <NUM> may receive location data for a client 110A or 110B (e.g., a GPS location) and provide map data for the geographic area surrounding the client (e.g., within a threshold distance of the client's current position).

The received map data can include one or more representations of the real world. For example, the map data can include a point cloud model, a plane matching model, a line matching model, a geographic information system (GIS) model, a building recognition model, a landscape recognition model, etc. The map data may also include more than one representation of a given type at different levels of detail. For example, the map data may include two or more point cloud models, each including different number of points.

The client 110A, 110B may compare the map data to data collected by one or more sensors to refine the client's location. For example, by mapping the images being captured by a camera on the client 110A, 110B to a point cloud model, the client's location and orientation may be accurately determined (e.g., to within one centimeter and <NUM> degrees). The client 110A, 110B provides the determined location and orientation back to the AR environment module <NUM> along with any actions taken by the player (e.g., shooting, selecting a virtual item to interact with, dropping a virtual item, etc.). Thus, the AR environment module <NUM> can update the status of the game for all players engaged in the AR environment.

The map processing module <NUM> updates map data based on current conditions (e.g., data from the data ingest module <NUM>). Because the real world is not static, the map data in the local data store <NUM> may not represent current real-world conditions. For example, the same park trail in Vermont may look very different in different seasons. In summer, the trail might be clear and the surrounding trees will be covered in foliage. In contrast, in winter, the trail may be blocked by drifts of snow and the trees may be bare. The map processing module <NUM> may transform the map data to approximate such changes.

In one embodiment, the map processing module <NUM> retrieves current condition data to identify a transformation and applies that transformation to the map data. The transformations for different conditions may be defined by heuristic rules, take the form of trained machine-learning models, or use a combination of both approaches. For example, the map processing module <NUM> might receive current weather condition data, select a transformation for the current weather conditions, and apply that transformation to the map data. Alternatively, the map processing module <NUM> may pre-calculate the transformed maps and store them (e.g., in the local data store <NUM>). In this case, when a client 110A or 110B connects to the cell tower, the map processing module determines the current conditions, selects the appropriate pre-calculated version of the map data, and provides that version to the client.

The authority check module <NUM> maintains synchronization between game states of different clients 110A and 110B. In one embodiment, the authority check module <NUM> confirms that game actions received from clients 110A and 110B are consistent with the game state maintained by the AR environment module <NUM>. For example, if two players both try to pick up the same in-game item, the authority check module <NUM> determines which player receives the item (e.g., based on timestamps associated with the requests). As described, the use of a P2P protocol and local processing at the cell tower may significantly reduce the latency of a player's actions being seen at other players' clients. Therefore, the likelihood (and number) of instances of such conflicts arising and being resolved by the authority check module <NUM> is reduced. Therefore, the AR experience may be improved.

The authority check module <NUM> may also maintain synchronization between its copy of the state of the AR environment (the intermediate node state) and a master state maintained by the server <NUM>. In one embodiment, the authority check module <NUM> periodically (e.g., every <NUM> to <NUM> seconds) receives global updates regarding the state of the AR environment from the server <NUM>. The authority check module <NUM> compares these updates to the intermediate node state and resolves any discrepancies. For example, if a player's request to pick up an item was initially approved by the authority check module <NUM> but a game update from the server <NUM> indicates the item was picked up by another player (or otherwise made unavailable) before the player attempted to pick it up, the authority check module <NUM> might send an update to the player's client indicating the item should be removed from the player's inventory.

This process may provide value for clients 110A and 110B located close to a boundary between coverage provided by different cell towers <NUM>. In this case, players connected to different cell towers <NUM> may both be able to interact with the same virtual element. Thus, each individual cell tower <NUM> might initially approve conflicting interactions with the element, but the server <NUM> would detect the conflict and send updates to resolve the conflict (e.g., instructing one of the cell towers to revoke its initial approval of the action and update its local state accordingly).

The local data store <NUM> is one or more non-transitory computer-readable media configured to store data used by the cell tower. In one embodiment, the stored data may include map data, current conditions data, a list of currently (or recently) connected clients 110A and 110B, a local copy of the game state for the geographic region, etc. Although the local data store <NUM> is shown as a single entity, the data may be split across multiple storage media. Furthermore, some of the data may be stored elsewhere in the communication network and accessed remotely. For example, the cell tower <NUM> may access current condition data remotely (e.g., from a third-party server) as needed.

<FIG> illustrates a process for using a low-latency datagram-responsive computer network protocol, according to one embodiment. A cell tower <NUM> receives <NUM> a datagram <NUM> addressed to a client 110A, the target client device. In other embodiments, the cell tower <NUM> may be another type of intermediary node that performs the same operations as the cell tower <NUM> of this embodiment. The datagram <NUM> may have been sent to the cell tower <NUM> from another client device, such as client 110B. The datagram <NUM> also describes an action that occurred in a shared AR environment, such as a one associated with a parallel-reality game in which players' locations in the real world correlate with their positions in the game world.

The cell tower <NUM> analyzes <NUM> the datagram <NUM> to determine whether the datagram is P2P based on its P2P flag <NUM>. If the datagram <NUM> is P2P, the cell tower <NUM> sends <NUM> the datagram <NUM> to the client 110A to update a local state of the shared AR environment at the client 110A to show the action. If the datagram <NUM> is not P2P, the cell tower <NUM> sends <NUM> the datagram <NUM> to the server <NUM> to update a master state of the shared AR environment to show the action and its effects on the AR environment. In some embodiments, the cell tower <NUM> also sends some or all of the P2P datagrams to the server <NUM> after sending them to the client 110A. Thus, the clients 110A and 110B may synchronize their local states based on the P2P message while the server <NUM> maintains the master state that may be used to resolve discrepancies between local states of different clients. By bypassing the server <NUM> for P2P datagrams, the cell tower <NUM> may improve the latency of actions that occur in the AR environment when the datagram does not need processing by the server <NUM> before the local state of the AR environment is updated. In various embodiments, the local state is updated with a latency between <NUM> millisecond and <NUM> milliseconds, <NUM> millisecond and <NUM> milliseconds, <NUM> millisecond and <NUM> milliseconds, or <NUM> millisecond and <NUM> milliseconds.

In some embodiments, the cell tower <NUM> follows multiple steps to determine if a datagram <NUM> is P2P. The cell tower <NUM> analyzes the indicator, or P2P flag <NUM>, to determine if the datagram <NUM> should be sent P2P. The cell tower <NUM> then determines whether client 110A is currently connected to the cell tower <NUM>. If so, the cell tower <NUM> determines that the datagram <NUM> is P2P and can be sent straight to the client 110A instead of the server <NUM>. If the cell tower <NUM> is not current connected to the client 110A, then the cell tower <NUM> sends the datagram <NUM> to the server <NUM>, even if the P2P flag <NUM> indicates that the datagram is P2P.

The process in <FIG> may be further described in relation to an example shared AR environment that is incorporated into a parallel reality game where players throw balls of light at one another, which other players dodge or catch in real-time. When a sending player, associated with client 110B in this example, throws a ball of light at a target player, associated with client 110A, the client 110B creates a datagram <NUM> describing the action (e.g., throwing the ball of light). The action is between players and should occur quickly in the shared AR environment, so the client 110B indicates on the datagram <NUM> that the datagram <NUM> is P2P. The client 110B sends the datagram <NUM> to the cell tower <NUM>, which determines what to do with the datagram <NUM>. Since the datagram is P2P, the cell tower <NUM> sends the datagram <NUM> to client 110A instead of the server <NUM>. Client 110A receives the datagram <NUM> and integrates the data from the payload <NUM> into the local state of the shared AR environment (e.g., shows the target player that the sending player threw a ball of light at them). By not sending the datagram <NUM> to the server <NUM>, the latency is reduced. With a low enough latency, the action may appear in the target player's local presentation as though it happened in real-time, allowing the game play to continue more quickly. This may also allow players to experience a sense of direct interaction with each either. For example, in a virtual catch game, one player could throw a virtual ball and witness another player catch the virtual ball by placing their client in the trajectory of the ball.

The cell tower <NUM> may send the datagram <NUM>, or a copy of the datagram <NUM>, to the server <NUM> after sending the datagram <NUM> to the client 110A. This way, the master state of the shared AR environment is updated to show that the sending player threw a ball of light at the target player. Sending the datagram <NUM> to the server <NUM> may provide a way to resolve conflicts between actions performed by different players that are closer together in time than the latency. Additionally, the server <NUM> may handle sending information from the datagram <NUM> to other cell towers when a client 110A or 110B is connected to another cell tower (e.g., when the client 110A or 110B switches to a neighboring cell tower, a player messages another player with a client 110A or 110B connected to a different cell tower, etc.). In some embodiments, the cell tower may determine a group of clients 110A and 110B that are currently connected to the cell tower <NUM> and the shared AR environment (e.g., all clients that are connected to the cell tower and the AR environment) and send the datagram to the group of clients 110A and 110B so that players associated with those clients 110A and 110B can see the action occur quickly, seemingly in real-time (e.g., with latency of less than <NUM> milliseconds).

<FIG> is a high-level block diagram illustrating an example computer <NUM> suitable for use within the computer network shown in <FIG>, according to an embodiment. The example computer <NUM> includes at least one processor <NUM> coupled to a chipset <NUM>. The chipset <NUM> includes a memory controller hub <NUM> and an input/output (I/O) controller hub <NUM>. A memory <NUM> and a graphics adapter <NUM> are coupled to the memory controller hub <NUM>, and a display <NUM> is coupled to the graphics adapter <NUM>. A storage device <NUM>, keyboard <NUM>, pointing device <NUM>, and network adapter <NUM> are coupled to the I/O controller hub <NUM>. Other embodiments of the computer <NUM> have different architectures.

In the embodiment shown in <FIG>, the storage device <NUM> is a non-transitory computer-readable storage medium such as a hard drive, compact disk read-only memory (CD-ROM), DVD, or a solid-state memory device. The memory <NUM> holds instructions and data used by the processor <NUM>. The pointing device <NUM> is a mouse, track ball, touch-screen, or other type of pointing device, and is used in combination with the keyboard <NUM> (which may be an on-screen keyboard) to input data into the computer system <NUM>. The graphics adapter <NUM> displays images and other information on the display <NUM>. The network adapter <NUM> couples the computer system <NUM> to one or more computer networks.

The types of computers used by the entities of <FIG> can vary depending upon the embodiment and the processing power required by the entity. For example, a server <NUM> might include a distributed database system comprising multiple blade servers working together to provide the functionality described. Furthermore, the computers can lack some of the components described above, such as keyboards <NUM>, graphics adapters <NUM>, and displays <NUM>.

Claim 1:
A method, comprising:
receiving, at a cell tower (<NUM>), a datagram (<NUM>) from a sending client device (110A, 110B) that is connected to a shared augmented reality, AR, environment, the datagram (<NUM>) including data regarding an action in the shared augmented reality environment and an indicator (<NUM>, <NUM>) of whether the datagram (<NUM>) is peer-to-peer, wherein the indicator (<NUM>, <NUM>) identifies an AR session;
determining whether the datagram (<NUM>) is peer-to-peer by comparing the indicator (<NUM>, <NUM>) with a list of indicators maintained by the cell tower (<NUM>);
responsive to determining that the datagram (<NUM>) is peer-to-peer, sending the datagram (<NUM>) to one or more target client devices (110A, 110B) connected to the shared augmented reality environment to update a local state of the shared augmented reality environment at the one or more target client devices (110A, 110B) in view of the action; and
responsive to determining that the datagram (<NUM>) is not peer-to-peer, sending the datagram (<NUM>) to a server (<NUM>) to update a master state of the shared augmented reality environment at the server (<NUM>) in view of the action.