On fundamental tradeoffs between delay bounds and computational complexity in packet scheduling algorithms

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 CPS (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) CPS-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.