The Library
Comparison-based FIFO buffer management in QoS switches
Tools
Al-Bawan, Kamal, Englert, Matthias and Westermann, Matthias (2016) Comparison-based FIFO buffer management in QoS switches. In: 12th Latin American Theoretical Informatics Symposium (LATIN), 2016, Ensenada, México, 11-15 Apr 2016. Published in: Proceedings of the 12th Latin American Theoretical Informatics Symposium (LATIN), 2016, 9644 pp. 27-40. doi:10.1007/978-3-662-49529-2_3
|
PDF
WRAP_Englert_qos_latin16.pdf - Accepted Version - Requires a PDF viewer. Download (427Kb) | Preview |
Official URL: https://doi.org/10.1007/978-3-662-49529-2_3
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 FIFO buffer and only one packet can be transmitted. Packets may be kept in the buffer of limited size and, due to the FIFO property, the sequence of transmitted packets has to be a subsequence of the arriving packets. The differentiated service concept is implemented by attributing each packet with a non-negative value corresponding to its service level. A buffer management algorithm can reject arriving packets and preempt buffered packets. The goal is to maximize the total value of transmitted packets.
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 algorithms proves to be robust in the realm of QoS switches. Kesselman et al. (SIAM J. Comput., 2004) present a comparison-based algorithm that is 2-competitive. For a long time, it has been an open problem whether a comparison-based algorithm exists with a competitive ratio below 2. We present a lower bound of 1 + 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.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Alternative Title: | |||||||
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Online algorithms, Switching theory | ||||||
Series Name: | Lecture Notes in Computer Science | ||||||
Journal or Publication Title: | Proceedings of the 12th Latin American Theoretical Informatics Symposium (LATIN), 2016 | ||||||
Publisher: | Springer | ||||||
Official Date: | 2016 | ||||||
Dates: |
|
||||||
Volume: | 9644 | ||||||
Page Range: | pp. 27-40 | ||||||
DOI: | 10.1007/978-3-662-49529-2_3 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Date of first compliant deposit: | 7 January 2016 | ||||||
Date of first compliant Open Access: | 7 January 2016 | ||||||
Funder: | European Research Council (ERC) | ||||||
Grant number: | 307696 (ERC) | ||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | 12th Latin American Theoretical Informatics Symposium (LATIN), 2016 | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Ensenada, México | ||||||
Date(s) of Event: | 11-15 Apr 2016 | ||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year