The Library
Lower and upper bounds on FIFO buffer management in QoS switches
Tools
Englert, Matthias and Westermann, Matthias (2006) Lower and upper bounds on FIFO buffer management in QoS switches. In: Azar, Yossi and Erlebach, Thomas, (eds.) Algorithms – ESA 2006. Lecture Notes in Computer Science, 4168 . Springer Verlag, pp. 352-363. ISBN 9783540388753
PDF
fulltext22.pdf Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (448Kb) |
Official URL: http://dx.doi.org/10.1007/11841036_33
Abstract
We consider FIFO buffer management for switches providing differentiated services. In each time step, an arbitrary number of packets arrive, and only one packet can be sent. The buffer can store a limited number of packets, and, due to the FIFO property, the sequence of sent packets has to be a subsequence of the arriving packets. The differentiated service model is abstracted by attributing each packet with a value according to its service level. A buffer management strategy can drop packets. The goal is to maximize the sum of values of sent packets.
For only two different packet values, we introduce the account strategy and prove that this strategy achieves an optimal competitive ratio of ≈1.282, if the buffer size tends to infinity, and an optimal competitive ratio of $(\sqrt{13}-1)/2 \approx 1.303$ , for arbitrary buffer sizes. For general packet values, the simple preemptive greedy strategy (PG) is studied. We show that PG achieves a competitive ratio of $\sqrt{3} \approx 1.732$ which is the best known upper bound on the competitive ratio of this problem. In addition, we give a lower bound of $1 + 1 / \sqrt{2} \approx 1.707$ on the competitive ratio of PG which improves the previously known lower bound. As a consequence, the competitive ratio of PG cannot be further improved significantly.
Item Type: | Book Item | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Series Name: | Lecture Notes in Computer Science | ||||
Publisher: | Springer Verlag | ||||
ISBN: | 9783540388753 | ||||
Book Title: | Algorithms – ESA 2006 | ||||
Editor: | Azar, Yossi and Erlebach, Thomas | ||||
Official Date: | 2006 | ||||
Dates: |
|
||||
Volume: | 4168 | ||||
Page Range: | pp. 352-363 | ||||
DOI: | 10.1007/11841036_33 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |