Differentiated services for a network processor

• US 20030152084A1
• Filed: 09/19/2002
• Published: 08/14/2003
• Est. Priority Date: 09/19/2001
• Status: Active Grant

• Current Assignee: Bay Microsystems, Inc. (Vcinity, Inc.)
• Original Assignee: Bay Microsystems, Inc. (Vcinity, Inc.)
• Inventors: Lee, Barry, Trinh, Man Dieu
• Granted Patent: US 7,349,403 B2
• Time in Patent Office: Days
• US Class Current: 370/395.21
• CPC Class Codes: G06F 15/00 Digital computers in general details G06F1/00 – G06F13/00; Data processing equipment in general
• CPC Class Codes: G06F 17/00 Digital computing or data processing equipment or methods, specially adapted for specific functions information retrieval, database structures or file system structures therefor G06F16/00
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units
• CPC Class Codes: H04L 12/28 characterised by path configuration, e.g. LAN [Local Area Networks] or WAN [Wide Area Networks] wireless communication networks H04W ; arrangements for dividing the transmission path H04W40/00
• CPC Class Codes: H04L 12/56 Packet switching systems
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/22 Traffic shaping
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/623 Weighted service order

Abstract

A differentiated services device is described. In one embodiment, the differentiated services device includes: a traffic metering unit to indicate whether an information element in a flow conforms to a peak rate and a committed rate; a storage congestion metering unit to determine whether the information element should be accepted or discarded; and a marking unit to mark the information element with one of a plurality of mark values, wherein the marking unit is coupled to the traffic metering unit and the storage congestion metering unit. Also, a method of marking an information element in a flow is described. In one embodiment, the method includes: indicating whether the information element in the flow conforms to a peak rate and a committed rate; determining whether the information element should be accepted or discarded; and marking the information element with one of a plurality of mark values.

Claims

1. A differentiated services device comprising:

a traffic metering unit to indicate whether an information element in a flow conforms to a peak rate and a committed rate;

a storage congestion metering unit to determine whether the information element should be accepted or discarded; and

a marking unit to mark the information element with one of a plurality of mark values, wherein the marking unit is coupled to the traffic metering unit and the storage congestion metering unit.

2. The differentiated services device of claim 1, wherein the storage congesting metering unit uses an average occupancy of a class within a storage unit to which the flow of the information element belongs to determine whether the information element should be accepted or discarded.

3. The differentiated services device of claim 1, wherein the marking unit uses one of an output of the traffic metering unit and an output of the storage congestion metering unit, and one of a color-blind policy and a color-aware policy to determine with which one of the plurality of mark values to mark the information element.

4. The differentiated services device of claim 1, wherein the information element is a packet.

5. The differentiated services device of claim 1, wherein the traffic metering unit comprises:

a first length determination unit to determine a length of the information element;

a first time interval required determination unit to determine a time interval required between arrival of two successive information elements given a quality of service of the flow to which the information element belongs; and

a first conformance checking unit to determine whether the information element conforms to one of the peak rate and the committed rate.

6. The differentiated services device of claim 5, wherein the traffic metering unit further comprises:

a second length determination unit to determine the length of the information element;

a second time interval required determination unit to determine the time interval required between the arrival of two successive information elements given the quality of service of the flow to which the information element belongs; and

a second conformance checking unit to determine whether the information element conforms to one of the peak rate and the committed rate.

7. The differentiated services device of claim 6, wherein the first conformance checking unit comprises:

a first conformance without debt checking unit, wherein the first conformance without debt checking unit uses a “

token bucket” and

the time interval required between the arrival of two successive information elements to determine whether there is conformance to the committed rate without debt checking; and

a first conformance with debt checking unit, wherein the first conformance with debt checking unit uses the “

token bucket”

, an “

actual time”

, and a time limit that can be borrowed from subsequent time intervals, to determine whether there is conformance to the committed rate with debt checking;

further wherein the second conformance checking unit comprises;

a second conformance without debt checking unit wherein the second conformance without debt checking unit uses the “

token bucket” and

the time interval required between the arrival of two successive information elements to determine whether there is conformance to the peak rate without debt checking; and

a second conformance with debt checking unit, wherein the second conformance with debt checking unit uses the “

token bucket”

, the “

actual time”

, and the time limit that can be borrowed from subsequent time intervals, to determine whether there is conformance to the peak rate with debt checking.

