Stability and non-stability of the FIFO protocol

J. Díaz, D. Koukopoulos, S. Nikoletseas, M. Serna, P. Spirakis, D. M. Thilikos

Research output: Contribution to conferencePaperpeer-review


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

Original languageEnglish (US)
Number of pages5
StatePublished - 2001
Event13th Annual Symposium on Parallel Algorithms and Architectures (SPAA 2001) - Crete Island, Greece
Duration: Jul 3 2001Jul 6 2001


Conference13th Annual Symposium on Parallel Algorithms and Architectures (SPAA 2001)
CityCrete Island

ASJC Scopus subject areas

  • Software
  • Safety, Risk, Reliability and Quality


Dive into the research topics of 'Stability and non-stability of the FIFO protocol'. Together they form a unique fingerprint.

Cite this