TY - GEN
T1 - Online packet scheduling under adversarial jamming
AU - Jurdzinski, Tomasz
AU - Kowalski, Dariusz R.
AU - Lorys, Krzysztof
N1 - Funding Information:
This work was supported by the Polish National Science Centre grant DEC-2012/06/M/ST6/00459.
Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - We consider the problem of scheduling packets of different lengths via a directed communication link prone to jamming errors. Dynamic packet arrivals and errors aremodelled by an adversary. We focus on estimating competitive throughput of online scheduling algorithms. We design an online algorithm for scheduling packets of arbitrary lengths, achieving optimal competitive throughput in (1/3, 1/2] (the exact value depends on packet lengths). Another algorithm we design makes use of additional resources in order to achieve competitive throughput 1, that is, it achieves at least as high throughput as the best schedule without such resources, for any arrival and jamming patterns. More precisely, we show that if the algorithm can run with double speed, i.e., with twice higher frequency, then its competitive throughput is 1. This demonstrates that throughput of the best online fault-tolerant scheduling algorithms scales well with resource augmentation. Finally, we generalize the first of our algorithms to the case of any f ≥ 1 channels and obtain competitive throughput 1/2 in this setting in case packets lengths are pairwise divisible (i.e., any larger is divisible by any smaller).
AB - We consider the problem of scheduling packets of different lengths via a directed communication link prone to jamming errors. Dynamic packet arrivals and errors aremodelled by an adversary. We focus on estimating competitive throughput of online scheduling algorithms. We design an online algorithm for scheduling packets of arbitrary lengths, achieving optimal competitive throughput in (1/3, 1/2] (the exact value depends on packet lengths). Another algorithm we design makes use of additional resources in order to achieve competitive throughput 1, that is, it achieves at least as high throughput as the best schedule without such resources, for any arrival and jamming patterns. More precisely, we show that if the algorithm can run with double speed, i.e., with twice higher frequency, then its competitive throughput is 1. This demonstrates that throughput of the best online fault-tolerant scheduling algorithms scales well with resource augmentation. Finally, we generalize the first of our algorithms to the case of any f ≥ 1 channels and obtain competitive throughput 1/2 in this setting in case packets lengths are pairwise divisible (i.e., any larger is divisible by any smaller).
KW - Adversarial jamming
KW - Competitive throughput
KW - Online algorithms
KW - Packet scheduling
KW - Resource augmentation
UR - http://www.scopus.com/inward/record.url?scp=84942526059&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84942526059&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-18263-6_17
DO - 10.1007/978-3-319-18263-6_17
M3 - Conference contribution
AN - SCOPUS:84942526059
SN - 9783319182629
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 193
EP - 206
BT - Approximation and Online Algorithms - 12th International Workshop, WAOA 2014, Revised Selected Papers
A2 - Svensson, Ola
A2 - Bampis, Evripidis
PB - Springer Verlag
T2 - 12th International Workshop on Approximation and Online Algorithms, WAOA 2014
Y2 - 11 September 2014 through 12 September 2014
ER -