Apparatus and method for fair message exchanges in distributed multi-player games

• US 20050192098A1
• Filed: 02/27/2004
• Published: 09/01/2005
• Est. Priority Date: 02/27/2004
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Inventors: Paul, Sanjoy, Guo, Katherine H., Rangarajan, Sampath, Mukherjee, Sarit
• Granted Patent: US 7,584,248 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 exchange of messages to players of a distributed multi-player game taking place over a communications network, said method comprising the steps of:

utilizing a multi-player game server that generates update messages to said players and receives action messages from said players;

delivering said action messages for processing by said game server in an order of increasing reaction time, reaction time being a difference between reception of an update message by a player and a sending of an action message by said player in response to said update message.

2. The method of claim 1, wherein a game server proxy is operable in connection with said game server for receiving and ordering of said action messages and forwarding said action messages to said game server.

3. The method of claim 2, wherein each action message received at said game server proxy is delayed until a computed delivery time is reached to ensure fair processing of the action messages sent from all players.

4. The method of claim 2, wherein said server proxy associates a message number with the update messages sent to said players thereby tracking an update message to which an action message responds.

5. The method of claim 2 wherein said server proxy records a sending time for an update message and associates said update message with a sending time.

6. The method of claim 2, wherein a player proxy is operable in connection with said game server for receiving said update messages from said game server and forwarding said update messages to said game players, and for receiving said action messages from said game players and forwarding said action messages to said game server.

7. The method of claim 6, wherein a player proxy records reception time of an update message and uses said reception time to calculate said reaction time once action message is sent by a player.

8. The method of claim 6, wherein said player proxy sends an update message number, reaction time and action message number with an action message.

9. The method of claim 6, wherein a message split mechanism is employed at said player proxy when multiple update messages are outstanding, each action message associated with a window of update messages, a reaction time being calculated for each action message with respect to each said outstanding update message.

10. The method of claim 3, wherein the wait timeout period is calculated by some multiple of the expected round trip time between said server proxy and player proxy.

11. The method of claim 1, wherein an appropriate delivery time formula for an action message is utilized depending on whether action messages arrive in order and within their wait timeout periods, action messages arrive out of order but within their wait timeout periods, or action messages arrive outside their wait timeout periods

12. The method of claim 2, wherein said server proxy, when an action message is received, computes a position in a queue where said action message should be inserted and a local delivery time at which said message is to be delivered to said game server.

13. The method of claim 12, wherein said delivery queue is kept sorted based on message number and reaction time, respectively.

14. The method of claim 11, wherein the delivery time of an action message at a server proxy is calculated before being inserted to a delivery queue, and recalculated upon new action message arrival when messages arrive in order or out of order but within their wait timeout periods.

15. The method of claim 11, wherein action message numbers are used by a server proxy when messages arrive out of order to order messages from a specific player and to determine whether all earlier messages sent by said player have arrived.

16. The method of claim 11, wherein delivery time of an action message at a server proxy is calculated before being inserted to the delivery queue, and recalculated upon new action message arrival and action message delivery when messages arrive outside of the wait timeout period.

17. The method of claim, 6 wherein, when action messages are sent by players, a set of tuples are tagged onto each of the action messages by their proxies each representing the reaction time from the time a set of update messages are received, wherein a window for which this information needs to be sent is indicated by the server proxy when it sends an update message.

18. The method of claim 6, wherein a window of update messages for which reaction times are needed is indicated by the server proxy to the player proxies, the window being based on the determination by the server proxy about when to stop accepting action messages corresponding to a particular update message.

28. The method of claim 3, wherein said delivery time is based on a given wait timeout period.

29. The method of claim 12, wherein an action message being inserted into multiple queues corresponding each to a respective update message in its window.

19. A method of providing a fair exchange of messages to players of a distributed multi-player game taking place over a communications network, said multi-player game generating update messages to said players and receiving action messages from said players, said method comprising the steps of:

receiving an update message from said game server at a player proxy;

recording reception time of said update message at said player proxy; and

calculating a reaction time using said reception time, said reaction time transmitted by a player in connection with an action message.

20. The method of claim 19, wherein said player proxy sends an update message number, reaction time and action message number with an action message.

21. The method of claim 19, wherein said reaction time is used by said multi-player game to order responses by said players to thereby provide said fair exchange of messages.

22. A system including computer readable code including instructions for use by a server operating in connection with a distributed multi-player game, said instructions providing a fair exchange of messages to players of a distributed multi-player game taking place over a communications network and comprising the steps of:

generating update messages to said players and receiving action messages from said players by way of said server;

delivering said action messages for processing by said game server in an order of increasing reaction time, reaction time being a difference between reception of an update message by a player and a sending of an action message by said player in response to said update message.

23. The system of claim 22, further including code for use by player proxies of said multi-player game, said code being operable to:

receive an update message from said game server at a player proxy;

record reception time of said update message at said player proxy; and

calculate a reaction time using said reception time, said reaction time transmitted by a player in connection with an action message.

24. The method of claim 23, wherein said player proxy sends an update message number, reaction time and action message number with an action message.

25. The method of claim 23, wherein said reaction time is used by said multi-player game at said server proxy to order responses by said players to thereby provide said fair exchange of messages.

26. The method of claim 22, wherein an appropriate delivery time formula for an action message is utilized at said server proxy depending on whether action messages arrive in order and within their wait timeout periods, action messages arrive out of order but within their wait timeout periods, or action messages arrive outside their wait timeout periods

27. The method of claim 22, wherein a server proxy, when an action message is received, computes a position in a queue where said action message should be inserted and a local delivery time at which said message is to be delivered to said game server.