Methods for congestion mitigation in infiniband

• US 7,000,025 B1
• Filed: 05/07/2002
• Issued: 02/14/2006
• Est. Priority Date: 05/07/2001
• Status: Active Grant

• Current Assignee: Kenexa Technology Incorporated (International Business Machines Corporation)
• Original Assignee: Adaptec Incorporated (Steel Partners Holdings LP)
• Inventors: Wilson, Andrew W.
• Primary Examiner(s): Vu, Thong
• Application Number:
  US10/141,147
• Time in Patent Office: 1,379 Days
• Field of Search: 709224-226, 709240-235, 370/230, 370/231, 370/235, 370/402, 370/229, 710/317, 702/186
• US Class Current: 709/235
• 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/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/31 by tagging of packets, e.g. using discard eligibility [DE] bits
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

A method for optimizing data transmission in a data transfer system is provided where the data transfer system includes a transmitting device that transmits data to a receiving device through a switch. The method includes monitoring data transfer congestion in a buffer of the switch. The monitoring includes marking the data when data transfer congestion is detected. If data transfer congestion is detected, the method includes marking an acknowledgement (ACK) data after the marked data is received by the receiving device. The method further includes transmitting the ACK data from the receiving device to the transmitting device. The method also includes adjusting a data transfer rate between the transmitting device and the receiving device based on data transfer congestion. Monitoring data transfer congestion includes marking the data according to a probability corresponding to a percentage of time that the buffer is full.

Claims

1. A method for optimizing data transmission in a data transfer system, the data transfer system including a transmitting device that transmits data to a receiving device through a switch, comprising:

monitoring data transfer congestion in a buffer of the switch, the monitoring including marking the data when data transfer congestion is detected;

if data transfer congestion is detected,

marking an acknowledgement (ACK) data after the marked data is received by the receiving device;

transmitting the ACK data from the receiving device to the transmitting device; and

adjusting a data transfer rate between the transmitting device and the receiving device based on data transfer congestion, the adjusting a data transfer rate including increasing the data transfer rate when the ACK data is not marked and decreasing the data transfer rate when the ACK data is marked;

wherein decreasing the data transfer rate is defined by using the following equation;

CRL′

=actual rate−

K*(rate of packets covered by ACK),

where CRL′

is a new congestion rate limit;

where actual rate is an actual rate of issue of data.

2. A method for optimizing data transmission in a data transfer system as recited in claim 1, wherein increasing the data transfer rate which occurs when a congestion rate limit (CRL) is greater than a slow start rate threshold (SSRT) value is defined by using the following equation:

CRL′

=CRL+(BR/CRL)*Br,

where CRL′

is a congestion rate limit after a data transfer increase;

where BR is a base rate.

3. A method for optimizing data transmission in a data transfer system, the data transfer system including a transmitting device that transmits data to a receiving device through a switch, comprising:

monitoring data transfer congestion in a buffer of the switch, the monitoring including marking the data when data transfer congestion is detected, the monitoring data transfer congestion including marking the data according to a probability corresponding to a percentage of time that the buffer is full;

if data transfer congestion is detected,

marking an acknowledgement (ACK) data after the marked data is received by the receiving device;

transmitting the ACK data from the receiving device to the transmitting device;

if the ACK data is marked,

decreasing a data transfer rate multiplicatively between the transmitting device and the receiving device; and

if the ACK data is unmarked,

increasing the data transfer rate additively between the transmitting device and the receiving device;

wherein decreasing the data transfer rate is defined by using the following equation;

CRL′

=actual rate−

K*(rate of packets covered by ACK).

4. A method for optimizing data transmission in a data transfer system as recited in claim 3, wherein the switch is an Infiniband based switch.

5. A method for optimizing data transmission in a data transfer system as recited in claim 3, wherein increasing the data transfer rate which occurs when a congestion rate limit (CRL) is greater than a slow start rate threshold (SSRT) value is defined by using the following equation:

CRL′

=CRL+(BR/CRL)*BR.

6. A method for optimizing data transmission in a data transfer system as recited in claim 3, wherein the buffer is an output buffer in the switch.

7. A method for optimizing data transmission in a data transfer system as recited in claim 3, wherein the buffer is an input buffer in the switch.

8. A method for optimizing data transmission in a data transfer system as recited in claim 3, wherein K has a value between 0.1 and 1.

9. A method for optimizing data transmission in a data transfer system as recited in claim 3, wherein K has a value of 0.5.

10. A method for optimizing data transmission in a data transfer system, the data transfer system including a transmitting device that transmits data to a receiving device through a switch, comprising:

monitoring data transfer congestion in a buffer of the switch, the monitoring including marking the data when data transfer congestion is detected, the monitoring data transfer congestion including marking the data according to a probability corresponding to a percentage of time that the buffer is full;

