Method and apparatus for congestion management in computer networks using explicit rate indication

• US 5,633,859 A
• Filed: 09/16/1994
• Issued: 05/27/1997
• Est. Priority Date: 09/16/1994
• Status: Expired due to Fees

• Current Assignee: Ohio State University
• Original Assignee: Ohio State University
• Inventors: Viswanathan, Ram, Jain, Raj, Kalyanaraman, Shiv
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): PHILLIPS, MATTHEW
• Application Number:
  US08/307,375
• Time in Patent Office: 984 Days
• Field of Search: 370/84, 370/17, 370/58.2, 370/58.3, 370/68.1, 370/58.1, 370/60, 370/60.1, 370/94.1, 370/110.1
• US Class Current: 370/234
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5635 Backpressure, e.g. for ABR
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04Q 2213/13545 monitoring of signaling messages, intelligent network
• CPC Class Codes: H04Q 2213/13561 congestion - inc. overflow
• CPC Class Codes: H04Q 2213/13564 load balancing
• CPC Class Codes: H04Q 3/0091 Congestion or overload control

Abstract

An explicit rate indication method for congestion management in computer and telecommunication networks. Sources monitor their load and provide the information periodically to switches. The switches, in turn, compute the load level and ask the sources to adjust their rates up or down. The scheme achieves high link utilization, fair allocation of rates among contending sources and provides quick convergence.

Claims

1. A method adaptable for use in a computer network having at least one source and at least one destination between which data is transferred via a switch, the method comprising steps of:

determining the actual load level of the switch;

receiving a control cell from the source in the switch, the control cell including a first load adjustment factor and being transmitted from the source at a first transmission rate;

determining a second load adjustment factor in accordance with the current load level and a first load adjustment factor;

sending the control cell including the second load adjustment factor to at least one of the source and the destination;

receiving the control cell at the at least one of the source and the destination;

sending the control cell to the source by the destination if received at the destination; and

,

selectively adjusting the first transmission rate of the source to a second transmission rate in accordance with the second load adjustment factor.

2. The method according to claim 1 wherein the adjusting is accomplished using backward explicit congestion notification.

3. The method according to claim 2 further comprising providing a timestamp to the control cell to indicate when the control cell was generated.

4. The method according to claim 3 further comprising ignoring the control cell based on a value of the timestamp.

5. The method according to claim 2 wherein the sending of the control cell to the source from the switch only occurs if the switch is overloaded.

6. The method according to claim 1 wherein the adjusting is accomplished using forward explicit congestion notification.

7. The method according to claim 1 further comprising adjusting the second load adjustment in the switch in accordance with a determination of a fair share allocated to a flow based on a target cell rate and a number of active sources in the network.

8. The method according to claim 1 wherein the selectively adjusting comprises determining whether the first transmission rate or the second transmission rate is used by the source in accordance with at least one of whether the second load adjustment factor is greater than or equal to one and whether the second transmission rate is less than the first transmission rate.

9. A method for controlling an end system transmitting data at a first transmission rate in a network having a switch through which data is transferred, the method comprising steps of:

receiving a control cell from the switch, the control cell including a load adjustment factor determined in accordance with an actual load of the switch;

determining a second transmission rate based on the first transmission rate and the load adjustment factor;

selectively adjusting the end system to transmit data at the second transmission rate if the load adjustment factor is

     1) greater than or equal to one and the second transmission rate is less than the first transmission rate, or

     2) less than one and the second transmission rate is greater than the first transmission rate.

10. The method according to claim 9 further comprising determining an average rate and an instantaneous rate of the end system.

11. A method for controlling an end system having a first transmission rate in a network having a switch through which data is transferred, the method comprising steps of:

receiving a control cell from the switch, the control cell including a load adjustment factor determined in accordance with an actual load of the switch and a time stamp indicating when the control cell was generated;

determining a second transmission rate based on the first transmission rate and the load adjustment factor;

