A near-optimal packet scheduler for QoS networks

A packet scheduler in a quality-of-service (QoS) network should be sophisticated enough to support stringent QoS constraints at high loads, but it must also have a simple implementation so that packets can be processed at the speed of the transmission link. The earliest-deadline-first (EDF) scheduler is the optimal scheduler for bounded-delay services in the sense that it provides the tightest delay guarantees of any scheduler, but an implementation of EDF requires the sorting of packets, a complex operation that is not practical for high-speed networks. In this study we present the design, implementation and analysis of the novel rotating-priority-queues⁺ (RPQ⁺) scheduler that is near-optimal in the sense that it can approximate EDF with arbitrary precision. The RPQ⁺ scheduler uses a set of prioritized FIFO queues whose priorities are rearranged (rotated) periodically to increase the priority of waiting packets. We derive admission control tests for RPQ⁺ and show that it has the following desirable properties: its implementation requires operations independent of the number of queued packets, it can provide worst-case delay guarantees, and its efficiency is “between” that of EDF and static-priority (SP) schedulers. We use numerical examples, including examples based on MPEG video, to show that in realistic scenarios RPQ⁺ can closely approximate EDF even for infrequent queue rotations