Delayed-start method for minimizing internal switch congestion

• US 7,911,960 B1
• Filed: 08/13/1999
• Issued: 03/22/2011
• Est. Priority Date: 08/13/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Woolet, Steven Paul, Aydemir, Metin, Heddes, Marco C., Jeffries, Clark Debs
• Primary Examiner(s): PHAN, MAN U
• Application Number:
  US09/373,837
• Time in Patent Office: 4,239 Days
• Field of Search: 370229-236, 370/249, 370395-418, 370/428, 370/429, 370252-351, 370364-389, 709217-224
• US Class Current: 370/236
• CPC Class Codes: H04L 47/266 Stopping or restarting the source, e.g. X-on or X-off
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 49/506 Backpressure

Abstract

A data flow control method and system within a data switch. The data switch includes a plurality of input sections each having an associated input buffer and each transmitting data to an output section. In response to a detection of congestion within the output section, data transmissions from the plurality of input sections to the output section are paused. Input buffer occupancies of each of the input sections are then determined. Thereafter, and in response to a backpressure relief signal, the restart of said data transmission from each of the input sections to the output section is delayed in inverse proportion to each of the determined input buffer occupancies.

Claims

1. A data flow control method within a data switch having a plurality of input sections each including a respective input buffer from which that input section transmits data to an output section through a switching fabric, said data flow control method comprising the steps of:

defining a plurality of occupancy levels, including a high level and a low level, each uniquely corresponding to a range of input buffer occupancy values;

pausing data transmission from said plurality of input sections to said output section in response to a detection of congestion within said switching fabric or within said output section;

determining input buffer occupancy of the input buffer of each of said plurality of input sections during said pause;

computing a delay interval based upon said input buffer occupancy; and

delaying restart of data transmission from said plurality of input sections to said output section in accordance with said computed delay interval.

2. The data flow control method of claim 1, wherein said data switch further includes an output buffer within said output section and the switching fabric routes data from said input section to said output section, and wherein said step of pausing data transmission from said input section is preceded by the steps of:

detecting a congested condition within said output buffer; and

in response to said detection of a congested condition within an output buffer, generating a backpressure signal within said switching fabric.

3. The data flow control method of claim 2, wherein said step of detecting a congested condition within said output buffer comprises detecting a backpressure signal from said switching fabric.

4. The data flow control method of claim 3, wherein said step of pausing data transmission is initiated in response to an input section among the plurality of input sections receiving said backpressure signal.

5. The data flow control method of claim 2, wherein said detection of congestion within said output buffer comprises the step of detecting a high level of occupancy within said output buffer.

6. The data flow control method of claim 5, further comprising the steps of:

monitoring said output buffer for an indication of congestion;

detecting an indication of congestion within said output buffer;

generating a congestion indication signal in response to said step of detecting an indication of congestion;

delivering said congestion indication signal from said switching fabric to an input section among the plurality of input sections; and

pausing data transmission from said input section to said output section in response to said delivery of said congestion indication signal.

7. The data flow control method of claim 1, wherein the duration of said computed delay interval varies inversely with said determined input buffer occupancy.

8. The data flow control method of claim 1, wherein said step of determining input buffer occupancies during said pause comprises the steps of:

reading an exact input buffer occupancy value for each of said input sections; and

in accordance with said occupancy level definitions, assigning one of said occupancy levels to each of said input sections in response to said step of reading an exact input section buffer occupancy value.

9. The data flow control method of claim 1, wherein said data switch further comprises an intelligent control device, and wherein said step of determining input buffer occupancies further comprises the steps of:

in a periodic manner within said intelligent control device;

reading an input buffer occupancy value for each of said plurality of input sections;

associating each of said input section buffer occupancy values with a buffer occupancy level; and

assigning said occupancy levels to corresponding input sections.

10. A data flow control system within a data switch having a plurality of input sections each including a respective input buffer from which that input section transmits data to an output section through a switching fabric, said data flow control system comprising:

means for defining a plurality of occupancy levels, including a high level and a low level, each uniquely corresponding to a range of input buffer occupancy values;

means for pausing data transmission from said plurality of input sections to said output section in response to a detection of congestion within said switching fabric or within said output section;

means for determining input buffer occupancy of the input buffer of each of said plurality of input sections during said pause; and

means for computing a delay interval based upon said determined input buffer occupancy and for delaying restart of data transmission from said plurality of input sections to said output section in accordance with said computed delay interval.

11. The data flow control system of claim 10, wherein said data switch further includes an output buffer within said output section and the switching fabric routes data from said input section to said output section, and wherein said means for pausing data transmission from said input section further comprises:

means for detecting a congested condition within said output buffer; and

means for generating a backpressure signal within said switching fabric in response to detecting a congested condition within an output buffer.

12. The data flow control system of claim 11, wherein said means for detecting a congested condition within said output buffer comprises means for detecting a backpressure signal from said switching fabric.

13. The data flow control system of claim 12, wherein said means for pausing data transmission is initiated in response to an input section among the plurality of input sections receiving said backpressure signal.

14. The data flow control system of claim 11, wherein said means for detecting congestion within said output buffer comprises means for detecting a high level of occupancy within said output buffer.

15. The data flow control system of claim 14, further comprising:

means for monitoring said output buffer for an indication of congestion;

means for detecting an indication of congestion within said output buffer;

means for generating a congestion indication signal in response to detecting an indication of congestion;

means for delivering said congestion indication signal from said switching fabric to an input section among the plurality of input sections; and

means for pausing data transmission from said input section to said output section in response to delivering said congestion indication signal.

16. The data flow control system of claim 10, wherein the duration of said computed delay interval varies inversely with said determined input buffer occupancy.

17. The data flow control system of claim 10, wherein said means for determining input buffer occupancies during said pause comprises:

means for reading an exact input buffer occupancy value for each of said input sections; and

means for assigning one of said occupancy levels to each of said input sections in accordance with said occupancy level definitions.

18. The data flow control system of claim 10, wherein said data switch further comprises an intelligent control device, and wherein said means for determining input buffer occupancies further comprises:

means for reading an input buffer occupancy value for each of said plurality of input sections;

means for associating each of said input section buffer occupancy values with a buffer occupancy level; and

means for assigning said occupancy levels to corresponding input sections.