Load Balancing Under Strict Compatibility Constraints

References

• [1] Arapostathis A, Hmedi H, Pang G (2021) On uniform exponential ergodicity of Markovian multiclass many-server queues in the Halfin–Whitt regime. Math. Oper. Res. 46(2):772–796.Google Scholar
• [2] Braess D (1968) Über ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung 12(1):258–268.Google Scholar
• [3] Bramson M (2011) Stability of join the shortest queue networks. Ann. Appl. Probab. 21(4):1568–1625.Crossref, Google Scholar
• [4] Budhiraja A, Mukherjee D, Wu R (2019) Supermarket model on graphs. Ann. Appl. Probab. 29(3):1740–1777.Crossref, Google Scholar
• [5] Cardinaels E, Borst SC, van Leeuwaarden JSH (2019) Job assignment in large-scale service systems with affinity relations. Working paper, Eindhoven University of Technology, Eindhoven, Netherlands.Google Scholar
• [6] Cardinaels E, Borst S, van Leeuwaarden JSH (2020) Redundancy scheduling with locally stable compatibility graphs. Working paper, Eindhoven University of Technology, Eindhoven, Netherlands.Google Scholar
• [7] Chung FRK, Graham RL, Wilson RM (1989) Quasi-random graphs. Combinatorica 9(4):345–362.Crossref, Google Scholar
• [8] Cruise J, Jonckheere M, Shneer S (2020) Stability of JSQ in queues with general server-job class compatibilities. Queueing Systems 95(3–4):271–279.Crossref, Google Scholar
• [9] Deimling K (2006) Ordinary Differential Equations in Banach Spaces. Lecture Notes in Mathematics, vol. 596 (Springer, Berlin).Google Scholar
• [10] Ethier SN, Kurtz TG (2009) Markov Processes: Characterization and Convergence (John Wiley & Sons, Hoboken, NJ).Google Scholar
• [11] Foss SG, Chernova NI (1998) On the stability of a partially accessible multi-station queue with state-dependent routing. Queueing Systems 29(1):55–73.Crossref, Google Scholar
• [12] Gamarnik D, Stolyar AL (2012) Multiclass multiserver queueing system in the Halfin–Whitt heavy traffic regime: Asymptotics of the stationary distribution. Queueing Systems 71(1–2):25–51.Crossref, Google Scholar
• [13] Gast N (2015) The power of two choices on graphs: The pair-approximation is accurate. Squillante M (Workshop chair), ed. Proc. Workshop Math. Performance Model. Anal. (Association for Computing Machinery, New York), 69–71.Google Scholar
• [14] Hajek B (1982) Hitting-time and occupation-time bounds implied by drift analysis with applications. Adv. Appl. Probab. 14(3):502–525.Crossref, Google Scholar
• [15] He YT, Down DG (2008) Limited choice and locality considerations for load balancing. Performance Evaluation 65(9):670–687.Crossref, Google Scholar
• [16] Hmedi H, Arapostathis A, Pang G (2019) Uniform stability of a class of large-scale parallel server networks. Working paper, University of Texas at Austin.Google Scholar
• [17] Janson S, Luczak T, Rucinski A (2000) Random Graphs (John Wiley & Sons, Hoboken, NJ).Crossref, Google Scholar
• [18] Kurtz TG (1981) Approximation of Population Processes (SIAM, Philadelphia).Crossref, Google Scholar
• [19] Meyn SP, Tweedie RL (1993) Markov Chains and Stochastic Stability (Springer, London).Crossref, Google Scholar
• [20] Mishra AK, Hellerstein JL, Cirne W, Das CR (2010) Toward characterizing cloud backend workloads: Insights from Google compute clusters. Performance Evaluation Rev. 37(4):34–41.Crossref, Google Scholar
• [21] Mitzenmacher M (1996) The power of two choices in randomized load balancing. Unpublished PhD thesis, University of California, Berkeley.Google Scholar
• [22] Mitzenmacher M (2001) The power of two choices in randomized load balancing. IEEE Trans. Parallel Distributed Systems 12(10):1094–1104.Crossref, Google Scholar
• [23] Mukherjee D, Borst SC, Van Leeuwaarden JSH (2018) Asymptotically optimal load balancing topologies. Chaintreau A, Golubchik L, Zhang Z-L, eds. Proc. ACM Measurement Anal. Comput. Systems (Association for Computing Machinery, New York), 14.Google Scholar
• [24] 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.Link, 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.Crossref, Google Scholar
• [26] Reiss C, Tumanov A, Ganger GR, Katz RH, Kozuch MA (2012) Heterogeneity and dynamicity of clouds at scale: Google trace analysis. Carey M (Program Chairs), Hand S, eds. Proc. Third ACM Sympos. Cloud Comput. (Association for Computing Machinery, New York), 7.Google Scholar
• [27] Roughgarden T, Tardos E (2002) How bad is selfish routing? J. ACM 49(2):236–259.Crossref, Google Scholar
• [28] Stolyar AL (1995) On the stability of multiclass queueing networks: A relaxed sufficient condition via limiting fluid processes. Markov Processes Related Fields 1(4):491–512.Google Scholar
• [29] Stolyar AL (2005) Optimal routing in output-queued flexible server systems. Probab. Engrg. Inform. Sci. 19(2):141–189.Crossref, Google Scholar
• [30] Stolyar AL (2017) Pull-based load distribution among heterogeneous parallel servers: The case of multiple routers. Queueing Systems 85(1):31–65.Crossref, Google Scholar
• [31] Tang D, Subramanian VG (2019) Derandomized load balancing using random walks on expander graphs. Working paper, University of California, Berkeley.Google Scholar
• [32] Tang D, Subramanian VG (2019) Random walk based sampling for load balancing in multi-server systems. Chaintreau A, Golubchik L, Zhang Z-L, eds. Proc. ACM Measurement Anal. Comput. Systems (Association for Computing Machinery, New York), 14.Google Scholar
• [33] Tsitsiklis JN, Xu K (2013) On the power of (even a little) resource pooling. Stochastic Systems 2(1):1–66.Link, Google Scholar
• [34] Tsitsiklis JN, Xu K (2013) Queueing system topologies with limited flexibility. Harchol-Balter M (General Chair), ed. Proc. ACM SIGMETRICS Internat. Conf. Measurement Model. Comput. Systems (Association for Computing Machinery, New York), 167–178.Google Scholar
• [35] Tsitsiklis JN, Xu K (2017) Flexible queueing architectures. Oper. Res. 65(5):1398–1413.Link, Google Scholar
• [36] Turner SR (1998) The effect of increasing routing choice on resource pooling. Probab. Engrg. Inform. Sci. 12(1):109–124.Crossref, Google Scholar
• [37] Van der Boor M, Borst SC, van Leeuwaarden JSH (2017) Load balancing in large-scale systems with multiple dispatchers. Akan OB (General Chairs), Sivakumar RS, eds. Proc. IEEE Conf. Comput. Comm. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 1–9.Google Scholar
• [38] Van der Boor M, Borst SC, Van Leeuwaarden JSH, Mukherjee D (2018) Scalable load balancing in networked systems: Universality properties and stochastic coupling methods. Sirakov B, de Souza PN, Viana M, eds. Proc. Internat. Congress Mathematicians (World Scientific, Singapore), 3893–3923.Google Scholar
• [39] Van der Hofstad R (2017) Random Graphs and Complex Networks, vol. 1 (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [40] Vargaftik S, Keslassy I, Orda A (2020) LSQ: Load balancing in large-scale heterogeneous systems with multiple dispatchers. IEEE/ACM Trans. Networking 28(3):1186–1198.Crossref, Google Scholar
• [41] 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
• [42] Wang W, Maguluri ST, Srikant R, Ying L (2018) Heavy-traffic delay insensitivity in connection-level models of data transfer with proportionally fair bandwidth sharing. ACM SIGMETRICS Performance Evaluation Rev. 45(3):232–245.Crossref, Google Scholar
• [43] Wang W, Maguluri ST, Srikant R, Ying L (2018) Heavy-traffic insensitive bounds for weighted proportionally fair bandwidth sharing policies. Preprint, submitted August 6, https://arxiv.org/abs/1808.02120.Google Scholar
• [44] Wang W, Zhu K, Ying L, Tan J, Zhang L (2016) MapTask scheduling in MapReduce with data locality: Throughput and heavy-traffic optimality. IEEE/ACM Trans. Networking 24(1):190–203.Crossref, Google Scholar
• [45] Weng W, Zhou X, Srikant R (2020) Optimal load balancing with locality constraints. Chaintreau A, Golubchik L, Zhang Z-L, eds. Proc. ACM Measurement Anal. Comput. Systems (Association for Computing Machinery, New York), 45.Google Scholar
• [46] Xie Q, Yekkehkhany A, Lu Y (2016) Scheduling with multi-level data locality: Throughput and heavy-traffic optimality. Song M (General Chair), Westphal C (General Chair), eds. Proc. 35th Annual IEEE Internat. Conf. Comput. Comm. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 1–9.Google Scholar
• [47] Yekkehkhany A, Nagi R (2020) Blind GB-PANDAS: A blind throughput-optimal load balancing algorithm for affinity scheduling. IEEE/ACM Trans. Networking 28(3):1199–1212.Crossref, Google Scholar
• [48] Yekkehkhany A, Hojjati A, Hajiesmaili MH (2018) GB-PANDAS: Throughput and heavy-traffic optimality analysis for affinity scheduling. Performance Evaluation Rev. 45(3):2–14.Crossref, Google Scholar
• [49] Zhou X, Shroff N, Wierman A (2021) Asymptotically optimal load balancing in large-scale heterogeneous systems with multiple dispatchers. Perform. Eval. 145:102146.Crossref, Google Scholar