Electrical computers and digital processing systems: multicomput – Computer-to-computer protocol implementing – Computer-to-computer data transfer regulating
Reexamination Certificate
1999-08-11
2004-01-06
Jean, Frantz B. (Department: 2155)
Electrical computers and digital processing systems: multicomput
Computer-to-computer protocol implementing
Computer-to-computer data transfer regulating
C709S233000, C709S234000, C709S235000
Reexamination Certificate
active
06675220
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to managing a queue of packets to avoid congestion. More specifically, the invention relates to improved techniques for implementing in hardware Random Early Detection (RED) mechanisms.
Random Early Detection (RED) was originally conceived as a congestion avoidance mechanism to be embedded in Internet routers. The basic principle behind RED is to control the average length of a router output queue in order to avoid long term congestion. For each incoming packet, the average queue length is calculated. If the average queue length is below a predefined minimum threshold, the packet is accepted and stored in the output queue for transmission.
If the average queue size is above the minimum threshold but below a predefined maximum threshold, a probability is computed and the packet gets dropped (or marked) according to this probability. The probability is proportional to the average queue size so the larger the queue size, the higher is the probability for an incoming packet to get dropped. Finally, if the average queue size is above the maximum threshold, all incoming packets are dropped until the average queue size falls again below the maximum threshold. More details on RED may be found in “Random Early Detection Gateways for Congestion Avoidance,” Sally Floyd et al., IEEE/ACM Transactions on Networking, August 1993, which is hereby incorporated by reference.
Depending on the particular transport layer protocol used, when packet drops are detected, the sources can take appropriate countermeasures such as, for instance, backing off their transmission rates in order to reduce the traffic volume at the congested router. For example, if the transport protocol exploited is the Transmission Control Protocol (TCP), the loss of a packet is interpreted as a congestion indication and the TCP sources immediately reduce their transmission rates. Discarding packets is also a useful means to control the average queue size when non-reactive transport protocols such as User Datagram Protocol (UDP) are utilized. If packets are not dropped but instead are marked, it is the responsibility of the transport protocol to take the appropriate counter measures when it detects packets that have been marked by RED.
There are a number of advantages in using RED. The stochastic nature of RED guarantees that the number of dropped packets for a connection is proportional to the bandwidth currently being used by the connection. Also, global synchronization phenomena among different TCP sources do not occur because RED routers drop packets individually rather than in bursts as tail drop routers do. Moreover, by keeping the average queue size low, RED is able to reduce the average end-to-end delay while allowing occasional traffic bursts to find enough room to be accommodated within queues without significant losses.
However, there are a number of disadvantages with conventional implementations of RED. Firstly, the probability of dropping packets RED relies upon should ensure that the distribution of dropped packets is relatively uniform. However, in most RED in hardware implementations based on simplifications of the conventional scheme it is very likely for the distribution of packet drops to be highly non-uniform (e.g., multiple packets are dropped in a row). Additionally, packets can be dropped even after the current queue size has fallen below the minimum threshold because the average queue size is still above the minimum threshold. Finally, conventional implementations of RED are not very suitable for a hardware implementation because they are based on computations that involve a number of noninteger multiplications and divisions and also exploit an exponential function.
It would be beneficial to have improved techniques for queue management schemes such as RED. It would also be beneficial to have techniques for improving the distribution of dropped packets and preventing packets from being dropped when the current queue size is below the minimum threshold. Additionally, it would be beneficial to have techniques for easily implementing RED hardware, in order to exploit this mechanism in high speed devices such as a local area network (LAN) switch.
SUMMARY OF THE INVENTION
The present invention provides techniques for managing queues of packets, such as in RED. When the size (average or otherwise) of the queue is greater than a minimum threshold, packets are dropped according to a probability. Once a packet is dropped, the minimum threshold is increased so that it is unlikely that subsequent packets will be dropped, unless the size of the queue is greater than a maximum threshold. As packets are received without being dropped, the minimum threshold is decreased until it reaches its original value. Thus, the distribution of dropped packets is more uniform. Some specific embodiments of the invention are described below.
In one embodiment, the invention provides a method of managing a queue of packets. A packet is received and the average queue size is calculated. If the average queue size is above a minimum threshold, the packet is dropped according to a probability and if the packet is dropped, the minimum threshold is increased. In a preferred embodiment, if the average queue size is greater than a maximum threshold, the probability is 1 so the packet is dropped with complete certainty.
In another embodiment, the invention provides a method of managing a queue of packets including receiving a packet. The average queue size is calculated and the current queue size is determined. Then, a comparison queue size is calculated as the lesser of the average queue size and the current queue size. The comparison queue size is utilized to determine whether to drop the packet, such as in RED. In a preferred embodiment, the average queue size is calculated at specified time intervals.
In another embodiment the invention provides a method of managing a queue of packets including receiving a packet. A random number is generated and a bit-mask is utilized to mask the random number. If the sum of a queue size and the masked random number is greater than a maximum threshold, the packet is dropped and the mask is reset. When a specified number of packets is received without dropping a packet, the mask is shifted to increase the potential size of the masked random number. In a preferred embodiment, the queue size is a lesser of an average queue size and the current queue size.
REFERENCES:
patent: 5231633 (1993-07-01), Hluchyj et al.
patent: 5936958 (1999-08-01), Soumiya et al.
patent: 5974518 (1999-10-01), Nogradi
patent: 6167445 (2000-12-01), Gai et al.
patent: 6252848 (2001-06-01), Skirmont
patent: 6333917 (2001-12-01), Lyon et al.
Jacobsen et al., “RED in a different light” Jun. 1, 1999.*
Jacobson et al., “RED in a Different Light,” Jun. 1, 1999.
Lin et al., “Dynamics of Random Early Detection,” Sep., 1997, ACM SIGCOMM'97 Conference, Palais de Festivals, Cannes, France.
Floyd et al., “Random Early Detection Gateways for Congestion Avoidance,” Aug. 1993, IEEE/ACM Transactions on Networking.
Bergamasco Davide
Edsall Thomas J.
McCloghrie Keith
Morandin Guglielmo M.
Cisco Technology Inc.
Jean Frantz B.
Ritler, Lang & Kaplan LLP
LandOfFree
Techniques for the hardware implementation of 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 Techniques for the hardware implementation of random early..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Techniques for the hardware implementation of random early... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3260428