Measuring the Impact of Adversarial Errors on Packet Scheduling Strategies

Date Added: Jun 2013
Format: PDF

In this paper, the authors explore the problem of achieving efficient packet transmission over unreliable links with worst case occurrence of errors. In such a setup, even an omniscient offline scheduling strategy cannot achieve stability of the packet queue, nor is it able to use up all the available bandwidth. Hence, an important first step is to identify an appropriate metric for measuring the efficiency of scheduling strategies in such a setting. To this end, they propose a relative throughput metric which corresponds to the long term competitive ratio of the algorithm with respect to the optimal.