Randomized competitive algorithms for online buffer management in the adaptive adversary model

摘要

In the problem of buffer management with bounded delay, packets with weights and deadlines arrive at a network switch over time, and the goal is to send those packets on the outgoing link while maximizing the total weight of the packets that are sent before their deadlines. We present a study of randomized algorithms that are competitive against an adaptive adversary. Previous studies considered only the oblivious adversary model that does not capture dependency of network traffic on the packet scheduling algorithm. We give a new analysis of a previously known algorithm, which shows that it remains e/(e - 1)-competitive even against an adaptive adversary. We complement this with a 4/3 lower bound on the competitive ratio on 2-bounded instances, in which each packet has a lifespan of one or two steps. We also study more restricted 2-uniform instances, in which every packet has a lifespan of exactly two steps. For such instances we give a 1.2 lower bound on the competitive ratio of arbitrary algorithms and 4/3 lower bound on the competitive ratio of memoryless scale-invariant algorithms. Finally, we devise a 4/3-competitive memoryless scale-invariant algorithm for 2-bounded instances, matching two of these lower bounds.