×

Join-the-shortest queue diffusion limit in Halfin-Whitt regime: sensitivity on the heavy-traffic parameter. (English) Zbl 1434.60263

Summary: Consider a system of \(N\) parallel single-server queues with unit-exponential service time distribution and a single dispatcher where tasks arrive as a Poisson process of rate \(\lambda (N)\). When a task arrives, the dispatcher assigns it to one of the servers according to the Join-the-Shortest Queue (JSQ) policy. P. Eschenfeldt and D. Gamarnik [Math. Oper. Res. 43, No. 3, 867–886 (2018; Zbl 1433.60087)] identified a novel limiting diffusion process that arises as the weak-limit of the appropriately scaled occupancy measure of the system under the JSQ policy in the Halfin-Whitt regime, where \((N-\lambda(N))/\sqrt{N}\to\beta>0\) as \(N\to\infty\). The analysis of this diffusion goes beyond the state of the art techniques, and even proving its ergodicity is nontrivial, and was left as an open question. Recently, exploiting a generator expansion framework via the Stein’s method, A. Braverman [“Steady-state analysis of the join the shortest queue model in the Halfin-Whitt regime”, Preprint, arXiv:1801.05121] established its exponential ergodicity, and adapting a regenerative approach, the authors [Ann. Appl. Probab. 29, No. 2, 1262–1309 (2019; Zbl 1467.60069)] analyzed the tail properties of the stationary distribution and path fluctuations of the diffusion.
However, the analysis of the bulk behavior of the stationary distribution, namely, the moments, remained intractable until this work. In this paper, we perform a thorough analysis of the bulk behavior of the stationary distribution of the diffusion process, and discover that it exhibits different qualitative behavior, depending on the value of the heavy-traffic parameter \(\beta\). Moreover, we obtain precise asymptotic laws of the centered and scaled steady-state distribution, as \(\beta\) tends to 0 and \(\infty\). Of particular interest, we also establish a certain intermittency phenomena in the \(\beta\to\infty\) regime and a surprising distributional convergence result in the \(\beta \to 0\) regime.

MSC:

60K25 Queueing theory (aspects of probability theory)
60J60 Diffusion processes
60K05 Renewal theory
60H20 Stochastic integral equations
PDFBibTeX XMLCite
Full Text: DOI arXiv Euclid

References:

