Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1997-06-19
2002-05-07
Nguyen, Chau (Department: 2663)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S236100
Reexamination Certificate
active
06385168
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the management of data traffic in a network having multi-data streams and more particularly to an algorithm and device for fairly allocating available bandwidth to contending connections in a data network, the allocation being based on global queue size.
BACKGROUND
The device and algorithm of the present invention will be described and illustrated with reference to the available bit rate (ABR) service category of an asynchronous transfer mode (ATM) network. It is to be understood, however, that this is only one environment in which this invention finds application.
As is known the ATM Forum Traffic Management working group has defined five service categories which are distinguished by the parameter sets which describe source behaviour and quality of service guarantees. These five service categories are; constant bit rate (CBR), real-time variable bit rate (rtVBR), non-real-time variable bit rate (nrtVBR), available bit rate (ABR) and unspecified bit rate (UBR). The ABR and UBR service categories are intended to carry data traffic which has no specific cell loss or delay guarantees. The UBR service category is the simplest of the two and may in future provide only a guaranteed minimum cell rate. The ABR service category provides source-to-destination flow control, with minimum cell rate (MCR) guarantee, that attempts but is not guaranteed to achieve zero cell loss. The ABR service category was defined in order to take advantage of available bandwidth within an ATM network during intervals when higher priority traffic was not completely utilizing the network capacity. In order to meet nominal cell loss guarantees ABR traffic employs a feedback loop which effectively monitors congestion at nodes throughout the network and periodically reports back to the source so that data traffic can be adjusted accordingly.
ABR flow control is achieved by the source sending special resource management (RM) cells through the network. Each switch in the network indicates its congestion status by optionally writing into the RM cell and forwarding the cell into the next switch in the data path. Finally, the destination turns the RM cell back towards the source and the switches in the backward data path mark congestion information into the RM cell which is ultimately received by the source. The source then adjusts its sending rate in response to the information contained in the RM cell.
The RM cell contains three fields which may be written to in order to describe the congestion status of the switch: a no increase (NI) bit which indicates that the source must not increase its sending rate; a congestion indication (CI) bit which indicates that the source must decrease its sending rate; and an explicit rate (ER) field which contains the minimum explicit rate calculated by any switch in the data path.
An explicit rate (ER) algorithm must be deployed at any contention point in the data path. For the purpose of this description a contention point is defined as a queuing point in which the aggregate arrival rate of cells is greater than the aggregate service rate. In the context of the present invention the service rate pertains to the capacity available to ABR and is in general time-dependent. A switch may have one or more contention points. An ER algorithm attempts to fairly distribute bandwidth between ABR connections at a contention point.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a device and algorithm which performs an explicit rate calculation to achieve fair allocation of bandwidth and which requires only an aggregate count of ABR cells.
Therefore, in accordance with a first aspect of the present invention there is provided a device for fairly allocating available bandwidth between contending connections at a contention point in a switch for processing multi-service traffic streams between a source and a destination comprising; queue monitoring means to continually compare the aggregate queue depth of the aggregate traffic stream at the contention point with a predefined queue depth threshold and periodically generating a function therefrom; an algorithm device for calculating the currently offered bandwidth at the contention point based on the function and the offered bandwidth of a previous calculation; calculating means to periodically generate an offered cell rate value for the contention point based on the currently offered bandwidth and a service weight assigned to the traffic stream; and feedback means to return the offered cell rate value to the source for updating the flow rate of the traffic stream therefrom.
In a preferred embodiment of the invention the device and algorithm are used in relation to the available bit rate service category in an asynchronous transfer mode communication network.
In accordance with a second aspect of the present invention there is provided a method of fairly allocating bandwidth between contending connections at a contention point in a switch for processing multi-service cell traffic streams from multiple sources, the method comprising the steps of monitoring the aggregate cell queue depth at the contention point, comparing the aggregate queue depth associated with the aggregate traffic stream at the contention point with a predefined queue depth threshold and periodically generating a function therefrom; calculating the currently offered bandwidth at the contention point based on the aforementioned function and the offered bandwidth of a previous calculation; periodically generating an offered cell rate value for the contention point based on the currently offered bandwidth and a service weight assigned to the traffic stream; and returning the offered cell rate value to the source for updating the flow rate of the traffic stream therefrom.
In accordance with a third aspect of the present invention there is provided a recursive algorithm for fairly allocating bandwidth between ABR connections at a contention point in an ATM network. The algorithm has the form:
OBW
(
k
)=
g
(
QD,T
)×
OBW
(
k
−1)
where:
OBW is the total offered bandwidth to all ABR connections;
QD is the total queue depth utilized by all ABR connections; and
T is a configurable threshold.
REFERENCES:
patent: 5313454 (1994-05-01), Bustini et al.
patent: 5594729 (1997-01-01), Kanakia et al.
patent: 5734825 (1998-03-01), Lauck et al.
patent: 5737313 (1998-04-01), Kolarov et al.
patent: 5805577 (1998-09-01), Jain et al.
patent: 5864536 (1999-01-01), Foglar
patent: 5867482 (1999-02-01), Kobayashi
patent: 5898669 (1999-04-01), Shimony et al.
patent: 5926625 (1999-07-01), Corlett et al.
patent: 5956322 (1999-09-01), Charny
patent: 5966381 (1999-10-01), Buckley et al.
patent: 6046983 (2000-04-01), Hasegawa et al.
Jangkyung Kim et al; “Fixed Queue Length (FQL) Control for ABR with Long Propagation”; ATM Forum/97-0008, Feb. 1997.
L. Kalampoukas et al; “An efficient rate allocation algorithm for ATM networks providing max-min fairness”.
Cathy Fulton et al; “UT: ABR Feedback Control with Tracking”; ATM Forum/96-1540, Nov. 10, 1996.
S. Mascolo et al; “ATM Rate Based Congestion Using a Smith Predictor: an EPRCA Implementation”. Proceedings on INFOCOM '96, vol. 2, pp 569-576.
The ATM Forum Technical Committee; Traffic Management Specification Version 4.0; Apr. 1996.
Davis Tom
Ganti Sudhakar
Lee Denny L. S.
(Marks & Clerk)
Alcatel Canada Inc.
Nguyen Chau
Trinh D.
LandOfFree
Fair share bandwidth allocation algorithm and device does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fair share bandwidth allocation algorithm and device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fair share bandwidth allocation algorithm and device will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2865004