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. |