Techniques for the hardware implementation of random early detection mechanisms

• US 6,675,220 B1
• Filed: 08/11/1999
• Issued: 01/06/2004
• Est. Priority Date: 08/11/1999
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Bergamasco, Davide, Morandin, Guglielmo M., McCloghrie, Keith, Edsall, Thomas J.
• Primary Examiner(s): Jean, Frantz B.
• Application Number:
  US09/372,480
• Time in Patent Office: 1,609 Days
• Field of Search: 709/232, 709/234, 709/235, 709/233, 370/229, 370/336, 370/249
• US Class Current: 709/232
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames

Abstract

Techniques for managing queues of packets are provided. Once the average queue size crosses a minimum threshold, packets are dropped according to a probability. Once a packet is dropped, the minimum threshold is increased in order to decrease the likelihood that a subsequent packet will be dropped. As packets are accepted, the minimum threshold is decreased gradually to its original value so that the distribution of dropped packets is very uniform.

Claims

1. A method of managing a queue of packets, comprising:

receiving a packet;

calculating an average queue size;

if the average queue size is above a minimum threshold, dropping the packet according to a probability; and

if the packet is dropped, increasing the minimum threshold.

2. The method of claim 1, wherein if the average queue size is greater than a maximum threshold, the probability is 1 so the packet is dropped.

3. The method of claim 1, further comprising determining a class of service for the packet, where the class of service defines the minimum threshold for the packet.

4. A method of managing a queue of packets, comprising:

receiving a packet;

calculating an average queue size;

if the average queue size is above a minimum threshold, dropping the packet according to a probability; and

if the packet is dropped, increasing the minimum threshold, wherein increasing the minimum threshold includes setting the minimum threshold equal to a maximum threshold.

5. A method of managing a queue of packets, comprising:

receiving a packet;

calculating an average queue size;

if the average queue size is above a minimum threshold, dropping the packet according to a probability;

if the packet is dropped, increasing the minimum threshold; and

if a specified number of packets are received without dropping a packet, decreasing the minimum threshold.

6. The method of claim 5, wherein the minimum threshold is decreased each time the specified number of packets are received without dropping a packet.

7. The method of claim 6, wherein the minimum threshold is decreased by an amount that increases exponentially each time the specified number of packets are received without dropping a packet.

8. A method of managing a queue of packets, comprising:

receiving a packet;

calculating an average queue size;

determining a current queue size;

calculating a comparison queue size as a lesser of the average queue size and the current queue size; and

utilizing the comparison queue size to determine whether to drop the packet.

9. The method of claim 8, further comprising calculating the average queue size at specified time intervals.

10. The method of claim 8, further comprising if the comparison queue size is above a minimum threshold, dropping the packet according to a probability.

11. The method of claim 8, wherein if the average queue size is greater than a maximum threshold, the probability is 1 so the packet is dropped.

12. A method of managing a queue of packets, comprising:

receiving a packet;

calculating an average queue size;

determining a current queue size;

calculating a comparison queue size as a lesser of the average queue size and the current queue size; and

if the comparison queue size is above a minimum threshold, dropping the packet according to a probability; and

if the packet is dropped, increasing the minimum threshold.

13. The method of claim 12, further comprising calculating the average queue size at specified time intervals.

14. The method of claim 12, wherein increasing the minimum threshold includes setting the minimum threshold equal to a maximum threshold.

15. The method of claim 12, further comprising if a specified number of packets are received without dropping a packet, decreasing the minimum threshold.

16. The method of claim 15, wherein the minimum threshold is decreased each time the specified number of packets are received without dropping a packet.

17. The method of claim 16, wherein the minimum threshold is decreased by an amount that increases exponentially each time the specified number of packets are received without dropping a packet.

18. The method of claim 12, wherein if the average queue size is greater than a maximum threshold, the probability is 1 so the packet is dropped.

19. The method of claim 12, further comprising determining a class of service for the packet, where the class of service defines the minimum threshold for the packet.

20. A method of managing a queue of packets, comprising:

receiving a packet;

generating a random number;

utilizing a mask to mask the random number;

if a sum of a queue size and the masked random number is greater than a maximum threshold, dropping the packet and resetting the mask; and

when a specified number of packets are received without dropping a packet, shifting the mask to increase the potential size of the masked random number.

21. The method of claim 20, wherein the queue size is an average queue size.

22. The method of claim 20, wherein the queue size is a lesser of an average queue size and a current queue size.

23. The method of claim 20, further comprising determining a class of service for the packet, where the class of service defines at least one of the mask and the maximum threshold.

24. An apparatus that manages a queue of packets, comprising:

means for receiving a packet;

means for calculating an average queue size;

means for dropping the packet according to a probability if the average queue size is above a minimum threshold; and

means for increasing the minimum threshold if the packet is dropped.

25. An apparatus that manages a queue of packets, comprising:

means for receiving a packet;

means for calculating an average queue size;

means for determining a current queue size;

means for calculating a comparison queue size as a lesser of the average queue size and the current queue size; and

means for utilizing the comparison queue size to determine whether to drop the packet.

26. An apparatus that manages a queue of packets, comprising:

means for receiving a packet;

means for calculating an average queue size;

means for determining a current queue size;

means for calculating a comparison queue size as a lesser of the average queue size and the current queue size; and

means for dropping the packet according to a probability if the comparison queue size is above a minimum threshold; and

means for increasing the minimum threshold if the packet is dropped.

27. An apparatus that manages a queue of packets, comprising:

means for receiving a packet;

means for generating a random number;

means for utilizing a mask to mask the random number;

means for dropping the packet and resetting the mask if a sum of a queue size and the masked random number is greater than a maximum threshold; and

means for shifting the mask to increase the potential size of the masked random number when a specified number of packets are received without dropping a packet.