Load Balancing in the Nondegenerate Slowdown Regime

References

• Adan I, van Houtum G-J, van der Wal J (1994) Upper and lower bounds for the waiting time in the symmetric shortest queue system. Ann. Oper. Res. 48(2):197–217.Crossref, Google Scholar
• Asmussen S (2003) Applied Probability and Queues (Springer-Verlag, New York).Google Scholar
• Atar R (2012) A diffusion regime with nondegenerate slowdown. Oper. Res. 60(2):490–500.Link, Google Scholar
• Atar R, Gurvich I (2014) Scheduling parallel servers in the nondegenerate slowdown diffusion regime: Asymptotic optimality results. Ann. Appl. Probab. 24(2):760–810.Crossref, Google Scholar
• Atar R, Solomon N (2011) Asymptotically optimal interruptible service policies for scheduling jobs in a diffusion regime with nondegenerate slowdown. Queueing Systems 69(3–4):217–235.Crossref, Google Scholar
• Badonnel R, Burgess M (2008) Dynamic pull-based load balancing for autonomic servers. Network Operations and Management Symposium, 2008. NOMS 2008 (IEEE, New York), 751–754.Crossref, Google Scholar
• Billingsley P (2013) Convergence of Probability Measures (John Wiley & Sons, Hoboken, NJ).Google Scholar
• Bonomi F (1990) On job assignment for a parallel system of processor sharing queues. IEEE Trans. Comput. 39(7):858–869.Crossref, Google Scholar
• Borst S, Mandelbaum A, Reiman MI (2004) Dimensioning large call centers. Oper. Res. 52(1):17–34.Link, Google Scholar
• Bramson M, Lu Y, Prabhakar B (2012) Asymptotic independence of queues under randomized load balancing. Queueing Systems 71(3):247–292.Crossref, Google Scholar
• Bramson M, Lu Y, Prabhakar B (2013) Decay of tails at equilibrium for FIFO join the shortest queue networks. Ann. Appl. Probab. 23(5):1841–1878.Crossref, Google Scholar
• Braverman A (2018) Steady-state analysis of the join the shortest queue model in the Halfin-Whitt regime. Preprint arXiv:1801.05121.Google Scholar
• Brown L, Gans N, Mandelbaum A, Sakov A, Shen H, Zeltyn S, Zhao L (2005) Statistical analysis of a telephone call center: A queueing-science perspective. J. Amer. Statist. Assoc. 100(469):36–50.Crossref, Google Scholar
• Erlang AK (1917) Solution of some problems in the theory of probabilities of significance in automatic telephone exchanges. Post Office Electrical Engineer's J. 10:189–197.Google Scholar
• Eschenfeldt P, Gamarnik D (2018) Join the shortest queue with many servers. The heavy traffic asymptotics. Math. Oper. Res. 43(3):867–886.Link, Google Scholar
• Flatto L, McKean HP (1977) Two queues in parallel. Comm. Pure Appl. Math. 30(2):255–263.Crossref, Google Scholar
• Foschini G, Salz J (1978) A basic dynamic routing problem and diffusion. IEEE Trans. Comm. 26(3):320–327.Crossref, Google Scholar
• Foss S, Stolyar AL (2017) Large-scale join-idle-queue system with general service times. J. Appl. Probab. 54(4):995–1007.Crossref, Google Scholar
• Foss SG (1980) Approximation of multichannel queueing systems. Sib. Math. J. 21(6):851–857.Crossref, Google Scholar
• Foss SG (1984) Queues with customers of several types. Advances in Probability Theory: Limit Theorems and Related Problems (Springer, New York), 348–377.Google Scholar
• Freidlin MI, Wentzell AD (1998) Random Perturbations of Dynamical Systems, Vol. 260 (Springer, New York).Crossref, Google Scholar
• Gamarnik D, Tsitsiklis JN, Zubeldia M (2016) Delay, memory, and messaging tradeoffs in distributed service systems. Proc. 2016 ACM SIGMETRICS Internat. Conf. Measurement Model. Comput. Sci. (Association for Computing Machinery, New York), 1–12.Crossref, Google Scholar
• Gupta V, Balter MH, Sigman K, Whitt W (2007) Analysis of join-the-shortest-queue routing for web server farms. Performance Eval. 64(9):1062–1081.Crossref, Google Scholar
• Gurvich I (2004) Design and control of the M/M/N queue with multi-class customers and many servers. Unpublished master’s thesis, Technion, Haifa, Israel.Google Scholar
• Haight FA (1958) Two queues in parallel. Biometrika 45(3–4):401–410.Crossref, Google Scholar
• Halfin S, Whitt W (1981) Heavy-traffic limits for queues with many exponential servers. Oper. Res. 29(3):567–588.Link, Google Scholar
• He S (2015) Diffusion approximation for efficiency-driven queues: A space-time scaling approach. Working paper, National University of Singapore.Google Scholar
• Hunt PJ, Kurtz TG (1994) Large loss networks. Stochastic Processes Their Appl. 53(2):363–378.Crossref, Google Scholar
• Iglehart DL, Whitt W (1970) Multiple channel queues in heavy traffic. I. Adv. Appl. Probab. 2(1):150–177.Crossref, Google Scholar
• Jonckheere M, Prabhu BJ (2016) Asymptotics of insensitive load balancing and blocking phases. SIGMETRICS Performance Eval. Rev. 44(1):311–322.Crossref, Google Scholar
• Kelly FP (2011) Reversibility and Stochastic Networks (Cambridge University Press, New York).Google Scholar
• Kendall DG (1951) Some problems in the theory of queues. J. Royal Statist. Soc. Ser. B (Methodological) 13:151–185.Crossref, Google Scholar
• Khasminskii RZ (1966) On stochastic processes defined by differential equations with a small parameter. Theory Probab. Appl. 11(2):211–228.Crossref, Google Scholar
• Kingman JFC (1961) Two similar queues in parallel. Ann. Math. Statist. 32(4):1314–1323.Crossref, Google Scholar
• Laws CN, Teh YC (2000) Alternative routeing in fully connected queueing networks. Adv. Appl. Probab. 32(4):962–982.Crossref, Google Scholar
• Liu Z, Nain P, Towsley D (1995) Sample path methods in the control of queues. Queueing Systems 21(3–4):293–335.Crossref, Google Scholar
• Lu Y, Xie Q, Kliot G, Geller A, Larus JR, Greenberg A (2011) Join-idle-queue: A novel load balancing algorithm for dynamically scalable web services. Performance Eval. 68(11):1056–1071.Crossref, Google Scholar
• Luczak MJ, Norris JR (2013) Averaging over fast variables in the fluid limit for Markov chains: Application to the supermarket model with memory. Ann. Appl. Probab. 23(3):957–986.Crossref, Google Scholar
• Maglaras C, Yao J, Zeevi A (2017) Optimal price and delay differentiation in large-scale queueing systems. Management Sci. 64(5):2427–2444.Link, Google Scholar
• Mandelbaum A, Shaikhet G (2004) Personal communication.Google Scholar
• Mitzenmacher M (2001) The power of two choices in randomized load balancing. IEEE Trans. Parallel Distrib. Systems 12(10):1094–1104.Crossref, Google Scholar
• Mukherjee D, Borst SC, van Leeuwaarden JSH, Whiting PA (2016) Universality of load balancing schemes on the diffusion scale. J. Appl. Probab. 53(4):1111–1124.Crossref, Google Scholar
• Pang G, Talreja R, Whitt W (2007) Martingale proofs of many-server heavy-traffic limits for Markovian queues. Probab. Surv. 4(1):193–267.Crossref, Google Scholar
• Robert P, Véber A (2015) A stochastic analysis of resource sharing with logarithmic weights. Ann. Appl. Probab. 25(5):2626–2670.Crossref, Google Scholar
• Stolyar AL (2015) Pull-based load distribution in large-scale heterogeneous service systems. Queueing Systems 80(4):341–361.Crossref, Google Scholar
• Tsitsiklis JN, Xu K (2012) On the power of (even a little) resource pooling. Stochastic Systems 2(1):1–66.Link, Google Scholar
• Veretennikov AY (1991) On the averaging principle for systems of stochastic differential equations. Math. USSR Sbornik 69(1):271–284.Crossref, Google Scholar
• Vvedenskaya ND, Dobrushin RL, Karpelevich FI (1996) Queueing system with selection of the shortest of two queues: An asymptotic approach. Probl. Peredachi Inform. 32(1):20–34.Google Scholar
• Walton NS (2012) Flow-level convergence and insensitivity for multi-class queueing networks. Stochastic Systems 2(1):115–148.Link, Google Scholar
• Whitt W (2003) How multiserver queues scale with growing congestion-dependent demand. Oper. Res. 51(4):531–542.Link, Google Scholar
• Winston W (1977) Optimality of the shortest line discipline. J. Appl. Probab. 14(1):181–189.Crossref, Google Scholar
• Ying L (2016) On the rate of convergence of the power-of-two-choices to its mean-field limit. Preprint arXiv:1605.06581Google Scholar