On Fundamental Tradeoffs between Delay Bounds and Computational Complexity in Packet Scheduling Algorithms. Jun Xu and Richard J. Lipton (Georgia Institute of Technology)

In this work, we clarify, extend and solve an open problem concerning the computational complexity for packet scheduling algorithms to achieve tight end-to-end delay bounds.  We first focus on the difference between the time a packet finishes service in a scheduling
algorithm and its virtual finish time under a GPS (General Processor Sharing) scheduler, called GPS-relative delay.  We prove that, under a slightly restrictive but reasonable computational model, the lower bound computational complexity of any scheduling algorithm that
guarantees O(1) GPS-relative delay bound is Omega(log_2 n) (widely believed as a ``folklore theorem'' but never proved).  We also discover that, surprisingly, the complexity lower bound remains the same even if the delay bound is relaxed to O(n^a) for 0<a<1.  This implies that the delay-complexity tradeoff curve is ``flat'' in the ``interval'' [O(1), O(n)).  We later extend both complexity results (for O(1) or O(n^a) delay) to a much stronger computational model.  Finally, we show that the same complexity lower bounds are conditionally applicable to guaranteeing tight end-to-end delay bounds.  This is done by untangling the relationship between the
GPS-relative delay bound and the end-to-end delay bound.

Papers are provided as a service to all by the members of ACM SIGCOMM.

This paper is available in Adobe PDF format.