Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1998-08-19
2001-12-25
Ngo, Ricky (Department: 2664)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S249000, C370S252000, C370S412000
Reexamination Certificate
active
06333917
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to congestion control and avoidance in a communications network and, more particularly, to avoiding and controlling congestion in a packet network, such as an asynchronous transfer mode (ATM) network, using a random early detection (RED) strategy. Although the context of this discussion is that of ATM networks, it should be appreciated that the invention has a much broader potential application, and may, for example, be used in all packet networks, including IP. The prior art teaches several ways of avoiding and controlling congestion in a communications network. Two such strategies, known as partial packet discard (PPD) and early packet discard (EPD), help improve throughput during congestion, but the improvement is only partial and can be oscillatory in nature.
In many cases, transport-layer protocols such as TCP still suffer enough loss to temporarily shut down. In the scenarios where packets from many connections are discarded, the sources will all react to congestion and slow down in a synchronous manner. As a result, depending on the size of the buffer and network parameters, a sufficient amount of time may pass such that the buffer completely drains, thereby causing underutilization of the link until the sources increase their transmission rates again. ATM Available Bit Rate (ABR) service, a third approach to congestion avoidance, is effective but requires special source and destination hardware.
Random early detection is yet another strategy for congestion avoidance and control. In short, it provides congestion avoidance by controlling the average queue size. Advantageously, RED causes packet loss in a more distributed fashion than alternative strategies, and does not require specialized hardware—it finctions with existing TCP protocols and hardware. Rather than waiting until the buffer is full or essentially full, RED tries to anticipate the congestion and, as the queue grows, begins signaling congestion by marking or discarding packets, but only periodically. In response to each packet marked or discarded, one source at most will react and slow down, resulting in a reduction in total quantity of traffic transmitted to the switch. If the amount of reduction is insufficient, RED will react by increasing the rate or frequency of packets discarded. If the reduction was sufficient to ease the congestion, RED will reduce the frequency of discard.
S. Floyd and V. Jacobson describe the basic RED algorithm in their paper titled “
Random Early Detection Gatewaysfor Congestion Avoidance
,” IEEE/ACM Transactions on Networking, vol. 1, no. 4, pp. 397-413, August 1993.
FIG. 1
shows such a RED system indicated generally by reference numeral
10
. The RED system controls average queue size by utilizing filter
12
to compute an average queue occupancy based on the instantaneous queue occupancy. When a packet arrives, the filter updates the average occupancy, which the algorithm uses to determine whether to mark the incoming packet. Marking can be accomplished explicitly (e.g., indicating congestion by tagging ATM cells using the Explicit Forward Congestion Indication (EFCI) field) or implicitly (e.g., discarding packets, to which a source protocol such as TCP reacts by slowing down its transmission rate). The algorithm compares the average queue size to a minimum threshold, min
th
, and maximum threshold, max
th
(
14
). If the average queue size exceeds the maximum threshold, all arriving packets are marked. Packets are not marked so long as the average queue size remains below the minimum threshold. When the average queue size is between the thresholds, each arriving packet is marked with a per-packet marking probability P
a
, which weights the random decision of whether or not to mark the packet. To compute the final per-packet marking probability p
a
, the algorithm first determines an intermediate packet marking probability p
b
by comparing average queue size to the minimum threshold and maximum threshold (
14
). As the average queue size varies from min
th
to max
th
, the intermediate packet marking probability p
b
varies linearly from 0 to the maximum probability, max
p
. The algorithm then computes the final packet marking probability p
a
(
16
) as a function of the intermediate probability p
b
and a count of the number of packets received since the last marked packet. The final packet marking probability increases slowly as the count increases since the last marked packet.
RED's intermittent discards can be preferable to bursty discards caused by EPD or Cell Loss Priority (CLP) thresholds because the latter, which typically affects more than one source at nearly the same time, can result in synchronization of sources. This situation creates an unnecessarily large reduction in the offered load and, therefore, the queue fill. For reasonably sized queues, this can result in queue depletion, which in turn leads to underutilization of the link and less bandwidth for the sources. Further, multiple packet losses from a single source may cause the source to timeout, which causes a significant transient disruption to the fairness of the bandwidth received by each source, and may also cause the source to unnecessarily retransmit some packets.
While known implementations of RED possess certain advantages over other known strategies, it nevertheless suffers from several disadvantages. First, it uses a simple linear finction for translating the amount of control into a discard probability, despite studies that show the relation between source bandwidth and RED discard rate to be decidedly non-linear. Next, current implementations of RED rely on a discard probability that entails a random decision to discard. Basic RED also fails to employ per-connection information, and, as a result, discards may be inconsistent and lack uniformity. Additionally, RED may be prone to biases in the system response caused by connections having different attributes. Still further, basic RED specifies only a queue operating range and not a single queue operating point. Lastly, RED is currently applied only on enqueue, i.e., as packets arrive at the gateway. In certain situations, this can lead to an increase in the time it takes to instruct a source to slow down.
It is, therefore, desirable to provide an enhanced random early detection scheme which addresses each of the aforementioned deficiencies present in current RED implementations. Each of the enhancements associated with the present invention translates into improved performance and reduced buffer requirements. It is even more desirable to provide an improved random early detection strategy for congestion control and avoidance in a network by applying the RED process on dequeue of packets from the gateway and accelerating RED decisions across the queue or link. Further, it is desirable to improve the RED process by linearizing the system response and removing variation in the system response caused by randomness, and to provide a custom finction for linearizing the system. Still further, it is desirable to improve the RED process by specifying a discard rate rather than a discard probability, and to provide specific measures for selecting which connection packets are to be discarded. It is also desirable to introduce a per-connection weight parameter to allow customization of the treatment given each connection and to introduce a control algorithm into the RED process which permits the specification of a single queue operating point.
SUMMARY OF THE INVENTION
A method, consistent with the present invention, is for use in controlling congestion in a network, the network including a switch having a queue for receiving packets transmitted over the network from a plurality of source connections. The method comprises the steps of determining whether to mark a packet as an indication of congestion based on fill of the queue, and marking the packet as the packet leaves the queue.
Another method, consistent with the present invention, is for use in controlling congestion in a network, the ne
Lyon Norman A.
Morris Todd D.
Finnegan Henderson Farabow Garrett & Dunner L.L.P.
Ngo Ricky
Nortel Networks Limited
Tran Phuc
LandOfFree
Method and apparatus for red (random early detection) and... 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 red (random early detection) and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for red (random early detection) and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2582414