Adversarial queuing theory
Top Cited Papers
- 1 January 2001
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 48 (1) , 13-38
- https://doi.org/10.1145/363647.363659
Abstract
We consider packet routing when packets are injected continuously into a network. We develop an adversarial theory of queuing aimed at addressing some of the restrictions inherent in probabilistic analysis and queuing theory based on time-invariant stochastic generation. We examine the stability of queuing networks and policies when the arrival process is adversarial, and provide some preliminary results in this direction. Our approach sheds light on various queuing policies in simple networks, and paves the way for a systematic study of queuing with few or no probabilistic assumptions.Keywords
This publication has 34 references indexed in Scilit:
- Fast Algorithms for Finding O(Congestion + Dilation) Packet Routing SchedulesCombinatorica, 1999
- Any work-conserving policy stabilizes the ring with spatial re-useIEEE/ACM Transactions on Networking, 1996
- Stability and convergence of moments for multiclass queueing networks via fluid limit modelsIEEE Transactions on Automatic Control, 1995
- On Positive Harris Recurrence of Multiclass Queueing Networks: A Unified Approach Via Fluid Limit ModelsThe Annals of Applied Probability, 1995
- Instability of FIFO Queueing Networks with Quick Service TimesThe Annals of Applied Probability, 1994
- Packet routing and job-shop scheduling inO(congestion+dilation) stepsCombinatorica, 1994
- A generalized processor sharing approach to flow control in integrated services networks: the multiple node caseIEEE/ACM Transactions on Networking, 1994
- Distributed scheduling based on due dates and buffer prioritiesIEEE Transactions on Automatic Control, 1991
- Randomized parallel communications on an extension of the omega networkJournal of the ACM, 1987
- Product Form and Local Balance in Queueing NetworksJournal of the ACM, 1977