Pseudo-relative mode WRED/tail drop mechanism

• US 8,441,925 B1
• Filed: 06/09/2008
• Issued: 05/14/2013
• 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): Hoang, Thai
• Assistant Examiner(s): ONAMUTI, GBEMILEKE J
• Application Number:
  US12/135,617
• Time in Patent Office: 1,800 Days
• Field of Search: 370/235, 370/230, 370/229
• US Class Current: 370/229
• 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 network device comprising:

a memory that includes at least a first queue, the memory to store data transmitted via the network device; and

a processor to;

determine a current usage level of the memory,

select, based on a characteristic of data stored in the first queue, a drop profile associated with a range of memory locations, of the memory,

where each of the memory locations is associated with one of a plurality of random early detection (RED) rules, and

where the drop profile comprises;

a first portion that is associated with a first range of normalized queue fullness values and includes a first plurality of memory locations, of the range of memory locations, and

a second portion that is associated with a second range of normalized queue fullness values and includes a second plurality of memory locations, of the range of memory locations,

calculate a normalized weighted average queue fullness value associated with the first queue,

determine, based on the drop profile, whether the normalized weighted average queue fullness value is included in the first range of normalized queue fullness values or the second range of normalized queue fullness values,

where, when the normalized weighted average queue fullness value is included in the first range of normalized queue fullness values, the processor is to;

determine that a drop probability associated with the first queue comprises a zero drop probability, and

allow data to enter the first queue without dropping any of the data, based on the drop probability comprising the zero drop probability,

where, when the normalized weighted average queue fullness value is included in the second range of normalized queue fullness values, the processor is to;

identify one of the plurality of random early detection (RED) rules based on the normalized weighted average queue fullness value and the range of memory locations, of the drop profile,

determine, based on the identified one of the plurality of RED rules, a maximum threshold associated with the first queue,

where a rate of change of a drop probability associated with the second range of normalized queue fullness values is based on a slope, associated with the second range of normalized queue fullness values, that varies based on the maximum threshold, and

randomly drop data from the first queue, based on a drop probability obtained from the drop profile when the normalized weighted average queue fullness exceeds the minimum threshold and does not exceed the maximum threshold.

2. The network device of claim 1, where the processor is further to:

tail drop data from the first queue when the normalized weighted average queue fullness value is included in the second range of normalized queue fullness values and the normalized weighted average queue fullness exceeds the maximum threshold.

3. The network device of claim 1, where the drop profile is stored as a series of values in the range of memory locations.

4. The network device of claim 3, where the slope is a non-linear function of queue occupancy.

5. The network device of claim 3, where the slope is a linear function of queue occupancy.

6. The network device of claim 1, where the first range of normalized queue fullness values is associated with a minimum threshold value that corresponds to the first queue comprising an empty queue.

7. The network device of claim 6, where the slope comprises a function of a queue occupancy of the first queue.

8. A method of providing congestion control for data stored in one or more queues associated with a network device, the method comprising:

determining, by the network device, a global resource usage level of the one or more queues;

determining, by the network device, a weighted average queue fullness of a first queue, of the one or more queues;

selecting, by the network device, a weighted random early detection (WRED) rule, of a plurality of WRED rules, based on a type of data stored in the first queue;

calculating, by the network device, a minimum queue fullness threshold, of the first queue, responsive to the determined global resource usage level and based on the WRED rule;

selecting, by the network device and based on the selected WRED rule, a drop profile, where the drop profile is implemented as a series of values stored in a range of memory locations, where each value, of the series of values, is associated with a corresponding one of a plurality of random early detection (RED) rules;

normalizing, by the network device, the weighted average queue fullness to one of the series of values based on a quantity of memory locations, of the range of memory locations storing the series of values;

identifying, by the network device, one of the series of values, based on normalizing the weighted average queue fullness;

identifying, by the network device, a drop probability corresponding to the identified series of values based on the drop profile;

identifying, by the network device and based on the identified one of the series of values, one of the plurality of RED rules;

determining, by the network device and based on the identified one of the plurality of RED rules, a maximum queue fullness threshold associated with the first queue; and

randomly dropping data from the first queue based on the drop probability when the weighted average queue fullness exceeds the minimum queue fullness threshold and does not exceed the maximum queue fullness threshold.

9. The method of claim 8, where the drop profile comprises a linear function of queue occupancy.

10. The method of claim 8, where the maximum queue fullness threshold and the minimum queue fullness threshold are defined as a fractional amount of a length of the first queue.

11. A method of providing congestion control for data stored in one or more queues of a network device, the method comprising:

determining, by the network device, a weighted average queue fullness as an amount occupied of a first queue, of the one or more queues;

selecting, by the network device, a drop profile associated with a single weighted random early detection (WRED) rule and a plurality of random early detection (RED) rules;

determining, by the network device, a minimum queue fullness threshold based on the drop profile,

where the WRED is associated with the first queue based on a characteristic of data stored in the first queue;

implementing the drop profile as a series of values stored in a range of memory locations, each value, of the series of values, being associated with a corresponding one of the plurality of RED rules;

normalizing, by the network device, the weighted average queue fullness to determine a normalized weighted average queue fullness value based on a quantity of memory locations included in the range of memory locations;

identifying, by the network device, one of the series of values based on the normalized weighted average queue fullness value;

identifying, by the network device and based on the identified one of the series of values, the corresponding one of the plurality of RED rules associated with the identified one of the series of values;

calculating, by the network device, a maximum queue fullness threshold based on the identified one of the plurality of RED rules;

identifying, by the network device, a drop percentage associated with dropping data from the first queue when the weighted average queue fullness exceeds the minimum queue fullness threshold and does not exceed the maximum queue fullness threshold, based on the normalized weighted average queue fullness value and a slope associated with the series of values and the maximum queue fullness threshold; and

randomly dropping, by the network device, data from the first queue based on the drop percentage when the weighted average queue fullness exceeds the minimum queue fullness threshold and does not exceed the maximum queue fullness threshold.

12. The method of claim 11, further comprising:

dropping, based on the drop profile, data from the first queue when the weighted average queue fullness exceeds the maximum queue fullness threshold; and

not dropping, based on the drop profile, data from the first queue when the weighted average queue fullness does not exceed the minimum queue fullness threshold.

13. The method of claim 12, further comprising:

assigning a first drop probability to a first portion of the series of values, where the first portion comprises a first plurality of values, of the series of values; and

assigning a second drop probability to each value of a second portion of the series of values, where the second portion comprises a second plurality of values, of the series of values, that is different from the first plurality of values, and

where the second drop probability is assigned to each value of the second portion as a function of queue occupancy of the first queue.

14. The method of claim 13, where the first drop probability is zero, and

where determining the minimum queue threshold value includes:

determining whether the first portion of the series of values includes the identified one of the series of values, and

determining not to drop any data from the first queue based on the first drop probability when the first portion of the series of values includes the identified one of the series of values.

15. The method of claim 13, where the function of queue occupancy produces a maximum value less than one.

16. The method of claim 12, where the slope comprises a non-linear function of queue occupancy of the first queue.