Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-24T00:44:27.587Z Has data issue: false hasContentIssue false
  • English
  • Français

Rare events in series of queues

Part of: Special processes

Published online by Cambridge University Press:  14 July 2016

Pantelis Tsoucas
Pantelis Tsoucas*
Affiliation:
IBM Research Division
*
∗ Postal address: IBM Research Division, T. J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY 10598, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

In an ergodic network of K M/M/1 queues in series we consider the rare event that, as N increases, the total population in the network exceeds N during a busy period. By utilizing the contraction principle of large deviation theory, an action functional is obtained for this exit problem. The ensuing minimization is carried out for K = 2 and an indication is given for arbitrary K. It is shown that, asymptotically and for unequal service rates, the ‘most likely' path for this rare event is one where the arrival rate has been interchanged with the smallest service rate. The problem has been posed in Parekh and Walrand [7] in connection with importance sampling simulation methods for queueing networks. Its solution has previously been obtained only heuristically.

Keywords

LARGE DEVIATIONSQUEUES IN SERIES

MSC classification

Primary: 60K25: Queueing theory
Type
Research Papers
Information
Journal of Applied Probability , Volume 29 , Issue 1 , March 1992 , pp. 168 - 175
Copyright
Copyright © Applied Probability Trust 1992 

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

A version of this work was presented at the ORSA/TIMS Conference, New York, NY, 16–18 October 1989.

References

[1]Bucklew, J. A. (1990) Large Deviation Techniques in Decision, Simulation and Estimation. Wiley, New York.Google Scholar
[2]Cottrell, M., Fort, J.-C. and Malgouyres, G. (1983) Large deviations and rare events in the study of stochastic algorithms. IEEE Trans. Autom. Control 28, 907–920.Google Scholar
[3]Dupuis, P., Ellis, R. and Weiss, A. (1989) Large deviations for Markov processes with discontinuous statistics, I: general upper bounds. Preprint, Center for Appl. Math. and Math. Comp., University of Massachusetts-Amherst.Google Scholar
[4]Frater, M. A. and Anderson, B. D. O. (1989) Fast estimation of the statistics of excessive backlogs in tandem networks of queues. Austral. Telecomm. Res. 23, 49–55.Google Scholar
[5]Fresnedo, R. D. (1989) Quick simulation of rare events in networks. Proc. Winter Simulation Conf. Washington, DC.Google Scholar
[6]Gelfand, I. M. and Fomin, S. V. (1963) Calculus of Variations. Prentice Hall, Englewood Cliffs, NJ.Google Scholar
[7]Parekh, S. and Walrand, J. (1989) A quick simulation method for excessive backlogs in networks of queues. IEEE Trans. Autom. Control 34, 54–66.Google Scholar
[8]Reiman, M. I. (1984) Open queueing networks in heavy traffic. Math. Operat. Res. 9, 441–458.Google Scholar
[9]Varadhan, S. R. S. (1984) Large Deviations and Applications. Society for Industrial and Applied Mathematics, Philadelphia.Google Scholar
[10]Weber, R. (1979) The interchangeability of ·/M/1 queues in tandem. J. Appl. Prob. 16, 690–695.Google Scholar
[11]Weiss, A. (1983) The large deviations of a Markov process which models traffic generation. Bell Lab. Tech. Memo.Google Scholar
[12]Wentzell, A. D. (1976) Rough limit theorems on large deviation for Markov stochastic processes II. Theory Prob. Appl. 21, 499–512.Google Scholar