APPARATUS AND METHOD FOR FAIR MESSAGE EXCHANGES IN DISTRIBUTED MULTI-PLAYER GAMES

• US 20110009196A1
• Filed: 09/20/2010
• Published: 01/13/2011
• Est. Priority Date: 02/27/2004
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Paul, Sanjoy, Guo, Katherine H., Mukherjee, Sarit, Rangarajan, Sampath
• Granted Patent: US 8,597,124 B2
• Time in Patent Office: Days
• US Class Current: 463/42
• CPC Class Codes: A63F 13/12 involving interaction between a plurality of game devices, e.g. transmisison or distribution systems protocols for networked virtual reality, networked games H04L29/06034
• CPC Class Codes: A63F 13/30 Interconnection arrangements between game servers and game devices; Interconnection arrangements between game devices; Interconnection arrangements between game servers
• CPC Class Codes: A63F 13/358 Adapting the game course according to the network or server load, e.g. for reducing latency due to different connection speeds between clients
• CPC Class Codes: A63F 2300/534 for network load management, e.g. bandwidth optimization, latency reduction
• CPC Class Codes: G07F 17/32 for games, toys, sports, or amusements
• CPC Class Codes: G07F 17/3269 Timing aspects of game play, e.g. blocking/halting the operation of a gaming machine
• CPC Class Codes: H04L 65/40 Support for services or applications
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/12 specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks
• CPC Class Codes: H04L 67/61 taking into account QoS or priority requirements
• CPC Class Codes: H04L 67/62 Establishing a time schedule for servicing the requests
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

Abstract

The Fair-Order Service of the present invention delivers action messages to the server as soon as it is feasible. Because action messages from different players exhibit different reaction times with respect to an update message, the Fair-Ordering Service executed at the server dynamically enforces a sufficient waiting period on each action message to guarantee the fair processing of all action messages. In reality, the waiting period at the server is bounded because of the real-time nature of interactive games. The algorithms that offer Fair Ordering Service take into consideration delayed and out-of-order action messages. When action messages corresponding to multiple update messages are interleaved, the Fair-Ordering Service matches the action message to the appropriate update message. It accomplishes this by maintaining a window of update messages and using the reaction times for an action message for each of the update messages in the window. This enables state changes at the game server to be performed with fairness to all the players. The Fair-Order Service invention is based on a framework that uses a proxy architecture making it transparent to any specific game application. The service is well suited to client-server based, online multi-player games, where a fair order of player actions is critical to the game outcome.

Claims

1. A method of providing a fair exchanging of messages to players in a distributed multi-player game, the distributed multi-player game using a game server configured for generating update messages for the players and processing action messages from the players, the method comprising:

propagating update messages toward players and receiving action messages from players; and

delivering the action messages for processing by the game server in an order of increasing reaction time without clock synchronization among the game server and the players, reaction time being indicative of a difference between reception of an update message by a player and sending of an action message by the player in response to the update message.

2. The method of claim 1, wherein delivery of each action message is delayed until a computed delivery time is reached to ensure fair processing of the action messages of the players.

3. The method of claim 1, wherein, for each of the update messages, a message number is associated with the update message for use in identifying the action message with which the update message is associated.

4. The method of claim 1, wherein each action message comprises an update message number and a reaction time.

5. The method of claim 1, wherein each of the action messages has a respective wait timeout period associated therewith, the method further comprising:

computing, for each received action message, a respective delivery time for use in delivering the action message for processing by the game server, wherein an appropriate delivery time formula for an action message is utilized depending on at least one of whether action messages arrive in order and whether action messages arrive within their wait timeout periods.

6. The method of claim 5, wherein:

a first delivery time formula is utilized when action messages arrive in order and within their wait timeout periods;

a second delivery time formula is utilized when action messages arrive out of order and within their wait timeout periods; and

a third delivery time formula is utilized when action messages arrive outside their wait timeout periods.

