PACKET SCHEDULING USING HIERARCHICAL SCHEDULING PROCESS WITH PRIORITY PROPAGATION

• US 20160142331A1
• Filed: 11/14/2014
• Published: 05/19/2016
• Est. Priority Date: 11/14/2014
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: XPLIANT, INC. (Marvell Technology Group Limited)
• Inventors: DANIEL, Tsahi, PANCHAGNULA, Vamsi
• Granted Patent: US 10,447,608 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 47/60 implementing hierarchical scheduling
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority

Abstract

System and method of data routing according to a hierarchical scheduling process. Incoming data traffic is allocated to various queues of a buffer. A scheduling tree has a top level for queues, a bottom level for egress ports, and a plurality of intermediate levels corresponding to different granularities with respect to service categories. Each queue is assigned to a particular node in each intermediate level of the scheduling tree. The scheduling tree traverses through multiple scheduling stages from the bottom to the top level to select a winner node in each level based on a variety of fairness and differentiating variables. A queue associated with the winner nodes in various levels is selected for outgoing transmission at the selected egress port. Priority information is dynamically propagated from upper nodes to lower nodes such that a subsequent scheduling process uses the updated priority information.

Claims

1. A method of routing data traffic over a communication network, said method comprising:

mapping incoming data traffic into data groups, wherein a respective data group is assigned to nodes of different levels in a scheduling tree;

responsive to a priority of said respective data group being changed, dynamically updating priorities of said nodes of said different levels;

selecting an egress port of a data routing device;

based on said egress port, selecting an upper node according to a scheduling process based on updated priorities of nodes in a same level with said upper node, wherein said upper node is in a subtree of a lower node that has been selected according to a prior scheduling process;

selecting a data group associated with selected nodes of said scheduling tree; and

sending data in a selected data group to said egress port for transmission.

3. The method as described in claim 1, wherein said dynamically updating comprises propagating an updated priority of said respective data group to said nodes in said different levels.

4. The method as described in claim 3, wherein said propagating comprises determining an updated priority for a first node that is associated with said respective data group by comparing updated priorities of a plurality of data groups that are associated with said first node.

5. The method as described in claim 1 further comprising buffering said incoming data traffic, wherein said data groups correspond to queues in a buffer.

6. The method as described in claim 1, wherein said nodes of said different levels correspond to network service categories in different granularity levels.

7. The method as described in claim 1, wherein said selecting said egress port comprises selecting said egress port in accordance with a pipeline scheduler process.

8. The method as described in claim 1, wherein said priority of said respective data group is changed responsive to a new data packet mapped to said respective data group.

2. The method as described in claim 2, wherein said scheduling process comprises a Deficit Weighted Round Robin (DWRR) process, and wherein said scheduling process is further based on variables representing strict priority enable, weight, and token bucket.

9. An apparatus for routing data over a communication network, said apparatus comprising:

an ingress port configured to receive data streams;

a buffer unit coupled to the ingress ports and configured to store said data streams;

egress ports coupled to the buffer unit and configured to transmit said data streams;

first logic coupled to the ingress port and the buffer unit and configured to;

map incoming data traffic into data groups, wherein a respective data group is assigned to nodes of different levels in a scheduling tree; and

an arbiter coupled to the data mapping logic and configured to;

responsive to a priority of said respective data group being changed, dynamically update priorities of said nodes of said different levels;

select an egress port;

based on said egress port, select an upper node according to a scheduling process based on updated priorities of nodes in a same level with said upper node, wherein said upper node is in a subtree of a lower node that has been selected according to a prior scheduling process;

select a data group associated with selected nodes of said scheduling tree for outgoing transmission at said egress port.

10. The apparatus as described in claim 9, wherein said scheduling process comprises a Deficit Weighted Round Robin (DWRR) process and is further based on variables representing strict priority enable, weight, and token bucket.

11. The apparatus as described in claim 9, wherein said scheduling tree is user customizable.

12. The apparatus as described in claim 9, wherein said arbiter is further configured to propagate an updated priority of said respective data group to said nodes of said different levels.

13. The apparatus as described in claim 9, wherein said arbiter is further configured to determine an updated priority for a first node of said nodes by comparing updated priorities of a plurality of data groups that are associated with said first node.

14. The apparatus as described in claim 13, wherein said priority of said respective data group is changed responsive to a new data packet mapped to said respective data group.

15. The apparatus as described in claim 9, wherein said first circuitry and said arbiter are integrated in an Application-Specific Integrated Circuit (ASIC).

16. A method of scheduling data traffic at a network switching device, said method comprising:

mapping incoming data traffic into data groups in a buffer, wherein said data groups are classified based on a hierarchy, wherein;

an intermediate level of said hierarchy comprises a plurality of categories; and

a respective category in said intermediate level has a subordinate category; and

selecting an egress port of said network switching device;

responsive to a priority of a respective data group being updated, propagating an updated priority of said respective data group to categories associated with said respective data group across said hierarchy;

based on said egress port, selecting a category for a respective level according to a scheduling process based on updated priorities associated with categories in said respective level, wherein a selected category for said respective level is a subordinate of a selected category in another level that has been selected according to a prior scheduling process;

identifying a data group associated with selected categories in various levels of said hierarchy; and

sending data in an identified data group to said egress port for transmission.

17. The method as described in claim 16, wherein said scheduling comprises selecting an egress port of a network switching apparatus in accordance with a pipeline scheduling process.

18. The method as described in claim 17, wherein said propagating comprises computing an updated priority for a first category by selecting a highest priority among subordinate categories of said first category, wherein said first category is associated with said respective data group.

19. The method as described in claim 18, wherein said scheduling process is further based on variables representing strict priority enable, weight, and credit bucket shaper.

20. The method as described in claim 19, wherein said scheduling process comprises a Deficit Weighted Round Robin (DWRR) process, and wherein further said selected categories of said various levels of said hierarchy correspond to network user groups in different granularity levels.