Improved Competitive Guarantees for QoS Buffering
We consider a network providing Differentiated Services (Diffserv) which allow Internet service providers (ISP) to offer different levels of Quality of Service (QoS) to different traffic streams. We study FIFO buffering algorithms, where packets must be transmitted in the order they arrive. The buffer space is limited, and packets are lost if the buffer is full. 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 arbitrary packet values that for the first time achieves a competitive ratio better than 2, namely 2-e for a constant e> 0.