Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1997-12-10
2001-02-06
Kizou, Hassan (Department: 2738)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S231000, C370S235000, C370S253000
Reexamination Certificate
active
06185187
ABSTRACT:
RELATED APPLICATIONS
The present application is based upon a provisional application filed Dec. 11, 1996 by the assignee hereof, which is included herein by reference. patent application entitled “ATM NETWORK AVAILABLE BIT RATE (ABR) FLOW CONTROL SYSTEM”, Attorney Docket RA9-96-049, filed on, assigned to the assignee of the present application and included herein by reference.
FIELD OF THE INVENTION
The present invention relates generally to data communications networks and more particularly to a flow control system for regulating the flow of information within a network.
BACKGROUND OF THE INVENTION
Asynchronous Transfer Mode (ATM) networks are expected to provide support for heterogeneous traffic classes having diverse quality of service (QoS) requirements. To that end, four classes of traffic have been defined based on the QoS desired by a session. The four classes, in decreasing order of priority are set forth below.
A Constant Bit Rate (CBR) traffic class has stringent requirements for both loss and delay. Typically, a peak rate reservation is made along the path for a given session. Applications that might use this class of service are voice and uncompressed video. A Variable Bit Rate (VBR) traffic class has slightly less stringent delay requirements. The traffic is usually “bursty”, and therefore, to improve utilization, a reservation is made which is somewhat less than the peak rate of the session. VBR traffic may be further sub-divided into real-time variable bit rate (rt-VBR) and non-real-time variable bit rate (nrt-VBR) depending on the nature of the delay guarantees required. Compressed video and multimedia email are examples of applications that may use the rt-VBR and nrt-VBR classes, respectively. An Available Bit Rate (ABR) traffic class is a “best effort” service class for applications such as file transfer and email. An amount of bandwidth termed “minimum cell rate” (MCR) is reserved for each session. Each session then gets an additional amount of bandwidth depending on availability. A session is guaranteed a very low loss provided its traffic conforms to its ACR. There are, however, no delay guarantees. An elaborate flow control mechanism is used to maximize network utilization, minimize loss and ensure that sessions share the bandwidth in a fair manner. An “unspecified bit rate” (UBR) is also a “best effort” service class. Unlike ABR, there is no flow control and there are no guarantees for loss or delay. Of the four classes of ATM network traffic control presented above, the present disclosure is focused upon the rate based flow control methodologies used for the ABR traffic class.
Efficient informational flow control has been an important consideration in the research and design of high speed communications networks. The ATM Forum has recently standardized rate-based flow control for best effort traffic in asynchronous transfer mode (ATM) networks. Flow control processing varies a sender's allowable rate of information transfer in response to feedback from the network. The simplest switches provide only binary feedback; i.e. “congested” or “not congested”. The ATM forum has standardized two methodologies, namely explicit forward congestion information (EFCI) and relative rate (RR) marking. In a network with EFCI switches, if the feedback received indicates that the network is not congested, the session's source increases its allowable cell rate (ACR); otherwise the ACR is reduced. In a network with RR marking switches, an additional form of feedback is possible where the source simply maintains its ACR.
Typically the sending rate of a session during which information is being transferred will oscillate around a desired operating point. Using such a scheme, a session traveling many “hops” (node-to-node transfers) will be asked to reduce its ACR if any one of the nodes along its path is congested. It is therefore at a disadvantage with respect to sessions traversing a single hop (or fewer hops). Serious fairness problems result, where long haul sessions are “starved”. This well known problem is commonly referred to as “beat down”. One solution to the beat down problem is to use “explicit rate” (ER) methodologies where switches are more intelligent, and can compute an estimate of the allowable rate for each session. These switches are considerably more complex to implement, even more so when targeted for high speed operation. An alternative solution to this problem is for switches to use intelligent marking where the switch selectively indicates congestion to only those sessions having a high level of activity.
In the past, practitioners have suggested the use of increase and decrease algorithms, such as an additive increase and a multiplicative decrease, for congestion avoidance. However, most of these proposals suffer from the above noted “beat down” problem. As a result, simple increase and decrease algorithms such as EFCI and RR marking result in an unfair allocation of bandwidth since the sessions traversing more hops get “beaten down”.
Others have proposed the use of selective binary feedback as a solution to the beat down problem. In such schemes, routers perform measurements and calculations to compute a “max-min” fair share for each session passing through it. The router will then set the congestion indicator for only those sessions using more than the computed fair share. However, some proposed schemes are targeted for router-based connectionless networks and do not specifically address ATM networks. Moreover, prior art schemes require the maintaining of per-session information and to perform an iterative calculation to estimate the fair share for each session. Also, such schemes require that the bandwidth demand for each session be estimated by measuring the resources consumed by the session at the router. This technique is relatively complicated and is also difficult to implement.
In another prior art scheme, an intelligent switch maintains a value representative of the mean allowable rate for a session. If the switch is congested, the congestion indicator (CI) bit is set in the resource management (RM) cells of those sessions whose ACR is bigger than this value. That technique requires constant modification of the mean allowable cell rate using the CCR value in the RM cell and some other parameters for manipulating the rate when the switch is congested. This technique is also quite complicated and difficult to implement.
In still another proposed solution, a lower priority is given to sessions entering the network at a given switch, and higher priority is given to sessions that are “transiting” through that switch. However, that technique may not be compliant with standardized procedures that require that all conforming traffic be treated with the same priority at a switch. Further, the above technique relates more to throughput than it does to “fairness”. The scheme assumes a wide area network (WAN) environment where the network is overloaded so that losses occur. In a local area network (LAN) scenario running ABR, that assumption is not necessarily true.
Thus there is a need for an intelligent marking scheme for RR marking switches which is easy to implement and which provides a more effective control methodology for information flow within networks.
SUMMARY OF THE INVENTION
A data transfer flow control system for a communications network includes a plurality of nodes interconnected by transmission links. Buffers located at the switches are arranged to store information segments or data cells of data transfer sessions. Resource management cells are also transmitted along with data cells in the information transfer sessions. The resource management cells have fields which contain information useful in managing information transfer rates along the network. As the amount of session traffic at any node increases, the level of occupancy of the buffers for that node correspondingly increases. At every network node, a “fair share” cell rate is determined for each output transmission link using the cell rate capacity of the link and the numbe
Ghanwani Anoop
Marin Gerald Arnold
Vu Ken Van
International Business Machines - Corporation
Kizou Hassan
Slavitt Mitchell
Wilder Robert V.
Woods Gerald R.
LandOfFree
Method and apparatus for relative rate marking switches 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 relative rate marking switches, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for relative rate marking switches will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2602953