8. The differentiated services device of claim 1, wherein the storage congestion metering unit comprises:

a first multiplexer to select one of a plurality of average occupancy counters that corresponds to a class of the flow to which the information element belongs;

a compare unit coupled to the first multiplexer, wherein the compare unit uses the one of the plurality of average occupancy counters with a maximum number of occupied rows and a minimum number of rows to provide at least one select signal;

a drop probability calculation unit coupled to the first multiplexer, wherein the drop probability calculation unit calculates a drop probability for the class;

a discard scheduler coupled to, the drop probability calculation unit, wherein the discard scheduler receives the drop probability and information regarding order of arrival of the information element and outputs a discard scheduler output; and

a second multiplexer coupled to the discard scheduler and the compare unit, wherein the second multiplexer receives the at least one select signal, the discard scheduler output, an always discard signal, and an always accept signal, and outputs a discard or accept signal.

9. The differentiated services device of claim 8, wherein the drop probability calculation unit comprises:

a subtract unit, wherein the subtract unit subtracts the minimum number of occupied rows from the one of the plurality of average occupancy counters and provides a subtract unit output;

a division unit coupled to the subtract unit, wherein the division unit divides the subtract unit output by a number of rows per drop probability increment and provides a division unit output; and

a multiplication unit coupled to the division unit, wherein the multiplication unit multiplies the division unit output with a drop probability increment per row step and outputs the drop probability.

10. The differentiated services device of claim 1, wherein the marking unit comprises:

a multiplexer, wherein the multiplexer receives an output of the traffic metering unit, an output of the storage congestion metering unit, and a marking mode signal, and outputs one of the output of the traffic metering unit and the output of the storage congestion metering unit; and

a color aware or color blind marking unit coupled to the multiplexer, wherein the color aware or color blind marking unit receives an output from the multiplexer, the marking mode signal, a marking instruction signal, and information regarding marking performed by an upstream device, and outputs the one of the plurality of mark values.

11. A method of marking an information element in a flow, comprising:

indicating whether the information element in the flow conforms to a peak rate and a committed rate;

determining whether the information element should be accepted or discarded; and

marking the information element with one of a plurality of mark values.

12. The method of claim 11, wherein the determining comprises using an average occupancy of a class within a storage unit to which the flow of the information element belongs to determine whether the information element should be accepted or discarded.

13. The method of claim 11, wherein the marking comprises using one of an output of the traffic metering unit and an output of the storage congestion metering unit, and using one of a color-blind policy and a color-aware policy to determine with which one of the plurality of mark values to mark the information element.

14. The method of claim 11, wherein the information element is a packet.

15. The method of claim 11, wherein the indicating comprises:

first determining a length of the information element;

first determining a time interval required between arrival of two successive information elements given a quality of service of the flow to which the information element belongs; and

first determining whether the information element conforms to one of the peak rate and the committed rate.

16. The method of claim 15, wherein the indicating further comprises:

second determining the length of the information element;

second determining the time interval required between the arrival of two successive information elements given the quality of service of the flow to which the information element belongs; and

second determining whether the information element conforms to one of the peak rate and the committed rate.

17. The method of claim 16, wherein the first determining whether the information element conforms comprises:

first determining whether there is conformance to the committed rate without debt checking using a “

token bucket” and

the time interval required between the arrival of two successive information elements; and

first determining whether there is conformance to the committed rate with debt checking using the “

token bucket”

, an “

actual time”

, and a time limit that can be borrowed from subsequent time intervals;

further wherein the second determining whether the information element conforms comprises;

second determining whether there is conformance to the peak rate without debt checking using the “

token bucket” and

the time interval required between the arrival of two successive information elements; and

second determining whether there is conformance to the peak rate with debt checking using the “

token bucket”

, the “

actual time”

, and the time limit that can be borrowed from subsequent time intervals.

18. The method of claim 11, wherein the determining comprises:

selecting one of a plurality of average occupancy counters that corresponds to a class of the flow to which the information element belongs;

comparing the one of the plurality of average occupancy counters with a maximum number of occupied rows and a minimum number of occupied rows to provide at least one select signal;

calculating a drop probability for the class;

providing a discard scheduler output based on the drop probability and information regarding order of arrival of the information element;

