Randomized algorithms for Buffer Management with 2-Bounded Delay

Abstract. 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 maximiz-ing the total weight of the packets that are sent before their deadlines expire. In the 2-bounded delay case, each packet has to be sent either in the step of its release or in the next step. In the deterministic case, the optimal competitive ratio for this case is φ ≈ 1.618. In the randomized case, against oblivious adversaries, the optimal competitive ratio is 1.25. The only yet unresolved case is that of randomized algorithms against adaptive adversaries. For this case, we give a complete solution by prov-ing that the optimal competitive ratio is 4/3. Additionally, we give a lower bound of 1.2 for the 2-uniform case.