Breaking the Barrier of 2 for the Competitiveness of Longest Queue Drop

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10493438" target="_blank" >RIV/00216208:11320/24:10493438 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=BmEdgThbwo" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=BmEdgThbwo</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1145/3676887" target="_blank" >10.1145/3676887</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Breaking the Barrier of 2 for the Competitiveness of Longest Queue Drop

Popis výsledku v původním jazyce

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 evicted. 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 whichever queue is currently the longest, breaking ties arbitrarily. The LQD algorithm was first introduced in 1991, and has been 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.6918-competitive, establishing the first (2 - P ) upper bound for the competitive ratio of LQD for a constant epsilon&gt; 0 .

Název v anglickém jazyce

Breaking the Barrier of 2 for the Competitiveness of Longest Queue Drop

Popis výsledku anglicky

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 evicted. 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 whichever queue is currently the longest, breaking ties arbitrarily. The LQD algorithm was first introduced in 1991, and has been 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.6918-competitive, establishing the first (2 - P ) upper bound for the competitive ratio of LQD for a constant epsilon&gt; 0 .

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA22-22997S" target="_blank" >GA22-22997S: Efektivní a realistické modely ve výpočetní teorii voleb</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

ACM Transactions on Algorithms

ISSN

1549-6325

e-ISSN

1549-6333

Svazek periodika

20

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

29

Strana od-do

38

Kód UT WoS článku

001356742900001

EID výsledku v databázi Scopus

2-s2.0-85207064777