Zlepšený online algoritmus pro zpracování front QoS jednotkách

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F07%3A00097689" target="_blank" >RIV/67985840:_____/07:00097689 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Improved online algorithms for buffer management in QoS switches

Popis výsledku v původním jazyce

We consider the following buffer management problem arising in QoS networks: packets with specified weights and deadlines arrive at a network switch and need to be forwarded so that the total weight of forwarded packets is maximized. Packets not forwarded before their deadlines are lost. The main result of the paper is an online $64/33/approx 1.939$-competitive algorithm --the first deterministic algorithm for this problem with competitive ratio below $2$. For the $2$-uniform case we give an algorithm with ratio $/approx 1.377$ and a matching lower bound.

Název v anglickém jazyce

Improved online algorithms for buffer management in QoS switches

Popis výsledku anglicky

We consider the following buffer management problem arising in QoS networks: packets with specified weights and deadlines arrive at a network switch and need to be forwarded so that the total weight of forwarded packets is maximized. Packets not forwarded before their deadlines are lost. The main result of the paper is an online $64/33/approx 1.939$-competitive algorithm --the first deterministic algorithm for this problem with competitive ratio below $2$. For the $2$-uniform case we give an algorithm with ratio $/approx 1.377$ and a matching lower bound.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2007

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

—

Svazek periodika

4

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

19

Strana od-do

1-19

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—