The Library
Online packet scheduling with bounded delay and lookahead
Tools
Böhm, Martin, Chrobak, Marek, Jeż, Łukasz, Li, Fei, Sgall, Jiří and Veselý, Pavel (2019) Online packet scheduling with bounded delay and lookahead. Theoretical Computer Science, 776 . pp. 95-113. doi:10.1016/j.tcs.2019.01.013 ISSN 0304-3975.
|
PDF
WRAP-online-packet-scheduling-bounded-delay-lookahead-Veselý-2019.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (934Kb) | Preview |
Official URL: http://dx.doi.org/10.1016/j.tcs.2019.01.013
Abstract
We study the online bounded-delay packet scheduling problem (Packet Scheduling), where packets of unit size arrive at a router over time and need to be transmitted over a network link. Each packet has two attributes: a non-negative weight and a deadline for its transmission. The objective is to maximize the total weight of the transmitted packets. This problem has been well studied in the literature; yet currently the best published upper bound is 1.828 [8],still quite far from the best lower bound ofφ≈1.618 [11, 2, 6].In the variant of Packet Scheduling with s-bounded instances, each packet can be scheduled in at most s consecutive slots, starting at its release time. The lower bound of φ applies even to the special case of 2-bounded instances, and a φ-competitive algorithm for 3-boundedinstances was given in [5]. Improving that result, and addressing a question posed by Goldwasser [9], we present a φ-competitive algorithm for 4-boundedinstances. We also study a variant of Packet Scheduling where an online algorithm has the additional power of1-lookahead, knowing at time t which packets will arrive at time t+ 1. For Packet Scheduling with 1-lookahead restricted to 2-bounded instances, we present an online algorithm with competitive ratio12(√13−1)≈1.303 and we prove a nearly tight lower boundof14(1 +√17)≈1.281. In fact, our lower bound result is more general: using only 2-boundedinstances, for any integer`≥0 we prove a lower bound of12(`+1)(1 +√5 + 8`+ 4`2) for online algorithms with`-look ahead, i.e., algorithms that at time t can see all packets arriving by time t+`. Finally, for non-restricted instances we show a lower bound of 1.25 for randomized algorithms with`-lookahead, for any`≥0.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software T Technology > TK Electrical engineering. Electronics Nuclear engineering |
||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
Library of Congress Subject Headings (LCSH): | Routers (Computer networks), Computer scheduling | ||||||||
Journal or Publication Title: | Theoretical Computer Science | ||||||||
Publisher: | Elsevier Science BV | ||||||||
ISSN: | 0304-3975 | ||||||||
Official Date: | 12 July 2019 | ||||||||
Dates: |
|
||||||||
Volume: | 776 | ||||||||
Page Range: | pp. 95-113 | ||||||||
DOI: | 10.1016/j.tcs.2019.01.013 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Date of first compliant deposit: | 28 March 2019 | ||||||||
Date of first compliant Open Access: | 11 January 2020 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year