Improved competitive guarantees for QoS buffering

We consider a network providing Differentiated Services (Diffserv), which allow Internet Service Providers (ISP s) to offer different levels of Quality of Service (QoS) to different traffic streams. We study two types of buffering policies that are used in network switches supporting QoS. In the FIFO type, packets must be transmitted in the order they arrive. In the uniform bounded-delay type, there is a maximum delay time associated with the switch and each packet must be transmitted within this time, or otherwise it is dropped. In both models, the buffer space is limited, and packets are lost when the buffer overflows. Each packet has an intrinsic value, and the goal is to maximize the total value of transmitted packets. Our main contribution is an algorithm for the FIFO model with arbitrary packet values that for the first time achieves a competitive ratio better than 2, namely 2 - epsilon for a constant epsilon > 0. We also describe an algorithm for the uniform bounded delay model which simulates our algorithm for the FIFO model, and show that it achieves the same competitive ratio.