selectively adjusting the end system to transmit the data at the second transmission rate if the load adjustment factor is greater than or equal to one and the second transmission rate is less than the first transmission rate.

12. The method according to claim 11 further comprising determining whether the time stamp is greater than or equal to a stored time stamp representing a most recent control cell acted upon to decrease transmission rate and performing the determining and the selectively adjusting only if the time stamp is greater than or equal to the stored time stamp.

13. A method for controlling a switch in a computer network operating in a utilization band and having at least two end systems, a first end system having an average rate of data transmission, the method comprising steps of:

determining the actual load level of the switch;

receiving a control cell from the first end system, the control cell including a first load adjustment factor;

selectively determining a second load adjustment factor in accordance with the load level and the first load adjustment factor;

sending the control cell including the first load adjustment factor to a second end system if the first load adjustment factor is greater than or equal to the second load adjustment factor;

sending the control cell including the second load adjustment factor to the second end system if the second load adjustment factor is greater than the first load adjustment factor.

14. The method according to claim 13 further comprising sending the control cell including the second load adjustment factor to the source if the second load adjustment factor is greater than the first load adjustment factor, a backward explicit congestion notification option is present, and the second load adjustment factor is greater than one.

15. The method according to claim 13 further comprising:

determining a target rate of transmission;

determining a total number of active source end systems;

determining a fair share rate for each source end system based on the target rate and the total number of active source end systems, wherein selectively determining the second load adjustment factor comprises

selecting the load level as the second load adjustment factor if the network is not operating within a predetermined target utilization band,

selecting the load level divided by a number greater than one as the second load adjustment factor if the network is operating in the target utilization band and the average rate is less than or equal to the fair share rate, and

selecting the load level divided by a second number less than one as the second load adjustment factor if the network is operating in the target utilization band and the average rate is greater than the fair share rate.

16. The method according to claim 15 further comprising selecting a target level less than one to be used to determine transmission rate.

17. The method according to claim 13 further comprising:

determining a target rate;

determining a total number of active virtual channels;

determining a total number of active source end systems;

determining a fairshare rate for each source end system based on the target rate and the total number of active source end systems;

determining whether the load level is greater than or equal to an upper load bound;

determining whether a load level is less than a lower load bound;

wherein if the load level is greater than or equal to the upper load bound, the selectively determining comprises

selecting one as the second load adjustment factor if the average rate is less than the fairshare rate and the number of active virtual channels is not equal to one,

selecting a maximum of one and the average rate divided by the fairshare rate as the second load adjustment level if

     1) the average rate is greater than or equal to the fair share rate or the number of active virtual channels is equal to one and

     2) the average rate is less than the fair share rate multiplied by the load level,

selecting the load level to be the second load adjustment factor

     1) if the average rate is greater than the fair share rate or the number of active virtual channels is equal to one,

     2) if the average rate is greater than or equal to the fair share rate multiplied by the load level and

     3) if the average rate is less than the target cell rate,

selecting the load level multiplied by the average rate divided by the target cell rate

     1) if the average rate is greater than or equal to the fair share rate or the number of active virtual channels equals one,

     2) if the average rate is greater than or equal to the fair share rate multiplied by the load level and

     3) if the average rate is greater than or equal to the target cell rate,

and wherein if the load level is less than the lower load bound, the selectively determining comprises

selecting the load level as the second load adjustment factor if

     1) the average rate is less than the fair share multiplied by the load level or

     2) the number of active virtual channels equals one,

selecting the second load adjustment factor based on the average rate, the load level, and the total number of active virtual channels

     1) if the average rate is less than the target cell rate multiplied by the load level,

     2) if the average rate is greater than or equal to the fair share rate multiplied by the load level and

     3) if the number of active virtual channels is not equal to one,

selecting one as the second load adjustment factor

     1) if the average rate is greater than or equal to the target rate multiplied by the load level,

     2) if the average rate is greater than or equal to the fair share rate multiplied by the load level and

     3) if the number of active virtual channels does not equal one.

