US6069872A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Explicit rate congestion control system and method
Assignee: RPX Corp
•
Filing: 1997-11-20
•
Granted: 2000-05-30
•
Expires: 2017-11-20
Abstract
Abstract An explicit rate congestion control system and method to support available bit rate service in asynchronous transfer mode (ATM) networks is provided. The system and method observe the maximum usage of different connections and incorporates both rate and queue length information to achieve a stable operation of the ATM network. The control of congestion and fairness is separated which permits the system and method to have a common framework to support multiple fairness criteria. The system and method may operate with switches implementing both aggregate and per connection queuing at their ports. In the method, the number of active connections at a bottleneck node is only used to normalize control and to redistribute spare bandwidth during transient conditions and does not affect the steady state fair rate used by each connection.
Inventors
- 👤 Flavio Bonomi
- 👤 Michael K. Wong
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 18:03
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L12/5602; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L2012/5629; H04L2012/5631; H04L2012/5632; H04L2012/5635; H04L2012/5636; H04L2012/5678; H04L2012/5679; H04L2012/5681; H04L2012/5682
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
198 words
A method for controlling congestion in a network switch by controlling the transmission rate of a source connected by a virtual channel to a transmission resource within the switch, the source transmitting data at a current cell rate, the method comprising: estimating a total number of connections connected to the transmission resource within the switch that are transmitting data through the transmission resource within the switch to generate an estimated number of active connections; determining a fair bandwidth allocation in accordance with a predetermined fairness criteria over a predetermined interval based on the current cell rate and the minimum cell rate of all sources connected through the transmission resource within the switch and the spare bandwidth of the transmission resource for each source connected through the transmission resource; calculating an adjusted transmission rate for a particular source connected to the transmission resource within the switch based on said current cell rate of the source, said fair bandwidth allocation, said estimated number of active connections and a queue length; and transmitting said adjusted transmission rate backwards to the particular source in order to explicitly control the transmission rate of the source and control the congestion of the network switch.
Claim 2
Independent Claim
198 words
A method for controlling congestion in a network switch by controlling the transmission rate of a source connected by a virtual channel to a transmission resource within the switch, the source transmitting data at a current cell rate, the method comprising: estimating a total number of connections connected to the transmission resource within the switch that are transmitting data through the transmission resource within the switch to generate an estimated number of active connections; determining a fair bandwidth allocation in accordance with a predetermined fairness criteria over a predetermined interval based on the current cell rate and the minimum cell rate of all sources connected through the transmission resource within the switch and the spare bandwidth of the transmission resource for each source connected through the transmission resource; calculating an adjusted transmission rate for a particular source connected to the transmission resource within the switch based on said current cell rate of the source, said fair bandwidth allocation, said estimated number of active connections and a queue length; and transmitting said adjusted transmission rate backwards to the particular source in order to explicitly control the transmission rate of the source and control the congestion of the network switch.
Claim 3
Dependent Claim
28 words
The method of claim 1, wherein said queue length comprises a normalized queue length which is inversely proportional to the number of active connections sharing a transmission resource.
Claim 4
Dependent Claim
80 words
The method of claim 1, wherein estimating the total number of connections comprises determining a total number of resource management cells that are received at the transmission resource during a predetermined period for each of a plurality of connections and adding the numbers resulting from multiplying the total number of resource management cells received in said predetermined period by an inverse of the current cell rate for the corresponding connection to determine an estimate for the total number of connections.
Claim 5
Dependent Claim
54 words
The method of claim 1, wherein estimating the total number of connections comprises determining a total number of resource management cells received at the transmission resource during a predetermined period for a plurality of connections and multiplying the total number with the inverse of an estimate of the fair bandwidth allocation for the connection.
Claim 6
Dependent Claim
38 words
The method of claim 1, wherein estimating the total number of connections comprises generating a weighted value for each connection to the transmission resource to generate a weighted estimate of the total number of connections to the switch.
Claim 7
Dependent Claim
64 words
The method of claim 1, wherein the allocation determination comprises determining a maximum value of a current cell rate for all connections sharing the transmission resource such that the current cell rate of a connection is greater than the minimum cell rate for that connection, and dividing the spare bandwidth of the transmission resource by the number of active connections sharing the transmission resource.
Claim 8
Dependent Claim
65 words
The method of claim 1, wherein the allocation determination comprises determining the maximum value, over the predetermined interval and over all active connections sharing the transmission resource, of a difference between a current cell rate for a connection and a minimum cell rate for that connection, and dividing the spare bandwidth of the transmission resource by the number of active connections sharing the transmission resource.
Claim 9
Dependent Claim
145 words
The method of claim 1, wherein the allocation determination comprises determining a maximum value, over the predetermined interval and over all active connections sharing the transmission resource, of a current cell rate divided by a weight associated with the connection and dividing the spare bandwidth of the transmission resource by a normalized number of active connections sharing the transmission resource, wherein said normalized number is generated by the equation (Σ J (N RM /L×W VC (J)/CCR J ), wherein Σ represents the sigma operation for all J cells received during the past L duration, N RM represents the frequency at which the resource management cells are transmitted, W VC (J) is a weight associated with the virtual connection to which the J th relates to, and CCR J represents the current cell rate on the virtual circuit to which the J th cell relates to.
Claim 10
Independent Claim
206 words
A system for controlling congestion in a network switch by controlling the transmission rate of a source connected by a virtual channel to a transmission resource within the switch, the source transmitting data at a current cell rate, the system comprising: means for estimating a total number of connections connected to the transmission resource within the switch that are transmitting data through the transmission resource within a switch to generate an estimated number of active connections; means for determining a fair bandwidth allocation in accordance with a predetermined fairness criteria over a predetermined interval based on the current cell rate and the minimum cell rate of all sources connected through the transmission resource within the switch and the spare bandwidth of the transmission resource for each source connected through the transmission resource; means for calculating an adjusted transmission rate for a particular source connected to the transmission resource within the switch based on said current cell rate of the source, said fair bandwidth allocation, said estimated number of active connections and a queue length; and means for transmitting said adjusted transmission rate backwards to the particular source in order to explicitly control the transmission rate of the source and control the congestion of the network switch.
Claim 11
Independent Claim
206 words
A system for controlling congestion in a network switch by controlling the transmission rate of a source connected by a virtual channel to a transmission resource within the switch, the source transmitting data at a current cell rate, the system comprising: means for estimating a total number of connections connected to the transmission resource within the switch that are transmitting data through the transmission resource within a switch to generate an estimated number of active connections; means for determining a fair bandwidth allocation in accordance with a predetermined fairness criteria over a predetermined interval based on the current cell rate and the minimum cell rate of all sources connected through the transmission resource within the switch and the spare bandwidth of the transmission resource for each source connected through the transmission resource; means for calculating an adjusted transmission rate for a particular source connected to the transmission resource within the switch based on said current cell rate of the source, said fair bandwidth allocation, said estimated number of active connections and a queue length; and means for transmitting said adjusted transmission rate backwards to the particular source in order to explicitly control the transmission rate of the source and control the congestion of the network switch.
Claim 12
Dependent Claim
28 words
The system of claim 9, wherein said queue length comprises a normalized queue length which is inversely proportional to the number of active connections sharing the transmission resource.
Claim 13
Dependent Claim
81 words
The system of claim 9, wherein said estimation means comprises means for determining a total number of resource management cells that are received at the transmission resource during a predetermined period for each of a plurality of connections and means for adding the numbers resulting from multiplying the total number of resource management cells received in said predetermined period by an inverse of the current cell rate for the corresponding connection to determine an estimate for the total number of connections.
Claim 14
Dependent Claim
54 words
The system of claim 9, wherein said estimating means comprises means for determining a total number of resource management cells received at the transmission resource during a predetermined period for a plurality of connections and means for combining such number with the inverse of an estimate of the fair bandwidth allocation for the connection.
Claim 15
Dependent Claim
37 words
The system of claim 9, wherein said estimating means comprises means for generating a weighted value for each connection to the switch to generate a weighted estimate of the total number of connections to the transmission resource.
Claim 16
Dependent Claim
69 words
The system of claim 9, wherein said allocation determination means comprises means for determining a maximum value of a current cell rate for all connections sharing the transmission resource such that the current cell rate of a connection is greater than the minimum cell rate for that connection, and means for dividing the spare bandwidth of the transmission resource by the number of active connections sharing the transmission resource.
Claim 17
Dependent Claim
70 words
The system of claim 9, wherein the allocation determination means comprises means for determining the maximum value, over the predetermined interval and over all active connections sharing a transmission resource, of a difference between a current cell rate for a connection and a minimum cell rate for that connection, and means for dividing the spare bandwidth of the transmission resource by the number of active connections sharing the transmission resource.
Claim 18
Dependent Claim
150 words
The system of claim 9, wherein the allocation determination means comprises means for determining a maximum value, over the predetermined interval and over all active connections sharing the transmission resource, of a current cell rate divided by a weight associated with the connection and means for dividing the spare bandwidth of the transmission resource by a normalized number of active connections sharing the transmission resource, wherein said normalized number is generated by the equation (Σ J (N RM /L×W VC (J)/CCR J ), wherein Σ represents the sigma operation for all J cells received during the past L duration, N RM represents the frequency at which the resource management cells are transmitted, W VC (J) is a weight associated with the virtual connection to which the J th relates to, and CCR J represents the current cell rate on the virtual circuit to which the J th cell relates to.
References Cited (Backward Citations)
US5805577A
Cited
US5754530A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-05-30 | 2003-11-29 | 2004-05-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-05-30 | 2007-11-29 | 2008-05-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-05-30 | 2011-11-29 | 2012-05-30 | $7700.00 | Window Closed / Lapsed |