Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1999-05-27
2003-07-01
Chin, Wellington (Department: 2664)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S235000, C370S231000, C370S236000
Reexamination Certificate
active
06587437
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of data communications networks and more particularly, to a method and apparatus for source to destination flow control by means of accelerated feedback of network congestion information.
BACKGROUND OF THE INVENTION
The emergence of the Asynchronous Transfer Mode (ATM) networking protocol is intended as a response to the demand for faster data communications and more sophisticated processing. The ATM protocol relates to a cell based switching and multiplexing technology that is designed to be a general purpose transfer mode for a wide range of traffic services. Communications networks now serve a range of new applications involving mixed media traffic comprising data, voice, still and moving images and video. The aim of the ATM networking protocol is to provide a more flexible facility for the transmission of such traffic and for the allocation of transmission bandwidth in order to efficiently utilize network resources.
The ATM networking protocol is advantageous in that it provides network administrators and end users with multiple classes of communications service. The ATM Forum Traffic Management Working Group has defined five service categories for cell transmission which are distinguished by parameter sets used to describe source behaviour and quality of service (QoS) guarantees. These service categories are identified as 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), all of which are set out in the
Traffic Management Specification,
Version 4.0, which was published by the ATM Forum Technical Committee under document no. af-tm-0056.000 in April 1996. An addendum to this specification entitled “Addendum to Traffic Management V4.0 for ABR parameter negotiation” was published under document no. af-tm-077.000 in January 1997.
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, as it optionally provides only a guaranteed minimum cell rate. The ABR service category provides source to destination flow control that attempts, but is not guaranteed, to achieve zero cell loss. Thus, the ABR service category offers users a relatively high quality of service in terms of cell loss probability and yet seeks to maintain high network resource utilization. Traffic management techniques such as those adopting flow control are used to protect a network and its various end-systems from congestion in order to achieve network performance and utilization objectives.
Flow control in the ABR service category is achieved by arranging for each source node of a network to send special resource management (RM) cells through the network. The RM cells are typically interleaved with data cells in the network. Each network entity or element, for instance a switch or node in the network, may indicate its congestion status by writing into the RM cell. The RM cell is then forwarded on to the next network element in the data path. At the destination network element, the RM cell is turned back towards the source. The network entities in the backward data path may mark congestion information into the RM cell, which is ultimately received by the source may then adjust its sending rate in response to the information contained in the received RM cell.
The RM cell typically contains three fields which may be written to in order to describe the congestion status of a network entity. First, the cell provides a “no increase” (NI) it which indicates that the source must not increase its sending rate. Second, there is provided a congestion indication (CI) bit which indicates that the source must decrease its sending rate. Third, the RM cell contains an explicit rate (ER) field which contains the minimum explicit rate of transmission as may be calculated by any network element in the data path. The concepts of an explicit rate and of algorithms for calculating explicit rates are described in greater detail below. The behaviour of a network source in response to the information contained in these three RM fields is well-known to those skilled in this art.
Various mechanisms can be used in order to achieve flow control in a network. These mechanisms can be classified broadly depending on the congestion monitoring criteria used and the feedback mechanism employed. The feedback mechanisms are either binary in nature or calculate an explicit rate of transmission. In each case flow control information is provided to the source through the RM cell, as explained in greater detail herebelow.
In one method of binary flow control, known to those skilled in this art as Binary ABR, a particular bit in each data cell is set during network congestion. The bit in question is an indicator of forward congestion and is hence known as an Explicit Forward Congestion Indicator bit, or EFCI bit. If a data cell arrives at the network destination node with its EFCI bit set, the node will set an internal variable, known as the CI_State, to a value of 1. Otherwise, the CI_State variable within the node is set to a value of 0. When a resource management cell arrives at the same destination node, and this particular node has its CI_State variable set to a value of 1, the node will set the previously mentioned CI bit in the RM cell also to a value of 1. The RM cell will make its way along the data path to the network source node and this source node will increase its rate of transmission if the CI bit of the arriving RM cell is set to 0, but will decrease its transmission rate if the CI bit of the RM cell is set to 1.
Those skilled in this art will readily appreciate that Binary ABR is a random method of exerting flow control, in that the mechanism cannot control which particular ABR connection will receive restrictive flow control information at any particular point in time. Flow control will therefore vary depending on the instantaneous traffic flow at each contention point in the network. Generally, it is thought that the Binary ABR mechanism is more susceptible to instability in larger networks. Binary feedback schemes where all the connections may share a common FIFO queue may sometimes suffer from unfairness problems depending on the network topology and the source and destination behaviour employed. Given the same level of congestion at all of the switches along a data path, connections travelling more hops have a higher probability of having their EFCI bits set than those travelling a smaller number of hops. Depending on the source and destination behaviour employed, these long hop connections get very few opportunities to increase their rates of transmission and consequently their throughputs are starved. This gives rise to what those in this art have called a “beat down” problem. Potential unfairness problems in binary feedback schemes where all of the virtual connections share a common queue can be alleviated in some cases. For instance, one known enhancement in this regard is to provide separate queues for each virtual connection or for groups of virtual connections.
In explicit rate feedback schemes, a network node such as a switch will perform three important functions. First, the switch will compute the fair share of the network bandwidth that can be supported for a virtual connection. Second, the switch will determine its load. By way of example, this can be done either by monitoring queue lengths or queue growth rates associated with buffering incoming cells. Third, an actual explicit rate of transmission for the connection will be determined by the switch and this information will be sent to the source. Examples of explicit rate switch mechanisms known to those skilled in this art are the Enhanced Proportional Rate Control Algorithm (EPRCA) and two congestion avoidance schemes, namely Explicit Rate Indication for Congestion Avoidance (ERICA) and Congestion Avoidance using Proportional Control (CAPC).
Various explicit rate
Lee Denny L. S.
Sterne Jason T.
Alcatel Canada Inc.
Blake, Cassels and Graydon LLP
Chin Wellington
Maccione Alfred A.
Schultz William
LandOfFree
ER information acceleration in ABR traffic does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with ER information acceleration in ABR traffic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and ER information acceleration in ABR traffic will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3006442