Our main contribution is a thorough investigation of the natural greedy algorithms in various models. For the FIFO model we prove tight bounds on the competitive ratio of the greedy algorithm that discards the packets with the lowest value. We also prove that the greedy algorithm that drops the earliest packets among all low-value packets is the best greedy algorithm. This algorithm can be as much as $1.5$ times better than the standard tail-drop policy, that drops the latest packets.

In the bounded delay model we show that the competitive ratio of any online algorithm for a uniform bounded delay buffer is bounded away from $1$, independent of the delay size. We analyze the greedy algorithm in the general case and in three special cases: delay bound $2$; link bandwidth $1$; and only two possible packet values.

Finally, we consider the off-line scenario. We give efficient optimal algorithms and study the relation between the bounded-delay and FIFO models in this case.

Click here for paper (pdf).