One to Rule Them All: A General Randomized Algorithm for Buffer Management with Bounded Delay

摘要

We give a memoryless scale-invariant randomized algorithm MlX-R for buffer management with bounded delay that is e/(e - 1)-competitive against an adaptive adversary, together with better performance guarantees for many restricted variants, including the s-bounded instances. In particular, Mix-R attains the optimum competitive ratio of 4/3 on 2-bounded instances. Both Mix-R and its analysis are applicable to a more general problem, called Item Collection, in which only the relative order between packets' deadlines is known. Mix-R is the optimal memoryless randomized algorithm against adaptive adversary for that problem in a strong sense. While some of the provided upper bounds were already known, in general, they were attained by several different algorithms.