Online Packet Scheduling Under Adversarial Jamming

Abstract

We consider the problem of scheduling packets of different lengths via a directed communication link prone to jamming errors. Dynamic packet arrivals and errors are modelled 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\ge 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).

This work was supported by the Polish National Science Centre grant DEC-2012/06/M/ST6/00459.