Home | Articles | Past volumes | About | Login | Notify | Contact | Search
 Stochastic Systems > Vol. 7 (2017) open journal systems 


Heavy-traffic limit for the initial content process

A. Korhan Aras, North Carolina State University
Yunan Liu, North Carolina State University
Ward Whitt, Columbia University


Abstract
To understand the performance of a queueing system, it can be useful to focus on the evolution of the content that is initially in service at some time. That necessarily will be the case in service systems that provide service during normal working hours each day, with the system shutting down at some time, except that all customers already in service at the termination time are allowed to complete their service. Also, for infinite-server queues, it is often fruitful to partition the content into the initial content and the new input, because these can be analyzed separately. With i.i.d service times having a non-exponential distribution, the state of the initial content can be described by specifying the elapsed service times of the remaining initial customers. That initial content process is then a Markov process. This paper establishes a many-server heavy-traffic (MSHT) functional central limit theorem (FCLT) for the initial content process in the space \(\mathbb{D}_{\mathbb{D}}\), assuming a FCLT for the initial age process, with the number of customers initially in service growing in the limit. The proof applies a symmetrization lemma from the literature on empirical processes to address a technical challenge: For each time, including time 0, the conditional remaining service times, given the ages, are mutually independent but in general not identically distributed.

AMS 2000 subject classifications: Primary 60K25; secondary 60F17, 90B22, 37C55.

Keywords: Heavy-traffic limits for queues, many-server queues, infiniteserver queues, terminating queues, time-varying arrivals, two-parameter processes, central limit theorem for non-identically distributed random variables.

Creative Common LOGO

Full Text: PDF


Aras, A. Korhan, Liu, Yunan, Whitt, Ward, Heavy-traffic limit for the initial content process, Stochastic Systems, 7, (2017), 95-142 (electronic). DOI: 10.1214/15-SSY175.

References

[1]    Billingsley, P(1999). Convergence of Probability Measures, 2nd ed., Wiley, New York. MR1700749

[2]    Bremaud, P. (1981). Point Processes and Queues: Martingale Dynamics, Springer-Verlag, New York. MR0636252

[3]    Decreusefond, L. and Moyal, P. (2008). A functional central limit theorem for the M∕GI∕queue. Ann. Appl. Probab. 18(6) 2156–2178. MR2473653

[4]    Donsker, M. (1952). Justification and extension of Doob’s heuristic approach to the Kolmogorov-Smirnov theorems. Ann. Math. Statist. 23 277–281. MR0047288

[5]    Duffield, N. and Whitt, W. (1997). Control and recovery from rare congestion events in a large multi-server system. Queueing Syst. 26 69–104. MR1480867

[6]    Ethier, S. N. and Kurtz, T. G. (1986). Markov Processes: Characterization and Convergence. Wiley, New York. MR0838085

[7]    Feller, W. (1971). An Introduction to Probability Theory and its Applications, John Wiley and Sons, New York. MR0270403

[8]    Gerhardt, I. and Nelson, B. (2009). Transforming renewal processes for simulation of nonstationary arrival processes. INFORMS J. Comput. 21(4) 630–640. MR2588345

[9]    Glynn, P. W. and Whitt, W. (1991). A new view of the heavy-traffic limit theorem for the infinite-server queue. Adv. in Appl. Probab. 23(1) 188–209. MR1091098

[10]    Goldberg, D. and Whitt, W. (2008). The last departure time from an Mt∕G∕queue with a terminating arrival process. Queueing Syst. 58(2) 77–104. MR2390269

[11]    He, B., Liu, Y. and Whitt, W. (2016). Staffing a service system with non-Poisson nonstationary arrivals. Probability in the Engineering and Information Sciences. 30 593–621. MR3569137

[12]    Gut, A. (2005). Probability: A Graduate Course. Springer, New York. MR2125120

[13]    Halfin, S. and Whitt, W. (1981). Heavy-traffic limits for queues with many exponential servers. Oper. Res. 29(3) 567–588. MR0629195

[14]    Iglehart, D. and Whitt, W. (1970). Multiple channel queues in heavy traffic II: Sequences, networks, and batches. Adv. in Appl. Probab. 2(2) 355–369. MR0282443

[15]    Jacod, J. and Shiryaev, A. N. (1987). Limit Theorems for Stochastic Processes. Springer-Verlag, Berlin. MR0959133

[16]    Kang, W. and Pang, G. (2014). Equivalence of fluid models for Gt∕GI∕N + GI queues. Working paper, Pennsylvania State University.

[17]    Kang, W. and Ramanan, K. (2010). Fluid limits of many-server queues with reneging. Ann. Appl. Probab. 20(6) 2204–2260. MR2759733

[18]    Kaspi, H. and Ramanan, K. (2011). Law of large numbers limits for many-server queues. Ann. Appl. Probab. 21(1) 33–114. MR2759196

[19]    Kaspi, H. and Ramanan, K. (2013). SPDE limits of many-server queues. Ann. Appl. Probab. 23(1) 145–229. MR3059233

[20]    Krichagina, E. V. and Puhalskii, A. A. (1997). A heavy-traffic analysis of a closed queueing system with a GI∕service center. Queueing Syst. 25 235–280. MR1458591

[21]    Liu, R., Kuhl, M. E., Liu, Y. and Wilson, J. R. Modeling and simulation of nonstationary and non-Poisson processes. Working paper, North Carolina State University, 2017.

[22]    Liu, Y. and Whitt, W. (2011). Large-time asymptotics for the Gt∕Mt∕st + GIt many-server fluid queue with abandonment. Queueing Systems 67 145–182. MR2771198

[23]    Liu, Y. and Whitt, W. (2012). A many-server fluid limit for the Gt∕GI∕st+GI queueing model experiencing periods of overloading. Oper. Res. Lett. 40(5) 307–312. MR2956434

[24]    Liu, Y. and Whitt, W. (2014). Many-server heavy-traffic limit for queues with time-varying parameters. Ann. Appl. Probab. 24(1) 378–421. MR3161651

[25]    Liu, Y. and Whitt, W. (2014). Stabilizing performance in networks of queues with time-varying arrival rates. Prob. Engr. Inf. Sci. 28(4) 419–449. MR3256197

[26]    Louchard, G. (1988). Large finite population queueing systems. Part 1: The infinite server model Comm. Statist. Stochastic Models 4(3) 473–505. MR0971602

[27]    Marcus, M. B. and Zinn, J. (1984). The bounded law of the iterated logarithm for the weighted empirical distribution process in the non-i.i.d case. Ann. Probab. 12(2) 335–360. MR0735842

[28]    Massey, W. A. and Whitt, W. (1994). Unstable asymptotics for nonstationary queues. Math. Oper. Res. 19(2) 267–291. MR1290501

[29]    Pang, G., Talreja, R. and Whitt, W. (2007). Martingale proofs of many-server heavy-traffic limits for Markovian queues. Probab. Surv. 4 193–267. MR2368951

[30]    Pang, G. and Whitt, W. (2010). Two-parameter heavy-traffic limits for infinite-server queues. Queueing Syst. 65(4) 325–364. MR2671058

[31]    Pang, G. and Whitt, W. (2013). Two-parameter heavy-traffic limits for infinite-server queues with dependent service times. Queueing Syst. 73(2) 119–146. MR3016577

[32]    Puhalskii, A. A. and Reed, J. E. (2010). On many-server queues in heavy traffic. Ann. Appl. Probab. 20(1) 129–195. MR2582645

[33]    Puhalskii, A. A. and Reiman, M. I. (2000). The multiclass GI∕PH∕N queue in the Halfin-Whitt regime. Adv. in Appl. Probab. 32(2) 564–595. MR1778580

[34]    Reed, J. (2009). The G∕GI∕N queue in the Halfin-Whitt regime. Ann. Appl. Probab. 19(6) 2211–2269. MR2588244

[35]    Reed, J. and Talreja, R. (2015). Distribution-valued heavy-traffic limits for the G∕GI∕queue. Ann. Appl. Probab. 25(3) 1420–1474. MR3325278

[36]    Shorack, G. R. and Wellner, J. A. (2009). Empirical Processes with Applications to Statistics. SIAM Classics 59 (Updated version of 1986 Wiley edition). MR3396731

[37]    Skorohod, A. V. (1956). Limit theorems for stochastic processes. Theor. Probab. Appl. 1 261–290. MR0084897

[38]    Talreja, R. and Whitt, W. (2009). Heavy-traffic limits for waiting times in many-server queues with abandonment. Ann. Appl. Probab. 19(6) 2137–2175. MR2588242

[39]    Vapnik, V. N. and Cervonenkis, A. Y. (1971). On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications 16 264–280. MR0288823

[40]    Whitt, W. (1982). On the heavy-traffic limit theorem for GI∕G∕queues. Adv. Appl. Probab. 14(1) 171–190. MR0644013

[41]    Whitt, W. (2002). Stochastic-Process Limits, Springer-Verlag, New York. MR1876437

[42]    Whitt, W. (2005). Heavy-traffic limits for the GI∕H2∕n∕m queue. Math. Oper. Res. 30(1) 1–27. MR2125135

[43]    Zhang, J. (2013). Fluid models of many-server queues with abandonment. Queueing Syst. 73(2) 147–193. MR3016578




Home | Articles | Past volumes | About | Login | Notify | Contact | Search

Stochastic Systems. ISSN: 1946-5238