Improved Online Algorithms for Buffer Management in QoS Switches

摘要

The following buffer management problem is studied: packets with specified weights and deadlines arrive at a network switch and need to be forwarded so that the total weight of forwarded packets is maximized. A packet not forwarded before its deadline brings no profit. The main result is an online 64/33 ≈ 1.939-competitive algorithm, the first deterministic algorithm for this problem with competitive ratio below 2. In the s-uniform case, where for all packets the deadline equals the arrival time plus s, we give an 5 - 10~(1/2) ≈ 1.838-competitive algorithm. This algorithm achieves the same ratio in a more general scenario when all packets are similarly ordered. For the 2-uniform case we give an algorithm with ratio ≈ 1.377 and a matching lower bound.