Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1999-04-15
2003-01-28
Vanderpuye, Ken (Department: 2732)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S236100, C370S468000
Reexamination Certificate
active
06512743
ABSTRACT:
FIELD OF THE INVENTION
This invention pertains generally to Asynchronous Transfer Mode (ATM) packet switching, and more particularly to methods and systems for switch bandwidth allocation for ATM available bit rate service.
BACKGROUND OF THE INVENTION
ATM is a networking standard designed to provide simultaneous support for voice, video, and data traffic. An ATM network is packet-switched, but supports only one particular packet size—a 53-byte packet called a cell. Without regard to the type of information contained in a cell, each ATM cell must have a five-byte cell header and a 48-byte payload.
ATM is connection oriented. That is, two systems must set up an end-to-end “connection” over the network before they can communicate. But the connection does not require a dedicated circuit like a traditional telephone network connection; instead, the connection is merely a grant of permission to transmit cells at a negotiated data rate, with some guarantees as to quality-of-service (QoS) pararmeters such as minimum cell rate, average cell rate, and network delay. The term commonly used for an ATM connection is a Virtual Channel or “VC”.
ATM contains several service classes, each designed to meet the needs of particular types of information sources. The Constant Bit Rate (CBR) service class is most appropriate for sources having a known, constant transmission rate, such as traditional PCM-sampled telephone signals. The Variable Bit Rate (VBR) service class allows some variation in transmission rate but provides bandwidth guarantees, and is appropriate for digital video (e.g., MPEG-coded or H.26x video) and similar applications. The Available Bit Rate (ABR) service class is appropriate for most data transmission. ATM switches monitor their excess capacity (that part not being used by other service classes with guaranteed rates) and allocate that capacity to their ABR connections. Each ABR source is required, in return, to control its rate as directed by the switches in its connection path. Finally, the Unspecified Bit Rate (UBR) service class is also available for data transmission. UBR traffic has no guarantees as to cell loss rate or delay, but places few restraints on the behavior of sources.
ABR and UBR traffic can be regarded as “best-effort” traffic. That is, CBR and VBR traffic have precedence because of their QoS guarantees, and ATM switches work to schedule ABR and UBR traffic around their CBR and VBR. traffic. In order to provide an incentive for best-effort traffic sources to utilize ABR connections, ATM switches attempt to divide their unreserved capacity fairly and efficiently between all competing ABR sources.
The “ERICA” and “ERICA+” switch congestion avoidance algorithms, as disclosed by R. Jain et al. in U.S. Pat. No. 5,805,577, represent a state-of-the-art approach to controlling ABR traffic. These algorithms measure switch utilization over “averaging intervals”, including making a count of the number of sources that utilized the switch during the interval. At the end of each such interval, an available ABR capacity for the next such interval is computed. Then, a “fair share” of the available ABR capacity is determined by dividing the capacity by the number of sources that were active over the preceding interval.
An overload factor is also calculated to represent the current overall switch load as a percentage. An explicit rate is then assigned to each source for use during the next measurement interval, based on its current rate, as:
Explicit Rate=max( Fair Share, Current Rate/Overload Factor)
This explicit rate is communicated to its corresponding source.
SUMMARY OF THE INVENTION
The present invention is related to ATM switch operation, and more particularly, to allocation of bandwidth between competing ABR sources. The goals of the present invention are to maximize throughput and minimize queueing delay, while treating each source fairly.
The present invention overcomes several shortcomings of prior art algorithms such as “ERICA”. First, the prior art algorithms do not directly identify, and consider the effect of, sources that cannot or do not wish to transmit their “fair share”—this causes such algorithms to underestimate the true “fair share” available to those sources that want to transmit more, resulting in slow convergence to max-min fairness. Second, these algorithms tend to base each VC's explicit rate proportionally on that VC's current rate and on the distance the switch loading is from its optimal loading—an approach that also slows convergence toward a fair solution. Third, these algorithms generally attempt to distribute one or two global solutions to all sources, instead of predicting individual source behavior and tailoring the solution to each source. Fourth, these algorithms generally cannot provide feedback to sources at a rate that exceeds the switch's averaging interval. And fifth, these algorithms do not provide for an efficient and fair allocation of bandwidth between ABR and UBR sources.
The present invention includes a recognition of the problems identified above, and solutions to each. For example, one embodiment of the present invention includes a procedure for identifying VC's that have their rate limited at other points in their connection—this allows bandwidth that cannot be utilized by such bottlenecked sources to be immediately allocated to other, non-bottlenecked sources. And in one embodiment, overall switch queue congestion is not a direct factor in setting source rates—instead, the source rate for each source depends on that source's own current congestion and recent behavior. The present invention also includes embodiments that combine rate measurements, which require an averaging interval, with queue measurements, which do not, in order to provide rate-based feedback that can vary at a rate greater than the averaging interval. And finally, the present invention includes embodiments that allocate some bandwidth explicitly to UBR sources, and yet make excess UBR bandwidth immediately available to ABR sources if UBR sources are under-utilizing it.
In one aspect of the present invention, a method of determining allowable cell rates for sources utilizing a switch is disclosed. The method comprises the steps of estimating the number of rate-controlled sources actively utilizing the switch, and estimating the cell rate available to serve those sources. Active sources that are likely bottlenecked elsewhere in their connection are identified. A reduced available cell rate is estimated by reducing the cell rate available to serve the active sources by a bottlenecked source cell rate based on estimated cell rates of the active sources that are likely bottlenecked elsewhere. Finally, a fair share of the reduced available cell rate is calculated by apportioning the reduced available cell rate among those active sources that are not likely bottlenecked elsewhere.
In a second aspect of the invention, a method of providing rate feedback to a rate-controlled source utilizing a switch is disclosed. The switch monitors the cell queue occupancy for the rate-controlled source. Upon receiving a backward resource management cell bound for the rate-controlled source, the switch calculates an explicit rate for the source based on a fair share rate and the source's predicted cell queue occupancy. The switch then inserts the explicit rate in the backward resource management cell when the explicit rate is lower than the explicit rate already contained in the cell.
In yet another aspect of the invention, a cell switch is disclosed. The cell switch comprises a cell queue that maintains a source cell queue for each rate-controlled source utilizing the switch, and a cell counter that counts the number of cells passing through each source cell queue. The cell switch further comprises a bottlenecked source detector that detects bottlenecked sources based on statistics calculated by the cell counter. Preferably, the cell switch also has a resource management cell processor that calculates an explicit rate for a resource
Cisco Technology Inc.
Marger & Johnson & McCollom, P.C.
Vanderpuye Ken
LandOfFree
Bandwidth allocation for ATM available bit rate service does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Bandwidth allocation for ATM available bit rate service, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bandwidth allocation for ATM available bit rate service will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3018765