HIERARCHICAL PIPELINED DISTRIBUTED SCHEDULING TRAFFIC MANAGER

• US 20100278190A1
• Filed: 04/29/2009
• Published: 11/04/2010
• Est. Priority Date: 04/29/2009
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Ho, Edward, Dhruvanarayan, Srivi, Chen, Sun Den, Wang, Patrick, Feng, Michael, Chen, Edmund, Chow, Stephen, Yip, Thomas C., Rozario, Ranjit
• Granted Patent: US 7,986,706 B2
• Time in Patent Office: Days
• US Class Current: 370/412
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/60 implementing hierarchical scheduling
• CPC Class Codes: H04L 47/623 Weighted service order
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

A hierarchical pipelined distributed scheduling traffic manager includes multiple hierarchical levels to perform hierarchical winner selection and propagation in a pipeline including selecting and propagating winner queues of a lower level to subsequent levels to determine one final winning queue. The winner selection and propagation is performed in parallel between the levels to reduce the time required in selecting the final winning queue. In some embodiments, the hierarchical traffic manager is separated into multiple separate sliced hierarchical traffic managers to distributively process the traffic.

Claims

1. An apparatus, comprising:

a queue memory enqueue/dequeue and hierarchical traffic manager admission arbiter to perform the following;

arbitrate between a set of one or more requesters including new packet enqueue requests and queue reentry requests, and

selectively admit queues corresponding to the new packet enqueue requests and queue reentry requests into a hierarchical pipelined distributed scheduling traffic manager; and

the hierarchical pipelined distributed scheduling traffic manager coupled with the queue memory enqueue/dequeue and hierarchical traffic manager admission arbiter, the hierarchical pipelined distributed scheduling traffic manager including the following;

a lowest level including a plurality of nodes each associated with a node of one of a plurality of intermediate levels, each node at the lowest level representing a different queue,

the plurality of intermediate levels each including a plurality of nodes each associated with a plurality of nodes at a lower level and a node at a higher level, each node of the intermediate levels to include a scheduler to perform the following;

select winning queues between the associated plurality of nodes at the lower level, and

propagate the winning queues to the associated node at the higher level, and

a highest level including a node associated with a plurality of nodes at a lower level, the node to include a scheduler to perform the following;

select winning queues between the associated plurality of nodes at the lower level,

cause the winning queues to exit the hierarchical pipelined distributed scheduling traffic manager, and

generate queue reentry requests corresponding to the winning queues.

2. The apparatus of claim 1, wherein the set of requesters further includes packet dequeue requests that each corresponds to a set of one or more packets of a queue that are ready to leave that queue, wherein the queue memory enqueue/dequeue and hierarchical traffic manager admission arbiter is to perform the following for each selected packet dequeue request,

decrement a number of packets currently enqueued in that corresponding queue by a quantity of the set of packets;

decrement a number of bytes that correspond to the packets currently enqueued in that corresponding queue by an amount of bytes of the set of packets;

decrement a packet offset value by the quantity of the set of packets; and

begin a packet transmission process.

3. The apparatus of claim 1, wherein the hierarchical pipelined distributed scheduling traffic manager is separated into a plurality of separate sliced hierarchical pipelined distributed scheduling traffic manager that each include their own memories, shapers, and schedulers.

4. The apparatus of claim 1, wherein at least some of the selectively admitted queues are admitted into the hierarchical pipelined distributed scheduling traffic manager as a batch of packets, wherein the batch of packets allow for back to back same winning queue selection.

5. The apparatus of claim 1, wherein each of the schedulers of the intermediate levels is further to perform the following:

preempt a previous winning queue with a current winning queue if the current winning queue has a higher arbitration precedence than the previous winning queue; and

propagate the current winning queue to the associated node at the higher level.

6. The apparatus of claim 1, wherein an aggregation ratio between levels is configurable by a system operator.

7. The apparatus of claim 1, wherein the hierarchical pipelined distributed scheduling traffic manager is to perform winning queue selection in parallel.

8. The apparatus of claim 1, wherein at least some of the nodes of one of the intermediate levels is selectively associated with a node at a higher level that is not a next highest level relative to that intermediate level.

9. The apparatus of claim 1, wherein the set of requesters further includes rate token update requests that each correspond to a queue, wherein the queue memory enqueue/dequeue and hierarchical traffic manager admission arbiter is to perform the following for each rate token update request,

retrieve a rate token running counter for the queue associated with the rate token update request;

add one or more tokens to the rate token counter;

determine whether the added tokens cause a rate status change and generate a rate status change request for one of the nodes at one of the intermediate levels.

