A hierarchical packet scheduler using hole-filling and multiple packet buffering. Packet references are enqueued 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. Packet references are dequeued from the hierarchical packet scheduler at a root level scheduler of the one or more schedulers.