The Library
Comparison-based buffer management in QoS switches
Tools
Al-Bawani, Kamal, Englert, Matthias and Westermann, Matthias (2018) Comparison-based buffer management in QoS switches. Algorithmica, 80 (3). pp. 1073-1092. doi:10.1007/s00453-017-0393-2 ISSN 0178-4617.
|
PDF
WRAP-comparison-based-buffer-Englert-2017.pdf - Accepted Version - Requires a PDF viewer. Download (745Kb) | Preview |
Official URL: https://doi.org/10.1007/s00453-017-0393-2
Abstract
The following online problem arises in network devices, e.g., switches, with quality of service (QoS) guarantees. In each time step, an arbitrary number of packets arrive at a single buffer and only one packet can be transmitted. The differentiated service concept is implemented by attributing each packet with a non-negative value corresponding to its service level. The goal is to maximize the total value of transmitted packets. We consider two models of this problem, the FIFO and the bounded-delay model. In the FIFO model, the buffer can store a limited number of packets and the sequence of transmitted packets has to be a subsequence of the arriving packets. In this model, a buffer management algorithm can reject arriving packets and preempt buffered packets. In the bounded-delay model, the buffer has unbounded capacity, but each packet has a deadline and packets can only be transmitted before their deadlines. Here, a buffer management algorithm determines the packet to be sent in each time step. We study comparison-based buffer management algorithms, i.e., algorithms that make their decisions based solely on the relative order between packet values with no regard to the actual values. This kind of algorithm proves to be robust in the realm of QoS switches. Kesselman et al. (SIAM J Comput 33(3):563–583, 2004) present two deterministic comparison-based online algorithms, one for each model, which are 2-competitive. For a long time, it has been an open problem, whether a comparison-based online algorithm exists, in either model, with a competitive ratio below 2. In the FIFO model, we present a lower bound of 1+1/2–√≈1.7071+1/2≈1.707 on the competitive ratio of any deterministic comparison-based algorithm and give an algorithm that matches this lower bound in the case of monotonic sequences, i.e., packets arrive in a non-decreasing order according to their values. In the bounded-delay model, we show that no deterministic comparison-based algorithm exists with a competitive ratio below 2. In the special s-uniform case, where the difference between the arrival time and deadline of any packet equals s, we present a randomized comparison-based algorithm that is 5 / 3-competitive.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software T Technology > TK Electrical engineering. Electronics Nuclear engineering |
||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
Library of Congress Subject Headings (LCSH): | Quality of service (Computer networks), Algorithms | ||||||||
Journal or Publication Title: | Algorithmica | ||||||||
Publisher: | Springer Verlag | ||||||||
ISSN: | 0178-4617 | ||||||||
Official Date: | March 2018 | ||||||||
Dates: |
|
||||||||
Volume: | 80 | ||||||||
Number: | 3 | ||||||||
Page Range: | pp. 1073-1092 | ||||||||
DOI: | 10.1007/s00453-017-0393-2 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Date of first compliant deposit: | 7 November 2017 | ||||||||
Date of first compliant Open Access: | 2 May 2018 | ||||||||
Funder: | European Research Council (ERC) | ||||||||
Grant number: | Grant Agreement No. 307696 (ERC) |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year