Priority queue schedulers with approximate sorting in output-buffered switches

All recently proposed packet-scheduling algorithms for output-buffered swit ches that support quality-of-service (QoS) transmit packets in some priorit y order, e.g., according to deadlines, virtual finishing times, eligibility times, or other time stamps that are associated with a packet. Since maint aining a sorted priority queue introduces significant overhead, much emphas is on QoS scheduler design is put on methods to simplify the task of mainta ining a priority queue. In this paper, we consider an approach that attempt s to approximate a sorted priority queue at an output-buffered switch. The goal is to trade off less accurate sorting for lower computational overhead . Specifically, this paper presents a scheduler that approximates the sorte d queue of an earliest-deadline-first (EDF) scheduler. The approximate sche duler is implemented using a set of prioritized first-in/first-out (FTFO) q ueues that are periodically relabeled. The scheduler can be efficiently imp lemented with a fixed number of pointer manipulations, thus enabling an imp lementation in hardware. Necessary and sufficient conditions for the worst- case delays of the scheduler with approximate sorting are presented. Numeri cal examples, including traces based on MPEG video, demonstrate that in rea listic scenarios, scheduling with approximate sorting is a viable option.