Show simple item record

dc.contributor.authorXu, Junen_US
dc.contributor.authorLipton, Richard J.
dc.date.accessioned2005-06-17T17:39:59Z
dc.date.available2005-06-17T17:39:59Z
dc.date.issued2002en_US
dc.identifier.urihttp://hdl.handle.net/1853/6534
dc.description.abstractIn 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 that guarantees O (1) GPS-relative delay bounds is Ω (log₂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 (nª) 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 (na) delay) to a much stronger computational model. Finally, we show that the same complexity lower bounds are applicable to guaranteeing tight end-to-end delay bounds. This is done by untangling the subtle relationship between the GPS-relative delay bound and the end-to-end delay bound.en_US
dc.format.extent307367 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technologyen_US
dc.relation.ispartofseriesCC Technical Report; GIT-CC-02-21en_US
dc.subjectComplexity bounds
dc.subjectComputational models
dc.subjectDelay bounds
dc.subjectPacket scheduling algorithms
dc.subjectGeneral Processor Sharing
dc.subjectGPS
dc.subjectGPS-relative delay
dc.titleOn Fundamental Tradeoffs between Delay Bounds and Computational Complexity in Packet Scheduling Algorithmsen_US
dc.typeTechnical Reporteng_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record