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 fa 1.377 and a matching lower bound.
展开▼
