Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
2000-02-01
2003-12-30
Vanderpuye, Kenneth (Department: 2661)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S235100
Reexamination Certificate
active
06671258
ABSTRACT:
FIELD OF THE INVENTION
The invention generally relates to a method and system for buffering data packets at a queuing point in a digital communications device such as a network node. More particularly the invention relates to a system for achieving a fair distribution of buffer space between adaptive flows of traffic, the sources of which decrease their transmission rate in response to congestion notification, and non-adaptive flows of traffic, the sources of which do not alter their transmission rate in response to congestion notification.
BACKGROUND OF THE INVENTION
In order to effect statistical multiplexing in a store and forward digital communications device, such devices will typically queue data packets for subsequent processing or transmission in a common storage resource such as a memory buffer. At such a gateway or queuing point, the common storage resource may be shared by traffic flows associated with various classes of service, interface ports, or some other common attributes which define an aggregation of the most granular traffic flows. With traffic of such a multi-faceted nature, sophisticated communication devices need some type of congestion control system in order to ensure that the common storage resource is “fairly” allocated amongst the various traffic flows.
INTERNET ROUTERS
For example, in an Internet router, the transport level protocol may be some form of TCP (Transmission Control Protocol) or UDP (User Datagram Protocol). The datagrams or packets of such protocols are somewhat different and hence may be used to define different traffic flows. Within each of these protocols the packets may be associated with one of several possible classes or qualities of service which may further define the traffic flows at a hierarchically lower level of aggregation or higher level of granularity. (A number quality of service schemes for the Internet are currently being proposed by various standard-setting bodies and other organizations, including the Integrated Service/RSVP model, the Differentiated Services (DS) model, and Multi-Protocol Label Switching (MPLS), and the reader is referred to Xiao and Lee,
Internet QoS: A Big Picture
, Department of Computer Science, Michigan State University, <http://www.cse.msu.edu/
−
xiaoxipe/researchLink.html>, Sep. 9, 1999, for an overview of these schemes.) Still more granular traffic flows may be defined by packets which share some common attributes such as originating from a particular source and/or addressed to a particular destination, including at the most granular levels packets associated with a particular application transmitted between two end-users.
In an IP router the memory buffer at any given gateway or queuing point may be organized into a plural number of queues which may, for example, hold packets in aggregate for one of the classes of service. Alternatively, each queue may be dedicated to a more granular traffic flow. Regardless of the queuing structure, when the memory buffer becomes congested, it is often desirable to apportion its use amongst traffic flows in order to ensure the fair distribution of the buffer space. The distribution may be desired to be effected at one or more different levels of aggregation, such as memory partitionment between interface ports, and between classes of service associated with any given interface port.
One typically implemented buffer management scheme designed to minimize buffer congestion of TCP/IP flows is the Random Early Detection (RED) algorithm. Under RED, packets are randomly dropped in order to cause different traffic flow sources to reduce their transmission rates at different times. This prevents buffers from overflowing and causing packets to be dropped simultaneously from multiple sources. Such behaviour, if unchecked, leads to multiple TCP sources simultaneously lowering and then increasing their transmission rates, which can cause serious oscillations in the utilization of the network and significantly impede its performance. RED also avoids a bias against bursty traffic since, during congestion, the probability of dropping a packet for a particular flow is roughly proportional to that flow's share of the bandwidth. For further details concerning RED, see Floyd and Jacobson,
Random Early Detection Gateways for Congestion Avoidance
, 1993 IEEE/ACM Transactions on Networking.
However, it has been shown that RED does not always fairly allocate buffer space or bandwidth amongst traffic flows. This is caused by the fact that at any given time RED imposes the same loss rate on all flows, regardless of their bandwidths. Thus, RED may accidentally drop packets from the same connection, causing temporary non-uniform dropping among identical flows. In addition, RED does not fairly allocate bandwidth when a mixture of non-adaptive and adaptive flows such as UDP and TCP flows share link resources. TCP is an adaptive flow because the packet transmission rate for any given flow depends on its congestion window size which in turn varies markedly with packet loss (as identified by non-receipt of a corresponding acknowledgement within a predetermined time-out period). UDP flows are non-adaptive because their packet transmission rates are independent of loss rate. Thus, unless UDP sources are controlled through a fair discard mechanism, they compete unfairly with TCP sources for buffer space and bandwidth. See more particularly Lin and Morris,
Dynamics of Random Early Detection
, Proceedings of SIGCOMM'97.
A variant of the RED algorithm that has been proposed to overcome these problems is the Flow Random Early Drop (FRED) algorithm introduced by Lin and Morris, supra. However, one drawback of FRED is the large number of state variables that needs to be maintained for providing isolation between adaptive and non-adaptive flows. This can prove problematic for high capacity, high speed, routers, and better solutions are sought.
ATM Switch
In an asynchronous transfer mode (ATM) communication system, the most granular traffic flow (from the ATM perspective) is a virtual connection (VC) which may belong to one of a number of different types of quality of service categories. The ATM Forum Traffic Management working group has defined five (5) traffic classes or service categories, which are distinguished by the parameter sets which describe source behaviour and quality of service (QoS) guarantees. These categories include 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) service categories. The ABR and UBR service categories are intended to carry data traffic which has no specific cell loss or delay guarantees. UBR service does not specify traffic related guarantees while ABR service attempts to provide a minimum useable bandwidth, designated as a minimum cell rate (MCR). The ATM Forum Traffic Management working group and International Telecommunications Union (ITU) have also proposed a new service category, referred to as guaranteed frame rate (GFR). GFR is intended to provide service similar to UBR but with a guaranteed minimum useable bandwidth at the frame or AAL packet level, which is mapped to the cell level by an MCR guarantee.
In an ATM device such as a network switch the memory buffer at any given queuing point may be organized into a plural number of queues which may hold data packets in aggregate for VCs associated with one of the service categories. Alternatively, each queue may be dedicated to a particular VC. Regardless of the queuing structure, each VC can be considered as a traffic flow and groups of VCs, spanning one or more queues, can also be considered as a traffic flow defined at a hierarchically higher level of aggregation or lower level of granularity. For instance, a group of VCs associated with a particular service class or input/output port may define a traffic flow. When the memory buffer becomes congested, it may be desirable to apportion its use amongst service categories, and amongst various traffic flows thereof at vario
Alcatel Canada Inc.
Blake Cassels & Graydon LLP
Vanderpuye Kenneth
LandOfFree
Dynamic buffering system having integrated random early... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dynamic buffering system having integrated random early..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic buffering system having integrated random early... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3108155