Congestion window control based on queuing delay and packet loss

• US 8,514,715 B2
• Filed: 04/11/2011
• Issued: 08/20/2013
• Est. Priority Date: 04/22/2010
• Status: Active Grant

• Current Assignee: Akamai Technologies, Inc.
• Original Assignee: Akamai Technologies, Inc.
• Inventors: Jin, Cheng, Liu, Victor, Low, Steven, Rao Gururajan, Santosh, Yang, Lingfeng
• Primary Examiner(s): Shah, Chirag
• Assistant Examiner(s): PERSAUD, AMARNAUTH G
• Application Number:
  US13/084,456
• Publication Number:
  US 20110261691A1
• Time in Patent Office: 862 Days
• Field of Search: None
• US Class Current: 370/235
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/193 at the transport layer, e.g. TCP related
• CPC Class Codes: H04L 47/27 Evaluation or update of window size, e.g. using information derived from acknowledged [ACK] packets
• CPC Class Codes: H04L 47/28 in relation to timing considerations
• CPC Class Codes: H04L 47/29 using a combination of thresholds

Abstract

A method of controlling size of a congestion window, includes, at a transmitting device, transmitting a plurality of data packets over a communication channel from the transmitting device to a receiver, determining a queuing delay and a loss rate of the transmission, comparing the queuing delay to a threshold queuing delay, comparing the loss rate to a threshold loss rate, and in response to a determination that the queuing delay is greater than the threshold queuing delay and the loss rate is greater than the threshold loss rate, resetting the size of the congestion window in accordance with a function of the current size of the congestion window, the queuing delay, and the loss rate, wherein at equilibrium the function generates a value inversely proportional to a weighted sum of an excess queuing delay and an excess loss rate.

Claims

1. A method of controlling size of a congestion window, comprising:

at a transmitting device;

transmitting a number of data packets over a communication channel from the transmitting device to a receiver;

determining a queuing delay of the transmission, wherein the queuing delay corresponds to the difference of an average round trip time of the data packets and a base round trip time of the data packets;

determining a loss rate of the transmission, wherein the loss rate corresponds to the ratio of a number of data packets lost in the transmission to the number of data packets transmitted;

comparing the queuing delay to a threshold queuing delay;

comparing the loss rate to a threshold loss rate;

in response to a determination that the queuing delay is greater than the threshold queuing delay and the loss rate is less than the threshold loss rate, resetting the size of the congestion window in accordance with a first function of a current size of the congestion window and the queuing delay, wherein at equilibrium the first function generates a value inversely related to an excess queuing delay, which corresponds to the difference between the queuing delay and the threshold queuing delay;

in response to a determination that the queuing delay is less than the threshold queuing delay and the loss rate is greater than the threshold loss rate, resetting the size of the congestion window in accordance with a second function of the current size of the congestion window and the loss rate, wherein at equilibrium the second function generates a value inversely related to an excess loss rate, which corresponds to the difference between the loss rate and the threshold loss rate;

in response to a determination that the queuing delay is greater than the threshold queuing delay and the loss rate is greater than the threshold loss rate, resetting the size of the congestion window in accordance with a third function of the current size of the congestion window, the queuing delay, and the loss rate, wherein at equilibrium the third function generates a value inversely proportional to a weighted sum of the excess queuing delay and excess loss rate.

2. The method of claim 1, wherein the weighted sum is a convex sum.

6. The non-transitory computer readable storage medium of claim 2, wherein the weighted sum is a convex sum.

3. An apparatus for controlling size of a congestion window, the apparatus comprising:

a transceiver to transmit a plurality of packets over a communication channel to a receiver;

one or more processors; and

memory for storing instructions to be executed by the one or more processors, the stored instructions to;

determine a queuing delay of the transmission, wherein the queuing delay corresponds to the difference of an average round trip time of the data packets and a base round trip time of the data packets;

determine a loss rate of the transmission, wherein the loss rate corresponds to the ratio of a number of data packets lost in the transmission to the number of data packets transmitted;

compare the queuing delay to a threshold queuing delay;

compare the loss rate to a threshold loss rate;

in response to a determination that the queuing delay is greater than the threshold queuing delay and the loss rate is less than the threshold loss rate, reset the size of the congestion window in accordance with a first function of a current size of the congestion window and the queuing delay, wherein at equilibrium the first function generates a value inversely related to an excess queuing delay, which corresponds to the difference between the queuing delay and the threshold queuing delay;

in response to a determination that the queuing delay is less than the threshold queuing delay and the loss rate is greater than the threshold loss rate, reset the size of the congestion window in accordance with a second function of the current size of the congestion window and the loss rate, wherein at equilibrium the second function generates a value inversely related to an excess loss rate, which corresponds to the difference between the loss rate and the threshold loss rate;

in response to a determination that the queuing delay is greater than the threshold queuing delay and the loss rate is greater than the threshold loss rate, reset the size of the congestion window in accordance with a third function of the current size of the congestion window, the queuing delay, and the loss rate, wherein at equilibrium the third function generates a value inversely proportional to a weighted sum of the excess queuing delay and excess loss rate.

4. The apparatus of claim 3, wherein the weighted sum is a convex sum.

5. A non-transitory computer readable storage medium, storing one or more programs for execution by one or more processor of an apparatus that includes a transceiver to transmit packets over a communication channel to a receiver;

wherein the one or more programs are for execution by the one or more processors of the apparatus so as to perform a method comprising;

