The Library
Considering suppressed packets improves buffer management in quality of service switches
Tools
Tools
Tools
Englert, Matthias and Westermann, Matthias (2012) Considering suppressed packets improves buffer management in quality of service switches. SIAM Journal on Computing, Volume 41 (Number 5). pp. 1166-1192. doi:10.1137/110856745
Research output not available from this repository, contact author.
Official URL: http://dx.doi.org/10.1137/110856745
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.
| Item Type: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Divisions: | Faculty of Science > Computer Science | ||||||||
| Journal or Publication Title: | SIAM Journal on Computing | ||||||||
| Publisher: | SIAM | ||||||||
| ISSN: | 0097-5397 | ||||||||
| Official Date: | 11 September 2012 | ||||||||
| Dates: |
|
||||||||
| Volume: | Volume 41 | ||||||||
| Number: | Number 5 | ||||||||
| Number of Pages: | 27 | ||||||||
| Page Range: | pp. 1166-1192 | ||||||||
| DOI: | 10.1137/110856745 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| Adapted As: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
