Abstract
The time τ(n) of first passage from queue length x to queue length n>x in a many-server queue with both the arrival process and service intensities governed by a finite Markov process is considered. The mean and the Laplace transform are computed as solutions of systems of linear equations coming out by optional stopping of a martingale obtained as a stochastic integral of the exponential Wald martingale for Markov additive processes. Compared to existing techniques for QBD's, the approach has the advantage of being far more efficient for large n.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
D. Aldous and L. Shepp, The least variable phase type distribution is Erlang, Stochastic Models 3 (1987) 467–473.
S. Asmussen, Extreme value theory for queues via cycle maxima, Extremes 1 (1998) 137–168.
S. Asmussen, Applied Probability and Queues, 2nd ed. (Springer, Berlin, 2003).
S. Asmussen, F. Avram and M.R. Pistorius, Russian and American put options under exponential phase-type Lévy models, Stochastic Process. Appl. (2003) to appear.
S. Asmussen, M. Jobmann and H.P. Schwefel, Explicit buffer overflow calculations for queues via martingales, Queueing Systems 42 (2002) 63–90.
S. Asmussen and O. Kella, A multi-dimensional martingale for Markov additive processes and its applications, Adv. in Appl. Probab. 32 (2000) 376–393.
S. Asmussen and O. Kella, On optional stopping of some exponential martingales for Lévy processes with or without reflection, Stochastic Process. Appl. 91 (2001) 47–55.
S. Asmussen and J.R. Møller, Calculation of the steady-state waiting time distribution in GI/PH/c and MAP/PH/c queues, Queueing Systems 37 (2001) 9–29.
F. Baccelli and A.M. Makowski, Dynamic, transient and stationary behaviour of the M/G/1 queue via martingales, Ann. Probab. 17 (1989) 1691–1699.
F. Ball and V.T. Stefanov, Further approaches to computing fundamental characteristics of birth-death processes, J. Appl. Probab. 38 (2001) 995–1005.
A. Dassios and P. Embrechts, Martingales and insurance risk, Stochastic Models 5 (1989) 181–217.
C.D. Fuh and T. Lai, Wald's equation, first passage times and moments of ladder variables in Markov random walks, J. Appl. Probab. 35 (1998) 566–580.
D.P. Gaver, P.A. Jacobs and G. Latouche, Finite birth-and-death models in randomly changing environments, Adv. in Appl. Probab. 16 (1984) 715–731.
P. Glasserman and S.-G. Kou, Limits of first passage times to rare sets in regenerative processes, Ann. Appl. Probab. 5 (1995) 424–445.
B.V. Gnedenko and I.N. Kovalenko, Introduction to Queueing Theory, 2nd ed. (Birkhäuser, Basel, 1989).
M. Jacobsen, Martingales and the Distribution of the Time to Ruin (MaPhySto, Aarhus, 2002).
V. Kalashnikov, Regenerative Processes (CRC Press, Boca Raton, FL, 1994).
V. Kalashnikov, Mathematical Methods in Queueing Theory (Kluwer Academic, Dordrecht, 1994).
V. Kalashnikov, Geometric Sums: Bounds for Rare Events with Applications (Kluwer Academic, Dordrecht, 1997).
J. Keilson, A limit theorem for passage times in ergodic regenerative processes, Ann. Math. Statist. 37 (1966) 866–870.
J. Keilson, Markov Chain Models — Rarity and Exponentiality (Springer, Berlin, 1979).
O. Kella and W. Stadje, On hitting times for compound Poisson dams with exponential jumps and linear release rate, J. Appl. Probab. 38 (2001) 781–786.
O. Kella and W. Whitt, Useful martingales for stochastic storage processes with Lévy input, J. Appl. Probab. 29 (1992) 396–403.
G. Latouche, C.E.M. Pearce and P.G. Taylor, Invariant measures for quasi-birth-and-death processes, Stochastic Models 14 (1998) 443–460.
G. Latouche and V. Ramaswami, Introduction to Matrix Analytic Methods in Stochastic Modeling (SIAM, Philadelphia, PA, 1999).
M.F. Neuts, A versatile Markovian point process, J. Appl. Probab. 16 (1979) 764–779.
M.F. Neuts, Models based on the Markovian arrival process, IEICE Trans. Comm. E 75-B (1992) 1255–1265.
J. Preater, On the severity of M/M/∞ congested episodes, J. Appl. Probab. 39 (2002) 228–230.
D. Revuz and M. Yor, Continuous Martingales and Brownian Motion, 3rd ed. (Springer, Berlin, 1999).
P. Robert, Réseaux et Files d'Attente: Méthodes Probabilistes (Springer, Berlin, 2000).
K.-I. Sato, Lévy Processes and Infinitely Divisible Distributions (Cambridge Univ. Press, Cambridge, 1999).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Asmussen, S., Pihlsgård, M. Transient Properties of Many-Server Queues and Related QBDs. Queueing Systems 46, 249–270 (2004). https://doi.org/10.1023/B:QUES.0000027986.41904.05
Issue Date:
DOI: https://doi.org/10.1023/B:QUES.0000027986.41904.05