Multiplex communications – Data flow congestion prevention or control
Reexamination Certificate
1997-09-12
2001-06-26
Patel, Ajit (Department: 2662)
Multiplex communications
Data flow congestion prevention or control
C370S232000
Reexamination Certificate
active
06252847
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to ATM networks and more specifically to a system and method for calculating a quotient-based explicit rate algorithm for ABR traffic transported through an ATM network without employing a division operation.
BACKGROUND
Asynchronous transfer mode (ATM) is rapidly becoming the technology of choice for high speed broad-band communications. The fixed length data element or cell permits the transport of multimedia data including voice and video from a network source to a network destination. The ATM Forum has defined five categories of service for ATM cell traffic including both real time and non-real time connections. The five categories of service 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 quality of service (QoS) for each service category has also been specified in order to accommodate the different traffic requirements. Obviously real time traffic cannot tolerate significant time delays through the network. On the other hand, data traffic such as electronic-mail can tolerate time delays but must ensure minimal cell loss.
Available bit rate (ABR) service category is one of the most important mechanisms for carrying bandwidth on demand traffic such as today's local area network (LAN) traffic. ABR traffic is particularly significant in that it makes optimum use of network bandwidth by dynamically adjusting its transmission rate to use the bandwidth not involved in higher priority traffic. In order to make optimum use of the bandwidth and still ensure minimal cell loss the ABR service category employs a feedback loop which monitors network congestion and returns congestion information to the data source. The congestion information is carried in resource management (RM) cells within the cell header. The resource management cells receive congestion information at each node as the ABR traffic progresses from the source to the destination. At the destination the resource management cell is returned to the source, again passing through each node where updated congestion information may be inserted. The congestion information may indicate that the source traffic should continue at its present rate or that it should be reduced in view of severe congestion. A third type of information that may be carried by the resource management cell is explicit rate (ER) information. Explicit rate information is an indication of the ABR traffic which may be transmitted from the source without increasing congestion to the point where cells may be dropped.
Explicit rate information is based on the instantaneous bandwidth available to ABR traffic, i.e. bandwidth not committed to CBR and VBR traffic, and the number of connections or contention points requiring bandwidth. It is understood that explicit rate marking provides a better network utilization performance by forcing the ABR source to transmit at a desirable rate during network congestion conditions. Not only does ER marking encourage faster rate convergence under congestion, but it provides better fairness to ABR connections competing for the same network resources, both bandwidth and buffer usage.
Many explicit rate algorithms have been identified and most of these have a common characteristic in that division is involved. The division arithmetic is employed in these algorithms to distribute bandwidth fairly amongst the competing ABR connections. To realize such an operation poses a serious challenge especially at today's ATM interface speed which operates at hundreds of megabits per second. Division is viewed as an infrequent operation by the computing design community because of the significantly greater number of processing steps than are required for addition, subtraction and multiplication. The larger number of processing steps result in greater time delays and/or system complexity.
To handle ABR flow control at an ATM interface, the ER algorithm must operate in real time to sustain the required throughput. Regrettably, it does not enjoy the luxury of using a low-latency divider as in the environment of a general purpose computer. The present invention addresses this dilemma by bypassing the division operation in quotient-based explicit rate algorithms thus achieving a high throughput without incurring the high cost and design complexity of a high speed floating point divider.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a system and a method for calculating a quotient-based explicit rate algorithm without employing a division operation.
It is a further object of the present invention to calculate the quotient-based algorithm by using a look-up table to obtain the value of the denominator.
Therefore, in accordance with a first aspect of the present invention there is provided a system for dynamically processing a quotient-based algorithm without utilizing a division operation comprising: measurement means for determining instantaneous values for the numerator and denominator of the quotient-based algorithm; a look-up table having stored values of the denominator; and multiplication means to access the look-up table for the value of the denominator and for multiplying the numerator and the value of the denominator obtained from the look-up table.
In accordance with a second aspect of the present invention there is provided a system for processing an explicit rate quotient-based algorithm for determining available bandwidth for ABR traffic at a contending connection in an ATM network transporting multi-service category ATM traffic from a source to a destination. The system comprises: calculating means for obtaining, at the contending connection, data respecting instantaneous bandwidth available for ABR cells through the network and the aggregate ABR bandwidth requirements; a look-up table for providing reciprocal values for the aggregate bandwidth requirements; and processing means to calculate the explicit rate by finding the product of the available bandwidth and the reciprocal value from the look-up table.
In accordance with a third aspect of the present invention there is provided a method of processing a quotient-based algorithm without utilizing a division operation comprising the steps of: determining the instantaneous value of the numerator and the denominator of the algorithm; obtaining a value for the denominator from a look-up table; and multiplying the numerator and the value of the denominator obtained from the look-up table to solve the algorithm.
REFERENCES:
patent: 4707798 (1987-11-01), Nakano
patent: 4823301 (1989-04-01), Knierim
patent: 5633859 (1997-05-01), Jain et al.
patent: 5754530 (1998-05-01), Awdeh et al.
patent: 5777984 (1998-07-01), Gun et al.
patent: 5812527 (1998-09-01), Kline et al.
patent: 5862059 (1999-01-01), Matula et al.
(Marks & Clerk)
Alcatel Canada Inc.
Patel Ajit
LandOfFree
Calculation of quotient-based explicit rate algorithm for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Calculation of quotient-based explicit rate algorithm for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Calculation of quotient-based explicit rate algorithm for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2458491