zbMATH — the first resource for mathematics

The stationary tail asymptotics in the \(GI/G/1\)-type queue with countably many background states. (English) Zbl 1136.60366
Summary: We consider the asymptotic behaviour of the stationary tail probabilities in the discrete-time \(GI/G/1\)-type queue with countable background state space. These probabilities are presented in matrix form with respect to the background state space, and shown to be the solution of a Markov renewal equation. Using this fact, we consider their decay rates. Applying the Markov renewal theorem, it is shown that certain reasonable conditions lead to the geometric decay of the tail probabilities as the level goes to infinity. We exemplify this result using a discrete-time priority queue with a single server and two types of customer.

60K25 Queueing theory (aspects of probability theory)
60K15 Markov renewal processes, semi-Markov processes
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
Full Text: DOI
[1] Abate, J. and Whitt, W. (1997). Asymptotics for M/G/1 low-priority waiting-time tail probabilities. Queueing Systems 25, 173–233. · Zbl 0894.60088 · doi:10.1023/A:1019104402024
[2] Alsmeyer, G. (1994). On the Markov renewal theorem. Stoch. Process. Appl. 50, 37–56. · Zbl 0789.60066 · doi:10.1016/0304-4149(94)90146-5
[3] Alsmeyer, G. (2000). The ladder variables of a Markov random walk. Prob. Math. Statist. 20, 151–168. · Zbl 0988.60069
[4] Arjas, E. and Speed, T. P. (1973). Symmetric Wiener–Hopf factorizations in Markov additive processes. Z. Wahrscheinlichkeitsth. 26, 105–118. · Zbl 0244.60056 · doi:10.1007/BF00533480
[5] Asmussen, S. (1987). Applied Probability and Queues , 2nd edn. Springer, New York. · Zbl 0624.60098
[6] Asmussen, S. (2000). Ruin Probabilities . World Scientific, Singapore. · Zbl 0960.60003
[7] Bertsimas, D., Paschalidis, I. C. and Tsitsiklis, J. N. (1999). Large deviations analysis of the generalized processor sharing policy. Queueing Systems 32, 319–349. · Zbl 0937.68011 · doi:10.1023/A:1019151423773
[8] Chan, H. P. and Lai, T. L. (2003). Saddlepoint approximations and nonlinear boundary crossing probabilities of Markov random walks. Ann. Appl. Prob. 13, 395–429. · Zbl 1029.60058 · doi:10.1214/aoap/1050689586
[9] Çinlar, E. (1975). Introduction to Stochastic Processes . Prentice-Hall, Englewood Cliffs, NJ.
[10] Collamore, J. F. (2002). Importance sampling techniques for the multidimensional ruin problem for general Markov additive sequences of random vectors. Ann. Appl. Prob. 12, 382–421. · Zbl 1021.65003 · doi:10.1214/aoap/1015961169
[11] Fayolle, G., Malyshev, V. A. and Menshikov, M. V. (1995). Topics in the Constructive Theory of Countable Markov Chains . Cambridge University Press. · Zbl 0823.60053 · doi:10.1017/CBO9780511984020
[12] Foley, R. D. and McDonald, D. R. (2001). Join the shortest queue: stability and exact asymptotics. Ann. Appl. Prob. 11, 569–607. · Zbl 1016.60078
[13] Grassmann, W. K. and Heyman, D. P. (1990). Equilibrium distribution of block-structured Markov chains with repeating rows. J. Appl. Prob. 27, 557–576. · Zbl 0716.60076 · doi:10.2307/3214541
[14] Li, Q. and Zhao, Y. Q. (2002). Light-tailed asymptotics of stationary probability vector of Markov chains of GI/G/1-type. Submitted.
[15] Loynes, R. M. (1962). The stability of a queue with non-independent inter-arrival and service times. Proc. Camb. Phil. Soc. 58, 497–520. · Zbl 0203.22303 · doi:10.1017/S0305004100036781
[16] McDonald, D. R. (1999). Asymptotics of first passage times for random walk in an orthant. Ann. Appl. Prob. 9, 110–145. · Zbl 0937.60091 · doi:10.1214/aoap/1029962599
[17] Miyazawa, M. (2002). A Markov renewal approach to the asymptotic decay of the tail probabilities in risk and queueing processes. Prob. Eng. Inf. Sci. 16, 139–150. · Zbl 1005.60094 · doi:10.1017/S0269964802162012
[18] Miyazawa, M. (2002). A paradigm of Markov additive processes for queues and their networks. In Matrix-Analytic Methods , eds G. Latouche and P. G. Taylor, World Scientific, River Edge, NJ, pp. 265–289. · Zbl 1162.90403
[19] Miyazawa, M. (2003). Conjectures on decay rates of tail probabilities in generalized Jackson and batch movement networks. J. Operat. Res. Soc. Japan 46, 74–98. · Zbl 1107.90320
[20] Miyazawa, M. (2004). The Markov renewal approach to M/G/1-type queues with countably many background states. Queueing Systems 46, 177–196. · Zbl 1056.90035 · doi:10.1023/B:QUES.0000021148.33178.0f
[21] Neuts, M. F. (1981). Matrix-Geometric Solutions in Stochastic Models. An Algorithmic Approach . Johns Hopkins University Press, Baltimore, MD. · Zbl 0469.60002
[22] Neuts, M. F. (1989). Structured Stochastic Matrices of M/G/1 Type and Their Applications . Marcel Dekker, New York. · Zbl 0695.60088
[23] Ney, P. and Nummelin, E. (1987). Markov additive processes. I. Eigenvalue properties and limit theorems. Ann. Prob. 15, 561–592. JSTOR: · Zbl 0625.60027 · doi:10.1214/aop/1176992159 · links.jstor.org
[24] Seneta, E. (1981). Nonnegative Matrices and Markov Chains , 2nd edn. Springer, New York. · Zbl 0471.60001
[25] Shurenkov, V. M. (1984). On the theory of Markov renewal. Theory Prob. Appl. 29, 247–265. · Zbl 0557.60078 · doi:10.1137/1129036
[26] Takahashi, Y., Fujimoto, K. and Makimoto, N. (2001). Geometric decay of the steady-state probabilities in a quasi-birth-and-death process with a countable number of phases. Stoch. Models 17, 1–24. · Zbl 0985.60074 · doi:10.1081/STM-100001397
[27] Zhang, Z. L. (1998). Large deviations and the generalized processor sharing schedule for a multiple-queue system. Queueing Systems 28, 349–376. · Zbl 0922.90070 · doi:10.1023/A:1019163509718
[28] Zhao, Y. Q., Li, W. and Alfa, A. S. (1999). Duality results for block-structured transition matrices. J. Appl. Prob. 36, 1045–1057. · Zbl 0978.60082 · doi:10.1239/jap/1032374754
[29] Zhao, Y. Q., Li, W. and Braun, W. J. (1998). Infinite block-structured transition matrices and their properties. Adv. Appl. Prob. 30, 365–384. · Zbl 0910.60052 · doi:10.1239/aap/1035228074
[30] Zhao, Y. Q., Li, W. and Braun, W. J. (2003). Censoring, factorizations and spectral analysis for transition matrices with block-repeating entries. Methodology Comput. Appl. Prob. 5, 35–58. · Zbl 1022.60073 · doi:10.1023/A:1024125320911
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.