selecting one of the discard scheduler output, an always discard signal, and an always accept signal using the at least one select signal; and

outputting a discard or accept signal based on the selecting one of the discard scheduler output, the always discard signal, and the always accept signal.

19. The method of claim 18, wherein the calculating the drop probability for the class comprises:

subtracting the minimum number of occupied rows from the one of the plurality of average occupancy counters and providing a subtraction output;

dividing the subtraction output by a number of rows per drop probability increment and providing a division output; and

multiplying the division unit output with a drop probability increment per row step and outputting the drop probability.

20. The method of claim 11, wherein the marking comprises:

selecting one an output of the traffic metering unit and an output of the storage congestion metering unit based on a marking mode signal, and outputting one of the output of the traffic metering unit and the output of the storage congestion metering unit based on the selecting; and

receiving an output from the multiplexer, the marking mode signal, a marking instruction signal, and information regarding marking performed by an upstream device, and outputting the one of the plurality of mark values.

21. A method of marking an information element, comprising:

determining whether the information element conforms to a peak rate;

if the information element does not conform to the peak rate, then marking the information element with a first mark value;

if the information element conforms to the peak rate, then determining whether the information element conforms to a committed rate;

if the information element does not conform to the committed rate, then marking the information element with a second mark value; and

if the information element conforms to the committed rate, then marking the information element with a third mark value.

22. The method of claim 21, wherein the information element is a packet.

23. The method of claim 21, further comprising:

prior to the determining whether the information element conforms to the peak rate, determining whether the information element has been previously marked with the first mark value by an upstream device;

if the determining whether the information element has been previously marked with the first mark value by the upstream device indicates that the information element has not been marked with the first mark value, then proceeding to the determining whether the information element conforms to the peak rate; and

if the determining whether the information element has been previously marked with the first mark value by the upstream device indicates that the information element has been marked with the first mark value, then maintaining the first mark value.

24. The method of claim 23, further comprising:

prior to the determining whether the information element conforms to the committed rate, determining whether the information element has been previously marked with the second mark value by the upstream device;

if the determining whether the information element has been previously marked with the second mark value by the upstream device indicates that the information element has not been marked with the second mark value, then proceeding to the determining whether the information element conforms to the committed rate; and

if the determining whether the information element has been previously marked with the second mark value by the upstream device indicates that the information element has been marked with the second mark value, then maintaining the second mark value.

25. A method of marking an information element in a flow, comprising:

determining whether average usage of a class to which the flow belongs is less than or equal to a maximum threshold;

if the average usage is greater than the maximum threshold, then marking the information element with a first mark value;

if the average usage is less than or equal to the maximum threshold, then determining whether the average usage is less than or equal to a minimum threshold;

if the average usage is greater than the minimum threshold, then marking the information element with a second mark value; and

if the average usage is less than or equal to the minimum threshold, then marking the information element with a third mark value.

26. The method of claim 25, wherein the information element is a packet and the average usage is the average information segment storage unit usage.

27. The method of claim 25, further comprising:

prior to the determining whether the average usage is less than or equal to the maximum threshold, determining whether the information element has been previously marked with the first mark value by an upstream device;

if the determining whether the information element has been previously marked with the first mark value by the upstream device indicates that the information element has not been marked with the first mark value, then proceeding to the determining whether the average usage is less than or equal to the maximum threshold; and

if the determining whether the information element has been previously marked with the first mark value by the upstream device indicates that the information element has been marked with the first mark value, then maintaining the first mark value.

28. The method of claim 27, further comprising:

prior to the determining whether the average usage is less than or equal to the minimum threshold, determining whether the information element has been previously marked with the second mark value by the upstream device;

if the determining whether the information element has been previously marked with the second mark value by the upstream device indicates that the information element has not been marked with the second mark value, then proceeding to the determining whether the average usage is less than or equal to the minimum threshold; and

if the determining whether the information element has been previously marked with the second mark value by the upstream device indicates that the information element has been marked with the second mark value, then maintaining the second mark value.

29. A method for traffic metering, comprising:

receiving an information element in a flow;

determining a length of the information element;

calculating a required time between information elements; and

determining whether the information element is a first information element of the flow;

if the information element is the first information element of the flow, then a debt is set to zero and a last conforming time (“

LCT”

) is set to an arrival time of the first information element; and

if the information element is not the first information element of the flow, then calculating the “

