Many network devices are configured to provide different quality of service (QoS) levels for different types/classes of traffic. When processing packets associated with a particular traffic class, for example, a network device may ensure that transmission latency is below a certain threshold, ensure that the drop/loss rate is below a certain threshold, apply “best efforts,” etc. The QoS level for a particular packet can be important, for example, when multiple packets are forwarded to a single egress port of a network device (e.g., a bridge), and therefore must contend for access to the egress port. In some network devices, each egress port is associated with multiple queues associated with various QoS levels, and a scheduler determines the order in which packets associated with the different queues/QoS levels are sent to the egress port for transmission over the network.
Schedulers in network devices typically implement scheduling hierarchies/trees in which each queue is associated with a leaf node of the tree. “Winning” queues are identified at various intermediate nodes within each hierarchy level, and passed to the next hierarchy level, until the next queue to be de-queued is identified at the root node of the tree. Conventional schedulers of this sort utilize a pipeline architecture that, in any given processing cycle, can process only one eligibility update at each level of the scheduling hierarchy. In network devices where the queue manager sends the scheduler only a single eligibility update at a time, this may not be problematic. Conventionally, the queue manager is capable of sending the scheduler more than one eligibility update at a time, however, conventional schedulers may lose/drop some or all of the eligibility updates that arrive in parallel with other eligibility updates, thereby increasing latencies for traffic associated with the dropped updates.