Data rate division among a plurality of input queues

• US 6,732,209 B1
• Filed: 03/28/2000
• Issued: 05/04/2004
• Est. Priority Date: 03/28/2000
• Status: Expired due to Term

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Anathakrishnan, Viswesh, Vaidyanathan, Arun, Cherukuri, Ravi K.
• Primary Examiner(s): Thai, Xuan M.
• Assistant Examiner(s): King, Justin
• Application Number:
  US09/536,885
• Time in Patent Office: 1,498 Days
• Field of Search: 710/240, 710/107, 710/117, 710/244, 370/402, 370/412, 370/523, 370/391, 370/355, 370/232, 707/9, 709/240, 714/117
• US Class Current: 710/240
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/6265 past bandwidth allocation

Abstract

An apparatus and method for distributing data transmission from a plurality of data input queues in a memory buffer to an output. The method includes associating a priority indicator with each data input queue, determining a priority indicator having a highest priority level among the plurality of priority indicators and selecting the data input queue associated with the priority indicator having the highest priority level to transmit to the output.

Claims

1. A method for distributing data transmission from a plurality of data input queues in a memory buffer to an output, said method comprising:

associating a priority indicator with each data input queue in the memory buffer;

determining a respective increment level for each of the plurality of data input queues in the memory buffer, the respective increment levels being proportional to respective desired bandwidths for the plurality of data input queues;

periodically increasing the respective priority indicators associated with the plurality of data input queues by the respective increment levels;

determining a priority indicator having a highest priority level among the plurality of priority indicators; and

selecting the data input queue associated with the priority indicator having the highest priority level to transmit to the output, including;

detecting a transmit condition indicating data is being transmitted from the selected data input queue to the output, and

decrementing the data input queue'"'"'s priority indicator by an amount of data transmitted.

2. The method of claim 1, wherein the step of associating a priority indicator with a data input queue further comprises:

setting the priority indicator to an initial priority level.

3. The method of claim 1, wherein the step of periodically increasing the priority indicators further comprises:

limiting the respective priority indicators to a value less than a maximum priority level.

4. The method of claim 3, wherein the step of limiting the respective priority indicators to a value less than a maximum priority level, further comprises,

detecting an overflow condition indicating that an overflowed priority indicator among the priority indicators has a value greater than the maximum priority level;

selecting a highest priority level among the priority indicators which is less than the maximum priority level; and

setting the priority level of the overflowed priority indicator to the larger of the indicator'"'"'s initial priority level and the highest priority level.

5. The method of claim 1, wherein the step of decrementing the data input queue'"'"'s priority indicator, further comprises:

limiting the data input queue'"'"'s priority indicator to a value greater than a minimum priority level.

6. The method of claim 5, wherein the step of limiting the data input queue'"'"'s priority indicator to a value greater than a minimum priority level comprises:

detecting an underflow condition indicating that an underflowed priority indicator among the priority indicators has a value less than a minimum priority level;

selecting a lowest priority level among the priority indicators which is greater than the minimum priority level; and

setting the priority level of the underflowed priority indicator to the smaller of the indicator'"'"'s initial priority level and the lowest priority level.

7. The method of claim 1, further comprising:

associating a rate cap flag with a data input queue; and

setting the rate cap flag to indicate that the data input queue is to be rate-capped.

8. The method of claim 7, wherein the step of selecting the data input queue associated with the priority indicator having the highest priority level further comprises:

determining whether the rate cap flag associated with a selected data input queue is set;

determining whether the priority indicator having the highest priority level and associated with the selected queue has a value less than the queue'"'"'s initial priority level; and

selecting another data input queue to transmit to the output.

9. A network device, comprising:

a memory buffer including a plurality of input queues, each of the plurality of input queues having an associated priority value and a rate cap indicator; and

a queue arbiter configured to determine which input queue among the plurality of input queues will send data to an output, the queue arbiter including;

an incrementor module configured to periodically increment respective priority values associated with the plurality of input queues according to respective weights associated with the plurality of input queues,

a selector module configured to select one of the plurality of input queues to send data to the output based on the priority values and the rate cap indicators associated with the plurality of input queues, and

a decrementor module configured to decrement the priority value of the one input queue that sent data in proportion to an amount of data sent.

10. The network device of claim 9, wherein the incrementor module is further configured to periodically increment the priority value associated with a given one of the input queues in proportion to a ratio of the weight associated with the given input queue to a total weight associated with the plurality of input queues.

11. The network device of claim 9, wherein the selector module is further configured to select the input queue whose priority value is highest if the associated rate cap indicator indicates that the input queue does not have a rate cap, and

wherein the selector module is still further configured to select the input queue whose priority value is second highest if the input queue associated with the highest priority value has a rate cap and the highest priority value does not exceed a rate cap threshold.

12. A method of selecting one input queue among a plurality of input queues in a memory buffer to send data to an output, comprising:

assigning a respective weight to each of the plurality of input queues in the memory buffer;

dynamically updating respective priority indicator values associated with respective ones of the plurality of input queues in proportion to the respectively assigned weights;

determining a respective increment level for each of the plurality of input queues in the memory buffer, the respective increment levels being proportional to respective output bandwidths associated with the plurality of input queues;

selecting a first one of the input queues whose associated priority value is highest if the first input queue is not rate capped or if the associated highest priority value exceeds a rate cap threshold; and

selecting among other ones of the input queues than the first input queue if the first input queue is rate capped and the associated highest priority value does not exceed the rate cap threshold.

13. The method of claim 12, further comprising:

sending data from the selected input queue to the output.

14. The method of claim 13, further comprising:

decrementing the priority value of the selected input queue in proportion to an amount of data sent to the output.

15. The method of claim 12, wherein the selecting among other ones of the input queues includes:

selecting a second one of the input queues whose associated priority value is second highest if the second input queue is not rate capped or if the associated second highest priority value exceeds the rate cap threshold.

16. The method of claim 12, wherein the rate cap threshold is identical to an initial priority indicator value associated with at least one of the plurality of input queues.