Hostname: page-component-7b7567c8c-p67k6 Total loading time: 0 Render date: 2026-11-19T18:00:07.678Z Has data issue: false hasContentIssue false

On the saturation rule for the stability of queues

Published online by Cambridge University Press:  14 July 2016

François Baccelli*
Affiliation:
INRIA Sophia Antipolis
Serguei Foss*
Affiliation:
Novosibirsk State University
*
∗ Postal address: INRIA Centre Sophia Antipolis, 06565 Valbonne, France. baccelli@sophia.inria.fr.
∗∗ Postal address: Novosibirsk State University, 630090 Novosibirsk, Russia. foss@math.nsk.su.

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.

MSC classification

Information

Type
Research Papers
Copyright
Copyright © Applied Probability Trust 1995 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable