Patent ID: 7646779

Claim:
An article of manufacture comprising: a machine-accessible storage medium on which is stored a plurality of executable instructions which, when executed on a processor, perform operations comprising: enqueing packet references into a hierarchical packet scheduler, wherein the hierarchical packet scheduler includes one or more levels, each level including one or more schedulers being served by one or more threads, wherein the number of threads serving a particular level is not dependent on the number of schedulers on the particular level; dequeuing packet references from the hierarchical packet scheduler at a root level scheduler of the one or more schedulers; and performing hole-filing operations to fill holes created in the one or more schedulers when packet references are passed toward the root level scheduler, the hole-filing operations including: obtaining a hole-filling message from a message board associated with a parent scheduler of the hierarchical packet scheduler, the parent scheduler having a hole to receive a packet reference; obtaining a state of a child scheduler that is identified in the hole-filling message, wherein the child scheduler includes the packet reference that is to fill the hole of the parent scheduler; identifying a tag packet reference in the child scheduler; and inserting the tag packet reference into the parent scheduler; wherein a first hole-filling operation is performed at a first scheduler without waiting for other hole-filling operations at levels further from the root level to complete.