Packet scheduling using hierarchical scheduling process with priority propagation
First Claim
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, and wherein a priority is associated with said respective data group;
changing said priority of said respective data group responsive to a new data packet mapped to said respective data group or a data packet leaving said respective data group;
responsive to said priority of said respective data group being changed, dynamically updating priorities of said nodes of said different levels;
traversing said scheduling tree from a bottom level to a top level to select a data group for transmission through an egress port of a plurality of egress ports of a data routing device, wherein said bottom level comprises said plurality of egress ports of said data routing device, wherein said traversing comprises;
selecting said egress port from said plurality of egress ports;
responsive to said selecting said egress port, selecting an upper node according to a scheduling process, wherein said scheduling process is based on;
state information of a lower node that is arranged in a lower level in said scheduling tree than said upper node, wherein said lower node has been selected according to a prior scheduling process during said traversing said scheduling tree, andupdated priorities of nodes in a same level with said upper node, wherein said upper node is arranged in a subtree of said lower node in said scheduling tree; and
identifying a data group, wherein said identified data group is associated with all nodes that are selected during said traversing said scheduling tree; and
sending data in said identified data group to said selected egress port for said transmission.
8 Assignments
0 Petitions
Accused Products
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.
6 Citations
18 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, and wherein a priority is associated with said respective data group; changing said priority of said respective data group responsive to a new data packet mapped to said respective data group or a data packet leaving said respective data group; responsive to said priority of said respective data group being changed, dynamically updating priorities of said nodes of said different levels; traversing said scheduling tree from a bottom level to a top level to select a data group for transmission through an egress port of a plurality of egress ports of a data routing device, wherein said bottom level comprises said plurality of egress ports of said data routing device, wherein said traversing comprises; selecting said egress port from said plurality of egress ports; responsive to said selecting said egress port, selecting an upper node according to a scheduling process, wherein said scheduling process is based on; state information of a lower node that is arranged in a lower level in said scheduling tree than said upper node, wherein said lower node has been selected according to a prior scheduling process during said traversing said scheduling tree, and updated priorities of nodes in a same level with said upper node, wherein said upper node is arranged in a subtree of said lower node in said scheduling tree; and identifying a data group, wherein said identified data group is associated with all nodes that are selected during said traversing said scheduling tree; and sending data in said identified data group to said selected egress port for said transmission. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. An apparatus for routing data over a communication network, said apparatus comprising:
-
ingress ports configured to receive data streams; a buffer unit coupled to said ingress ports and configured to store said data streams; egress ports coupled to said buffer unit and configured to transmit said data streams; first logic coupled to said ingress ports and said 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 wherein a priority is associated with said respective data group; and an arbiter coupled to said first logic and configured to; change said priority of said respective data group responsive to a new data packet mapped to said respective data group or a data packet leaving said respective data group; responsive to said priority of said respective data group being changed, dynamically update priorities of said nodes of said different levels; traverse said scheduling tree from a bottom level to a top level to select a data group for transmission through an egress port of a plurality of egress ports, wherein said bottom level comprises said plurality of egress ports, wherein to traverse said scheduling tree, said arbiter is configured to; select said egress port from said plurality of egress ports; responsive to said selection of said egress port, select an upper node according to a scheduling process, wherein said scheduling process is based on; state information of a lower node that is arranged in a lower level in said scheduling tree than said upper node, wherein said lower node has been selected according to a prior scheduling process during said traversal of said scheduling tree, and updated priorities of nodes in a same level with said upper node, wherein said upper node is in a subtree of said lower node in said scheduling tree; and identify a data group, wherein said identified data group is associated with all nodes that are selected during said traversal of said scheduling tree; and send data in said identified data group to said selected egress port for said transmission. - View Dependent Claims (9, 10, 11, 12, 13)
-
-
14. 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 a priority is associated with a respective data group of said data groups, wherein said data groups are classified based on a hierarchy, wherein;
a bottom level of said hierarchy comprises a plurality of egress ports of said network switching device; and
an intermediate level of said hierarchy comprises a plurality of categories, and wherein a respective category in said intermediate level has a subordinate category;updating said priority of said respective data group responsive to a new data packet mapped to said respective data group or a data packet leaves said respective data group; responsive to said priority of said 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; traversing said hierarchy from said bottom level a top level thereof to select a data group for transmission through an egress port of said plurality of egress ports, wherein said traversing comprises; selecting said egress port from said plurality of egress ports; responsive to said selecting said egress port, selecting a category for a respective level according to a scheduling process, wherein said scheduling process is based on; state information of a selected category in another level that is arranged in a lower level than said respective level, wherein said selected category in said another level has been selected according to a prior scheduling process during said traversing said hierarchy, and updated priorities associated with categories in said respective level, wherein said selected category for said respective level is a subordinate of said selected category in said another level; and identifying a data group associated with all categories in various levels of said hierarchy; and sending data in said identified data group to said selected egress port for said transmission. - View Dependent Claims (15, 16, 17, 18)
-
Specification