COMMUNICATION TRANSPORT OPTIMIZED FOR DATA CENTER ENVIRONMENT

• US 20110211449A1
• Filed: 02/26/2010
• Published: 09/01/2011
• Est. Priority Date: 02/26/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Prabhakar, Balaji, Attar, Mohammedreza Alizadeh, Greenberg, Albert G., Padhye, Jitendra D., Sridharan, Murari, Patel, Parveen K., Maltz, David A.
• Granted Patent: US 9,001,663 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/115 using a dedicated packet
• CPC Class Codes: H04L 47/19 at layers above the network layer network arrangements for networked applications for scheduling or organising the servicing of application requests H04L67/60
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/34 ensuring sequence integrity, e.g. using sequence numbers

Abstract

Methods and apparatus for congestion control in computer networks achieve high burst tolerance, low latency and high throughput with shallow-buffered switches. A method for controlling congestion includes transmitting a set of data packets on a network connection from a first computing device to a second computing device, identifying each data packet in the set of data packets that experienced congestion on the network connection, sending, by the second computing device to the first computing device, a sequence of bits that represents the number of data packets in the set of data packets that were identified as having experienced congestion, and adjusting a rate of transmitting data packets on the network connection based on the sequence of bits sent to the first computing device.

Claims

1. A method for controlling congestion on a network connection between a first computing device and a second computing device, comprising:

transmitting a set of data packets on the network connection from the first computing device to the second computing device;

identifying each data packet in the set of data packets that experienced congestion on the network connection;

sending, by the second computing device to the first computing device, a sequence of bits that represents the number of data packets in the set of data packets that were identified as having experienced congestion; and

adjusting a rate of transmitting data packets on the network connection based on the sequence of bits sent to the first computing device.

2. A method as defined in claim 1, wherein sending includes sending a packet whenever the second computing receives a packet identified as having experienced congestion after receiving a packet identified as not having experienced congestion.

3. A method as defined in claim 1, wherein identifying each data packet in the set of data packets that experienced congestion comprises the second computing device estimating a queue length at a last hop network device before the second computing device and identifying data packets as having experienced congestion when the queue length is greater than a threshold value over a period of time.

4. A method as defined in claim 3, wherein estimating the queue length comprises determining utilization of the link to the second computing device over a period of time and identifying data packets as having experienced congestion when the determined utilization is above a threshold for a period of time.

5. A method as defined in claim 1, wherein identifying includes marking the transmitted data packets if a queue size in a device on the network connection exceeds a predetermined, single value threshold K and notifying the first computing device of each marked data packet.

6. A method as defined in claim 5, further comprising estimating a measure of congestion on the network connection by determining, based on the sequence of bits, a fraction of data packets in the set of transmitted data packets that were identified as having experienced congestion and wherein adjusting includes adjusting the rate at which packets are transmitted based on the fraction of marked data packets in the set of transmitted data packets.

7. A method as defined in claim 6, wherein adjusting includes adjusting the rate at which packets are transmitted proportional to the fraction of marked data packets in the set of transmitted data packets.

8. A method as defined in claim 6, wherein estimating includes updating the measure of congestion once per round-trip-time.

9. A method as defined in claim 6, wherein adjusting includes reducing a length of a data packet transmission window by a factor of (1−

α

/2), wherein α

is a smoothed estimate of the fraction of marked data packets.

10. A method as defined in claim 6, wherein adjusting comprises the second computing device controlling the amount of data it receives by adjusting the size of a receiver advertised window.

11. A method as defined in claim 6, wherein estimating includes updating an estimated fraction of marked packets in a data packet transmission window for each data packet transmission window.

12. A method as defined in claim 6, wherein estimating includes updating an estimated measure of congestion in accordance with:

α

_i+1=(1−

g)α

_i+gF

where α

is a smoothed estimate of the fraction of marked data packets, F is the fraction of marked data packets in the last set of data packets, and g is the weight given to new samples with respect to past samples in estimating α

.

13. A non-transitory computer-readable storage medium encoded with computer-readable instructions that, when executed by a computing device, perform a method as defined in claim 1.

14. A method for controlling congestion on a network connection between a first computing device and a second computing device, comprising:

transmitting, by the first computing device, a set of data packets on the network connection to the second computing device;

marking data packets in the set of transmitted data packets if a queue size in a device on the network connection exceeds a predetermined, single value threshold K;

receiving, at the first computing device, information identifying data packets in the set of transmitted data packets that were marked;

estimating, at the first computing device, a measure of congestion on the network connection based on the data packets in the set of data packets that were identified as marked; and

adjusting, by the first computing device, a rate of transmitting data packets on the network connection based on the estimated measure of congestion.

15. A method as defined in claim 14, wherein adjusting includes decreasing the rate of transmitting data packets as the estimated measure of congestion increases.

16. A method as defined in claim 14, further comprising determining threshold K to be a value that allows full utilization of the network connection for large data flows.

17. A method as defined in claim 16, wherein determining threshold K includes choosing threshold K to be an amount of buffer space required to support full utilization of the network connection plus an amount of buffer space required to hold the largest burst size sent by the first computing device.

18. A method as defined in claim 17, wherein the amount of buffer space required to support full utilization of the network connection is determined as C·

RTT/7, where C is the capacity of the network connection in packets per second, RTT is round trip time in seconds and threshold K is in packets.

19. A non-transitory computer-readable storage medium coded with computer-readable instructions that, when executed by a computing device, perform a method as defined in claim 14.

20. A method for controlling congestion on a network connection between a first computing device and a second computing device, comprising:

transmitting a set of data packets on the network connection from the first computing device to the second computing device;

marking data packets in the set of transmitted data packets if a queue size in a device on the network connection exceeds a predetermined, single value threshold K;

sending, by the second computing device to the first computing device, a sequence of bits that represents the number of data packets in the set of data packets that were marked;

estimating a measure of congestion on the network connection by determining, based on the sequence of bits, a fraction of data packets in the set of transmitted data packets that were marked;

adjusting a rate of transmitting data packets on the network connection based on the fraction of marked data packets in the set of transmitted data packets; and

updating the estimated measure of congestion on the network connection for each set of transmitted data packets.