Dynamic queue threshold extensions to random early detection

• US 7,990,868 B1
• Filed: 03/24/2008
• Issued: 08/02/2011
• Est. Priority Date: 06/30/2003
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Gallagher, Shawn, Branam, Stephen, LeMaire, Thomas A, Ross, Ryan, Lipman, Michael E
• Primary Examiner(s): Phan; Tri H
• Application Number:
  US12/054,019
• Time in Patent Office: 1,226 Days
• Field of Search: 370412-418, 709223-226, 709/229, 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 method comprising:

allocating queue lengths to a plurality of queues in a buffer based on a number of queues in the buffer;

measuring a total amount of memory used in the buffer; and

updating the allocated lengths of one or more of the plurality of queues based on the measuring.

2. The method of claim 1, further comprising:

updating drop profiles associated with the plurality of queues based on measuring the total amount of memory used.

3. The method of claim 2, further comprising:

selectively dropping data based on the updated drop profiles.

4. The method of claim 3, where selectively dropping data includes:

randomly dropping data from at least one queue of the plurality of queues when a queue fullness of the at least one queue is between a minimum queue threshold and a maximum queue threshold associated with the updated drop profile of the at least one queue; and

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

5. The method of claim 4, where updating the drop profiles includes computing minimum queue thresholds and maximum queue thresholds associated with the updated drop profiles.

6. The method of claim 1, where updating the drop profiles includes updating different drop profiles that are associated with different types of data within the plurality of queues.

7. The method of claim 1, where updating the lengths of the plurality of queues includes changing the lengths of the plurality of queues.

8. A device comprising:

a buffer including a plurality of queues that store data; and

a processor to;

allocate queue lengths to the plurality of queues based on a number of queues in the buffer,

measure a total amount of memory used in the buffer, and

update the lengths of one or more queues of the plurality of queues in the buffer based on the measuring.

9. The device of claim 8, where the processor is further configured to:

update drop profiles associated with the plurality of queues based on the measuring.

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

selectively drop data based on the updated drop profiles.

11. The device of claim 9, where the processor is further configured to:

randomly drop data from at least one queue of the plurality of queues when a queue fullness of the at least one queue is between a minimum queue threshold and a maximum queue threshold associated with the updated 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 updated drop profile of the at least one queue.

12. The device of claim 11, where the processor is further configured to:

compute minimum queue thresholds and maximum queue thresholds associated with the drop profiles.

13. The device of claim 9, where the processor is further configured to:

update different drop profiles that are associated with different types of data within the plurality of queues.

14. A method comprising:

selectively dropping data in a queue when a fullness of the queue is greater than a minimum queue threshold and less than a maximum queue threshold;

dropping no data when the queue fullness is less than or equal to the minimum queue threshold; and

adjusting a capacity of the queue based on a fullness of a buffer memory that contains the queue.

15. The method of claim 14, where adjusting the capacity of the queue further comprises:

increasing the capacity of the queue as the fullness of the buffer memory decreases; and

decreasing the capacity of the queue as the fullness of the buffer memory increases.

16. The method of claim 14, where the minimum queue threshold and the maximum queue threshold are computed using percentages of the capacity of the queue.

17. The method of claim 14, further comprising:

dropping all new data from a tail of the queue when the queue fullness is greater than or equal to the maximum queue threshold.

18. The method of claim 14, where the selectively dropping includes:

looking up the minimum and maximum queue thresholds in a table using the capacity of the queue.

19. The method of claim 14, where the queue fullness is an exponential, weighted moving-average fullness.

20. The method of claim 14, further comprising:

updating a drop profile associated with the queue based on the fullness of the buffer memory.