Patent ID: 8230110

Claim:
A method comprising: storing, with a network device, data defining a plurality of nodes arranged in a hierarchical ordering from a root node to a plurality of leaf nodes, wherein each of the hierarchically-ordered nodes identify a relationship between the root node and the leaf nodes of the hierarchically-ordered nodes, and wherein each of the leaf nodes is associated with a different one of a plurality of queues storing one or more portions corresponding to at least one network packet, wherein the root node represents a network interface of the network device that provides a maximum bandwidth and the remaining nodes of the plurality of nodes represent allocations of portions of the maximum bandwidth provided by the network interface; storing, with the network device, corresponding scheduling data for the nodes of the hierarchical ordering, wherein the scheduling data defines for each of the root node and those of plurality of nodes positioned between the root node and the plurality of leaf nodes, a child count that indicates a total number of the plurality of nodes that depend from each of the root node and those of the plurality of nodes positioned between the root node and the plurality of leaf nodes, and wherein the scheduling data also defines for each of the plurality of leaf nodes a queue depth that indicates a total number of portions of packets stored by those queues of the plurality of queues associated with each of the plurality of leaf nodes; executing, with the network device, a first dequeue operation to traverse the plurality of hierarchically-ordered nodes and schedule processing of a portion of a first packet stored to one of the plurality of queues, wherein during execution, the first dequeue operation selects one of the plurality of queues while traversing the plurality of hierarchically-ordered nodes and, upon selecting the one of the plurality of queues, updates the scheduling data associated with at least one of the plurality of hierarchically-ordered nodes from which the selected one of the queues depends in the hierarchical ordering; and executing, with the network device, a second dequeue operation concurrently with the execution of the first dequeue operation; masking, with the first dequeue operation of the network device, at least one of the selected ones of the plurality of hierarchically-ordered nodes from which the selected one of the queues depends in the hierarchical ordering based on the updated scheduling data to exclude the node from consideration by the second dequeue operation concurrently executing with the first dequeue operation, wherein during execution, the second dequeue operation traverses the plurality of hierarchically-ordered nodes and schedules delivery of a portion of a second packet stored to one of the plurality of queues; and processing the portion of the first packet and the portion of the second packet with the network device as these portions are dequeued.