Improved Competitive Guarantees for QoS Buffering

Alexander Kesselman, Yishay Mansour, Rob van Stee

Abstract

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-ε for a constant ε> 0.
BibTeX
@inproceedings{kesselman2005improved,
  author = {Alexander Kesselman and Yishay Mansour and Rob van Stee},
  title = {{Improved Competitive Guarantees for QoS Buffering}},
  booktitle = {Algorithmica},
  year = {2005},
  url = {https://openreview.net/forum?id=GMr6ePevH4R},
}

Loading related content...

Figure