|
Abstract : |
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 rst focus on the dierence between the time a packet nishes service in a scheduling algorithm and its virtual nish 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 log2n) (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, |
