Subexponential asymptotics for steady state tail probabilities in a single-server queue with regenerative input flow

S. Zh. Aibatov   ; L. G. Afanasyeva

Teoriâ veroâtnostej i ee primeneniâ, Tome 62 (2017) no. 3, pp. 423-445

Résumé

The present paper is devoted to queueing systems with regenerative input flow in the presence of heavy tails. Our goal is to develop an asymptotics for the probability of the waiting time process in a stationary regime to exceed a high level. In this paper, we consider the total service time of customers arriving during the time-interval $[0,t]$ as an input flow $X(t)$. This allows us to consider a case when the service times $\{\eta_n\}_{n=1}^\infty$ are dependent random variables that, besides, may be dependent on a number of customers arriving in $[0,t]$. We obtain conditions for the virtual waiting time process in steady state to have a subexponential distribution function. We apply this result to a system with a Markov modulated semi-Markov input flow. We also consider a queue with a doubly stochastic Poisson flow in the case when the random intensity is a regenerative process. We show that these results could be transferred to corresponding systems with an unreliable server.

Détail

Keywords: large deviations, regenerative flow, subexponential distributions, waiting timeю.

Bibliographie

[1] L. G. Afanas'eva, E. E. Bashtova, “Limit theorems for queueing systems with doubly stochastic Poisson arrivals (heavy traffic conditions)”, Problems Inform. Transmission, 44:4 (2008), 352–369 | DOI | MR | Zbl

[2] L. G. Afanasyeva, E. E. Bashtova, “Large deviation probabilities for queuing system with regenerating input flow”, Theory Probab. Appl., 60:1 (2016), 120–126 | DOI | DOI | MR | Zbl

[3] S. Zh. Aibatov, “Veroyatnosti bolshikh uklonenii dlya sistemy $M/G/1/\infty$ s nenadezhnym priborom”, Teoriya veroyatn. i ee primen., 61:2 (2016), 378–384 | DOI

[4] A. A. Borovkov, “Some limit theorems in the theory of queues. I”, Theory Probab. Appl., 9:4 (1964), 550–565 | DOI | MR | Zbl

[5] A. A. Borovkov, “On factorization identities and properties of the distribution of the supremum of sequential sums”, Theory Probab. Appl., 15:3 (1970), 359–402 | DOI | MR | Zbl

[6] A. A. Borovkov, Stochastic processes in queueing theory, Appl. Math., Springer-Verlag, New York–Berlin, 1976, xi+280 pp. | MR | MR | Zbl | Zbl

[7] A. A. Borovkov, Probability theory, Gordon and Breach Science Publishers, Amsterdam, 1998, x+474 pp. | MR | MR | Zbl | Zbl

[8] A. A. Borovkov, “On subexponential distributions and asymptotics of the distribution of the maximum of sequential sums”, Siberian Math. J., 43:6 (2002), 995–1022 | DOI | MR | Zbl

[9] L. Afanasyeva, E. Bashtova, E. Bulinskaya, “Limit theorems for semi-Markov queues and their applications”, Comm. Statist. Simulation Comput., 41:6 (2012), 688–709 | DOI | MR | Zbl

[10] L. G. Afanaseva, E. E. Bashtova, “Coupling method for asymptotic analysis of queues with regenerative input and unreliable server”, Queueing Syst., 76:2 (2014), 125–147 | DOI | MR | Zbl

[11] G. Alsmeyer, M. Sgibnev, “On the tail behaviour of the supremum of a random walk defined on a Markov chain”, Yokohama Math. J., 46:2 (1999), 139–159 | MR | Zbl

[12] K. Arndt, “Asymptotic properties of the distribution of the supremum of a random walk on a Markov chain”, Theory Probab. Appl., 25:2 (1980), 309–324 | DOI | MR | Zbl

[13] S. Asmussen, “Semi-Markov queues with heavy tails”, Semi-Markov models and applications (Compiègne, 1998), Kluwer Acad. Publ., Dordrecht, 1999, 269–284 | MR | Zbl

[14] S. Asmussen, Applied probability and queues, Wiley Ser. Probab. Math. Statist. Appl. Probab. Statist., John Wiley Sons, Ltd., Chichester, 1987, x+318 pp. | MR | Zbl

[15] S. Asmussen, H. Schmidli, V. Schmidt, “Tail probabilities for non-standard risk and queueing processes with subexponential jumps”, Adv. in Appl. Probab., 31:2 (1999), 422–447 | DOI | MR | Zbl

