Dynamic bandwidth detection and response for online games

• US 7,680,038 B1
• Filed: 04/25/2005
• Issued: 03/16/2010
• Est. Priority Date: 04/25/2005
• Status: Active Grant

• Current Assignee: Electronic Arts Incorporated
• Original Assignee: Electronic Arts Incorporated
• Inventors: Gourlay, Michael J.
• Primary Examiner(s): Vu; Huy D
• Assistant Examiner(s): RENNER, BRANDON M
• Application Number:
  US11/115,061
• Time in Patent Office: 1,786 Days
• Field of Search: 370/238, 370/395.21, 370/395.41, 370/508, 370/519, 709223-226
• US Class Current: 370/230
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/25 with rate being modified by the source upon detecting a change of network conditions
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]

Abstract

Techniques for optimizing bandwidth usage while controlling latency. A latency mitigating congestion avoidance and control technique is described that is suitable for use with unreliable transport protocols. Embodiments of the present invention facilitate communication of data for applications that communicate using unreliable communication protocols and that would like to maximize use of available bandwidth but cannot tolerate high latencies. Techniques are described for preventing latency from exceeding a certain level, without destroying the ability of an application or system to probe for additional available bandwidth and maximize bandwidth usage.

Claims

1. A method of communicating data from a sender system to a receiver system via a network connection, the method comprising:

communicating data from the sender system to the receiver system in a first mode over the network connection, wherein communicating the data in the first mode comprises;

(a) determining an available bandwidth estimate for the network connection;

(b) determining a bandwidth target that is a fraction of the available bandwidth estimate, such that the bandwidth target is less than the available bandwidth estimate;

(c) communicating data from the sender system via the network connection using an unreliable protocol at a data rate that is substantially equal to the bandwidth target;

(d) monitoring latency associated with the network connection;

repeating (a), (b), (c), and (d) until a condition for exiting the first mode is satisfied; and

exiting the first mode upon determining that the condition for exiting the first mode is satisfied;

computing a latency threshold (latency_threshold) for the network connection, wherein the latency threshold computed for the network is computed as is set to a greater of (a) a minimum latency threshold value; and

(b) the smaller of the latency associated with the network connection plus a constant times a latency deviation value and a first latency value;

communicating data from the sender system to the receiver system in a second mode over the network connection, wherein communicating the data in the second mode comprises;

(e) determining an available bandwidth estimate for the network connection;

(f) determining a bandwidth target that is substantially equal to the available bandwidth estimate;

(g) communicating data from the sender system via the network connection using an unreliable protocol at a data rate that is substantially equal to or greater than the bandwidth target;

(h) monitoring latency associated with the network connection;

repeating (e), (f), (g), and (h) until a condition for exiting the second mode is satisfied; and

exiting the second mode upon determining that the condition for exiting the second mode is satisfied; and

alternating between the first mode and the second mode over the network connection.

2. The method of claim 1 wherein:

the data that is communicated is generated by an online game application hosted by the sender system; and

the receiver system is a data processing system receiving data from the online game application.

3. The method of claim 1 wherein the unreliable protocol used for communicating data in the first mode and in the second mode is User Datagram Protocol (UDP).

4. The method of claim 1 wherein the condition for exiting the first mode is satisfied when the latency associated with the network connection is less than a first latency value, wherein the first latency value is based upon a latency tolerance of an application generating the data being communicated.

5. The method of claim 1 wherein the condition for exiting the first mode is satisfied when the latency associated with the network connection is less than a first latency value and a time duration for the first mode has expired, wherein the first latency value is based upon a latency tolerance of an application generating the data being communicated.

6. The method of claim 1 wherein the condition for exiting the second mode is satisfied when the latency associated with the network connection is greater than the latency threshold (latency_threshold) computed for the network connection during the first mode or a time duration for the second mode has expired.

7. The method of claim 1 wherein the available bandwidth estimate for the network connection is increased during the second mode upon determining that data packet loss has not occurred.

8. A method of communicating data from a sender system via a plurality of network connections using an unreliable protocol, the method comprising:

communicating data from the sender system over the plurality of connections in a first mode, wherein communicating the data in the first mode comprises;

(a) determining an available bandwidth estimate for each network connection in the plurality of network connections;

(b) determining, for each network connection in the plurality of network connections, a bandwidth target that is a fraction of the available bandwidth estimate for the network connection, such that the bandwidth target is less than the available bandwidth estimate;

(c) communicating, for each network connection in the plurality of network connections, data via the network connection using an unreliable protocol at a data rate that is substantially equal to the bandwidth target determined for the network connection;

(d) monitoring latency associated with the plurality of network connections;

repeating (a), (b), (c), and (d) until a condition for exiting the first mode is satisfied; and

exiting the first mode upon determining that the condition for exiting the first mode is satisfied;

computing a latency threshold (latency_threshold) for each network connection in the plurality of network connections, wherein the latency threshold is computed as is set to a greater of (a) a minimum latency threshold value; and

