Communication transport optimized for data center environment

• US 9,001,663 B2
• Filed: 02/26/2010
• Issued: 04/07/2015
• Est. Priority Date: 02/26/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Attar, Mohammedreza Alizadeh, Sridharan, Murari, Patel, Parveen K., Prabhakar, Balaji, Maltz, David A., Padhye, Jitendra D., Greenberg, Albert G.
• Primary Examiner(s): Nguyen, Phuongchau Ba
• Application Number:
  US12/714,266
• Publication Number:
  US 20110211449A1
• Time in Patent Office: 1,866 Days
• Field of Search: 370/412, 370/235, 370/230, 370/234, 370/235.1, 370/249, 370/230.1, 370/253, 709/235, 379/221.03, 379/221.07
• US Class Current: 370/235.1
• 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 network congestion, comprising:

transmitting a first set of data packets from a source computing device to a destination computing device at a first transmission rate;

receiving, at the source computing device, information;

that identifies each data packet of the first set of data packets that was received at the destination computing device without a congestion marking;

that identifies each data packet of the first set of data packets that was received at the destination computing device with the congestion marking; and

that indicates, for each of the data packets of the first set of data packets, whether that specific data packet was received at the destination computing device with or without the congestion marking, wherein the information is received via indications transmitted by the destination computing device according to a state machine that transmits an indication for;

each series of M consecutive packets received by the destination computing device without the congestion marking, wherein M is greater than one;

each series of N consecutive packets received by the destination computing device with the congestion marking, wherein N is greater than one;

each particular packet received by the destination computing device without the congestion marking where a last packet received by the destination computing device relative to that particular packet was received by the destination computing device with the congestion marking; and

each given packet received by the destination computing device without the congestion marking where the last packet received by the destination computing device relative to that given packet was received by the destination computing device with the congestion marking;

determining an adjusted transmission rate, that is different from the first transmission rate, based at least in part on the received information; and

transmitting a second set of data packets from the source computing device to the destination computing device at the adjusted transmission rate.

2. The method of claim 1, wherein the received information also identifies a sequence of the data packets of the first set of data packets that were received at the destination computing device with the congestion marking and without the congestion marking.

3. The method of claim 1, wherein the congestion marking is an indication of a queue length at an intermediary computing device between the source computing device and the destination computing device.

4. The method of claim 1, wherein the congestion marking is an indication of a utilization of a link between the source computing device and the destination computing device.

5. The method of claim 1, wherein the adjusted transmission rate is based at least in part on a ratio of data packets received at the destination computing device without the congestion marking to data packets received at the destination computing device with the congestion marking.

6. The method of claim 5, wherein the adjusted transmission rate is based at least in part on a reduction of a length of a data packet transmission window by a factor of (1-α

/2), wherein a is a smoothed estimate of the ratio over multiple sets of data packets.

7. The method of claim 5, wherein the adjusted transmission rate is in accordance with:

α

_i+1=(1−

g)α

_i+gF

where α

is a smoothed estimate of the ratio over multiple sets of data packets, F is the ratio for the first set of data packets, and g is a weight given to new values of α

relative to past values of α

.

8. The method of claim 1, wherein the method further comprises:

updating the adjusted transmission rate at a frequency that is based on a round-trip-time between the source computing device and the destination computing device.

9. A computer storage memory encoded with instructions for performing operations to control network congestion, the operations comprising:

receiving a first set of data packets from a source computing device at a destination computing device; and

transmitting, from the destination computing device, indications to the source computing device according to a state machine that transmits an indication to the source computing device for;

each series of M consecutive packets received by the destination computing device without the congestion marking, wherein M is greater than one;

each series of N consecutive packets received by the destination computing device with the congestion marking, wherein N is greater than one;

each particular packet received by the destination computing device without the congestion marking where a last packet received by the destination computing device relative to that particular packet was received by the destination computing device with the congestion marking; and

each given packet received by the destination computing device without the congestion marking where the last packet received by the destination computing device relative to that given packet was received by the destination computing device with the congestion marking, wherein each of the indications

