The Library
Breaking the barrier of 2 for the competitiveness of longest queue drop
Tools
Antoniadis, Antonios, Englert, Matthias, Matsakis, Nicolaos and Veselý, Pavel (2021) Breaking the barrier of 2 for the competitiveness of longest queue drop. In: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Virtual, 12-16 Jul 2021. Published in: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), 198 17:1-17:20. ISBN 9783959771955. doi:10.4230/LIPIcs.ICALP.2021.17 ISSN 1868-8969.
|
PDF
WRAP-breaking-barrier-2-competitiveness-longest-queue-drop-Englert-2021.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (667Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.17
Abstract
We consider the problem of managing the buffer of a shared-memory switch that transmits packets of unit value. A shared-memory switch consists of an input port, a number of output ports, and a buffer with a specific capacity. In each time step, an arbitrary number of packets arrive at the input port, each packet designated for one output port. Each packet is added to the queue of the respective output port. If the total number of packets exceeds the capacity of the buffer, some packets have to be irrevocably rejected. At the end of each time step, each output port transmits a packet in its queue and the goal is to maximize the number of transmitted packets.
The Longest Queue Drop (LQD) online algorithm accepts any arriving packet to the buffer. However, if this results in the buffer exceeding its memory capacity, then LQD drops a packet from the back of whichever queue is currently the longest, breaking ties arbitrarily. The LQD algorithm was first introduced in 1991, and is known to be 2-competitive since 2001. Although LQD remains the best known online algorithm for the problem and is of practical interest, determining its true competitiveness is a long-standing open problem. We show that LQD is 1.707-competitive, establishing the first (2-ε) upper bound for the competitive ratio of LQD, for a constant ε > 0.
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 | |||||||||||||||
Library of Congress Subject Headings (LCSH): | Machine theory -- Mathematical models, Computational complexity, Online algorithms , Data structures (Computer science) | |||||||||||||||
Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | |||||||||||||||
Journal or Publication Title: | 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) | |||||||||||||||
Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | |||||||||||||||
ISBN: | 9783959771955 | |||||||||||||||
ISSN: | 1868-8969 | |||||||||||||||
Official Date: | 2021 | |||||||||||||||
Dates: |
|
|||||||||||||||
Volume: | 198 | |||||||||||||||
Page Range: | 17:1-17:20 | |||||||||||||||
DOI: | 10.4230/LIPIcs.ICALP.2021.17 | |||||||||||||||
Status: | Peer Reviewed | |||||||||||||||
Publication Status: | Published | |||||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | |||||||||||||||
Date of first compliant deposit: | 12 May 2020 | |||||||||||||||
Date of first compliant Open Access: | 14 May 2020 | |||||||||||||||
RIOXX Funder/Project Grant: |
|
|||||||||||||||
Conference Paper Type: | Paper | |||||||||||||||
Title of Event: | 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) | |||||||||||||||
Type of Event: | Conference | |||||||||||||||
Location of Event: | Virtual | |||||||||||||||
Date(s) of Event: | 12-16 Jul 2021 | |||||||||||||||
Related URLs: | ||||||||||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year