18. The method according to claim 13 further comprising:

determining a target rate;

determining a total number of active source end systems;

determining a fair share rate for each source end system based on the target rate and the total number of active source end systems;

determining a total number of underloaded virtual channels; and

,

recomputing the fair share rate,

wherein the selectively determining comprises selecting the average rate divided by the fair share rate as the second load adjustment factor if the fair share rate is constant.

33. The apparatus according to claim 13 further comprising:

means for determining a target rate of transmission;

means for determining a total number of active source end systems;

means for determining a fair share rate for each source end system based on the target rate and the total number of active source end systems,

wherein the means for selectively determining the second load adjustment factor comprises

means for selecting the load level as the second load adjustment factor if the network is not operating within a predetermined target utilization band,

means for selecting the load level divided by a number greater than one as the second load adjustment factor if the network is operating in the target utilization band and the average rate is less than or equal to the fair share rate, and

means for selecting the load level divided by a second number less than one as the second load adjustment factor if the network is operating in the target utilization band and the average rate is greater than the fair share rate.

34. The apparatus according to claim 33 further comprising means for selecting a target level less than one to be used to determine transmission rate.

19. An apparatus in a computer network having at least one source and at least one destination between which data is transferred via a switch, the apparatus comprising:

means for determining the actual load level of the switch;

means for receiving a control cell from the source in the switch, the control cell including a first load adjustment factor and being transmitted from the source at a first transmission rate;

means for determining a second load adjustment factor in accordance with the current load level and a first load adjustment factor;

means for sending the control cell including the second load adjustment factor to at least one of the source and the destination;

means for receiving the control cell at the at least one of the source and the destination;

means for sending the control cell to the source by the destination if received at the destination; and

,

means for selectively adjusting the first transmission rate of the source to a second transmission rate in accordance with the second load adjustment factor.

20. The apparatus according to claim 19 wherein the means adjusting includes means for using backward explicit congestion notification.

21. The apparatus according to claim 19 further comprising a timestamp in the control cell to indicate when the control cell was generated.

22. The apparatus according to claim 21 further comprising means for ignoring the control cell based on a value of the timestamp.

23. The apparatus according to claim 20 further comprising:

means for determining whether the switch is overloaded,

wherein the means for sending the control cell to the source from the switch includes means for sending the control cell to the source only if the switch is overloaded.

24. The apparatus according to claim 19 wherein the means for adjusting includes means for using forward explicit congestion notification.

25. The apparatus according to claim 19 further comprising means for adjusting the second load adjustment in the switch in accordance with a determination of a fair share allocated to a flow based on a target cell rate and a number of active sources in the network.

26. The apparatus according to claim 19 wherein the means for selectively adjusting comprises means for determining whether the first transmission rate or the second transmission rate is used by the source in accordance with at least one of whether the second load adjustment factor is greater than or equal to one and whether the second transmission rate is less than the first transmission rate.

27. An apparatus for controlling an end system having a first transmission rate in a network having a switch through which data is transferred, the apparatus comprising:

means for receiving a control cell from the switch, the control cell including a load adjustment factor determined in accordance with an actual load of the switch;

means for determining a second transmission rate based on the first transmission rate and the load adjustment factor;

means for selectively adjusting the end system to transmit data at the second transmission rate if the load adjustment factor is

     1) greater than or equal to one and the second transmission rate is less than the first transmission rate, or

     2) less than one and the second transmission rate is greater than the first transmission rate.

28. The apparatus according to claim 27 further comprising means for determining an average rate and an instantaneous rate of the end system.

29. An apparatus for controlling an end system having a first transmission rate in a network having a switch through which data is transferred, the apparatus comprising:

means for receiving a control cell from the switch, the control cell including a load adjustment factor determined in accordance with an actual load of the switch and a time stamp indicating when the control cell was generated;

