Hostname: page-component-78c5997874-mlc7c Total loading time: 0 Render date: 2024-11-09T06:36:01.712Z Has data issue: false hasContentIssue false
  • English
  • Français

On the saturation rule for the stability of queues

Part of: Special processes

Published online by Cambridge University Press:  14 July 2016

François Baccelli  and
Serguei Foss
François Baccelli*
Affiliation:
INRIA Sophia Antipolis
Serguei Foss*
Affiliation:
Novosibirsk State University
*
∗Postal address: INRIA Centre Sophia Antipolis, 06565 Valbonne, France. [email protected].
∗∗Postal address: Novosibirsk State University, 630090 Novosibirsk, Russia. [email protected].
Get access Rights & Permissions [Opens in a new window]

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

OPEN QUEUEING NETWORKSTATIONARY POINT PROCESSESMONOTONICITYSEPARABILITYFIRST AND SECOND-ORDER ERGODIC PROPERTIESSUBADDITIVE ERGODIC THEOREM

MSC classification

Primary: 60K25: Queueing theory
Type
Research Papers
Information
Journal of Applied Probability , Volume 32 , Issue 2 , June 1995 , pp. 494 - 507
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.)

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

[1] Baccelli, F., Cohen, G., Olsder, G. and Quadrat, J. P. (1992) Linearity and Synchronization. Wiley, New York.Google Scholar
[2] Baccelli, F. and Liu, Z. (1992) On a class of stochastic evolution equations arising in queueing theory. Ann. Appl. Prob. 20, 350–374.Google Scholar
[3] Baccelli, F. and Foss, S. (1994) Ergodicity of Jackson-type queueing networks. QUESTA 17, 5–72.Google Scholar
[4] Baccelli, F., Foss, S. and Gaujal, B. (1994) Structural, timed and stochastic properties of unbounded free choice Petri nets. INRIA Report No. 2411. Submitted to IEEE Trans. Autom Control. Google Scholar
[5] Bambos, N. and Walrand, J. (1993) Scheduling and stability of a class of parallel processing systems. Adv. Appl. Prob. 25, 176–202.Google Scholar
[6] Bambos, N. and Wasserman, K. (1994) On stationary tandem queueing networks with job feedback. QUESTA 15, 137–164.Google Scholar
[7] Borovkov, A. A. (1988) Asymptotic Methods in Queueing Theory. Wiley, New York.Google Scholar
[8] Borovkov, A. A. and Foss, S. G. (1992) Stochastically recursive sequences and their generalizations. Siberian Advances in Mathematics 2, 16–81.Google Scholar
[9] Bramson, M. (1993) Instability of FIFO queueing networks. Ann. Appl. Prob. 2, 414–431.Google Scholar
[10] Foss, S. and Chernova, N. (1995) Ergodic properties of polling models. Submitted to Problems of Information Transmission. Google Scholar
[11] Kelly, F. P. (1982) The throughput of a series of buffers. Adv. Appl. Prob. 14, 633–653.Google Scholar
[12] Kingman, J. F. C. (1973) Subadditive ergodic theory. Ann. Prob. 1, 883–909.CrossRefGoogle Scholar
[13] Lavenberg, S. (1978) Maximum departure rate of certain open queueing networks having finite capacity constraints. RAIRO série bleue, 12(4).Google Scholar
[14] Liggett, T. (1985) An improved version of Kingman's subadditive ergodic theorem. Ann. Prob. 13, 1279–1285.Google Scholar
[15] Meyn, S. P. and Down, D. (1994) Stability of generalized Jackson networks. Ann. Appl. Prob. 4, 124–148.Google Scholar
[16] Schrüger, K. (1991) Almost subadditive extensions of Kingman's ergodic theorem. Ann. Prob. 19, 1575–1586.Google Scholar