(b) the smaller of the latency associated with the network connection plus a constant times a latency deviation value and a first latency value;

communicating data from the sender system over a first network connection of the plurality of network connections in a second mode, wherein communicating the data in the second mode comprises;

(e) determining an available bandwidth estimate for each network connection in the plurality of network connections;

(f) determining a penalty for the first network connection;

(g) determining a bandwidth target for the first network connection based upon the available bandwidth estimate and the penalty determined for the first network connection;

(h) communicating data via the first network connection using an unreliable protocol at a data rate that is substantially equal to or greater than the bandwidth target determined for the first network connection;

(i) monitoring latency associated with the first network connection;

repeating (e), (f), (g), (h), and (i) until a condition for exiting the second mode is satisfied; and

exiting the second mode upon determining that a condition for exiting the second mode is satisfied; and

alternating between the first mode and the second mode over the first network connection.

9. The method of claim 8 wherein the penalty is determined based upon a latency tolerance of an application generating the data being communicated, and the latency associated with the first network connection.

10. The method of claim 8 wherein determining a bandwidth target for the first network connection in the second mode comprises:

if the latency associated with the network connection is greater than a first latency, then setting the bandwidth target based upon the available bandwidth estimate determined for the network connection in the second mode, a first constant, and the penalty determined for the network connection, wherein the first latency value is based upon a latency tolerance of an application generating the data being communicated.

11. The method of claim 10 wherein determining a bandwidth target for the first network connection in the second mode further comprises:

if the latency associated with the first network connection is greater than the latency threshold computed for the first network connection during the first mode, then setting the bandwidth target for the first network connection based upon the available bandwidth estimate determined for the first network connection in the second mode, a second constant, and the penalty determined for the first network connection, where the second constant is calculated based upon the first constant.

12. The method of claim 11 wherein determining a bandwidth target for the first network connection in the second mode further comprises:

if the latency associated with the first network connection is less than or equal to the latency threshold computed for the first network connection during the first mode, then setting the bandwidth target for the first network connection to the available bandwidth estimate determined for the first network connection in the second mode.

13. The method of claim 8 wherein the condition for exiting the first mode is satisfied when, in the first mode, the latency associated with a network connection from the plurality of network connections having the lowest associated latency is less than a first threshold latency value, the first threshold latency value determined based upon a latency tolerance of an application generating the data being communicated.

14. The method of claim 8 wherein the condition for exiting the first mode is satisfied when, in the first mode, the latency associated with a network connection from the plurality of network connections having the lowest associated latency is less than a first threshold latency value and a time duration for the first mode has expired, the first threshold latency value determined based upon a latency tolerance of an application generating the data being communicated.

15. The method of claim 8 further comprising:

wherein the condition for exiting the second mode is satisfied when, in the second mode,

the latency associated with the network connection in the second mode is greater than a first threshold latency value, or

a time duration for the first mode has expired, or

the latency associated with each network connection in the plurality of network connections is greater than the latency threshold (latency_threshold) computed for the network connection during the first mode.

16. The method of claim 8 wherein the unreliable protocol used for communicating data in the first mode and in the second mode is User Datagram Protocol (UDP).

17. The method of claim 8 wherein:

the data that is communicated is generated by an online game application hosted by the sender system; and

the receiver system is a data processing system receiving data from the online game application.

18. A system for communicating data to a receiver system using a network connection, the system comprising:

a processor;

a memory coupled to the processor, the memory configured to store a set of instructions which when executed by the processor cause the processor to;

communicate data to the receiver system in a first mode over the network connection, wherein communicating the data in the first mode comprises;

(a) determining an available bandwidth estimate for the network connection;

(b) determining a bandwidth target that is a fraction of the available bandwidth estimate, such that the bandwidth target is less than the available bandwidth estimate;

(c) communicating data to the receiver system via the network connection using an unreliable protocol at a data rate that is substantially equal to the bandwidth target;

(d) monitoring latency associated with the network connection;

repeating (a), (b), (c), and (d) until a condition for exiting the first mode is satisfied; and

exiting the first mode upon determining that the condition for exiting the first mode is satisfied;

computing a latency threshold (latency_threshold) for the network connection, wherein the latency threshold computed for the network is set to a greater of value of (a) a minimum latency threshold value; and

(b) the smaller of the latency associated with the network connection plus a constant times a latency deviation value and a first latency value;

communicate data to the receiver system in a second mode over the network connection, wherein communicating the data in the second mode comprises;

(e) determining an available bandwidth estimate for the network connection;

(f) determining a bandwidth target that is substantially equal to the available bandwidth estimate;

(g) communicating data to the receiver system via the network connection using an unreliable protocol at a data rate that is substantially equal to or greater than the bandwidth target;

(h) monitoring latency associated with the network connection;

repeating (e), (f), (g), and (h) until a condition for exiting the second mode is satisfied; and

exiting the second mode upon determining that the condition for exiting the second mode is satisfied; and

alternate between the first mode and the second mode over the network connection.

19. The system of claim 18 wherein:

the data that is communicates is generated by an online gaming application hosted by the system; and

