US5633859A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for congestion management in computer networks using explicit rate indication
Assignee: The Ohio State University
•
Filing: 1994-09-16
•
Granted: 1997-05-27
•
Expires: 2014-09-16
Abstract
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.
Inventors
- 👤 Raj Jain
- 👤 Shiv Kalyanaraman
- 👤 Ram Viswanathan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 10:53
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L12/5602; H04Q; H04Q3/00; H04Q3/0016; H04Q3/0062; H04Q3/0091; H04L2012/5629; H04L2012/5631; H04L2012/5632; H04L2012/5635; H04L2012/5678; H04L2012/5679; H04Q2213/00; H04Q2213/13545; H04Q2213/13561; H04Q2213/13564
Claims Analysis
Total Claims: 44
Claim 1
Independent Claim
162 words
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.
Claim 2
Independent Claim
162 words
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.
Claim 3
Dependent Claim
16 words
The method according to claim 1 wherein the adjusting is accomplished using backward explicit congestion notification.
Claim 4
Dependent Claim
23 words
The method according to claim 2 further comprising providing a timestamp to the control cell to indicate when the control cell was generated.
Claim 5
Dependent Claim
19 words
The method according to claim 3 further comprising ignoring the control cell based on a value of the timestamp.
Claim 6
Dependent Claim
26 words
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.
Claim 7
Dependent Claim
16 words
The method according to claim 1 wherein the adjusting is accomplished using forward explicit congestion notification.
Claim 8
Dependent Claim
44 words
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.
Claim 9
Dependent Claim
60 words
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.
Claim 10
Independent Claim
126 words
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.
Claim 11
Independent Claim
126 words
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.
Claim 12
Dependent Claim
20 words
The method according to claim 9 further comprising determining an average rate and an instantaneous rate of the end system.
Claim 13
Independent Claim
118 words
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.
Claim 14
Independent Claim
118 words
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.
Claim 15
Dependent Claim
58 words
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.
Claim 16
Independent Claim
144 words
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.
Claim 17
Independent Claim
144 words
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.
Claim 18
Dependent Claim
53 words
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.
Claim 19
Dependent Claim
159 words
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.
Claim 20
Dependent Claim
22 words
The method according to claim 15 further comprising selecting a target level less than one to be used to determine transmission rate.
Claim 21
Dependent Claim
519 words
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.
Claim 22
Dependent Claim
87 words
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.
Claim 23
Independent Claim
171 words
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.
Claim 24
Independent Claim
171 words
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.
Claim 25
Dependent Claim
18 words
The apparatus according to claim 19 wherein the means adjusting includes means for using backward explicit congestion notification.
Claim 26
Dependent Claim
22 words
The apparatus according to claim 19 further comprising a timestamp in the control cell to indicate when the control cell was generated.
Claim 27
Dependent Claim
21 words
The apparatus according to claim 21 further comprising means for ignoring the control cell based on a value of the timestamp.
Claim 28
Dependent Claim
46 words
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.
Claim 29
Dependent Claim
19 words
The apparatus according to claim 19 wherein the means for adjusting includes means for using forward explicit congestion notification.
Claim 30
Dependent Claim
46 words
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.
Claim 31
Dependent Claim
64 words
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.
Claim 32
Independent Claim
128 words
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.
Claim 33
Independent Claim
128 words
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.
Claim 34
Dependent Claim
22 words
The apparatus according to claim 27 further comprising means for determining an average rate and an instantaneous rate of the end system.
Claim 35
Independent Claim
122 words
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.
Claim 36
Independent Claim
122 words
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.
Claim 37
Dependent Claim
62 words
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.
Claim 38
Independent Claim
152 words
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.
Claim 39
Independent Claim
152 words
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.
Claim 40
Dependent Claim
55 words
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.
Claim 41
Dependent Claim
174 words
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.
Claim 42
Dependent Claim
24 words
The apparatus according to claim 33 further comprising means for selecting a target level less than one to be used to determine transmission rate.
Claim 43
Dependent Claim
536 words
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.
Claim 44
Dependent Claim
97 words
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.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-05-26 | 2000-11-25 | 2001-05-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-05-26 | 2004-11-25 | 2005-05-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-05-26 | 2008-11-25 | 2009-05-27 | $7700.00 | Window Closed / Lapsed |