Considering Suppressed Packets Improves Buffer Management in Quality of Service Switches
Authors:
- Matthias EnglertMEMatthias Englert
- Matthias WestermannMWMatthias Westermann
- 1 January 2012
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 41 (5) , 1166-1192
Abstract
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.
Keywords
This publication has 20 references indexed in Scilit:
- Randomized competitive algorithms for online buffer management in the adaptive adversary modelTheoretical Computer Science, 2011
- Buffer Management for Colored Packets with DeadlinesTheory of Computing Systems, 2011
- Bounded delay packet scheduling in a bounded bufferOperations Research Letters, 2010
- A survey of buffer management policies for packet switchesACM SIGACT News, 2010
- Lower and Upper Bounds on FIFO Buffer Management in QoS SwitchesAlgorithmica, 2008
- Improved online algorithms for buffer management in QoS switchesACM Transactions on Algorithms, 2007
- Online competitive algorithms for maximizing weighted throughput of unit jobsJournal of Discrete Algorithms, 2006
- Buffer Overflow Management in QoS SwitchesSIAM Journal on Computing, 2004
- Online Scheduling with Partial Job Values: Does Timesharing or Randomization Help?Algorithmica, 2003
- Competitive On-Line Scheduling with Level of ServiceJournal of Scheduling, 2003