Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-04-14
2003-04-29
Olms, Douglas (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S234000
Reexamination Certificate
active
06556578
ABSTRACT:
TECHNICAL FIELD
This invention is related to a method and system for managing data packet queuing in a network gateway environment. More particularly, this invention relates to a method and system that determines both when a packet must be dropped and what packet to drop and which also provides fair queuing link scheduling and hierarchical link sharing.
BACKGROUND OF THE INVENTION
An important aspect of a data network is management of gateway buffers. For large networks, such as the Internet, a typical gateway buffer will process many data flows, each of which must be buffered in some manner. In practice, the volume of each flow varies and each flow is often “greedy”, seeking to use more of the total buffer space than would be permitted under a fair share allocation. Gateway queuing policies therefore strive to balance maximum throughput with fair allocation of resources.
A common data transmission protocol is Transmission Control Protocol, (“TCP”). TCP, the most common data transport layer protocol used on local area networks and the Internet, is an adaptive protocol that seeks to adjust the data transport rate to the available link bandwidth. A TCP connection is a “closed loop” flow whose behavior depends on feedback from the network. This feedback comes in the form of acknowledgments (“ACKs”) from the destination site corresponding to successfully delivered data packets. When the network is congested, packets are dropped and corresponding ACKs are not returned. When TCP detects that a packet has been dropped, it reduces its data throughput. Thus TCP throughput is sensitive to packet dropping policies at congestion points in the network.
Packet dropping policies drop packets to manage buffer overload conditions and to signal a TCP flow to reduce its data throughput. Conventional packet dropping policies make a determination about one of either (a) when to drop a packet, in which case the packet to be dropped is fixed, or (b) which packet to drop, in which case when to drop is fixed. Conventional policies and can be classified according to which of the decisions are not fixed.
Known packet dropping policies, such as Early Random Drop (“ERD”), Random Early Detection (“RED”), and Flow Random Early Drop (“FRED”), determine when a packet drop is required based on the global state of the server or the local states of the individual data flows. Then, once the decision to drop a packet is made, the next incoming packet is dropped. In other words, the “what to drop” dimension is fixed. Both ERD and RED examine the global state of the server and drop a packet when the occupancy exceeds a given threshold. In ERD, incoming packets are dropped With a predetermined probability when the instantaneous buffer occupancy exceeds a minimum threshold. In RED, packets are always dropped when the global average queue length exceeds a maximum threshold and are dropped with a probability which is a function of the average queue length when the global average queue length is between a minimum threshold value and the maximum threshold. FRED operates similarly to RED, except that the state of each queue is examined. If an arriving packet's flow queue is greater than a global maximum threshold value, then the packet is dropped. If the queue length is between a minimum and the maximum thresholds, the packed is dropped with a given probability.
A primary drawback to these types of packet drop policies is that the policy is not fair to data flows with input rates that are smaller than their fair output share. This is because all of the data flows experience the same loss rate and, as a result, a flow that uses much less than its fair share still experiences dropped packets. This in turn prevents a low bandwidth adaptive flow, such as TCP, from claiming its fair share of the buffer resources and link bandwidth. In addition, the presence of a non-adaptive flow in the buffer can cause excessive packet drops from all of the flows. If a non-adaptive flow is aggressive in its use of buffer resources, the packet drops will cause the adaptive flows to reduce their bandwidth, thus preventing the adaptive flows from achieving their fair share of resources, even if the congestion is not severe. Furthermore, while FRED addresses some deficiencies of using the global state to make the when-to-drop decision, it may also be unfairly limiting, since no queue is allowed to have a length exceeding the global maximum threshold, even if no other queues are backlogged and thus, excess buffer capacity is available. In addition, neither RED, FRED, nor ERD contemplate managing flows which are assigned different shares of the server's resources.
Other packet drop algorithms such as Longest Queue Drop (“LQD”) and Approximated Longest Queue Drop (ALQD) drop a packet when the buffer is full. Thus, the “when to drop” dimension for these algorithms is fixed. The “what to drop” decision is based on the state of the per-flow queues. For example, when the buffer is full, LQD drops a packet from the largest queue. However, algorithms of this type also hinder adaptive flows from reaching their fair share of the link bandwidth. LQD in particular slows down the rate-adjustment of adaptive flows to changes in their allocated fair share due to changing load and the arrival and departure of bursts of competing traffic. LQD also produces large variations in the “short” term throughput of an adaptive flow, reducing the overall throughput.
Accordingly, it would be advantageous to provide a packet drop algorithm which solves these problems, provides an early signaling mechanism for adaptive flows, so that they can adjust their rates before more drastic cuts are needed, and fairly drops packets from flows exceeding a hierarchically assigned share of the server's resources, thus avoiding consecutive drops from the same flow and causing a “smoothing” out of the reductions in the rates of adaptive flows over all of the flows which seek to use more than their respective fair share.
SUMMARY OF THE INVENTION
According to the present invention, a method for managing a buffer pool is presented which considers both when a packet should be dropped and which packet should be dropped. The buffer receives data packets from two or more data flows and buffers these packets in a plurality of queues. On a recurring basis, such as the arrival and departure of packets from the buffer, the global average queue occupancy of the queues is determined. A packet-drop indication is provided when the global average exceeds a predetermined maximum threshold. When a packet is to be dropped, each of the queues is then evaluated to locate “offending” queues which are using more than a predetermined amount of the available global queue resources, i.e., those queues which are using more than a determined fair share of the global resources. One of the offender queues is then selected and a packet is dropped from the selected offender queue.
In a preferred embodiment, the global average queue occupancy is determined using an exponential weighted moving average filter. A packet drop indication is also preferably made on a probabilistic basis when the global average queue occupancy exceeds a predetermined minimum threshold but does not exceed the maximum threshold.
The buffer management method of the present invention can be used in combination with any type of link scheduler as part of a network gateway to increase system efficiency. Experimentally, the best performance increase relative to conventional buffer management techniques has been found to occur when early fair drop buffer management is used in connection with a per-flow fair link scheduling algorithm, such as WF, or a hierarchical link scheduling algorithm, such as WF
2
Q+.
REFERENCES:
patent: 6097698 (2000-08-01), Yang et al.
patent: 6141323 (2000-10-01), Rusu et al.
patent: 6181706 (2001-01-01), Anderson et al.
patent: 6215769 (2001-04-01), Ghani et al.
patent: 6219728 (2001-04-01), Yin
S. Floyd and V. Jacobson, “Random Early Detection Gateways for Congestion Avoidance”,IEEE/ACM Transactions on Netwo
Bruno John
Ozden Banu
Saran Huzur
Silberschatz Abraham
Darby & Darby PC
Lucent Technologies - Inc.
Nguyen Brian
Olms Douglas
LandOfFree
Early fair drop buffer management method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Early fair drop buffer management method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Early fair drop buffer management method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3075646