the receiver system is a data processing system receiving data from the online gaming application.

20. The system of claim 18 wherein the unreliable protocol used for communicating data in the first mode and in the second mode is User Datagram Protocol (UDP).

21. The system of claim 18 wherein the condition for exiting the first mode is satisfied when the latency associated with the network connection is less than a first latency value, wherein the first latency value is set based upon a latency tolerance of an application generating the data being communicated.

22. The system of claim 18 wherein the condition for exiting the first mode is satisfied when the latency associated with the network connection is less than a first latency value and a time duration for the first mode has expired, wherein the first latency value is set based upon a latency tolerance of an application generating the data being communicated.

23. The system of claim 18 wherein the condition for exiting the second mode is satisfied when the latency associated with the network connection is greater than the latency threshold (latency_threshold) computed for the network connection during the first mode or a time duration for the second mode has expired.

24. The system of claim 18 wherein the available bandwidth estimate for the network connection is increased during the second mode.

25. A system for communicating data using a plurality of network connections, the system comprising:

a processor; and

a memory coupled to the processor, the memory configured to store a set of instructions which when executed by the processor cause the processor to;

communicate data over the plurality of connections in a first mode, wherein communicating the data in the first mode comprises;

(a) determining an available bandwidth estimate for each network connection in the plurality of network connections;

(b) determining, for each network connection in the plurality of network connections, a bandwidth target that is a fraction of the available bandwidth estimate for the network connection, such that the bandwidth target is less than the available bandwidth estimate;

(c) communicating, for each network connection in the plurality of network connections, data via the network connection using an unreliable protocol at a data rate that is substantially equal to the bandwidth target determined for the network connection;

(d) monitoring latency associated with the plurality of network connections;

repeating (a), (b), (c), and (d) until a condition for exiting the first mode is satisfied; and

exiting the first mode upon determining that the condition for exiting the first mode is satisfied;

computing a latency threshold (latency_threshold) for each network connection in the plurality of network connections, wherein the latency threshold computed for the network connection is set to a greater of value of (a) a minimum latency threshold value; and

(b) the smaller of the latency associated with the network connection plus a constant times a latency deviation value and a first latency value;

communicating data over a first network connection of the plurality of network connections in a second mode, wherein communicating the data in the second mode comprises;

(e) determining an available bandwidth estimate for each network connection in the plurality of network connections;

(f) determining a penalty for the first network connection;

(g) determining a bandwidth target for the first network connection based upon the available bandwidth estimate and the penalty determined for the first network connection;

(h) communicating data via the first network connection using an unreliable protocol at a data rate that is substantially equal to or greater than the bandwidth target determined for the first network connection;

(i) monitoring latency associated with the first network connection;

repeating (e), (f), (g), (h), and (i) until a condition for exiting the second mode is satisfied; and

exiting the second mode upon determining that a condition for exiting the second mode is satisfied; and

alternating between the first mode and the second mode over the first network connection.

26. The system of claim 25 wherein the penalty is determined based upon a latency tolerance of an application generating the data that is communicated and the latency associated with the first network connection.

27. The system of claim 25 wherein determining a bandwidth target for the first network connection in the second mode comprises:

if the latency associated with the network connection is greater than a first latency, then setting the bandwidth target based upon the available bandwidth estimate determined for the first network connection in the second mode, a first constant, and the penalty determined for the first connection, wherein the first latency value is based upon a latency tolerance of an application generating the data that is communicated;

if the latency associated with the first network connection is greater than the latency threshold computed for the first network connection during the first mode, then setting the bandwidth target for the first network connection based upon the available bandwidth estimate determined for the first network connection in the second mode, a second constant, and the penalty determined for the first network connection, where the second constant is calculated based upon the first constant; and

if the latency associated with the first network connection is less than or equal to the latency threshold computed for the first network connection during the first mode, then setting the bandwidth target for the first network connection to the available bandwidth estimate determined for the first network connection in the second mode.

28. The system of claim 25 wherein the condition for exiting the first mode is satisfied when, in the first mode, the latency associated with a network connection from the plurality of network connections having the lowest associated latency is less than a first threshold latency value, the first threshold latency value determined based upon a latency tolerance of an application generating the data that is communicated.

29. The system of claim 25 wherein the condition for exiting the first mode is satisfied when, in the first mode, the latency associated with a network connection from the plurality of network connections having the lowest associated latency is less than a first threshold latency value and a time duration for the first mode has expired, the first threshold latency value determined based upon a latency tolerance of the application generating the data that is communicated.

30. The system of claim 25:

wherein the condition for exiting the second mode is satisfied when, in the second mode,

the latency associated with the network connection in the second mode is greater than a first threshold latency value, or

a time duration for the first mode has expired, or

the latency associated with each network connection in the plurality of network connections is greater than the latency threshold (latency_threshold) computed for the network connection during the first mode.

31. The system of claim 25 wherein the unreliable protocol used for communicating data in the first mode and in the second mode is User Datagram Protocol (UDP).