Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1998-05-13
2003-07-22
Ton, Dang (Department: 2666)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S395430
Reexamination Certificate
active
06597662
ABSTRACT:
I. BACKGROUND OF THE INVENTION
A. Field of the Invention
The present invention relates generally to digital networks, and in particular to apparatus and methods for optimizing max-min fair rate control in available bit rate (ABR) service in an asynchronous transfer mode (ATM) network.
B. Description of the Prior Art
FIG. 1
is a block diagram showing a prior art network architecture. Data is transferred between user
116
and user
118
according to a particular network protocol. The ATM protocol is commonly used for transferring data over a network.
FIG. 1
shows a representative path over which data may travel when transferred from user
116
to user
118
: over ATM network
110
, switch
114
, ATM network
120
, switch
122
, and ATM network
112
.
In the ATM protocol, data is divided and placed into ATM cells.
FIG. 2
is a block diagram showing the format of an ATM cell. The cell is comprised of the following fields: general flow control (GFC), virtual path identifier (VPI), virtual channel identifier (VCI), payload type identifier (PTI), cell loss priority (CLP), head error control (HEC), and the cell payload. The fields are well understood in the art, and will not be discussed in detail here.
Each cell carries a portion of the data being transferred. Even though the data is split into units, to each user the data appears to be transferred as a single unit. This is called a virtual circuit. A session is the period during which there is active communication between endpoints, such as user
116
and user
118
, on the network.
At any time, one or more sessions may be transferring cells across the network. Each session has unique characteristics. For example, real time applications, such as video and voice, require data to be transferred between sender and destination in a timely manner. Other data is not as time sensitive, and can therefore be transferred with less concern for timeliness.
ATM Service Categories
The ATM protocol recognizes that each session has certain requirements, and not all sessions have the same requirements. Therefore, different service categories are supported, including constant bit rate (CBR), variable bit rate (VBR), available bit rate (ABR), and unspecified bit rate (UBR). Each service category is designed to address the requirements of different types of sessions.
CBR and VBR services guarantee certain performance levels when transferring data. In contrast, ABR service does not provide the same level of guarantees as CBR and VBR, but attempts to provide best effort data services by using the bandwidth left over by CBR and VBR. The bandwidth for ABR, therefore, depends on the network bandwidth used by ongoing CBR and VBR sessions. Rates of ABR sessions are adjusted in response to the varying available bandwidth. ABR service is best suited for carrying network traffic that is not sensitive to delay and can tolerate varying rates during a session.
ABR Rate-based Feedback
To adjust ABR sessions in response to changing CBR and VBR demands, a rate-based feedback system is used. Each switch and the destination monitors network flow and provides network rate feedback information to the sender using resource management (RM) cells.
FIG. 3
is a block diagram showing an ATM cell carrying an RM cell in the payload. The RM cell is located in octets
1
-
48
of the payload, and is comprised of the following fields: protocol ID (ID), data flow direction (DIR), backward explicit rate congestion notification (BN), congestion indication (CI), no increase (NI), explicit rate (ER), current cell rate (CCR), minimum cell rate (MCR), and cyclic redundancy check for the RM cell (CRC-
10
).
The ER field comprises congestion information. Each switch reviews the ER field of the RM cell, and alters it if certain criteria are met. The RM cell returns to the sender, which adjusts its output rate based on the RM cell. In this way, the sender output rate is adjusted to account for congestion in the network as reflected in the ER field of the RM cell.
ABR Session
Generally, an ABR session begins by the sender making an ABR call setup request. Call setup establishes parameters for the ABR session, some of which control the rate at which the sender transmits data. The rate at which an ABR sender is allowed to send cells for transmission is the allowed cell rate (ACR). ACR is initially set by the sender to an initial cell rate (ICR). ACR is always maintained between the minimum cell rate (MCR) (
FIG. 3
, octets
12
and
13
) and the peak cell rate (PCR). The sender places ACR in the current cell rate (CCR) field (
FIG. 3
, octets
10
and
11
) of the RM cell, and the rate at which it wishes to transmit cells, usually the PCR, in the explicit rate (ER) field (
FIG. 3
, octets
8
and
9
).
After call setup, the sender begins transmitting data, and also sends out an initial RM cell. The RM cell is transmitted to the destination (or a virtual destination), and is returned to the sender. During its travel, the RM cell may be modified by switches in the network or by the destination. If any switch encountered along the way or the destination cannot support the rate indicated by the ER field, the value of the ER field is lowered to the level the switch or destination can support. When an RM cell reaches the destination, the destination turns the cell around for transfer back to the sender. The sender then adjusts its output transmission rate based on the ER field of the returned RM cell.
The general rule is that a switch should not increase the specified ER since information from switches previously encountered by the RM cell would then be lost. Forward RM cells can be modified by any switch on the forward path. Backward RM cells are generated on backward path and modified by switches on the backward path. ER is only modified for connections that are a bottleneck if the explicit rate of the switch is less than that carried in the ER field. Also, modification of the ER field only occurs on either their forward or backward journeys, but not on both.
In addition to RM cells generated by the sender, the destination and switches in the return transmission path may optionally generate a controlled number of RM cells. Each RM cell continues to travel through the network, ultimately returning to the sender. The sender, therefore, is constantly updating its output rate based on the incoming RM cells.
In summary, a sender receives an RM cell and adjusts its ACR depending on the ER field of the RM cell. Thus, the network dynamically adjusts flow rates of the ongoing sessions in the network.
Some sessions, however, receive more available bandwidth than others. “Fairness” is the measure of how the available bandwidth is distributed. There are many different definitions of fairness, but in most of the cases fairness is defined as proportional or additive to the MCR.
Prior art fairness algorithms distribute ACR among contending ABR connections under the assumption that MCR is zero. These techniques, however, fail to address the nonzero MCR case. That is, even though the sender is allowed to advertise a nonzero MCR, the prior art has not been proven to actually converge to a proper result under realistic assumptions (e.g., changing network loads).
It is desirable, therefore, to provide a method and system for providing fairness among contending ABR sessions.
II. SUMMARY OF THE INVENTION
The present invention satisfies this and other desires by providing fairness among contending ABR sessions. More particularly, the present invention determines congestion feedback information based on per port congestion analysis to provide convergence and simplicity of implementation.
An apparatus consistent with the present invention, for use in a network with rate-based feedback congestion control, comprises a device for counting cells that pass through a particular port to determine a count; a device for receiving available capacity information associated with the cells; and a device for developing a congestion control parameter based on the count and available capacity information.
A method consistent with the
Abraham Santosh P.
Bernstein Greg M.
Chhabra Gurpreet S.
Gullicksen Jeffrey T.
Kumar Anurag
Finnegan Henderson Farabow Garrett & Dunner L.L.P.
Nortel Networks Limited
Ton Dang
LandOfFree
Apparatus and method for optimizing max-min fair rate... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for optimizing max-min fair rate..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for optimizing max-min fair rate... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3050494