Measuring the Impact of Adversarial Errors on Packet Scheduling Strategies
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.