[16] A. A. Borovkov, K. A. Borovkov, Asymptotic analysis of random walks. Heavy-tailed distributions, Encyclopedia Math. Appl., Cambridge Univ. Press, Cambridge, 118, xxx+625 pp. | DOI | MR | Zbl

[17] J. W. Cohen, The single server queue, North-Holland Delta Ser., 8, North-Holland Publishing Co., Amsterdam–London; John Wiley Sons, Inc., New York, 1969, xiv+657 pp. | MR | Zbl

[18] D. Denisov, S. Foss, D. Korshunov, “Asymptotics of randomly stopped sums in the presence of heavy tails”, Bernoulli, 16:4 (2010), 971–994 | DOI | MR | Zbl

[19] S. Foss, T. Konstantopoulos, S. Zachary, “Discrete and continuous time modulated random walks with heavy-tailed increments”, J. Theoret. Probab., 20:3 (2007), 581–612 | DOI | MR | Zbl

[20] S. Foss, D. Korshunov, S. Zachary, An introduction to heavy-tailed and subexponential distributions, Springer Ser. Oper. Res. Financ. Eng., Springer, New York, 2011, x+123 pp. | DOI | MR | Zbl

[21] A. Ganesh, N. O'Connell, D. Wischik, Big queues, Lecture Notes in Math., 1838, Springer-Verlag, Berlin, 2004, xii+254 pp. | DOI | MR | Zbl

[22] D. P. Gaver, Jr., “A waiting line with interrupted service, including priorities”, J. Roy. Statist. Soc. Ser. B, 24 (1962), 73–90 | MR | Zbl

[23] P. W. Glynn, W. Whitt, “Logarithmic asymptotics for steady-state tail probabilities in a single-server queue”, J. Appl. Probab., 31A (1994), 131–156 | DOI | MR | Zbl

[24] J. Grandell, Doubly stochastic Poisson processes, Lecture Notes in Math., 529, Springer-Verlag, Berlin–New York, 1976, x+234 pp. | DOI | MR | Zbl

[25] P. R. Jelenković, A. A. Lazar, “Subexponential asymptotics of a Markov-modulated random walk with queueing applications”, J. Appl. Probab., 35:2 (1998), 325-347 | DOI | MR | Zbl

[26] C. Klüppelberg, “Subexponential distributions and integrated tails”, J. Appl. Prob., 25:1 (1988), 132–141 | DOI | MR | Zbl

[27] W. E. Leland, M. S. Taqqu, W. Willinger, D. Wilson, “On the self-similar nature of Ethernet traffic”, IEEE/ACM Trans. Netw., 2:1 (1994), 1–15 | DOI

[28] D. V. Lindley, “The theory of queues with a single server”, Proc. Cambridge Philos. Soc., 48:2 (1952), 277–289 | DOI | MR | Zbl

[29] R. M. Loynes, “The stability of a queue with non-independent inter-arrival and service times”, Proc. Cambridge Philos. Soc., 58:3 (1962), 497–520 | DOI | MR | Zbl

[30] W. L. Smith, “Regenerative stochastic processes”, Proc. Roy. Soc. London. Ser. A, 232:1188 (1955), 6–31 | DOI | MR | Zbl

[31] A. G. Pakes, “On the tails of waiting-time distributions”, J. Appl. Probab., 12:3 (1975), 555–564 | DOI | MR | Zbl

[32] E. J. G. Pitman, “Subexponential distribution functions”, J. Austral. Math. Soc. Ser. A, 29:3 (1980), 337–347 | DOI | MR | Zbl

[33] S. I. Resnick, “Heavy tail modeling and teletraffic data”, Ann. Statist., 25:5 (1997), 1805–1869 | DOI | MR | Zbl

[34] H. Thorisson, Coupling, stationarity, and regeneration, Probab. Appl. (N. Y.), Springer-Verlag, New York, 2000, xiv+517 pp. | MR | Zbl

[35] N. Veraverbeke, “Asymptotic behaviour of Wiener–Hopf factors of a random walk”, Stochastic Processes Appl., 5:1 (1977), 27–37 | DOI | MR | Zbl

[36] W. Willinger, M. S. Taqqu, W. E. Leland, D. V. Wilson, “Self-similarity in high-speed packet traffic: analysis and modeling of Ethernet traffic measurements”, Statist. Sci., 10:1 (1995), 67–85 | DOI | Zbl