Pseudo-relative mode WRED/tail drop mechanism

• US 8,948,011 B2
• Filed: 04/30/2013
• Issued: 02/03/2015
• Est. Priority Date: 06/09/2008
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Lamb, Joe, Findlen, Benjamin
• Primary Examiner(s): Ghowrwal, Omar
• Assistant Examiner(s): ONAMUTI, GBEMILEKE J
• Application Number:
  US13/873,794
• Publication Number:
  US 20130235725A1
• Time in Patent Office: 644 Days
• Field of Search: 370/229, 370/235
• US Class Current: 370/235
• CPC Class Codes: G01R 31/08 Locating faults in cables, transmission lines, or networks
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/326 with random discard, e.g. random early discard [RED]
• CPC Class Codes: H04L 47/623 Weighted service order

Abstract

A buffer memory can be configured to temporarily store data in a number of queues. A processor can be configured to measure a fullness of the buffer memory. The processor can be configured to adjust thresholds and drop profiles based on a measured global resource usage for a weighted random early detection (WRED) technique with less resources than a conventional.

Claims

1. A method comprising:

storing, by one or more processors of a network device, a plurality of drop probability values,

the plurality of drop probability values being stored at a corresponding plurality of memory locations, and

the plurality of drop probability values including;

a minimum drop probability value associated with a fill level of a queue being less than a first threshold,

a maximum drop probability value associated with the fill level of the queue being greater than a second threshold,

the second threshold being greater than the first threshold, and

a plurality of intermediate drop probability values associated with the fill level of the queue being between the first threshold and the second threshold,

the plurality of intermediate drop probability values being determined as a function of the fill level of the queue;

storing, by the one or more processors, a data unit to the queue;

determining, by the one or more processors, the fill level associated with the queue based on storing the data unit;

identifying, by the one or more processors, a particular memory location of the corresponding plurality of memory locations based on the fill level associated with the queue;

acquiring, by the one or more processors, a particular drop probability value, of the plurality of drop probability values, stored at the particular memory location,

the particular drop probability value being the minimum drop probability value, the maximum drop probability value, or one of the plurality of intermediate drop probability values; and

processing, by the one or more processors, the data unit based on the particular drop probability value.

2. The method of claim 1, where identifying the particular memory location includes:

determining an average fill level associated with a plurality of queues associated with the network device; and

identifying the particular memory location based on comparing the average fill level, associated with the plurality of queues, and the fill level associated with the queue.

3. The method of claim 1, where identifying the particular memory location includes:

selecting a random early detection (RED) rule, of a plurality of RED rules, based on a type of data stored in the queue;

calculating a minimum queue fullness threshold associated with the queue based on the selected RED rule,

the minimum queue fullness threshold being the first threshold; and

identifying the particular memory location based on comparing the fill level and the minimum queue fullness threshold.

4. The method of claim 3, where the plurality of drop probability values are associated with a drop profile associated with the selected RED rule.

5. The method of claim 1, where identifying the particular memory location includes:

determining, based on a random early detection (RED) rule, a maximum queue fullness threshold associated with the queue,

the maximum queue fullness threshold being the second threshold; and

identifying the particular memory location further based on comparing the fill level and the maximum queue fullness threshold.

6. The method of claim 1,

where the corresponding plurality of memory locations are associated with, respectively, a plurality of fill level ranges associated with the queue, and

where identifying the particular memory location includes:

identifying a particular fill level range, of the plurality of fill level ranges, that includes the fill level associated with the queue,

the particular memory location being associated with the particular fill level range.

7. The method of claim 1, where determining the fill level comprises:

determining the fill level based on storing the data unit and based on a speed of a link associated with the queue.

8. A system comprising:

a memory; and

a processor to;

store a plurality of drop probability values at a corresponding plurality of memory locations in the memory,

the corresponding plurality of memory locations being associated with, respectively, a plurality of fill level ranges, and

the plurality of drop probability values including;

a minimum drop probability value associated with a fill level of a queue being less than a first threshold,

a maximum drop probability value associated with the fill level of the queue being greater than a second threshold,

the second threshold being greater than the first threshold, and

a plurality of intermediate drop probability values associated with the fill level of the queue being between the first threshold and the second threshold,

