Article contents
On the saturation rule for the stability of queues
Published online by Cambridge University Press: 14 July 2016
Abstract
This paper focuses on the stability of open queueing systems under stationary ergodic assumptions. It defines a set of conditions, the monotone separable framework, ensuring that the stability region is given by the following saturation rule: ‘saturate' the queues which are fed by the external arrival stream; look at the ‘intensity' μ of the departure stream in this saturated system; then stability holds whenever the intensity of the arrival process, say λ satisfies the condition λ < μ, whereas the network is unstable if λ > μ. Whenever the stability condition is satisfied, it is also shown that certain state variables associated with the network admit a finite stationary regime which is constructed pathwise using a Loynes-type backward argument. This framework involves two main pathwise properties, external monotonicity and separability, which are satisfied by several classical queueing networks. The main tool for the proof of this rule is subadditive ergodic theory. It is shown that, for various problems, the proposed method provides an alternative to the methods based on Harris recurrence and regeneration; this is particularly true in the Markov case, where we show that the distributional assumptions commonly made on service or arrival times so as to ensure Harris recurrence can in fact be relaxed.
Keywords
MSC classification
- Type
- Research Papers
- Information
- Copyright
- Copyright © Applied Probability Trust 1995
Footnotes
Research supported in part by a grant from the European Commission DG XIII, under the BRA Qmips contract.
Research supported by a sabbatical grant from INRIA Sophia Antipolis.
References
- 54
- Cited by