Stability and non-stability of the FIFO protocol
Authors:
Open Access
- 3 July 2001
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 48-52
Abstract
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].Keywords
This publication has 5 references indexed in Scilit:
- Universal-stability results and performance bounds for greedy contention-resolution protocolsJournal of the ACM, 2001
- Adversarial queuing theoryJournal of the ACM, 2001
- Instability of FIFO Queueing NetworksThe Annals of Applied Probability, 1994
- A calculus for network delay. II. Network analysisIEEE Transactions on Information Theory, 1991
- A calculus for network delay. I. Network elements in isolationIEEE Transactions on Information Theory, 1991