Breaking the barrier of 2 for the competitiveness of longest queue drop
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10438025" target="_blank" >RIV/00216208:11320/21:10438025 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.4230/LIPIcs.ICALP.2021.17" target="_blank" >https://doi.org/10.4230/LIPIcs.ICALP.2021.17</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.ICALP.2021.17" target="_blank" >10.4230/LIPIcs.ICALP.2021.17</a>
Alternative languages
Result language
angličtina
Original language name
Breaking the barrier of 2 for the competitiveness of longest queue drop
Original language description
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 - ELEMENT OF) upper bound for the competitive ratio of LQD, for a constant ELEMENT OF > 0. (C) 2021 Antonios Antoniadis, Matthias Englert, Nicolaos Matsakis, and Pavel Veselý.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GX19-27871X" target="_blank" >GX19-27871X: Efficient approximation algorithms and circuit complexity</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
ISBN
978-3-95977-195-5
ISSN
1868-8969
e-ISSN
—
Number of pages
20
Pages from-to
—
Publisher name
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Place of publication
Dagstuhl, Germany
Event location
Virtual (Glasgow, Scotland)
Event date
Jul 12, 2021
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—