SI-WF2Q: WF2Q Approximation with Small Constant Execution Overhead

Martin Karsten

This paper presents a novel priority queue data structure and access operations for timer maintenance in the context of traffic shaping and scheduling in packet networks. The data structure and operations are used to construct an efficient General Processor Sharing (GPS) approximation scheduler. In contrast to existing proposals, this scheduler has constant and near-optimal delay and fairness properties, and can be implemented with bounded amortized O(1) algorithmic complexity, and has very low absolute execution overhead. The paper presents the data structure, the scheduling algorithm, and studies its execution complexity. The scheduling properties are analyzed and shown to relate nicely to existing work. Some illustrative simulation results are presented to reaffirm those properties.

IEEE Infocom 2006

Technical Report (with proofs):  PS / PDF (DOI)
Presentation Slides (OpenDocument Presentation, OpenOffice)

Important Copyright Notice:

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.