if data transfer congestion is detected,

marking an acknowledgement (ACK) data after the marked data is received by the receiving device;

transmitting the ACK data from the receiving device to the transmitting device;

if the ACK data is marked,

decreasing a data transfer rate multiplicatively between the transmitting device and the receiving device; and

if the ACK data is unmarked,

increasing the data transfer rate additively between the transmitting device and the receiving device;

wherein increasing the data transfer rate which occurs when a congestion rate limit (CRL) is greater than a slow start rate threshold (SSRT) value is defined by using the following equation;

CRL′

=CRL+(BR/CRL)*BR.

11. A method for optimizing data transmission in a data transfer system as recited in claim 10, wherein the switch is an Infiniband based switch.

12. A method for optimizing data transmission in a data transfer system as recited in claim 10, wherein the buffer is an output buffer in the switch.

13. A method for optimizing data transmission in a data transfer system as recited in claim 10, wherein the buffer is an input buffer in the switch.

14. A method for optimizing data transmission in a data transfer system, the data transfer system including a transmitting device that transmits data to a receiving device through a switch, comprising:

monitoring data transfer congestion in a buffer of the switch, the monitoring including marking the data when data transfer congestion is detected, the monitoring data transfer congestion including marking the data according to a probability corresponding to a percentage of time that the buffer is full;

if data transfer congestion is detected,

marking an acknowledgement (ACK) data after the marked data is received by the receiving device;

transmitting the ACK data from the receiving device to the transmitting device;

if the ACK data is marked,

decreasing a data transfer rate multiplicatively between the transmitting device and the receiving device; and

if the ACK data is unmarked,

increasing the data transfer rate additively between the transmitting device and the receiving device;

wherein decreasing the data transfer rate is defined by the following equation;

CWND′

=Bytes in flight−

K*(bytes covered by ACK).

15. A method for optimizing data transmission in a data transfer system as recited in claim 14, wherein increasing the data transfer rate which occurs when a send window is greater than an SSTHRESH value is defined by the following equation:

CWND′

=CWND+(MTU/CWND)*MTU.

16. A method for optimizing data transmission in a data transfer system as recited in claim 14, wherein K has a value between 0.1 and 1.

17. A method for optimizing data transmission in a data transfer system as recited in claim 14, wherein K has a value of 0.5.

18. An Infiniband switch to be used in a network system, the Infiniband switch defining a connection between a transmitting device and a receiving device, the Infiniband switch comprising:

an input buffer for receiving data from the transmitting device;

an output buffer for receiving data from the input buffer and delivering the data to the receiving device;

firmware having processing logic for monitoring congestion at the output buffer, the processing logic being configured to mark the data being communicated to the receiving device according to probability that congestion exists, the receiving device being configured to mark acknowledgement packets being communicated to the transmitting device when the data is marked, the transmitting device being configured to decrease data transmission rate upon receipt of marked acknowledgement packets and increase data transmission rate upon receipt of un-marked acknowledgement packets;

wherein the transmitting device decreases data transmission as defined by the following equation;

CRL′

=actual rate−

K*(rate of packets covered by ACK).

19. An Infiniband switch to be used in a network system as recited in claim 18, wherein the transmitting device increases the data transmission rate as defined by the following equation when a congestion rate limit (CRL) is greater than a slow start rate threshold (SSRT) value:

CRL′

=CRL+(BR/CRL)*BR.

20. An Infiniband switch to be used in a network system as recited in claim 18, wherein the processing logic marks data packets from the output buffer according to a probability corresponding to a percentage of time that the buffer is full.

21. An Infiniband switch to be used in a network system, the Infiniband switch defining a connection between a transmitting device and a receiving device, the Infiniband switch comprising:

an input buffer for receiving data from the transmitting device;

an output buffer for receiving data from the input buffer and delivering the data to the receiving device;

firmware having processing logic for monitoring congestion at the output buffer, the processing logic being configured to mark the data being communicated to the receiving device according to probability that congestion exists, the receiving device being configured to mark acknowledgement packets being communicated to the transmitting device when the data is marked, the transmitting device being configured to decrease data transmission rate upon receipt of marked acknowledgement packets and increase data transmission rate upon receipt of un-marked acknowledgement packets;

wherein the transmitting device decreases data transmission as defined by the following equation;

CWND′

=Bytes in flight−

K*(bytes covered by ACK).

22. An Infiniband switch to be used in a network system as recited in claim 21, wherein the transmitting device increases data transmission rate as defined by the following equation when a congestion rate limit (CWND) is greater than a slow start rate threshold (SSTHRESH) value:

CWND′

=CWND+(MTU/CWND)*MTU.

23. An Infiniband switch to be used in a network system as recited in claim 21, wherein the processing logic marks data packets from the output buffer according to a probability corresponding to a percentage of time that the buffer is full.