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 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.

Download full text files

Export metadata

Metadaten
Author:Maik Weinard
URN:urn:nbn:de:hebis:30-25176
DOI:https://doi.org/10.1007/11427186_38
ISBN:978-3-540-25920-6
ISBN:978-3-540-32078-4
Parent Title (English):Experimental and efficient algorithms : 4th international workshop ; proceedings / WEA 2005, Santorini Island, Greece, May 10 - 13, 2005 (Lecture notes in computer science ; Vol. 3503)
Publisher:Springer
Place of publication:Berlin ; Heidelberg ; New York
Editor:Sotiris Nikoletseas
Document Type:Part of a Book
Language:English
Date of Publication (online):2006/03/20
Year of first Publication:2005
Publishing Institution:Universitätsbibliothek Johann Christian Senckenberg
Contributing Corporation:Proceedings of 4th Int. Workshop on Experimental and Efficient Algorithms, Santorini, Griechenland, Mai 2005
Release Date:2006/03/20
Page Number:12
First Page:440
Last Page:451
Note:
© Springer-Verlag Berlin Heidelberg 2005
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 und Mathematik / Informatik
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Licence (German):License LogoDeutsches Urheberrecht

OPUS4 Logo