the plurality of intermediate drop probability values being determined as a function of the fill level of the queue,

store a data unit to the queue,

determine the fill level associated with the queue when the data unit is stored,

identify a particular fill level range, of the plurality of fill level ranges, that includes the fill level associated with the queue,

identify, based on the particular fill level range, a particular memory location of the corresponding plurality of memory locations,

acquire a particular drop probability value, of the plurality of intermediate drop probability values, stored at the particular memory location and that corresponds to the fill level, and

determine whether to drop the data unit based on the particular drop probability value.

9. The system of claim 8, where the processor, when identifying the particular memory location, is further to:

determine an average fill level associated with a plurality of queues associated with the system,

compare the average fill level, associated with the plurality of queues, and the fill level, associated with the queue, to produce comparison results, and

identify the particular memory location further based on the comparison results.

10. The system of claim 8, where the processor, when identifying the particular memory location, is further to:

select a random early detection (RED) rule, of a plurality of RED rules, based on a type of data stored in the queue,

calculate a minimum queue fullness threshold associated with the queue, based on the selected RED rule,

the minimum queue fullness threshold being the first threshold, and

identify the particular memory location further based on comparing the fill level and the minimum queue fullness threshold.

11. The system of claim 10, where the processor, when identifying the particular memory location, is further to:

determine, based on the selected RED rule, a maximum queue fullness threshold associated with the queue,

the maximum queue fullness threshold being the second threshold, and

identify the particular memory location further based on comparing the fill level and the maximum queue fullness threshold.

12. The system of claim 10, where the plurality of drop probability values are associated with a drop profile associated with the selected RED rule.

13. The system of claim 8, where the plurality of drop probability values are associated with at least one of:

a corresponding plurality of random early detection (RED) rules associated with the queue, or

a corresponding plurality of weighted random early detection (WRED) rules associated with the queue.

14. A non-transitory memory device to store instructions, the instructions comprising:

one or more instructions that, when executed by a processor associated with a network device, cause the processor to;

store a plurality of drop probability values at a respective plurality of memory locations,

the plurality of drop probability values including;

a minimum drop probability value associated with a fill level associated with a queue being less than a first threshold,

a maximum drop probability value associated with the fill level being greater than a second threshold,

 

the second threshold being greater than the first threshold, and

a plurality of intermediate drop probability values associated with the fill level being between the first threshold and the second threshold,

the plurality of intermediate drop probability values being determined as a function of the fill level,

store a data unit in the queue,

determine the fill level based on storing the data unit,

identify, based on the fill level a particular memory location of the respective plurality of memory locations,

acquire a particular drop probability value, of the plurality of intermediate drop probability values, stored at the particular memory location, and

process the data unit from the queue based on the particular drop probability value.

15. The non-transitory memory device of claim 14, where the one or more instructions to identify the particular memory location include:

one or more instructions that, when executed by the processor, cause the processor to;

calculate an average fill level associated with a plurality of queues associated with the network device, and

identify the particular memory location based on comparing the fill level to the average fill level.

16. The non-transitory memory device of claim 14, where the instructions further include:

one or more instructions that, when executed by the processor, cause the processor to;

select a random early detection (RED) rule, of a plurality of RED rules, based on a type of data stored in the queue, and

calculate the first threshold based on the selected RED rule.

17. The non-transitory memory device of claim 16, where the plurality of drop probability values are associated with a drop profile for the selected RED rule.

18. The non-transitory memory device of claim 14, where the instructions further include:

one or more instructions that, when executed by the processor, cause the processor to;

select a random early detection (RED) rule, of a plurality of RED rules, based on a type of data stored in the queue, and

determine, based on the selected RED rule, the second threshold associated with the queue, and

where the one or more instructions to identify the particular memory location further include;

one or more instructions that, when executed by the processor, cause the processor to;

identify the particular memory location based on comparing the fill level and the second threshold.

19. The non-transitory memory device of claim 14, where the instructions further comprise:

one or more instructions that, when executed by the processor, cause the processor to;

calculate the plurality of drop probability values as a function of the fill level of the queue.

20. The non-transitory memory device of claim 14, where the one or more instructions to process the data unit from the queue comprise:

one or more instructions that, when executed by the processor, cause the processor to;

drop the data unit based on the particular drop probability value.