Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1998-08-05
2002-09-24
Jung, Min (Department: 2663)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S236100
Reexamination Certificate
active
06456592
ABSTRACT:
FIELD OF THE INVENTION
The present invention is related to a method and apparatus for switching cells with a scheduler as a function of a memory mechanism's occupancy. More specifically, the present invention is related to an ATM switch which stamps explict rate to ABR VCs for controlling ABR traffic flow on a given link of the ATM switch with a scheduler as a function of a memory mechanism's occupancy.
BACKGROUND OF THE INVENTION
The Available Bit Rate (ABR) service of ATM networks was defined for bursty data applications which can adapt to time-varying bandwidth but which require low cell loss rate [ATM Forum. Traffic management specification version 4.0, April 1996]. ABR virtual connections (VCs) share the available bandwidth fairly, where the available bandwidth is the bandwidth leftover by the constant bit rate (CBR) and variable bit rate (VBR) traffic streams. In addition to getting a fair share of the available bandwidth, an ABR VC can also specify a minimum cell rate (MCR) which, once the ABR VC is admitted, is guaranteed.
The network provides the ABR sources with feedback information regarding the available bandwidth. Two feedback control approaches were studied: In the credit-based approach, a network node sends per-VC credits to the upstream node and the upstream node uses up a credit when it transmits a cell belonging to the VC. In the rate-based approach, the source periodically sends Resource Management (RM) cells which are turned back by the destination. The switches along the VC route indicate their congestion status in the returning RM cell.
Although, the credit-based approach (see e.g., [H. Kung and R. Morris. Credit-based flow control for ATM networks.
IEEE Networks,
9 (2):40-48, March/April 1995]) is conceptually simpler and guarantees zero cell losses, the ATM Forum selected the rate-based approach (see e.g., [F. Bonomi and K. Fendick. The rate-based flow control framework for the available bit rate ATM service.
IEEE Networks,
9(2):25-39, March/April 1995]) because it offered greater architectural flexibility. The complexity of the switch algorithm under the rate-based approach can be as simple as marking a congestion bit to as complex as computing an explicit rate (ER).
The ATM Forum defined the behavior of the end systems but left the details of the ABR switch algorithm design to the ATM switch designers. Several ER computing switch algorithms have been proposed and they essentially fall into two categories: exact fair share and approximate fair share computing algorithms. An exact fair share computing algorithm such as ERICA, ERICA+ [R. Jain, S. Kalyanaraman, R. Goyal, Fahmy S., and R. Viswanathan. ERICA switch algorithm: A complete description. ATM Forum Document Number: ATM Forum/96-1172, August 1996] and EDERA [N. Ghani.
Available Bit Rate Service in ATM Networks
. PhD thesis, University of Waterloo, 1997] measures the net available bandwidth of the switch output port and the number of active ABR VCs passing through the port. It then computes the fair share by dividing the available bandwidth by the number of active ABR VCs. On the other hand, an approximate fair share computing algorithm sch as the PRCA and EPRCA [L. Roberts. Enhanced PRCA (proportinal rate-control algorithm). ATM Forum Document: AF-TM 94-0735R1, August 1994], DMRCA and EDMRCA [F. M. Chiussi and Y. T. Wang. An ABR rate-based congestion control algorithm for ATM switches with per-VC queueing. In GLOBECOM '97, pages 771-778, 1997] avoids the floating-point division operation. It maintains port variables which are adjusted according to the congestion status of the switch output port. The ER of each VC is determined from these port variables. In general, the exact fair share computing algorithms perform better than the approximate fair share computing algorithms [N. Ghani.
Available Bit Rate Service in ATM Networks
. PhD thesis, University of Waterloo, 1997].
An important problem associated with the exact fair-share computing approach is the redistribution of bandwidth from ABR VCs bottle-necked elsewhere to those bottle-necked at the switch. For example, consider three active ABR VCs each with zero MCR, and let the net available bandwidth be 30 Mbits/sec, then the fair share for each ABR VC is 10 Mbits/sec. Assume that the first two ABR VCs are bottle-necked at the switch whereas the third ABR VC is bottle-necked at some other switch which prevents the third ABR VC from using more than 5 Mbits/sec. This implies that a bandwidth of 30−(10+10+5)=5 Mbits/sec has to be redistributed among the first two ABR VCs. Thus, the fair shares for the three VCs should be 12.5, 12.5, and 5.0 Mbits/sec, respectively.
The Explicit Rate Indication for Congestion Avoidance (ERICA), and ERICA+ [R. Jain, S. Kalyanaraman, R. Goyal, Fahmy S., and R. Viswanathan. Determining the number of active ABR sources in switch algorithms. ATM Form Document Number: ATM Forum/98-0154, February 1998; R. Jain, S. Kalyanaraman, R. Goyal, Fahmy S., and R. Viswanathan. ERICA switch algorithm: A complete description. ATM Form Document Number: ATM Forum/96-1172, August 1996] employ complex schemes for the redistribution which require the measurement of per-VC service rates. For example, ERICA+ solves the redistribution problem by dividing the available bandwidth by the effective number of active ABR VCs, rather than by the number of active ABR VCs. The effective number of active ABR VCs is defined as follows: The ABR VCs which are bottle-necked at the switch are counted as one whereas those which are bottle-necked elsewhere are counted only as a fraction equal to (Actual VC rate/Fair Share). Thus, to compute the effective number of active ABR VCs, the cell rate of each VC has to be measured at the switch port. The measurements of VC rate entails algorithms with O(n) space compleity and/or O(n) time complexity, where n is the number of VCs passing through the port. Hence, such switch algorithms are very expensive to implement in high-speed hardware.
The Enhanced Distributed Explicit Rate Algorithm (EDERA) [N. Ghani.
Available Bit Rate Service in ATM Networks
. PhD thesis, University of Waterloo, 1997] solves the redistribution problem by explicitly keeping track of the ABR VCs which are bottle-necked at the switch versus those bottle-necked elsewhere. EDERA assumes that the ABR sources indicate their segmented average source rate (SASR) in the RM cells where SASR is defined as the ratio of number of data cells between two RM cells to the time between the two RM cells. Note that SASR will be less than Allowed Cell Rate (ACR) if the VC is bottle-necked at some point in the network. Since the ATM Forum standards [ATM Forum. Traffic management specification version 4.0, April 1996] have opted not to include SASR indications in the RM cells, the EDERA scheme has to be suitably modified. Such a modification entails the measurement of VC rates at the switch output ports.
The present invention is directed to a novel ABR switch algorithm, Simple Explicit Rate Indication Algorithm (SERIA). Unlike ERICA, ERICA+ and EDERA, SERIA does not need to measure per-VC rates. In fact, SERIA is much simpler than the previously proposed exact fair share computing switch algorithms: The number of arithmetic and logical operations needed to handle events such as cell arrival and cell departure is a small number independent of the number of VCs. The simplicity of SERIA makes it particularly attractive for high speed implementations [M. Vishnu, D. Basak, and H. S. Kim. Method and apparatus for a simple explicit rate indication algorithm (SERIA) U.S. Patent Pending, 1998].
Extensive simulation results show that SERIA provides max-min fairness, converges to steady state quickly, utilizes 100% of the link bandwidth, and maintains tight buffer control.
SUMMARY OF THE INVENTION
The present invention pertains to an apparatus for switching cells from entities in a network. The app
Basak Debashis
Kim Hyong S.
Vishnu Meenarachagan
Jung Min
Marconi Communications Inc.
Schwartz Ansel M.
LandOfFree
Method and apparatus for a simple explicit rate indication... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for a simple explicit rate indication..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for a simple explicit rate indication... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2824796