Böhm, Martin ;
Chrobak, Marek ;
Jez, Lukasz ;
Li, Fei ;
Sgall, Jirí ;
Veselý, Pavel
Online Packet Scheduling with Bounded Delay and Lookahead
Abstract
We study the online boundeddelay packet scheduling problem (PacketScheduling), 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 nonnegative 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 its optimal competitive ratio remains unknown: the best upper bound is 1.828 [Englert and Westermann, SODA 2007], still quite far from the best lower bound of phi approx 1.618 [Hajek, CISS 2001; Andelman et al, SODA 2003; Chin and Fung, Algorithmica, 2003].
In the variant of PacketScheduling with sbounded instances, each packet can be scheduled in at most s consecutive slots, starting at its release time. The lower bound of phi applies even to the special case of 2bounded instances, and a phicompetitive algorithm for 3bounded instances was given in [Chin et al, JDA, 2006]. Improving that result, and addressing a question posed by Goldwasser [SIGACT News, 2010], we present a phicompetitive algorithm for 4bounded instances.
We also study a variant of PacketScheduling where an online algorithm has the additional power of 1lookahead, knowing at time t which packets will arrive at time t+1. For PacketScheduling with 1lookahead restricted to 2bounded instances, we present an online algorithm with competitive ratio frac{1}{2}(sqrt{13}  1) approx 1.303 and we prove a nearly tight lower bound of frac{1}{4}(1 + sqrt{17}) approx 1.281.
BibTeX  Entry
@InProceedings{bhm_et_al:LIPIcs:2016:6790,
author = {Martin B{\"o}hm and Marek Chrobak and Lukasz Jez and Fei Li and Jir{\'i} Sgall and Pavel Vesel{\'y}},
title = {{Online Packet Scheduling with Bounded Delay and Lookahead}},
booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)},
pages = {21:121:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770262},
ISSN = {18688969},
year = {2016},
volume = {64},
editor = {SeokHee Hong},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6790},
URN = {urn:nbn:de:0030drops67901},
doi = {10.4230/LIPIcs.ISAAC.2016.21},
annote = {Keywords: buffer management, online scheduling, online algorithm, lookahead}
}
2016
Keywords: 

buffer management, online scheduling, online algorithm, lookahead 
Seminar: 

27th International Symposium on Algorithms and Computation (ISAAC 2016)

Issue date: 

2016 
Date of publication: 

2016 