research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Article
Entered by:
TitleStability and non-stability of the FIFO protocol
Bibtex cite IDRACTI-RU1-2006-89
Journal ACM Symposium on Parallel Algorithms and Architectures
Year published 2006
Pages 48-52
In this paper, we analyze the stability properties of the FIFO protocol in the Adversarial Queueing model for packet routing. We show a graph for which FIFO is stable for any adversary with injection rate r ≰ 0.1428. We generalize this results to show upper bound for stability of any network under FIFO protocol, answering partially an open question raised by Andrews et al. in [2]. We also design a network and an adversary for which FIFO is non-stable for any r ≱ 0.8357, improving the previous known bounds of [2].
Diaz, Josep
Koukopoulos, Dimitrios
Nikoletseas, Sotiris
Serna, Maria
Spirakis, Paul
Thilikos, D
Publication ID313