Technique for providing end-to-end congestion control with no feedback from a lossless network

• US 7,035,220 B1
• Filed: 10/22/2001
• Issued: 04/25/2006
• Est. Priority Date: 10/22/2001
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Simcoe, Robert J.
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): SOL, ANTHONY M
• Application Number:
  US10/038,329
• Time in Patent Office: 1,646 Days
• Field of Search: None
• US Class Current: 370/236
• 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/18 End to end
• CPC Class Codes: H04L 47/215 using token-bucket
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/39 Credit based

Abstract

A congestion management technique achieves an end-to-end data flow rate that is supported by a lossless communications network. The end-to-end rate extends from a source end node to destination end node of the network and is preferably at or slightly below a bottleneck rate of the network. The destination end node determines, on its own and without any help from network elements, a supportable rate of activity in the network and provides feedback to the source end node. By achieving such a rate, data transmitted by the source end node can flow through the network without loss of packets and without the use of substantial buffering.

Claims

1. A method for achieving an end-to-end data flow rate supported by a communications network having a source and a destination interconnected by communication links, the method comprising the steps of:

initiating a data flow at the source over the links, the data flow comprising a plurality of packet pairs;

measuring an amount of data received at the destination over a predetermined time interval;

measuring a packet gap for each packet pair received at the destination over the predetermined time interval; and

determining, in response to the measured data and packet gap, a supportable data flow rate in the network so that the data flow initiated by the source can flow through the network without loss of data.

2. The method of claim 1 wherein the end-to-end data flow rate extends from the source to the destination of the network, the data flow rate being at or below a bottleneck rate of the network.

3. The method of claim 1 wherein the step of determining further comprises the step of providing feedback to the source.

4. The method of claim 3 wherein the step of providing feedback further comprises the step of communicating the supportable data flow rate to the source in the form of end-to-end credits extended to the source.

5. The method of claim 4 wherein the end-to-end credits enable transmission of a specific amount of data by the source over the predetermined time interval.

6. The method of claim 5 further comprising the steps of:

calculating an expected packet gap based on previously extended credits; and

determining if the measured packet gap is equal to or greater than the expected gap, or less than the expected gap.

7. The method of claim 6 wherein the steps of measuring and calculating allows the destination to inform the source whether to decrease or increase the amount of data flow during a next time interval.

8. The method of claim 7 further comprising the steps of:

if the measured data is less than expected, decreasing the credits extended to the source for the next interval;

if the measured data is equal to the extended credits, using the measured packet gap to determine whether to increase the credits; and

if the measured gap is less than expected, extending more credits from the destination to the source to thereby probe the network capacity.

9. The method of claim 8 further comprising the steps of:

providing a credit-based flow control mechanism; and

pacing out the data over the time interval in accordance with the credit-based flow control mechanism.

10. The method of claim 9 wherein the step of providing the credit-based flow control mechanism comprises the step of implementing the credit-based flow control mechanism as a leaky bucket.

11. The method of claim 9 wherein the paced out data is sent by the source in groups of two packets, back-to-back.

12. The method of claim 1 wherein the step of measuring the packet gap further comprises the step of averaging a plurality of packet gap measurements performed at the destination during the time interval.

13. A system adapted to achieve an end-to-end data flow rate supported by a communications network having a source and a destination interconnected by communication links, the system comprising:

a credit-based flow control mechanism configured to regulate packe pairs of a data flow over a predetermined time interval; and

congestion management logic configured to measure an amout of data received at the destination that has traversed the network over the time interval and to measure a packet gap for each received packet pair to determine if capacity of the network has increased, the congestion management logic further calculating an expected packet gap and determining if the measured packet gap is equal to or greater than the expected gap, or less than the expected gap

wherein a combination of the calculation and measurements allows the destination to inform the source whether to decrease or increase the amount of data sent during a next time interval.

14. The system of claim 13 wherein the congestion management logic comprises:

a measure circuit configured to measure the amount of data received form the source and the packet gap over the predetermined time interval; and

a flow control circuit coupled to the measure circuit, the flow control circuit configured to determine credits extended to the source for a subsequent data flow in response to the amount of measured data and the measured gap.

15. The system of claim 14 wherein the flow control circuit is further configured to generate a feedback message indicating the credits extended to the source for its subsequent data flow.

16. The system of claim 15 wherein the measure circuit is further configured to measure the packet gap between reception of an end of a first packet of the packet pair to reception of a beginning of second packet of the packet pair to determine whether adjustment of the end-to-end data flow rate is necessary.

17. The system of claim 16 wherein the measure circuit is further configured to average a plurality of the packet gap measurements over the predetermined time interval.

18. The system of claim 17 wherein the data sent under credit-based flow control is paced by a leaky bucket mechanism.

19. Apparatus for achieving an end-to-end data flow rate supported by a communications network having a source and a destination interconnected by communication links, the apparatus comprising:

means for initiating a data flow at the source over the links, the data flow comprising a plurality of packet pairs paced out over a predetermined time interval;

means for measuring an amount of data received at the destination over the predetermined time interval;

means for measuring a packet gap for the packet pairs at the destination over the predetermined time interval;

means for calculating an expected packet gap based on previously extended credits;

means for determining if the measured packet gap is equal to or greater than the expected gap, or less than the expected gap; and

means for determining, in response to the means for measuring and calculating, a supportable data flow rate in the network so that the data flow initiated by the source can flow through the network without loss of data.

20. A computer readable medium containing executable program instructions for achieving an end-to-end data flow rate supported by a communications network having a source and a destination interconnected by communication links, the executable program instructions comprising program instructions for:

initiating a data flow at the source over the links, the data flow comprising a plurality of packet pairs paced out over a predetermined time interval;

measuring an amount of data received at the destination over the predetermined time interval;

measuring a packet gap for the packet pairs at the destination over the predetermined time interval;

calculating an expected packet gap based on previously extended credits;

determining if the measured packet gap is equal to or greater than the expected gap, or less than the expected gap; and

determining a supportable data flow rate in the network so that the data flow initiated by the source can flow through the network without loss of data.