Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1998-03-02
2001-01-23
Marcelo, Melvin (Department: 2739)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S395430, C370S468000
Reexamination Certificate
active
06178159
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to asynchronous transfer mode (ATM) networks and, more particularly, to available-bit-rate (ABR) flow control algorithms.
BACKGROUND
The ABR service class has been defined by the ATM Forum as one of the five service classes in an ATM network. In an explicit-rate mode of ABR service in an ATM network, a real-time determination may be made as to the amount of bandwidth that each ABR circuit may utilize. The amount of bandwidth allocated to each ABR circuit is known as the Allowed Cell Rate (ACR). The ACR may be transmitted to the source of each circuit via special control cells known as resource management (RM) cells. The format of RM cells and the principles governing their generations and usage are specified by the ATM Forum Traffic Management 4.0 standard. There are two types of RM cells, Forward RM cells (FRM) which travel from the source to the destination, and Backward RM cells (BRM) which travel from the destination back to the source. Specifically, the Allowed Cell Rate is marked into the BRM cells because they are received by the source with a smaller delay than FRM cells. Also, according to the standard, the FRM cell contains a Current Cell Rate (CCR) field which is set by the source to indicate to the ATM network the cell rate at which the source is currently transmitting traffic. The intention of the CCR field is to assist the network in determining the ACR for all ABR circuits.
One key to a successful implementation of ABR service is the ATM network's capability to quickly and fairly adjust the allowed cell rate (ACR) for each ABR circuit when the level of congestion within the network changes. Accordingly, improved algorithms are desirable for varying the allowed cell rate (ACR) in ATM networks for each ABR circuit.
SUMMARY OF THE INVENTION
The present invention provides improved algorithms for varying the allowed cell rate (ACR) in ATM networks for each ABR circuit. Advantages of one or more aspects of the present invention include one or more of the following: 1) determining optimal ACR values which allow the sources to fully utilize the bandwidth of a trunk, 2) allowing convergence to an optimal ACR for each circuit quickly with minimal oscillation, 3) minimizing ACRs which are below the optimal values to prevent the ATM network bandwidth from being under-utilized, 4) minimizing ACRs which are above the optimal values to prevent buffer resources from being consumed and possible resulting loss of cells, 5) providing for weighted max-min fairness criteria as specified in the ATM Forum Traffic Management Document version 4.0 such that, for each trunk within the network, the ACR allocated to each circuit should be in proportion to the weight assigned to each circuit, and for a circuit traversing multiple trunks, the minimum ACR value allowed by all traversed trunks should be used as the ACR value for the circuit, 6) allowing for widely varying delays among different virtual circuits (VC) to accommodate a new allowed cell rate (ACR) values which arrive at the source with a varying delay after they are generated, 7) allowing for bottlenecked trunks where some VCs become bottlenecked at other trunks, and thus do not respond to an increase in ACR signaled by a particular trunk, and 8) the steady-state of the output queue length scales with the number of virtual circuits.
Aspects of the invention provide improved algorithms for use by the available-bit-rate (ABR) service in asynchronous-transfer-mode (ATM) networks to rapidly determine the optimal values of the Allowed Cell Rate (ACR) for individual Virtual Circuits (VC) using the ABR service.
In aspects of the present invention, each ATM switch along the path of an ABR virtual circuit (VC) calculates a weighted average of a measure of congestion at the particular ATM switch. The weighted average of the measure of congestion is then used to calculate an acceptable average rate at which the switch may operate. A weighted acceptable rate is then determined for each virtual circuit and compared with a measured and/or indicated cell rate for that virtual circuit. As an option, it may be desirable to keep track of the cell rate information of each of the virtual circuits to determine which virtual circuits are bottlenecked based on responsiveness of a measured cell rate to a newly requested cell rate. When the average cell rate is updated, the cell rates of bottlenecked connections are not included in the computation of a new average cell rate. In this manner, bottlenecked circuits will not reduce the responsiveness of the algorithm. In accordance with the above determinations, explicit rate and/or single-bit congestion indications are sent back to the traffic sources utilizing one or more resource-management (RM) cells. The feedback information contained in the resource-management cells may be utilized by each traffic source to regulate its traffic flow and thereby achieve high utilization of the network.
In another aspect of the invention, an algorithm is utilized which may perform one or more of the following functions in any combination and/or subcombination: 1) estimating the direction and extent of the desired change in the total flow rate based on both current queue length and sum of exponentially weighted past and present queue growth rates; 2) using a nonlinear mapping function to map estimated change in the total flow rate to the desired change in the average rate of all VCs; and/or 3) adapting to change of network conditions quickly.
Simulation studies show that algorithms in accordance with one or mores aspects of the invention exhibits one or more of the following properties: 1) robust performance in different network configurations, load conditions, and/or traffic types; 2) fast transient response yet very stable steady-state behaviors, thus maximizing the utilization of the network resource; 3) ensures the weighted max-min fairness among all VCs, even where there are VCs bottlenecked at some other switches; 4) low implementation complexity; 5) compatibility with other ABR flow control algorithms; and/or 6) compliance with existing ATM Forum traffic management standards.
REFERENCES:
patent: 4616359 (1986-10-01), Fontenot
patent: 5179556 (1993-01-01), Turner
patent: 5280470 (1994-01-01), Buhrke et al.
patent: 5457687 (1995-10-01), Newman
patent: 5535201 (1996-07-01), Zheng
patent: 5541926 (1996-07-01), Saito et al.
patent: 5577035 (1996-11-01), Hayter et al.
patent: 5583861 (1996-12-01), Holden
patent: 5675576 (1997-10-01), Kalampoukas et al.
patent: 5694554 (1997-12-01), Kawabata et al.
patent: 5737313 (1998-04-01), Kolarov et al.
patent: 5737314 (1998-04-01), Hatono et al.
patent: 5748614 (1998-05-01), Wallmeier
patent: 5754530 (1998-05-01), Awdeh et al.
patent: 5802040 (1998-09-01), Park et al.
patent: 5805577 (1998-09-01), Jain et al.
patent: 5805599 (1998-09-01), Mishra et al.
patent: 5812527 (1998-09-01), Kline et al.
patent: 5901147 (1999-05-01), Joffe
patent: 5933425 (1999-08-01), Iwata
patent: 5959993 (1999-09-01), Varma et al.
patent: 6069872 (2000-05-01), Bonomi et al.
patent: 6072775 (2000-06-01), Ikeda
W. Melody Moh, Evaluation of ABR Congestion Control Protocols for ATM LAN and WAN, IEEE, pp. 193-196, 1996.
Chen-Khong Tham & Wee-Seng Soh, Multi-sevice Connection Admission Control using Modular Neural Networks, IEEE, pp. 1022-1029, vol.3, 1998.
Slobodan S. Petrovic, ABR Service in ATM Networks: Performance Comparison between Adaptive Stochastic and ERICA Flow Control Schemes with Guaranteed Minimum Cell Rate, IEEE, pp. 61-69, 1996.
He Linhai
Wong Albert Kai-sun
Lucent Technologies - Inc.
Marcelo Melvin
Nguyen Phuongchau Ba
LandOfFree
Available bit rate flow control algorithms for ATM networks does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Available bit rate flow control algorithms for ATM networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Available bit rate flow control algorithms for ATM networks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2485374