Packet scheduling using hierarchical scheduling process
First Claim
1. A method of routing data traffic over a communication network, said method comprising:
- mapping incoming data traffic into data groups based on service categories, wherein a respective data group is assigned to nodes of different levels in a scheduling tree, wherein said scheduling tree comprises;
a bottom root level, wherein each node in said root level represent a respective egress port of a plurality of egress ports of said data routing device;
a plurality of intermediate levels; and
a top level, wherein each node in said top level represents a respective data group of said data groups, wherein said respective data group corresponds to a queue, traversing said scheduling tree from said bottom level to said top level, wherein said traversing comprises;
selecting an egress port from said plurality of egress ports of said data routing device;
responsive to a selection of said egress port, selecting an upper node in a first intermediate level of said scheduling tree according to a scheduling process based on values of a set of attributes associated with said upper node, wherein said upper node is associated with a lower node in a second intermediate level of said scheduling tree that has been selected according to a prior scheduling process, wherein selected nodes at different intermediate levels in the scheduling tree correspond to respective data groups based on service categories in different granularity levels;
responsive to said selection of said egress port and responsive to selections of nodes in said plurality of said intermediate levels, selecting a data group from the data groups; and
sending data in said data group to said egress port for 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. As a result, a queue associated with the winner nodes in various levels is selected and data from the queue is read out and sent to the selected egress port for transmission.
-
Citations
20 Claims
-
1. A method of routing data traffic over a communication network, said method comprising:
- mapping incoming data traffic into data groups based on service categories, wherein a respective data group is assigned to nodes of different levels in a scheduling tree, wherein said scheduling tree comprises;
a bottom root level, wherein each node in said root level represent a respective egress port of a plurality of egress ports of said data routing device;
a plurality of intermediate levels; and
a top level, wherein each node in said top level represents a respective data group of said data groups, wherein said respective data group corresponds to a queue, traversing said scheduling tree from said bottom level to said top level, wherein said traversing comprises;selecting an egress port from said plurality of egress ports of said data routing device;
responsive to a selection of said egress port, selecting an upper node in a first intermediate level of said scheduling tree according to a scheduling process based on values of a set of attributes associated with said upper node, wherein said upper node is associated with a lower node in a second intermediate level of said scheduling tree that has been selected according to a prior scheduling process, wherein selected nodes at different intermediate levels in the scheduling tree correspond to respective data groups based on service categories in different granularity levels;
responsive to said selection of said egress port and responsive to selections of nodes in said plurality of said intermediate levels, selecting a data group from the data groups; and
sending data in said data group to said egress port for transmission. - View Dependent Claims (2, 3, 4, 5, 6, 7)
- mapping incoming data traffic into data groups based on service categories, wherein a respective data group is assigned to nodes of different levels in a scheduling tree, wherein said scheduling tree comprises;
-
8. 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 port and configured to store said data streams; a plurality of egress ports coupled to the buffer unit and configured to transmit said data streams; a first circuitry coupled to the ingress port and the buffer unit and the first circuitry configured to map incoming data traffic into data groups based on service categories, wherein a respective data group is assigned to nodes of different levels in a scheduling tree; and scheduler circuitry coupled to said first circuitry and configured to; select an egress port from the plurality of egress ports, wherein the plurality of egress ports correspond to a single level of said scheduling tree; responsive to a selection of said egress port, select an upper node of said scheduling tree according to a scheduling process based on values of a set of attributes associated with said upper node, wherein said upper node of said scheduling tree is associated with a lower node of said scheduling tree that has been selected according to a prior scheduling process, wherein selected nodes at different levels of said scheduling tree correspond to data groups based on service categories in different granularity levels; and responsive to a selection of said egress port and responsive to selections of nodes in intermediate levels of said scheduling tree, select a data group from the data groups, the selected data group corresponding to a queue associated with the selected nodes of said scheduling tree. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
-
15. A method of scheduling data traffic at a data routing 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; a bottom level of said hierarchy corresponds to a plurality of egress ports, an intermediate level of said hierarchy comprises a plurality of categories and a respective category in said intermediate level has a subordinate category; and a top level of said hierarchy corresponds to queues in said buffer; and
scheduling data transmission from selected queues in said buffer to a selected egress port of said data routing device in accordance with a scheduling tree process, wherein said scheduling tree process comprises traversing from said bottom level to said top level, the egress port initially being selected from the plurality of egress ports at said bottom level of said hierarchy, the queues being selected at said top level of said hierarchy, and categories being selected at respective levels of said hierarchy, wherein said selected categories at different levels of said hierarchy correspond to data groups based on service categories associated with said selected egress port and in different granularity levels. - View Dependent Claims (16, 17, 18, 19, 20)
-
Specification