|Type of publication:||Article|
|Title||Stability and non-stability of the FIFO protocol|
|Bibtex cite ID||RACTI-RU1-2006-89|
|Journal ||ACM Symposium on Parallel Algorithms and Architectures|
|Year published ||2006|
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 . 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 .