10. The apparatus of claim 9, wherein each of the nodes of each of the intermediate levels and the node at the highest level further includes an arbiter to arbitrate between multiple requester groups including new packet enqueue requests, queue reentry requests, and rate status change requests to select requests for the scheduler to process, wherein the selected requests are passed to the scheduler to process.

11. The apparatus of claim 1, wherein each node at the lowest level and the plurality of intermediate levels is associated with a set of one or more scheduling precedence parameters that are used during selection of a winning queue.

12. The apparatus of claim 11, wherein the set of scheduling precedence parameters includes weight tokens, a priority, and rate status, wherein the queue memory enqueue/dequeue and hierarchical traffic manager admission arbiter is further to deduct the length of one or more packets from a weight token that is associated with each queue entering the hierarchical pipelined distributed scheduling traffic manager.

13. A method for traffic management, comprising:

arbitrating, at a queue memory enqueue/dequeue and hierarchical traffic manager admission arbiter, between a plurality of requester groups including a set of one or more new packet enqueue requests and a set of one or more queue reentry requests to select a request to service, wherein the new packet enqueue requests are generated in response to receipt of new packets, and wherein the queue reentry requests are generated in response to a previous winning queue;

admitting the selected request to a hierarchical pipelined distributed traffic manager that includes a lowest level, a set of one or more intermediate levels, and a highest level, wherein the lowest level includes a plurality of nodes each associated with a node at one of the set of intermediate levels, wherein each of the set of intermediate levels includes a plurality of nodes each associated with a plurality of nodes at a lower level and a node at a higher level, and wherein the highest level includes a node associated with a plurality of nodes at a lower level;

selecting a winning queue through hierarchical winner selection and propagation, wherein the hierarchical winner selection and propagation includes,

at each node of each of the set of intermediate levels performing the following;

selecting a winning queue associated between the associated nodes at the lower level, and,

propagating the winning queue to the associated node at the higher level, and

at the node of the highest one of the plurality of levels performing the following;

selecting a winning queue between the associated plurality of nodes at the lower level,

causing the wining queue to exit the hierarchical pipelined distributed traffic manager, and

generating a queue reentry request corresponding to the winning queue.

14. The method of claim 13 wherein the plurality of requestor groups further includes a set of one or more packet dequeue requests that each correspond to a set of one or more packets of a queue that are ready to leave that queue, the method further comprising for each selected packet dequeue request:

decrementing a number of packets currently enqueued in that corresponding queue by a quantity of the set of packets;

decrementing a number of bytes that correspond to the packets currently enqueued in that corresponding queue by an amount of bytes of the set of packets;

decrementing a packet offset value by the quantity of the set of packets; and

transmitting the one or more packets.

15. The method of claim 13 wherein the plurality of requestor groups further includes a set of one or more rate token update requests that each correspond to a queue, the method further comprising for each selected rate token update request:

retrieving a rate token running counter for the queue associated with the rate token update request;

adding one or more tokens to the rate token counter;

responsive to determining that the added tokens cause a rate status change, generating a rate status change request for one of the nodes at one of the intermediate levels.

16. The method of claim 13 wherein the hierarchical pipelined distributed scheduling traffic manager is separated into a plurality of separate sliced hierarchical pipelined distributed scheduling traffic manager that each include their own memories, shapers, and schedulers.

17. The method of claim 13 wherein the queue corresponding to the selected request is admitted into the hierarchical pipelined distributed scheduling traffic manager as a batch of packets, wherein the batch of packets allow for back to back same winning queue selection.

18. The method of claim 13 wherein each of the nodes of the intermediate levels further performs the following:

preempting a previous winning queue with a current winning queue responsive to determining that the current winning queue has a higher arbitration precedence than the previous winning queue; and

propagating the current winning queue to the associated node at the higher level.

19. The method of claim 13 wherein an aggregation ratio between levels is configurable by a system operator.

20. The method of claim 13 wherein the hierarchical pipelined distributed scheduling traffic manager is to perform winning queue selection in parallel.

21. The method of claim 13 wherein at least some of the nodes of one of the intermediate levels is selectively associated with a node at a higher level that is not a next highest level relative to that intermediate level.

22. The method of claim 13 wherein each node at the lowest level and the plurality of intermediate levels is associated with a set of one or more scheduling precedence parameters that are used during hierarchical winner selection and propagation.

23. The method of claim 22 wherein the set of scheduling precedence parameters includes weight tokens, a priority, and rate status, wherein the queue memory enqueue/dequeue and hierarchical traffic manager admission arbiter is further to deduct the length of one or more packets from a weight token that is associated with each queue entering the hierarchical pipelined distributed scheduling traffic manager.