Dynamic queue threshold extensions to random early detection

• US 7,369,500 B1
• Filed: 06/30/2003
• Issued: 05/06/2008
• Est. Priority Date: 06/30/2003
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Gallagher, Shawn, Branam, Stephen, Ross, Ryan, Lipman, Michael E., Lemaire, Thomas A.
• Primary Examiner(s): Pham; Chi
• Assistant Examiner(s): Phan; Tri H.
• Application Number:
  US10/608,215
• Time in Patent Office: 1,772 Days
• Field of Search: 370229-234, 370235-238, 370412-418, 709223-225, 709/232, 709/235
• US Class Current: 370/235
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 47/10 Flow control; Congestion control

Abstract

A buffer memory may be configured to temporarily store data in a number of queues. A processor may be configured to measure a fullness of the buffer memory. The processor may also be configured to assign sizes to the number of queues based on the fullness of the buffer memory. The processor may also adjust thresholds of drop profiles associated with the number of queues based on the sizes assigned to the number of queues.

Claims

1. A system for providing congestion control, comprising:

a buffer memory configured to temporarily store data in a plurality of queues; and

a processor configured to;

measure a total amount of memory occupied by the plurality of queues in the buffer memory,

modify lengths of the plurality of queues based on the total amount of memory occupied, where modifying the lengths of the plurality of queues includes decreasing the lengths of the plurality of queues when the total amount of memory occupied increases; and

modify drop profiles associated with the plurality of queues based on the total amount of memory occupied.

2. The system of claim 1, wherein the processor is further configured to:

initially allocate lengths to the plurality of queues based on a total number of the plurality of queues.

3. The system of claim 1, wherein when measuring the total amount of memory occupied, the processor is further configured to:

designate one of a plurality of discrete memory usage levels into which the total amount of memory falls.

4. The system of claim 1, wherein when modifying the drop profiles, the processor is configured to:

change minimum queue thresholds and maximum queue thresholds associated with the drop profiles based on the lengths of the plurality of queues.

5. The system of claim 1, wherein when modifying the drop profiles, the processor is further configured to:

modify different drop profiles that are associated with different classes of data within the plurality of queues.

6. The system of claim 1, wherein the processor is further configured to:

selectively drop data from the plurality of queues based on the drop profiles.

7. A system for providing congestion control, comprising:

a buffer memory configured to temporarily store data in a plurality of queues; and

a processor configured to;

measure a total amount of memory occupied by the plurality of queues in the buffer memory,

modify lengths of the plurality of queues based on the total amount of memory occupied, and

modify drop profiles associated with the plurality of queues based on the total amount of memory occupied, where modifying the drop profiles includes changing minimum queue thresholds and maximum queue thresholds associated with the drop profiles based on the lengths of the plurality of queues and where the minimum queue thresholds and the maximum queue thresholds are respectively percentages of the lengths of the plurality of queues.

8. A system for providing congestion control, comprising:

a buffer memory configured to temporarily store data in a plurality of queues; and

a processor configured to;

measure a total amount of memory occupied by the plurality of queues in the buffer memory,

modify lengths of the plurality of queues based on the total amount of memory occupied,

modify drop profiles associated with the plurality of queues based on the total amount of memory occupied, and

selectively drop data from the plurality of queues based on the drop profiles, where when selectively dropping data from the plurality of queues, the processor is configured to;

randomly drop data from at least one queue when a queue fullness is between a minimum queue threshold and a maximum queue threshold associated with a drop profile of the at least one queue, and

not drop data from the at least one queue when the queue fullness is less than the minimum queue threshold associated with the drop profile of the at least one queue.

9. A device, comprising:

a buffer memory configured to temporarily store data in a plurality of queues; and

a processor configured to;

measure a fullness of the buffer memory,

assign sizes to the plurality of queues based on the fullness of the buffer memory and based on a memory usage region into which the fullness of the buffer memory falls, and

adjust thresholds of drop profiles associated with the plurality of queues based on the sizes assigned to the plurality of queues.

10. The device of claim 9, wherein the processor is further configured to:

initially set the sizes for the plurality of queues based on a number of the queues.

11. The device of claim 9, wherein the buffer memory is associated with eight or more different memory usage regions.

12. The device of claim 9, further comprising:

a shared memory connected to the processor and configured to store information for use in adjusting thresholds of the drop profiles associated with the plurality of queues,

wherein when adjusting thresholds of the drop profiles, the processor is configured to;

read the information from the shared memory for use in adjusting the thresholds.

13. The device of claim 9, wherein when adjusting the thresholds of the drop profiles, the processor is further configured to:

modify thresholds that are associated with different types of data within the plurality of queues.

14. The device of claim 9, wherein the processor is further configured to:

selectively drop data from the plurality of queues based on the thresholds of the drop profiles that were adjusted.

15. A device, comprising:

a buffer memory configured to temporarily store data in a plurality of queues; and

a processor configured to;

measure a fullness of the buffer memory,

assign sizes to the plurality of queues based on the fullness of the buffer memory, and

adjust thresholds of drop profiles associated with the plurality of queues based on the sizes assigned to the plurality of queues, where when adjusting thresholds of the drop profiles, the processor is configured to;

change minimum queue thresholds and maximum queue thresholds of the drop profiles by determining respective percentages of the sizes of the plurality of queues.

16. A method for providing congestion control for data stored in queues, comprising:

periodically measuring a fullness of a memory that contains the queues;

decreasing sizes of the queues when the fullness of the memory increases;

increasing sizes of the queues when the fullness of the memory decreases; and

adjusting queue fullness thresholds based on the sizes of the queues, the queue fullness thresholds for a particular queue defining a queue fullness region inside which the data in the particular queue is randomly dropped.

17. The method of claim 16, wherein the adjusting includes:

computing the queue fullness thresholds using percentages of the sizes of the queues.

18. The method of claim 16, wherein the adjusting includes:

looking up the queue fullness thresholds in a table using the sizes of the queues.

19. The method of claim 16, further comprising:

randomly dropping data from the particular queue when a fullness of the particular queue falls within the queue fullness region defined by the queue fullness thresholds.

20. The method of claim 19, wherein the fullness of the particular queue is an exponential, weighted moving-average fullness.

21. A method for providing congestion control for data stored in queues, comprising:

dynamically changing oversubscription of the queues based on total usage of a memory that contains the queues to set new lengths for the queues; and

performing random early detection on the queues based on the new lengths, where the performing includes;

determining minimum and maximum queue fullness thresholds from percentages of the new lengths, and

randomly dropping data from one of the queues when a fullness of the one queue falls between the minimum and maximum queue fullness thresholds.

22. A system for providing congestion control for data stored in queues, comprising:

means for measuring memory usage;

means for updating a length of a queue based on the measured memory usage;

means for updating minimum and maximum thresholds of a drop profile associated with the queue based on the updated length of the queue, where the minimum and maximum thresholds are respectively percentages of the length of the queue; and

means for selectively dropping data from the queue based on the updated minimum and maximum thresholds of the drop profile associated with the queue.