Considering Suppressed Packets Improves Buffer Management in Quality of Service Switches
Matthias Englert, Matthias Westermann · SIAM Journal on Computing · 2012
The following buffer management problem arises in network switches providing different levels of services: At the beginning of each time step, one packet can be sent, and afterward an arbitrary number of new packets arrive. Packets that are not sent can be stored in a buffer. Each packet has a deadline, and a packet is automatically deleted from the buffer if it is still stored in the buffer by the end of its deadline. Additionally, each packet has a value which reflects its importance. A buffer management strategy determines the packet to be sent in each time step. The goal of a buffer management strategy is to maximize the sum of the values of sent packets. We introduce the concept of suppressed packets and present a deterministic strategy that is based on this concept. We show that this strategy achieves a competitive ratio of $2 \sqrt{2} - 1 \approx 1.828$, which is the best known competitive ratio in the deterministic case. In addition, we present a memoryless version of this strategy that achieves a competitive ratio of $\approx 1.893$. This is the first memoryless strategy that achieves a competitive ratio less than 2. Altogether, this demonstrates the potential of the concept of suppressed packets.