Stability and non-stability of the FIFO protocol
Josep Dı́az, Dimitrios K. Koukopoulos, Sotiris Nikoletseas, Marı́a Serna, Paul G. Spirakis, Dimitrios M. Thilikos · 2001
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].