The necessity of timekeeping in adversarial queueing

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 introd
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.
show moreshow less

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

    Share in Twitter Search Google Scholar
Metadaten
Author:Maik Weinard
URN:urn:nbn:de:hebis:30-25176
Document Type:Article
Language:English
Date of Publication (online):2006/03/20
Year of first Publication:2005
Publishing Institution:Univ.-Bibliothek Frankfurt am Main
Release Date:2006/03/20
Source:Proceedings of 4th Int. Workshop on Experimental and Efficient Algorithms, Santorini, Griechenland, Mai 2005, pp. 440-451.© Springer Verlag: LNCS Volume at Springer , http://www.springerlink.com/openurl.asp?genre=issue&issn=0302-9743&volume=3503
HeBIS PPN:263915492
Institutes:Informatik
Dewey Decimal Classification:004 Datenverarbeitung; Informatik
Sammlungen:Universitätspublikationen
Licence (German):License Logo Veröffentlichungsvertrag für Publikationen

$Rev: 11761 $