A phi-Competitive Algorithm for Scheduling Packets with Deadlines

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10404879" target="_blank" >RIV/00216208:11320/19:10404879 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1137/1.9781611975482.9" target="_blank" >https://doi.org/10.1137/1.9781611975482.9</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/1.9781611975482.9" target="_blank" >10.1137/1.9781611975482.9</a>

Jazyk výsledku

angličtina

Název v původním jazyce

A phi-Competitive Algorithm for Scheduling Packets with Deadlines

Popis výsledku v původním jazyce

In the online packet scheduling problem with deadlines (PacketScheduling, for short), the goal is to schedule transmissions of packets that arrive over time in a network switch and need to be sent across a link. Each packet has a deadline, representing its urgency, and a non-negative weight, that represents its priority. Only one packet can be transmitted in any time slot, so, if the system is overloaded, some packets will inevitably miss their deadlines and be dropped. In this scenario, the natural objective is to compute a transmission schedule that maximizes the total weight of packets which are successfully transmitted. The problem is inherently online, with the scheduling decisions made without the knowledge of future packet arrivals. The central problem concerning PacketScheduling, that has been a subject of intensive study since 2001, is to determine the optimal competitive ratio of online algorithms, namely the worst-case ratio between the optimum total weight of a schedule (computed by an offline algorithm) and the weight of a schedule computed by a (deterministic) online algorithm. We solve this open problem by presenting a ϕ-competitive online algorithm for PacketScheduling (where ϕ ALMOST EQUAL TO 1.618 is the golden ratio), matching the previously established lower bound. Read More: https://epubs.siam.org/doi/10.1137/1.9781611975482.9

Název v anglickém jazyce

A phi-Competitive Algorithm for Scheduling Packets with Deadlines

Popis výsledku anglicky

In the online packet scheduling problem with deadlines (PacketScheduling, for short), the goal is to schedule transmissions of packets that arrive over time in a network switch and need to be sent across a link. Each packet has a deadline, representing its urgency, and a non-negative weight, that represents its priority. Only one packet can be transmitted in any time slot, so, if the system is overloaded, some packets will inevitably miss their deadlines and be dropped. In this scenario, the natural objective is to compute a transmission schedule that maximizes the total weight of packets which are successfully transmitted. The problem is inherently online, with the scheduling decisions made without the knowledge of future packet arrivals. The central problem concerning PacketScheduling, that has been a subject of intensive study since 2001, is to determine the optimal competitive ratio of online algorithms, namely the worst-case ratio between the optimum total weight of a schedule (computed by an offline algorithm) and the weight of a schedule computed by a (deterministic) online algorithm. We solve this open problem by presenting a ϕ-competitive online algorithm for PacketScheduling (where ϕ ALMOST EQUAL TO 1.618 is the golden ratio), matching the previously established lower bound. Read More: https://epubs.siam.org/doi/10.1137/1.9781611975482.9

Druh

D - Stať ve sborníku

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/GA17-09142S" target="_blank" >GA17-09142S: Moderní algoritmy: Nové výzvy komplexních dat</a><br>

Návaznosti

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

Rok uplatnění

2019

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 statě ve sborníku

30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019

ISBN

978-1-61197-548-2

ISSN

—

e-ISSN

—

Počet stran výsledku

20

Strana od-do

123-142

Název nakladatele

Association for Computing Machinery (ACM)

Místo vydání

USA

Místo konání akce

San Diego, USA

Datum konání akce

6. 1. 2019

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—