actual time”

between arrival of two successive information elements and adjusting the required time between information elements to produce a “

token bucket”

that accounts for the debt incurred by a previous information element.

30. The method of claim 29 further comprising:

determining if the “

token bucket”

is less than or equal to the “

actual time”

; and

if the “

token bucket”

is less than or equal to the “

actual time”

, then indicating that the information element is conforming and resetting the debt and setting the LCT to the arrival time of the information element;

if the “

token bucket”

is greater than the “

actual time”

, then determining if the “

token bucket”

is less than or equal to the “

actual time”

plus a limit that can be borrowed from a subsequent time interval;

if the “

token bucket”

is less than or equal to the “

actual time”

plus the limit, then indicating that the information element is conforming and setting the LCT to the arrival time of the information element and setting the debt to the “

token bucket”

minus the actual time; and

if the “

token bucket”

is greater than the “

actual time”

plus the limit, then indicating that the information element is nonconforming.

31. A storage congestion metering unit comprising:

a first multiplexer to select a particular one of a plurality of average occupancy counts that corresponds to a class to which a flow of an information element belongs.

a class characteristic storage unit stores multiple entries, each of the entries corresponds to a particular one of a plurality of classes and each of the entries includes a scheduling entry that allows for a balanced discarding of the information element, a minimum number of occupied information segment storage units before a drop probability is used to determine whether to discard the information element, a maximum number of occupied information segment storage units at which threshold point the information element is discarded, a value “

G”

that specifies how often to increment the drop probability and a value “

I”

that specifies how much each drop probability increment should be;

a compare unit coupled to the first multiplexer, wherein the compare unit has as inputs the particular one of the plurality of average occupancy counts and the minimum and maximum number of occupied information segment storage units; and

a second multiplexer coupled to the compare unit;

wherein

if the compare unit finds that the particular one of the plurality of average occupancy counts is greater than or equal to the maximum number of occupied information segment storage units, then the compare unit instructs the second multiplexer to indicate that the information element is to be discarded;

if the compare unit finds that the particular one of the plurality of average occupancy counts is less than the minimum number of occupied information segment storage units, then the compare unit instructs the second multiplexer to indicate that the information element is to be accepted; and

if the compare unit finds that the particular one of the plurality of average occupancy counts is less than the maximum number of occupied information segment storage units and greater than or equal to the minimum number of occupied information segment storage units, then the compare unit instructs the second multiplexer to indicate whether to accept or discard the information element based on drop scheduling and the drop probability.

32. The storage congestion metering unit of claim 31 further comprising a drop probability calculation unit, wherein the drop probability calculation unit has as inputs the particular one of the plurality of average occupancy counts, the minimum and maximum number of occupied information segment storage units, the value “

G”

, and the value “

I”

, further wherein the drop probability calculation unit calculates the drop probability for the particular class.

33. The storage congestion metering unit of claim 32 further comprising a discard scheduler coupled to the drop probability calculation unit and the second multiplexer, wherein the discard scheduler receives the drop probability from the drop probability calculation unit and drop scheduling from the class characteristic storage unit, and outputs a discard or accept signal to the second multiplexer.

34. A method for storage congestion metering, comprising:

selecting a particular one of a plurality of average occupancy counts that corresponds to a class to which a flow of an information element belongs;

determining a drop probability for the class using the particular one of the plurality of average occupancy counts, a minimum number of occupied information segment storage units before a drop probability is used to determine whether to discard the information element, a maximum number of occupied information segment storage units at which threshold point the information element is discarded, a value “

G”

that specifies how often to increment the drop probability, and a value “

I”

that specifies how much each drop probability increment should be;

comparing the particular one of the plurality of average occupancy counts and the minimum and maximum number of occupied information segment storage units;

if the particular one of the plurality of average occupancy counts is greater than or equal to the maximum number of occupied information segment storage units, then outputting a signal to indicate that the information element is to be discarded;

if the particular one of the plurality of average occupancy counts is less than the minimum number of occupied information segment storage units, then outputting a signal to indicate that the information element is to be accepted; and

if the particular one of the plurality of average occupancy counts is less than the maximum number of occupied information segment storage units and greater than or equal to the minimum number of occupied information segment storage units, then outputting a signal to either discard or accept the information element based on drop scheduling and the drop probability.