Priority Queue Schedulers with Approximate Sorting in Output Buffered Switches


Jorg Liebeherr
Department of Computer Science
University of Virginia
Charlottesville, VA 22903

Dallas Wrege
IBM Corporation
Research Triangle Park, NC 27709


Abstract

All recently proposed packet scheduling algorithms for output-buffered switches which support QoS transmit packets in some priority order, for example, according to deadlines, virtual finishing times, eligibility times, or other timestamps that are associated with a packet. Since maintaining a sorted priority queue introduces significant overhead, much emphasis of QoS scheduler design is put on methods to simplify the task of maintaining a priority queue. In this study, we consider an approach which attempts 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 which approximates the sorted queue of an Earliest-Deadline-First (EDF) scheduler. The approximate scheduler is implemented using a set of prioritized FIFO queues which are periodically relabeled. The scheduler can be efficiently implemented with a fixed number of pointer manipulations, thus, enabling an implementation in hardware. Necessary and sufficient conditions for the worst-case delays of the scheduler with approximate sorting are presented. Numerical examples, including traces based on MPEG video, demonstrate that in realistic scenarios, scheduling with approximate sorting is a viable option.