7. The method of claim 1, wherein each of the action messages has a respective wait timeout period associated therewith, the method further comprising:

computing, for each received action message, a respective delivery time for use in delivering the action message for processing by the game server;

wherein the delivery time of an action message is calculated before being inserted to a delivery queue, and recalculated upon new action message arrival when action messages arrive in order or out of order but within their wait timeout periods;

wherein delivery time of an action message is calculated before being inserted to a delivery queue, and recalculated upon new action message arrival and action message delivery when action messages arrive outside of the wait timeout period.

8. The method of claim 1, wherein each of the update messages has a respective update message number associated therewith, the method further comprising:

queuing the action messages for use in delivering the action messages for processing by the game server, wherein the queued action messages are arranged in an order of increasing update message number and are further arranged for each update message in an order of increasing reaction time.

9. The method of claim 1, wherein delivering the action messages for processing by the game server comprises queuing the action messages, wherein:

for at least one of the action messages, queuing the action message for processing by the game server comprises executing a message splitting process in which the action message is queued a plurality of times based on the respective plurality of reaction times included within the received action message.

10. A method of providing a fair exchanging of messages to players in a distributed multi-player game, the distributed multi-player game using a game server configured for generating update messages for the players and receiving action messages from the players, the method comprising:

propagating a plurality of update messages generated by the game server, wherein the update messages are intended for a player;

receiving an action message associated with the player, wherein the action message comprises a plurality of reaction times associated with the respective plurality of update messages intended for the player; and

queuing the action message for processing by the game server, wherein the action message is queued using the reaction times included within the action message.

11. The method of claim 10, further comprising:

propagating, toward a player proxy associated with the player, an indication of a window of update messages for which the game server is still accepting action messages from the players.

12. The method of claim 10, wherein queuing the action message for processing by the game server comprises:

executing a message splitting process in which the action message is queued a plurality of times based on the respective plurality of reaction times included within the received action message.

13. The method of claim 12, wherein executing the message splitting process comprises:

queuing the action message in each of a plurality of queues associated with the respective plurality of update messages with which the plurality of reaction times are associated, wherein the action message is queued within the plurality of queues using the respective reaction times associated with the update messages.

14. The method of claim 10, wherein the action messages are queued such that the action messages are arranged in an order of increasing update message number and are further arranged for each update message in an order of increasing reaction time.

15. The method of claim 10, further comprising:

computing, for each received action message, a respective delivery time for use in delivering the action message for processing by the game server, wherein an appropriate delivery time formula for an action message is utilized depending on at least one of whether action messages arrive in order and whether action messages arrive within their wait timeout periods;

16. A method of providing a fair exchange of messages to players of a distributed multi-player game, the distributed multi-player game using a game server configured for generating update messages for the players and processing action messages from the players, the method comprising:

receiving a plurality of update messages generated by the game server and intended for a player;

receiving an action message generated by the player and intended for the game server;

updating the action message to include a plurality of reaction times associated with the respective update messages; and

propagating, toward the game server, the updated action message including the reaction times for the respective update messages.

17. The method of claim 16, wherein the updated action message comprises a plurality of tuples associated with the respective plurality of reaction times, wherein each tuple comprises an identification of an update message and an associated reaction time calculated for the update message.

18. The method of claim 16, further comprising:

calculating the reactions times for the update messages, wherein calculating the reactions times for the update messages comprises;

determining, for each of the update messages, a reception time of the update message at the player;

determining a transmission time of the action message by the player; and

for each of the update messages, calculating the reaction time for the update message using a difference between the transmission time of the action message and the reception time of the update message.

19. The method of claim 16, wherein the plurality of received update messages comprise a subset of update messages from a set of update messages generated for the player since an action message was last received from the player.

20. The method of claim 19, wherein the update messages in the subset of update messages are identified using a window of update messages, wherein the window of update messages identifies update messages for which the game server is still accepting action messages from the players.