Deciding the FIFO stability of networks in polynomial time

FIFO is the most prominent queueing strategy due to its simplicity and the fact that it only works with local information. Its analysis within the adversarial queueing theory however has shown, that there are networks th
FIFO is the most prominent queueing strategy due to its simplicity and the fact that it only works with local information. Its analysis within the adversarial queueing theory however has shown, that there are networks that are not stable under the FIFO protocol, even at arbitrarily low rate. On the other hand there are networks that are universally stable, i.e., they are stable under every greedy protocol at any rate r < 1. The question as to which networks are stable under the FIFO protocol arises naturally. We offer the first polynomial time algorithm for deciding FIFO stability and simple-path FIFO stability of a directed network, answering an open question posed in [1, 4]. It turns out, that there are networks, that are FIFO stable but not universally stable, hence FIFO is not a worst case protocol in this sense. Our characterization of FIFO stability is constructive and disproves an open characterization in [4].
show moreshow less

Download full text files

  • application/pdf 0305report.pdf (186 KB)

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

    Share in Twitter Search Google Scholar
Metadaten
Author:Maik Weinard
URN:urn:nbn:de:hebis:30:3-66757
URL:http://www.cs.uni-frankfurt.de/fbreports/0305report.ps
ISSN:1616-9107
Parent Title (English):Frankfurter Informatik-Berichte ; Nr. 05,3
Series (Serial Number):Frankfurter Informatik-Berichte (05, 3)
Publisher:Johann Wolfgang Goethe-Univ., Fachbereich Informatik und Mathematik, Inst. für Informatik
Place of publication:Frankfurt am Main
Document Type:Working Paper
Language:English
Year of Completion:2005
Year of first Publication:2005
Publishing Institution:Univ.-Bibliothek Frankfurt am Main
Release Date:2009/07/14
Note:
Diese Arbeit dürfen wir außerhalb der Universitätsbibliothek leider (aus urheberrechtlichen Gründen) nicht im Volltext zur Verfügung stellen.
Institutes:Informatik
Dewey Decimal Classification:004 Datenverarbeitung; Informatik
Sammlungen:Universitätspublikationen
Licence (German):License LogoArchivex. zur Lesesaalplatznutzung § 52b UrhG

$Rev: 11761 $