Method and apparatus for supporting real-time multi-user distributed applications

• US 20030204565A1
• Filed: 04/29/2002
• Published: 10/30/2003
• Est. Priority Date: 04/29/2002
• Status: Active Grant

• Current Assignee: Nokia of America Corporation (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Paul, Sanjoy, Guo, Katherine H., Lin, Yow-Jian
• Granted Patent: US 7,133,927 B2
• Time in Patent Office: Days
• US Class Current: 709/205
• CPC Class Codes: A63F 13/335 using Internet
• CPC Class Codes: A63F 13/35 Details of 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 13/71 using secure communication between game devices and game servers, e.g. by encrypting game data or authenticating players
• CPC Class Codes: A63F 2300/401 Secure communication, e.g. using encryption or authentication
• CPC Class Codes: A63F 2300/407 Data transfer via internet
• CPC Class Codes: A63F 2300/50 characterized by details of game servers
• CPC Class Codes: A63F 2300/532 using secure communication, e.g. by encryption, authentication
• CPC Class Codes: A63F 2300/534 for network load management, e.g. bandwidth optimization, latency reduction
• CPC Class Codes: H04J 3/0682 by delay compensation, e.g. by compensation of propagation delay or variations thereof, by ranging
• CPC Class Codes: H04L 12/4641 Virtual LANs, VLANs, e.g. virtual private networks [VPN] LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 47/431 using padding or de-padding
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

The present invention addresses the shortcoming of the prior art by providing a network support mechanism that is transparent to real-time multi-user distributed applications. In particular, the proposed invention is well suited for the type of online multi-player games in which a fair order of player actions is critical to the outcome. Without fairness support, remote players often receive much delayed data to act on, and their actions cannot compete in time with other players. The present invention proposes a network support mechanism, called Sync-VPN, for real time multi-user distributed applications such as multi-player online games. The approach assumes a client/server application model, where the server is responsible for coordinating state updates based on action messages sent by the clients. The approach addresses three desired features: predictable packet service, state update fairness, and player action fairness. It builds on top of bandwidth guaranteed VPN service to ensure predictable packet delay and loss characteristics. It uses a Sync-out mechanism to synchronize the delivery of state updates to all players in order for them to react to the same update fairly Its Sync-in mechanism processes action messages from all players in a fair order based on their real-time occurrence. Sync-VPN employees a round trip time estimation algorithm that is essential to both Sync-out and Sync-in mechanisms in estimating message latency. It also proposes three Sync-in algorithms that dictate a trade-off between added delay and improved fairness.

Claims

1. A method of providing synchronous delivery of data traffic to users of a network from a given location, said method comprising the steps of:

deriving a worst case delivery time for data injected into said network to be delivered to any of said users;

assigning a delivery time to said data traffic injected into said network based on said worst case delivery time;

delaying, if necessary, said data traffic reaching its destination prior to said delivery time; and

delivering said data traffic to said users of said network at said delivery time.

2. The method of claim 1, wherein said data traffic is identified by a value in at least one field of said data as belonging to a synchronous delivery service.

3. The method of claim 2, wherein said data traffic is filtered according to said value for processing in said network

4. The method of claim 2, wherein said identified value is a 6-tuple identification including Src.IP, Dst.IP, Src.Port, Dst.Port, Protocol, and TOS fields.

5. The method of claim 1, where said network is a virtual private network.

6. The method of claim 1, wherein said worst case delay is derived as half of the maximum estimated round trip time, max(eRTT_yz), ∀

zε

Z, between said given location y and any of said users z, and each eRTT_yz is derived based on a RTT estimation algorithm.

7. The method of claim 6, wherein said RTT estimation is the mean round trip time plus a round trip time variance factor.

8. The method of claim 1, further including providing substantially synchronous delivery of traffic injected from said users of said network to said given location.

9. The method of claim 5, wherein an application of said synchronous delivery of data traffic is selected from the group consisting of multi-player games, synchronized music and video conferencing

10. A method of providing fairly ordered responses of data traffic from users of a network to another location in said network, said method comprising the steps of:

deriving a waiting period for data injected into said network from a user to be delivered to said another location;

ordering said data traffic received from said users based on a send-time value associated with said data traffic injected into said network;

delaying said delivery of said data traffic for said waiting period;

delivering said data traffic to said another location in a fair order based on said step of ordering after said waiting period has expired.

11. The method of claim 10, wherein said delay period is long enough to enable receipt of a response from any user within a given response window.

12. The method of claim 10, where said delay period is based on message delay in said network of a subset of said users.

13. The method of claim 10, wherein said delay time T is represented as (r(h)−

s(h))≦

T≦

max(ps(i)), where the sending and received time of the current head message h is s(h) and r(h) respectively, and the message delay from player P_i to the another location is denoted as ps(i) and a probability function is applied to T.

14. A method of operating a server for providing synchronous delivery of data traffic to a select grouping of clients in a network, said method comprising the steps of:

deriving an estimated delivery time for data injected into said network to be delivered to any of said users;

assigning an actual delivery time to said data traffic injected into said network based on said estimated delivery time;

sending said data traffic to said users of said network, wherein said data traffic from said server is set to be synchronously delivered to said grouping of clients at said actual delivery time.

15. The method of claim 14, wherein said estimated delivery time is an estimated maximum delivery time.

16. The method of claim 14, wherein said worst case delay is derived as half of the maximum round trip time between said server and one of said clients, where the round trip time between said server and one of said clients is the mean round trip time plus a round trip time variance factor.

17. The method of claim 14, wherein said worst case delay □

□

is half of the current worst estimated round trip time max(eRTT_yz), ∀

zε

Z, and each eRTT_yz is derived based on a RTT estimation algorithm.

18. A method of operating a client device in a client server system for providing synchronous delivery of data traffic to a select grouping of clients in a network, said method comprising the steps of:

receiving data traffic from said server having a delivery time value associated therewith;

delaying, if necessary, said data traffic reaching its destination prior to said delivery time value; and

delivering said data traffic to said users of said network at said delivery time.