Improved online algorithms for buffer management in QoS switches

Result code in 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>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Improved online algorithms for buffer management in QoS switches
Original language description
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.
Czech name
Zlepšený online algoritmus pro zpracování front QoS jednotkách
Czech description
Článek studuje deterministické online algoritmy pro zpracování front

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

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

Similar results(10)