Nearly Optimal FIFO Buffer Management for DiffServ
We consider a FIFO buffer with finite storage space. An arbitrary
input stream of packets arrives at the buffer, but the output stream
rate is bounded, so overflows may occur. Motivated by DiffServ, we
assume that each packet has value either $1$ or $\alpha$, for some
$\alpha>1$. The buffer management task is to decide which packets to
drop so as to minimize the total value of lost packets, subject to
the buffer space bound, and to the FIFO order of sent packets. We
consider push-out buffers, where the algorithm may eject packets
from anywhere in the buffer. The best lower bound on the competitive
ratio of on-line algorithms for buffer
management is approximately $1.28$. In this paper we present an
on-line algorithm whose
competitive ratio is approximately $1.30$ for the \emph{worst case}
$\alpha$. The best previous general upper bound was about
$1.888$.
Click here
for paper (pdf).