Improved Competitive Guarantees for QoS Buffering
AbstractWe consider a network providing Differentiated
Services (DiffServ), which allow Internet Service
Providers (ISPs) 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 maximal 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-ε for a constant ε gt; 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.