means for determining a second transmission rate based on the first transmission rate and the load adjustment factor;

means for selectively adjusting the end system to transmit the data at the second transmission rate if the load adjustment factor is greater than or equal to one and the second transmission rate is less than the first transmission rate.

30. The apparatus according to claim 29 further comprising means for determining whether the time stamp is greater than or equal to a stored time stamp representing a most recent control cell acted upon to decrease transmission rate and means for performing the determining and the selectively adjusting only if the time stamp is greater than or equal to the stored time stamp.

31. An apparatus for controlling a switch in a computer network operating in a utilization band and having at least two end systems, a first end system having an average rate of data transmission, the apparatus comprising:

means for determining the actual load level of the switch;

means for receiving a control cell from the first end system, the control cell including a first load adjustment factor;

means for selectively determining a second load adjustment factor in accordance with the load level and the first load adjustment factor;

means for sending the control cell including the first load adjustment factor to a second end system if the first load adjustment factor is greater than or equal to the second load adjustment factor;

means for sending the control cell including the second load adjustment factor to the second end system if the second load adjustment factor is greater than the first load adjustment factor.

32. The apparatus according to claim 31 further comprising means for sending the control cell including the second load adjustment factor to the source if the second load adjustment factor is greater than the first load adjustment factor, a backward explicit congestion notification option is present, and the second load adjustment factor is greater than one.

35. The apparatus according to claim 31 further comprising:

means for determining a target rate;

means for determining a total number of active virtual channels;

means for determining a total number of active source end systems;

means for determining a fairshare rate for each source end system based on the target rate and the total number of active source end systems;

means for determining whether the load level is greater than or equal to an upper load bound;

means for determining whether a load level is less than a lower load bound;

wherein if the load level is greater than or equal to an upper load bound, the means for selectively determining includes means for;

selecting one as the second load adjustment factor if the average rate is less than the fairshare rate and the number of active virtual channels is not equal to one,

selecting a maximum of one and the average rate divided by the fairshare rate as the second load adjustment level if

     1) the average rate is greater than or equal to the fair share rate or the number of active virtual channels is equal to one and

     2) the average rate is less than the fair share rate multiplied by the load level,

selecting the load level to be the second load adjustment factor

     1) if the average rate is greater than the fair share rate or the number of active virtual channels is equal to one,

     2) if the average rate is greater than or equal to the fair share rate multiplied by the load level and

     3) if the average rate is less than the target cell rate,

selecting the load level multiplied by the average rate divided by the target cell rate

     1) if the average rate is greater than or equal to the fair share rate or the number of active virtual channels equals one,

     2) if the average rate is greater than or equal to the fair share rate multiplied by the load level and

     3) if the average rate is greater than or equal to the target cell rate,

and wherein the load level is less than the lower load bound, the means for selectively determining includes means for;

selecting the load level as the second load adjustment factor if

     1) the average rate is less than the fair share multiplied by the load level or

     2) the number of active virtual channels equals one,

selecting the second load adjustment factor based on the average rate, the load level, and the total number of active virtual channels

     1) if the average rate is less than the target cell rate multiplied by the load level,

     2) if the average rate is greater than or equal to the fair share rate multiplied by the load level and

     3) the number of active virtual channels is not equal to one,

selecting one as the second load adjustment factor

     1) if the average rate is greater than or equal to the target rate multiplied by the load level,

     2) if the average rate is greater than or equal to the fair share rate multiplied by the load level

     3) if the number of active virtual channels does not equal one.

36. The apparatus according to claim 31 further comprising:

means for determining a target rate;

means for determining a total number of active source end systems;

means for determining a fair share rate for each source end system based on the target rate and the total number of active source end systems;

means for determining underloaded virtual channels; and

,

means for recomputing the fair share rate,

wherein the means for selectively determining includes means for selecting the average rate divided by the fair share rate as the second load adjustment factor if the fair share rate is constant.