TY  - CHAP
A1  - Weinard, Maik
A2  - Nikoletseas, Sotiris
T1  - The necessity of timekeeping in adversarial queueing
T2  - Experimental and efficient algorithms : 4th international workshop ; proceedings / WEA 2005, Santorini Island, Greece, May 10 - 13, 2005 (Lecture notes in computer science ; Vol. 3503)
N2  - We study queueing strategies in the adversarial queueing model. Rather than discussing individual prominent queueing strategies we tackle the issue on a general level and analyze classes of queueing strategies. We introduce the class of queueing strategies that base their preferences on knowledge of the entire graph, the path of the packet and its progress. This restriction only rules out time keeping information like a packet’s age or its current waiting time.
We show that all strategies without time stamping have exponential queue sizes, suggesting that time keeping is necessary to obtain subexponential performance bounds. We further introduce a new method to prove stability for strategies without time stamping and show how it can be used to completely characterize a large class of strategies as to their 1-stability and universal stability.
Y1  - 2006
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/2892
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30-25176
SN  - 978-3-540-25920-6
SN  - 978-3-540-32078-4
N1  - © Springer-Verlag Berlin Heidelberg 2005
SP  - 440
EP  - 451
PB  - Springer
CY  - Berlin ; Heidelberg ; New York
ER  -