Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1998-12-24
2002-03-19
Yao, Kwang B. (Department: 2664)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S468000
Reexamination Certificate
active
06359863
ABSTRACT:
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not Applicable
REFERENCE TO A MICROFICHE APPENDIX
Not Applicable
NOTICE OF MATERIAL SUBJECT TO COPYRIGHT PROTECTION
All of the material in this patent document is subject to copyright protection under the copyright laws of the United States and of other countries. The owner of the copyright rights has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the United States Patent and Trademark Office file or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention pertains generally to congestion control systems for communications networks, and more particularly to rate allocation in ATM switched networks.
2. Description of the Background Art
Asynchronous Transfer Mode (ATM) is a networking protocol designed to efficiently support high speed digital voice and data communications. Broadband packet networks based on ATM enable the integration of traffic with a wide range of characteristics within a single communication network. In these networks, all communication at the ATM layer is in terms of fixed-size packets, called “cells” in ATM terminology. An ATM cell consists of 48 bytes of payload and 5 bytes for the ATM-layer header. Routing of cells is accomplished through packet switches over virtual circuits set up between endpoints. By the use of proper traffic scheduling algorithms, ATM is capable of handling multiple classes of traffic ranging from real-time video to best-effort traffic requiring no quality-of-service guarantees. An industry group, the ATM Forum, has defined a family of service categories to address these classes of traffic—specifically: Constant Bit Rate (CBR) service, Variable Bit Rate (VBR) service, Unspecified Bit Rate (UBR) service and Available Bit Rate (ABR) service.
A primary motivation for development of the ABR service category was the economical support of data traffic where each packet of data is segmented into ATM cells. Such “best-effort” traffic is generally characterized as having no real-time deadlines and requiring weak guarantees on the available bandwidth, delay, or cell loss rate. This “best-effort” mode is similar in nature to the service provided by the current Internet (generally using the Transmission Control Protocol (TCP) or User Datagram Protocol (UDP)), except that connections still need to be set up at the ATM layer over virtual circuits between endpoints, either explicitly or implicitly.
ATM raises new opportunities for implementing congestion control at a lower layer, providing the potential for improving the performance of TCP even above that obtained in today's datagram networks. The higher speed and possibly better congestion control algorithms which may arise with ATM's ABR service offer promise even for protocols designed for today's datagram service. The fixed size of ATM cells simplifies the implementation of the switching function in many cases, thus enabling ATM networks to scale up to high speeds.
While a number of congestion-control approaches for best effort traffic in ATM networks have been developed, they exhibit a number of problems including, in many cases, failure to achieve fairness in the allocation of link capacity among competing data flows, complicated buffering and/or queuing schemes, and, in some cases an absence of an end-to-end perspective for the control mechanism. Additionally, most of these approaches require either prior knowledge of the network configuration in order to set correctly the appropriate parameters or cooperation between the high-level protocols and the congestion control mechanisms at the ATM-layer.
One particular congestion control method, explicit rate setting, has been chosen by the ATM Forum as the best match for the ABR service. This method controls the bandwidth allocation to the connections directly. Since each ATM cell contains the same number of bits, control of a connection's bandwidth, measured as a bit rate, is achieved by directly controlling its cell rate, hence the approach is referred to as rate-based flow control. Control of the cell rate for a connection would occur at least at the transmission source, which would shape the connection's traffic as directed by feedback from the network. Optionally, such control may occur at points within the network as well. Under a rate-based framework, the share of bandwidth allocated to a connection is not supposed to depend on the delays between points where data is shaped on a per-connection basis.
The rate-based congestion control approach has the potential to provide close-to-ideal throughput with a fraction of the buffering required by link-level flow control, especially for wide area networks. With explicit rate setting, the source of each connection periodically transmits a special resource management (RM) cell. The RM cell specifies the bandwidth requested by the connection. Each switch on the path of the RM cell may modify the request based on the bandwidth it is able to allocate to the connection on its outbound link. On reaching its destination, the RM cell, having had its bandwidth request reduced by any switch unable to allocate the requested bandwidth, is returned to the source, which will then set its rate based on that of the bottleneck link in the path of the connection.
Significantly, however, the rate-based approach requires an algorithm for fair allocation of bandwidth among the connections sharing a common output link of a switch. On receipt of an RM cell from a connection (or, in the general case, a packet containing comparable information), the algorithm is invoked to determine the current bandwidth allocation of the connection on the output link, taking into account the available bandwidth and the current allocations of other connections.
The most robust method for fair rate allocation in packet-switching networks heretofore developed is disclosed in U.S. Pat. No., 5,675,576 to Kalampoukas et al. issued on Oct. 7, 1997, which is incorporated herein by reference. The scheme developed by Kalampoukas et al. addresses rate-based congestion control while still maintaining the max-min fairness criterion. The algorithm described by Kalampoukas et al. requires only a constant number of steps on receipt of an RM cell, in its computation of a fair allocation of the bandwidth for each connection. The algorithm, however, does not support the provision of a minimum guaranteed bandwidth for the connections, but instead treats all the connections equally in distributing the available bandwidth among the set of connections sharing the output link of the switch. Yet, the ability to provide such a guaranteed rate is essential to the support of certain applications, for example, those based on voice or video. In addition, the algorithm described by Kalampoukas et al. requires as an input the total available bandwidth on the output link as a parameter. In practice, however, this parameter may vary from instant to instant and a mechanism is required to estimate it dynamically. Likewise, their method also requires as input the current rate of each connection, typically conveyed within a field in the RM cell, to perform the computations. However, in practice this rate information carried within the RM cell may not correspond to the actual rate of the connection, resulting in inaccuracies in the computations, thus leading to under-utilization or congestion at the output link. Therefore, a means of estimating this actual rate of the connection is essential to avoiding such inaccuracies. Finally, the algorithm described by Kalampoukas et al. does not provide a mechanism for recovering bandwidth from connections that remain idle for a long time, resulting in under-utilization of the bandwidth of the output link.
Therefore, there is a need for a rate-based congestion control scheme that supports a minimum guaranteed rate per connection, has means of estimating the bandwidth of each connection from its actual b
Kalampoukas Lampros
Varma Anujan
O'Banion John P.
Pham Brenda H.
The Regents of the University of California
Yao Kwang B.
LandOfFree
Rate allocation system and method for ATM switched 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 Rate allocation system and method for ATM switched networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rate allocation system and method for ATM switched networks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2860214