Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-23T21:21:13.129Z Has data issue: false hasContentIssue false
  • English
  • Français

On the cut-off phenomenon in some queueing systems

Published online by Cambridge University Press:  14 July 2016

P. Konstantopoulos  and
F. Baccelli
P. Konstantopoulos
Affiliation:
INRIA
F. Baccelli*
Affiliation:
INRIA
*
∗ Postal address for both authors: INRIA, Sophia Antipolis, 2004 Route des Lucioles, 06565 Valbonne Cedex, France.
Get access Rights & Permissions [Opens in a new window]

Abstract

A number of stochastic queueing systems exhibit an interesting phenomenon known as the cut-off phenomenon. A properly scaled version of the distance between the transient process and the stationary one converges to a step function as the initial load converges to infinity. The purpose of this paper is to promote the idea that this phenomenon is a direct consequence of the coupling between the two processes, being thus generalizable to systems lacking any kind of Markovian structure.

Keywords

STATIONARY AND ERGODIC QUEUEING SYSTEMSTOTAL VARIATION DISTANCESETTLING TIME
Type
Research Papers
Information
Journal of Applied Probability , Volume 28 , Issue 3 , September 1991 , pp. 683 - 694
Copyright
Copyright © Applied Probability Trust 1991 

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

The work of P. Konstantopoulos was supported in part by the National Science Foundation under grant ASC 88–8802764.

References

[1] Aldous, D. (1983) Random Walks on Finite Groups and Rapidly Mixing Markov Chains. Lecture Notes in Mathematics 986, Springer-Verlag, Berlin.CrossRefGoogle Scholar
[2] Anantharam, V. (1988) The settling time of a closed Jackson network. Preprint.Google Scholar
[3] Baccelli, F. (1989) Ergodic theory of stochastic Petri nets. Ann. Prob. Google Scholar
[4] Baccelli, F. and Liu, Z. (1990) On a class of stochastic recursive sequences arising in queueing theory. Ann. Prob. Google Scholar
[5] Baccelli, F., Makowski, A. and Shwartz, A. (1989) The fork-join queue and related systems with synchronization constraints: Stochastic ordering, approximations and computable bounds. Adv. Appl. Prob. 21, 629–660.CrossRefGoogle Scholar
[6] Kingman, J. F. C. (1973) Subadditive ergodic theory. Ann. Prob. 1, 883–909.CrossRefGoogle Scholar
[7] Konstantopoulos, P. and Walrand, J. (1989) Stationarity and stability of fork-join networks. J. Appl. Prob. 26, 604–614.CrossRefGoogle Scholar
[8] Loynes, R. M. (1962) The stability of a queue with non-independent inter-arrival and service times. Proc. Camb. Phil. Soc. 58, 497–520.CrossRefGoogle Scholar
[9] Stamoulis, G. D. and Tsitsiklis, J. N. (1990) On the settling time of the congested G/G/ 1 queue. Adv. Appl. Prob. 22, 929–956.CrossRefGoogle Scholar