[1] Atar, R., Budhiraja, A. and Dupuis, P. (2001). On positive recurrence of constrained diffusion processes. Ann. Probab. 29 979-1000. · Zbl 1018.60081 · doi:10.1214/aop/1008956699
[2] Banerjee, S., Burdzy, K. and Duarte, M. (2019). Gravitation versus Brownian motion. Ann. Inst. Henri Poincaré 55 1531-1565. · Zbl 1466.60163 · doi:10.1214/18-AIHP927
[3] Banerjee, S. and Mukherjee, D. (2019). Join-the-Shortest Queue diffusion limit in Halfin-Whitt regime: Tail asymptotics and scaling of extrema. Ann. Appl. Probab. 29 1262-1309. · Zbl 1467.60069 · doi:10.1214/18-AAP1436
[4] Braverman, A. (2018). Steady-state analysis of the join the shortest queue model in the Halfin-Whitt regime. Availble at arXiv:1801.05121. · Zbl 1455.90035
[5] Budhiraja, A. and Lee, C. (2007). Long time asymptotics for constrained diffusions in polyhedral domains. Stochastic Process. Appl. 117 1014-1036. · Zbl 1119.60066 · doi:10.1016/j.spa.2006.11.007
[6] Dupuis, P. and Williams, R. J. (1994). Lyapunov functions for semimartingale reflecting Brownian motions. Ann. Probab. 22 680-702. · Zbl 0808.60068 · doi:10.1214/aop/1176988725
[7] Eschenfeldt, P. and Gamarnik, D. (2018). Join the shortest queue with many servers. The heavy-traffic asymptotics. Math. Oper. Res. 43 867-886. · Zbl 1433.60087
[8] Fralix, B., Knessl, C. and van Leeuwaarden, J. S. H. (2014). First passage times to congested states of many-server systems in the Halfin-Whitt regime. Stoch. Models 30 162-186. · Zbl 1303.60086 · doi:10.1080/15326349.2014.900385
[9] Gamarnik, D. and Goldberg, D. A. (2013). On the rate of convergence to stationarity of the M/M/N queue in the Halfin-Whitt regime. Ann. Appl. Probab. 23 1879-1912. · Zbl 1287.60111 · doi:10.1214/12-AAP889
[10] Gamarnik, D. and Goldberg, D. A. (2013). Steady-state \(GI/GI/n\) queue in the Halfin-Whitt regime. Ann. Appl. Probab. 23 2382-2419. · Zbl 1285.60090 · doi:10.1214/12-AAP905
[11] Hairer, M. and Mattingly, J. C. (2009). Slow energy dissipation in anharmonic oscillator chains. Comm. Pure Appl. Math. 62 999-1032. · Zbl 1169.82012 · doi:10.1002/cpa.20280
[12] Halfin, S. and Whitt, W. (1981). Heavy-traffic limits for queues with many exponential servers. Oper. Res. 29 567-588. · Zbl 0455.60079 · doi:10.1287/opre.29.3.567
[13] Karatzas, I. and Shreve, S. (2012). Brownian Motion and Stochastic Calculus 113. Springer, Berlin. · Zbl 0638.60065
[14] Kirsch, W. (2015). A survey on the method of moments. Preprint. Available at https://www.fernuni-hagen.de/stochastik/downloads/momente.pdf.
[15] Massart, P. (2007). Concentration Inequalities and Model Selection. Lecture Notes in Math. 1896. Springer, Berlin. · Zbl 1170.60006
[16] Meyn, S. P. and Tweedie, R. L. (1993). Markov Chains and Stochastic Stability. Communications and Control Engineering Series. Springer, London. · Zbl 0925.60001
[17] Mukherjee, D., Borst, S. C. and Van Leeuwaarden, J. S. H. (2018). Asymptotically optimal load balancing topologies. Proc. ACM Meas. Anal. Comput. Syst. 2 1-29.
[18] Mukherjee, D., Borst, S. C., van Leeuwaarden, J. S. H. and Whiting, P. A. (2016). Universality of load balancing schemes on the diffusion scale. J. Appl. Probab. 53 1111-1124. · Zbl 1356.60149 · doi:10.1017/jpr.2016.68
[19] Mukherjee, D., Borst, S. C., van Leeuwaarden, J. S. H. and Whiting, P. A. (2018). Universality of power-of-\(d\) load balancing in many-server systems. Stoch. Syst. 8 265-292. · Zbl 1446.60073
[20] Protter, P. E. (2005). Stochastic Integration and Differential Equations. Springer, Berlin.
[21] Thorisson, H. (2000). Coupling, Stationarity, and Regeneration. Probability and Its Applications (New York). Springer, New York. · Zbl 0949.60007
[22] Van der Boor, M., Borst, S. C., van Leeuwaarden, J. S. H. and Mukherjee, D. (2018). Scalable load balancing in networked systems: Universality properties and stochastic coupling methods. In Proc. Int. Cong. Math.’18 (B. Sirakov, P. N. de Souza and M. Viana, eds.) 3881-3912. · Zbl 1490.90100
[23] van Leeuwaarden, J. S. H. and Knessl, C. (2011). Transient behavior of the Halfin-Whitt diffusion. Stochastic Process. Appl. 121 1524-1545. · Zbl 1235.60133 · doi:10.1016/j.spa.2011.03.007
[24] van Leeuwaarden, J. S. H. and Knessl, C. (2012). Spectral gap of the Erlang A model in the Halfin-Whitt regime. Stoch. Syst. 2 149-207. · Zbl 1296.60256 · doi:10.1287/10-SSY012
[25] Van Leeuwaarden, J. S. H., Mathijsen, B. W. J. and Zwart, B. (2017). Economies-of-scale in resource sharing systems: Tutorial and partial review of the QED heavy-traffic regime. Available at arXiv:1706.05397. · Zbl 1447.60139 · doi:10.1137/17M1133944
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.