ALCOMFT-TR-01-118

J. Diaz, D. Koukopoulos, S. Nikoletseas, M. Serna, P. Spirakis and D. Thilikos
Stability and non-stability of the FIFO Protocol
Barcelona and Patras. Work packages 2 and 4. May 2001.

Abstract: In this paper, we analyze the stability properties of the FIFO protocol in the Adversarial Queueing model for packet rout- ing. 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 net- work and an adversary for which FIFO is non-stable for any r >= 0.8357, improving the previous known bounds of [2].

Postscript file: ALCOMFT-TR-01-118.ps.gz (80 kb).