transmitting a number of data packets over a communication channel from the transmitting device to a receiver;

determining a queuing delay of the transmission, wherein the queuing delay corresponds to the difference of an average round trip time of the data packets and a base round trip time of the data packets;

determining a loss rate of the transmission, wherein the loss rate corresponds to the ratio of a number of data packets lost in the transmission to the number of data packets transmitted;

comparing the queuing delay to a threshold queuing delay;

comparing the loss rate to a threshold loss rate;

in response to a determination that the queuing delay is greater than the threshold queuing delay and the loss rate is less than the threshold loss rate, resetting the size of the congestion window in accordance with a first function of a current size of the congestion window and the queuing delay, wherein at equilibrium the first function generates a value inversely related to an excess queuing delay, which corresponds to the difference between the queuing delay and the threshold queuing delay;

in response to a determination that the queuing delay is less than the threshold queuing delay and the loss rate is greater than the threshold loss rate, resetting the size of the congestion window in accordance with a second function of the current size of the congestion window and the loss rate, wherein at equilibrium the second function generates a value inversely related to an excess loss rate, which corresponds to the difference between the loss rate and the threshold loss rate;

in response to a determination that the queuing delay is greater than the threshold queuing delay and the loss rate is greater than the threshold loss rate, resetting the size of the congestion window in accordance with a third function of the current size of the congestion window, the queuing delay, and the loss rate, wherein at equilibrium the third function generates a value inversely proportional to a weighted sum of the excess queuing delay and excess loss rate.

7. A method of controlling size of a congestion window, comprising:

at a transmitting device;

transmitting a plurality of data packets over a communication channel from the transmitting device to a receiver;

determining a queuing delay of the transmission, wherein the queuing delay corresponds to the difference of an average round trip time of the data packets and a base round trip time of the data packets;

determining a loss rate of the transmission, wherein the loss rate corresponds to the ratio of a number of data packets lost in the transmission to the number of data packets transmitted;

comparing the queuing delay to a threshold queuing delay;

comparing the loss rate to a threshold loss rate;

determining an excess queuing delay, wherein excess queuing delay corresponds to the difference between the queuing delay and the threshold queuing delay;

determining an excess loss rate, wherein excess loss rate corresponds to the difference between the loss rate and the threshold loss rate;

in response to a determination that the queuing delay is greater than the threshold queuing delay and the loss rate is greater than the threshold loss rate, resetting the size of the congestion window in accordance with a function of the current size of the congestion window, the queuing delay, and the loss rate, wherein at equilibrium the function generates a value inversely proportional to a weighted sum of the excess queuing delay and excess loss rate.

8. The method of claim 7, wherein the weighted sum is a convex sum.

9. An apparatus for controlling size of a congestion window, the apparatus comprising:

a transceiver to transmit a plurality of packets over a communication channel to a receiver;

one or more processors; and

memory for storing instructions to be executed by the one or more processors, the stored instructions to;

transmit a plurality of data packets over a communication channel from the transmitting device to a receiver;

determine a queuing delay of the transmission, wherein the queuing delay corresponds to the difference of an average round trip time of the data packets and a base round trip time of the data packets;

determine a loss rate of the transmission, wherein the loss rate corresponds to the ratio of a number of data packets lost in the transmission to the number of data packets transmitted;

compare the queuing delay to a threshold queuing delay;

compare the loss rate to a threshold loss rate;

determine an excess queuing delay, wherein excess queuing delay corresponds to the difference between the queuing delay and the threshold queuing delay;

determine an excess loss rate, wherein excess loss rate corresponds to the difference between the loss rate and the threshold loss rate;

in response to a determination that the queuing delay is greater than the threshold queuing delay and the loss rate is greater than the threshold loss rate, reset the size of the congestion window in accordance with a function of the current size of the congestion window, the queuing delay, and the loss rate, wherein at equilibrium the function generates a value inversely proportional to a weighted sum of the excess queuing delay and excess loss rate.

10. The apparatus of claim 9, wherein the weighted sum is a convex sum.

11. A non-transitory computer readable storage medium, storing one or more programs for execution by one or more processor of an apparatus that includes a transceiver to transmit packets over a communication channel to a receiver;

wherein the one or more programs are for execution by the one or more processors of the apparatus so as to perform a method comprising;

transmitting a plurality of data packets over a communication channel from the transmitting device to a receiver;

determining a queuing delay of the transmission, wherein the queuing delay corresponds to the difference of an average round trip time of the data packets and a base round trip time of the data packets;

determining a loss rate of the transmission, wherein the loss rate corresponds to the ratio of a number of data packets lost in the transmission to the number of data packets transmitted;

comparing the queuing delay to a threshold queuing delay;

comparing the loss rate to a threshold loss rate;

determining an excess queuing delay, wherein excess queuing delay corresponds to the difference between the queuing delay and the threshold queuing delay;

determining an excess loss rate, wherein excess loss rate corresponds to the difference between the loss rate and the threshold loss rate;

in response to a determination that the queuing delay is greater than the threshold queuing delay and the loss rate is greater than the threshold loss rate, resetting the size of the congestion window in accordance with a function of the current size of the congestion window, the queuing delay, and the loss rate, wherein at equilibrium the function generates a value inversely proportional to a weighted sum of the excess queuing delay and excess loss rate.

12. The non-transitory computer readable storage medium of claim 11, wherein the weighted sum is a convex sum.