indicates, for each data packet received by the destination computing device from the source computing device since transmission of a last indication, whether that specific data packet was received at the destination computing device with or without the congestion marking.

10. The computer storage memory of claim 9, wherein the information also identifies a sequence of the data packets of the first set of data packets that were received at the destination computing device with the congestion marking and without the congestion marking.

11. The computer storage memory of claim 9, wherein the congestion marking is indicative of a queue length at an intermediary computing device between the source computing device and the destination computing device.

12. The computer storage memory of claim 9, wherein the congestion marking is indicative of a utilization of a link between the source computing device and the destination computing device.

13. The computer storage memory of claim 9, wherein the operations further comprise:

receiving a second set of data packets from the source computing device at the destination computing device, the second set of packets having been transmitted at a transmission rate based at least in part on the transmitted indications.

14. The computer storage memory of claim 9, wherein the operations further comprise:

receiving a second set of data packets from the source computing device at the destination computing device, the second set of packets having been transmitted at a transmission rate based at least in part on a ratio of data packets received at the destination computing device without the congestion marking to data packets received at the destination computing device with the congestion marking.

15. The computer storage memory of claim 9, wherein the operations further comprise:

receiving a second set of data packets from the source computing device at the destination computing device, the second set of packets having been transmitted at a transmission rate that is based at least in part on an equation;

(1-α

/2)

where α

is a smoothed estimate of a ratio over multiple sets of data packets.

16. The computer storage memory of claim 9, wherein the operations further comprise:

receiving a second set of data packets from the source computing device at the destination computing device, the second set of packets having been transmitted at a transmission rate that is based at least in part on an equation;

α

_i+1=(1-g)α

_i+gF

where α

is a smoothed estimate of a ratio over multiple sets of data packets, F is the ratio for the first set of data packets, and g is a weight given to new values of α

relative to past values of α

.

17. An apparatus for controlling network congestion, comprising a memory and a processor that are respectively configured to store and execute instructions that:

transmit a first set of data packets from a source computing device to a destination computing device at a first transmission rate;

receive, at the source computing device, information;

that identifies each data packet of the first set of data packets that was received at the destination computing device without a congestion marking;

that identifies each data packet of the first set of data packets that was received at the destination computing device with the congestion marking; and

that indicates, for each of the data packets of the first set of data packets, whether that specific data packet was received at the destination computing device with or without the congestion marking;

determine an adjusted transmission rate, different from the first transmission rate, based at least in part on the received information; and

transmit a second set of data packets from the source computing device to the destination computing device at the adjusted transmission rate, wherein;

the adjusted transmission rate is determined as a function of at least;

a ratio of data packets received at the destination computing device without the congestion marking to data packets received at the destination computing device with the congestion marking; and

a reduction of a length of a data packet transmission window by a factor of a smoothed estimate of the ratio over multiple sets of data packets; and

receiving the information includes;

receiving indications transmitted by the destination computing device according to a state machine that transmits an indication for;

each series of M consecutive packets received by the destination computing device without the congestion marking, wherein M is greater than one;

each series of N consecutive packets received by the destination computing device with the congestion marking, wherein N is greater than one;

each particular packet received by the destination computing device without the congestion marking where a last packet received by the destination computing device relative to that particular packet was received by the destination computing device with the congestion marking; and

each given packet received by the destination computing device without the congestion marking where the last packet received by the destination computing device relative to that given packet was received by the destination computing device with the congestion marking.

18. The apparatus of claim 17, wherein:

the adjusted transmission rate is determined as a function of at least;

a smoothed estimate, over multiple sets of data packets, of a ratio of data packets received at the destination computing device without the congestion marking to data packets received at the destination computing device with the congestion marking; and

a weight of new values of the smoothed estimate relative to past values of the smoothed estimate.

19. The apparatus of claim 17, wherein the congestion marking is an indication of a queue length at an intermediary computing device between the source computing device and the destination computing device and/or an indication of a utilization of a link between the source computing device and the destination computing device.

20. The method of claim 17, wherein the adjusted transmission rate is based at least in part on a smoothed estimate of the ratio over multiple sets of data packets and a relative importance of a current value of the smoothed estimate to past values of the smoothed estimate.