New Stability Results for Adversarial Queuing
Authors:
- Zvi LotkerZLZvi Lotker
- Boaz Patt-ShamirBPBoaz Patt-Shamir
- Adi RosénARAdi Rosén
- 1 January 2004
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 33 (2) , 286-303
Abstract
We consider the model of "adversarial queuing theory" for packet networks introduced by Borodin et al. [J. ACM, 48 (2001), pp. 13--38].We show that the scheduling protocol first-in-first-out (FIFO) can be unstable at any injection rate larger than 1/2 and that it is always stable if the injection rate is less than 1/d, where d is the length of the longest route used by any packet. We further show that every work-conserving (i.e., greedy) scheduling policy is stable if the injection rate is less than 1/(d+1).Keywords
This publication has 7 references indexed in Scilit:
- Stability of Adaptive and Nonadaptive Packet Routing Policies in Adversarial Queueing NetworksSIAM Journal on Computing, 2003
- Stability of networks and protocols in the adversarial queueing model for packet routingNetworks, 2001
- Universal-stability results and performance bounds for greedy contention-resolution protocolsJournal of the ACM, 2001
- Adversarial queuing theoryJournal of the ACM, 2001
- Adaptive Packet Routing for Bursty Adversarial TrafficJournal of Computer and System Sciences, 2000
- 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