Patent ID: 8565250

Claim:
A method of scheduling packets for transmission by a hardware network processor having a plurality of processing modules and at least one shared memory, the method comprising: generating, by a traffic manager of the network processor, a scheduling hierarchy comprising a tree structure of a root scheduler and N scheduler levels, wherein a scheduler is a branch node and a queue is a leaf node of the scheduling hierarchy, wherein N is a positive integer; receiving, by the traffic manager, a task provided by one of the plurality of processing modules of the network processor, the task corresponding to each of a plurality of received packets associated with one or more data flows; queuing, by the traffic manager, the received task in an associated queue of the scheduling hierarchy, wherein the queue is associated with the data flow corresponding to the received task, and wherein the queue has a corresponding scheduler level M, the queue having a corresponding parent scheduler at each of M−1 levels in the scheduling hierarchy, wherein M is a positive integer less than or equal to N; in a scheduling cycle of the traffic manager: scheduling, by a parent scheduler, a child node to transmit one or more tasks; responding, by the child node to the parent scheduler, whether the scheduling is accepted, and if so, providing a number of tasks accepted for scheduling; starting at the parent scheduler and iteratively repeating at each scheduling level until reaching the root scheduler of the scheduling hierarchy: maintaining, by each node in the scheduling hierarchy, one or more statistics corresponding to the node, wherein the one or more statistics comprises a scheduled task count; providing the number of tasks accepted for scheduling to a corresponding parent scheduler at a relative next scheduler level; updating the scheduled task count based on the number of tasks accepted for scheduling; and generating, by the traffic manager, one or more corresponding output packets corresponding to the scheduled tasks, thereby achieving a superscalar task scheduling throughput higher than the scheduling cycle of the traffic manager.