Asymptotic Optimality of Power-of-d Load Balancing in Large-Scale Systems

References

• [1] Atar R, Biswas A, Kaspi H (2018) Law of large numbers for the many-server earliest-deadline-first queue. Stochastic Processes Their Appl. 128(7):2270–2296.Google Scholar
• [2] Atar R, Budhiraja A, Ramanan K (2008) Deterministic and stochastic differential inclusions with multiple surfaces of discontinuity. Probab. Theory Related Fields 142(1):249–283.Google Scholar
• [3] Atar R, Biswas A, Kaspi H, Ramanan K (2018) A Skorokhod map on measure-valued paths with applications to priority queues. Ann. Appl. Probab. 28(1):418–481.Google Scholar
• [4] Borovkov AA (1976) Stochastic Processes in Queueing Theory (Springer, New York).Google Scholar
• [5] Costantini C (1992) The Skorohod oblique reflection problem in domains with corners and application to stochastic differential equations. Probab. Theory Related Fields 91(1):43–70.Google Scholar
• [6] Ephremides A, Varaiya P, Walrand J (1980) A simple dynamic routing problem. IEEE Trans. Automatic Control 25(4):690–693.Crossref, Google Scholar
• [7] 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
• [8] Ethier SN, Kurtz TG (2009) Markov Processes: Characterization and Convergence (John Wiley & Sons, Hoboken, NJ).Google Scholar
• [9] Feller W (1968) An Introduction to Probability Theory and Its Applications, vol. 1, 3rd ed., Wiley Series in Probability and Mathematical Statistics (John Wiley & Sons, New York).Google Scholar
• [10] Halfin S, Whitt W (1981) Heavy-traffic limits for queues with many exponential servers. Oper. Res. 29(3):567–588.Google Scholar
• [11] Hunt P, Kurtz T (1994) Large loss networks. Stochastic Processes Their Appl. 53(2):363–378.Google Scholar
• [12] Jagerman D (1974) Some properties of the Erlang loss function. Bell System Tech. J. 53(3):525–551.Google Scholar
• [13] Johri PK (1989) Optimality of the shortest line discipline with state-dependent service rates. Eur. J. Oper. Res. 41(2):157–161.Google Scholar
• [14] Kruk Ł, Lehoczky J, Ramanan K, Shreve S (2008) Double Skorokhod map and reneging real-time queues. Ethier SN, Feng J, Stockbridge RH, eds. Markov Processes and Related Topics: A Festschrift for Thomas G. Kurtz, Collections, vol. 4 (IMS, Beachwood, OH), 169–193.Crossref, Google Scholar
• [15] Kruk Ł, Lehoczky J, Ramanan K, Shreve S (2011) Heavy traffic analysis for EDF queues with reneging. Ann. Appl. Probab. 21(2):484–545.Google Scholar
• [16] Lions PL, Sznitman AS (1984) Stochastic differential equations with reflecting boundary conditions. Comm. Pure Appl. Math. 37(4):511–537.Google Scholar
• [17] Liptser R, Shiryaev A (1989) Theory of Martingales, Mathematics and Its Applications, vol. 49 (Kluwer, Dordrecht, Netherlands).Crossref, Google Scholar
• [18] Menich R (1987) Optimality of shortest queue routing for dependent service stations. Levine WS, ed. 26th IEEE Conf. Decision Control (IEEE, Los Angeles), 1069–1072.Google Scholar
• [19] Menich R, Serfozo RF (1991) Optimality of routing and servicing in dependent parallel processing systems. Queueing Systems 9(4):403–418.Google Scholar
• [20] Mitzenmacher M (2001) The power of two choices in randomized load balancing. IEEE Trans. Parallel Distribution Systems 12(10):1094–1104.Google Scholar
• [21] 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.Google Scholar
• [22] Mukherjee D, Borst SC, van Leeuwaarden JSH, Whiting PA (2018) Universality of power-of-d load balancing in many-server systems. Stochastic Systems 8(4):265–292.Google Scholar
• [23] Mukhopadhyay A, Mazumdar RR, Guillemin F (2015) The power of randomized routing in heterogeneous loss systems. Meo M, Rosenberg C, Wittevrongel S, eds. Proc. 2015 27th Internat. Teletraffic Congress (IEEE, Piscataway, NJ), 125–133.Google Scholar
• [24] Mukhopadhyay A, Karthik A, Mazumdar RR, Guillemin F (2015) Mean field and propagation of chaos in multi-class heterogeneous loss models. Performance Evaluation 91:117–131.Google Scholar
• [25] Pang G, Talreja R, Whitt W (2007) Martingale proofs of many-server heavy-traffic limits for Markovian queues. Probab. Surveys 4:193–267.Google Scholar
• [26] Patel P, Bansal D, Yuan L, Murthy A, Greenberg A, Maltz DA, Kern R, et al.. (2013) Ananta: Cloud scale load balancing. ACM SIGCOMM Comput. Comm. Rev. 43(4):207–218.Google Scholar
• [27] Ramanan K (2006) Reflected diffusions defined via the extended Skorokhod map. Electronic J. Probab. 11:934–992.Google Scholar
• [28] Robert P (2003) Stochastic Networks and Queues (Springer, Berlin Heidelberg).Google Scholar
• [29] Sparaggis PD, Towsley D, Cassandras CG (1993) Extremal properties of the shortest/longest non-full queue policies in finite-capacity systems with state-dependent service rates. J. Appl. Probab. 30(1):223–236.Google Scholar
• [30] Sparaggis PD, Towsley D, Cassandras CG (1994) Sample path criteria for weak majorization. Adv. Appl. Probab. 26(1):155–171.Google Scholar
• [31] Stolyar AL (2015) Pull-based load distribution in large-scale heterogeneous service systems. Queueing Systems 80(4):341–361.Google Scholar
• [32] Stolyar AL (2017) Pull-based load distribution among heterogeneous parallel servers: The case of multiple routers. Queueing Systems 85(1):31–65.Google Scholar
• [33] Stolyar AL, Ramanan K (2001) Largest weighted delay first scheduling: Large deviations and optimality. Ann. Appl. Probab. 11(1):1–48.Google Scholar
• [34] Towsley D (1995) Application of majorization to control problems in queueing systems. Chrétienne P, Coffman EG, Lenstra JK, Liu Z, eds. Scheduling Theory and Its Application (John Wiley & Sons, Chichester, UK), 295–311.Google Scholar
• [35] Towsley D, Sparaggis P, Cassandras C (1992) Optimal routing and buffer allocation for a class of finite capacity queueing systems. IEEE Trans. Automatic Control 37(9):1446–1451.Google Scholar
• [36] Turner SR (1998) The effect of increasing routing choice on resource pooling. Probab. Engrg. Inform. Sci. 12(1):109–124.Google Scholar
• [37] Vvedenskaya ND, Dobrushin RL, Karpelevich FI (1996) Queueing system with selection of the shortest of two queues: An asymptotic approach. Problemy Peredachi Informatsii 32(1):20–34.Google Scholar
• [38] Weber RR (1978) On the optimal assignment of customers to parallel servers. J. Appl. Probab. 15(2):406–413.Google Scholar
• [39] Whitt W (1984) Heavy-traffic approximations for service systems with blocking. AT&T Bell Laboratories Tech. J. 63(5):689–708.Google Scholar
• [40] Whitt W (2002) Stochastic-Process Limits, Springer Series in Operations Research and Financial Engineering (Springer-Verlag, New York).Crossref, Google Scholar
• [41] Winston W (1977) Optimality of the shortest line discipline. J. Appl. Probab. 14(1):181–189.Google Scholar
• [42] Xie Q, Dong X, Lu Y, Srikant R (2015) Power of d choices for large-scale bin packing. Sengupta S, Shah D, eds. Proc. 2015 ACM SIGMETRICS Internat. Conf. Measurement Model. Comput. Systems (ACM, New York), 321–334.Google Scholar