Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-16T16:57:45.253Z Has data issue: false hasContentIssue false
  • English
  • Français

A unified approach to fast teller queues and ATM

Part of: Special processes Limit theorems Operations research and management science Computer system organization

Published online by Cambridge University Press:  01 July 2016

B. Beck ,
A. R. Dabrowski  and
D. R. McDonald
B. Beck*
Affiliation:
Université Catholique de Louvain
A. R. Dabrowski*
Affiliation:
University of Ottawa
D. R. McDonald*
Affiliation:
University of Ottawa
*
∗ Postal address: Institut de Statistique, Université Catholique de Louvain, Voie du Roman Pays, 20, B-1348 Louvain-La-Neuve, Belgium.
∗∗ Postal address: Department of Mathematics and Statistics, University of Ottawa, Ottawa, Ontario, Canada K1N 6N5.
∗∗ Postal address: Department of Mathematics and Statistics, University of Ottawa, Ottawa, Ontario, Canada K1N 6N5.
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper examines a problem of importance to the telecommunications industry. In the design of modern ATM switches, it is necessary to use simulation to estimate the probability that a queue within the switch exceeds a given large value. Since these are extremely small probabilities, importance sampling methods must be used. Here we obtain a change of measure for a broad class of models with direct applicability to ATM switches.

We consider a model with A independent sources of cells where each source is modeled by a Markov renewal point process with batch arrivals. We do not assume the sources are necessarily identically distributed, nor that batch sizes are independent of the state of the Markov process. These arrivals join a queue served by multiple independent servers, each with service times also modeled as a Markov renewal process. We only discuss a time-slotted system. The queue is viewed as the additive component of a Markov additive chain subject to the constraint that the additive component remains non-negative. We apply the theory in McDonald (1999) to obtain the asymptotics of the tail of the distribution of the queue size in steady state plus the asymptotics of the mean time between large deviations of the queue size.

Keywords

Rare eventschange of measureh-transformasynchronous transfer modehotspot simulation

MSC classification

Primary: 60K25: Queueing theory
Secondary: 60F10: Large deviations 60K20: Applications of Markov renewal processes (reliability, queueing networks, etc.) 68M20: Performance evaluation; queueing; scheduling 90B22: Queues and service
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 31 , Issue 3 , September 1999 , pp. 758 - 787
Copyright
Copyright © Applied Probability Trust 1999 

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 of the last two authors supported in part by NSERC grant.

References

Anick, D., Mitra, D. and Sondhi, M. M. (1982). Stochastic theory of a data-handling system with multiple sources. Bell System Tech. J. 61, 1871–1894.Google Scholar
Asmussen, S. (1985). Conjugate processes and the simulation of ruin problems. Stoch. Proc. Appl. 20, 213–229.Google Scholar
Asmussen, S. (1995). Stationary distributions via first passage times. In Advances in Queueing (Probab. Stochastics Ser.), CRC, Boca Raton, FL, pp. 79–102.Google Scholar
Asmussen, S. (1997). Applied Probability and Queues. Wiley, Chichester, UK.Google Scholar
Asmussen, S. and Klüppelberg, C. (1997). Stationary M/G/1 excursions in the presence of heavy tails. J. Appl. Prob. 34, 208–212.Google Scholar
Bonneau, M-C. (1996). Accelerated simulation of a leaky bucket controller. , University of Ottawa, Ontario, Canada.Google Scholar
Bucklew, J. S. (1990). Large Deviation Techniques in Decision, Simulation and Estimation. Wiley, New York.Google Scholar
Duffield, N. G. and O'Connell, N. (1995). Large deviations and overflow probabilities for the general single-server queue, with applications. Math. Proc. Camb. Phil. Soc. 118, 363–374.Google Scholar
Feller, W. (1971). An Introduction to Probability Theory and Its Applications, Vol. II. Wiley, New York.Google Scholar
Glasserman, P. and Kou, S-G. (1995). Analysis of an importance sampling estimator for tandem queues. ACM Trans. Modeling Computer Simul. 5, 22–42.Google Scholar
Heidelberger, P. (1995). Fast simulation of rare events in queueing and reliability models. ACM Trans. Modeling Computer Simul. 5, 43–85.CrossRefGoogle Scholar
Kelly, F. P. (1991). Effective bandwidths of multiclass queues. Queueing Systems 9, 5–16.CrossRefGoogle Scholar
Kelly, F. P. (1996). Notes on effective bandwidths. In Stochastic Networks: Theory and Applications. Ed. Kelly, F. P., Zachary, S. and Ziedens, I. B., Oxford University Press, Oxford, pp. 141–168.Google Scholar
Kesidis, G., Walrand, J. and Chang, C-S. (1993). Effective bandwidths of multiclass Markov fluids and other ATM sources. IEEE/ACM Trans. Networking 1, 424–428.Google Scholar
Kesten, H. (1974). Renewals theory for functionals of a Markov chain with general state space. Ann. Prob. 2, 355–386.Google Scholar
Lamothe, G. (1998). Accelerated simulation of ATM switching fabrics. , University of Ottawa, Ontario, Canada.Google Scholar
Loynes, R. M. (1962). The stability of a queue with non-independent interarrival and service times. Proc. Camb. Phil. Soc. 58, 497–520.Google Scholar
Meyn, S. P. and Tweedie, R.L. (1993). Markov Chains and Stochastic Stability. Springer, New York.CrossRefGoogle Scholar
McDonald, D. (1999). Asymptotics of first passage times for random walk in an orthant. Ann. Appl. Prob. 9, 110–145.CrossRefGoogle Scholar
Ney, P. and Nummelin, E. (1987). Markov additive processes I. Eigenvalue properties and limit theorems. Ann. Prob. 15, 561–592.Google Scholar
Nicola, V. F., Shahabuddin, P., Heidelberger, P. and Glynn, P. W. (1992). Fast simulation of steady-state availability in non-Markovian highly dependable systems. IBM Research Report. Watson Research Laboratory, New York.Google Scholar
Orey, S. (1971). Limit Theorems for Markov Chain Transition Probabilities. Van Nostrand Reinhold, New York.Google Scholar
Parekh, S. and Walrand, J. (1989). A quick simulation method for excessive backlogs in networks of queues. IEEE Trans. Auto. Control 34, 54–66.Google Scholar
Sadowsky, J. and Szpankowski, W. (1995). The probability of large queue lengths and waiting times in a heterogeneous multiserver queue I: Tight limits. Adv. Appl. Prob. 27, 532–566.Google Scholar
Siegmund, D. (1976). Importance sampling in the Monte Carlo study of sequential tests. Ann. Statist. 4, 673–684.Google Scholar