The Library
Considering suppressed packets improves buffer management in QoS switches
Tools
Englert, Matthias and Westermann, Matthias (2007) Considering suppressed packets improves buffer management in QoS switches. In: ACM-SIAM symposium on Discrete algorithms, 7-9 Jan 2007, New Orleans, Louisiana. Published in: ACM-SIAM symposium on Discrete algorithms pp. 209-218. doi:10.1145/1283383.1283406
PDF
p209-englert.pdf Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (417Kb) |
Official URL: http://portal.acm.org/citation.cfm?doid=1283383.12...
Abstract
The following buffer management problem arises in network switches providing differentiated services: At the beginning of each time step, one packet can be sent, and afterwards an arbitrary number of new packets arrive. Packets that are not sent can be stored in a buffer. Each packet is attributed by 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. The differentiated service model is abstracted by attributing each packet with a value according to its service level. 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√2--1 ≈ 1.828, which is the best known competitive ratio in the deterministic case. Further, we present a memoryless version of this strategy that achieves a competitive ratio of ≈ 1.893. This is the first memoryless strategy that achieves a competitive ratio less than 2, and the competitive ratio of this strategy is even better than the ratios of all previously known deterministic strategies. This demonstrates the potential of the concept of suppressed packets. In addition, we present a simple strategy that achieves the optimal competitive ratio of min{(1 + α)/α, 2α/(α+1)} ≤ √2, if only two packet values 1 and α > 1 are possible.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | ACM-SIAM symposium on Discrete algorithms | ||||
Publisher: | Association for Computing Machinery | ||||
Official Date: | 7 January 2007 | ||||
Dates: |
|
||||
Page Range: | pp. 209-218 | ||||
DOI: | 10.1145/1283383.1283406 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | ACM-SIAM symposium on Discrete algorithms | ||||
Type of Event: | Conference | ||||
Location of Event: | 7-9 Jan 2007 | ||||
Date(s) of Event: | New Orleans, Louisiana |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |