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