Online packet scheduling under adversarial errors

We consider the problem of scheduling packets of different sizes via a directed communication link prone to errors, where dynamic packet arrivals and errors are modeled by an adversary. Packets arrive over time to be transmitted over a channel in which instantaneous errors occur at times not known to the algorithm in advance. We focus on estimating the competitive throughput of online scheduling algorithms defined as the ratio between the total size of packets successfully transmitted by an online algorithm and the largest total size of packets which can be transmitted for the same arrival and error patterns. First, we design two online algorithms with optimal competitive throughput in various scenarios. One algorithm works for any f≥1 channels and attains the competitive throughput 1/2 provided that sizes of packets satisfy the divisibility property (i.e., any larger size is divisible by any smaller). The other algorithm achieves the optimal competitive throughput in (1/3,1/2] for arbitrary sizes of packets on one communication channel, where the exact value of the competitive throughput depends on the sizes of packets. Second, we focus on algorithms working with speedup s≥1. In this setting, online algorithms transmit packets s times faster than the offline optimum solution they are compared against. We design an algorithm which attains the competitive throughput 1 if it works with speedup 2 in the case that sizes of packets satisfy the divisibility property and with speedup s∈[4,6) for arbitrary sizes of packets. This demonstrates that throughput of the best online fault-tolerant scheduling algorithms scales well with resource augmentation.