A lower bound on the queueing delay in resource constrained load balancing. (English) Zbl 1457.60138

Gamarnik, David; Tsitsiklis, John N.; Zubeldia, Martin

Ann. Appl. Probab. 30, No. 2, 870-901 (2020).

Summary: We consider the following distributed service model: jobs with unit mean, general distribution, and independent processing times arrive as a renewal process of rate \(\lambda n\), with \(0<\lambda <1\), and are immediately dispatched to one of several queues associated with \(n\) identical servers with unit processing rate. We assume that the dispatching decisions are made by a central dispatcher endowed with a finite memory, and with the ability to exchange messages with the servers.
We study the fundamental resource requirements (memory bits and message exchange rate), in order to drive the expected queueing delay in steady-state of a typical job to zero, as \(n\) increases. We develop a novel approach to show that, within a certain broad class of “symmetric” policies, every dispatching policy with a message rate of the order of \(n\), and with a memory of the order of \(\log n\) bits, results in an expected queueing delay which is bounded away from zero, uniformly as \(n \to \infty\). This complements existing results which show that, in the absence of such limitations on the memory or the message rate, there exist policies with vanishing queueing delay (at least with Poisson arrivals and exponential service times).

MSC:

60K25	Queueing theory (aspects of probability theory)
68M20	Performance evaluation, queueing, and scheduling in the context of computer systems

Keywords:

load balancing; queueing delay; resource constraints

References:

[1]	Alon, N., Lubetzky, E. and Gurel-Gurevich, O. (2009). Choice-memory tradeoff in allocations. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2009 230-238. IEEE Computer Soc., Los Alamitos, CA. · Zbl 1292.60010
[2]	Azar, Y., Broder, A. Z., Karlin, A. R. and Upfal, E. (1999). Balanced allocations. SIAM J. Comput. 29 180-200. · Zbl 0937.68053
[3]	Baccelli, F. and Brémaud, P. (2003). Elements of Queueing Theory: Palm Martingale Calculus and Stochastic Recurrences, 2nd ed. Applications of Mathematics (New York) 26. Springer, Berlin. · Zbl 1021.60001
[4]	Badonnel, R. and Burgess, M. (2008). Dynamic pull-based load balancing for autonomic servers. In Network Operations and Management Symposium (NOMS).
[5]	Bramson, M., Lu, Y. and Prabhakar, B. (2013). Decay of tails at equilibrium for FIFO join the shortest queue networks. Ann. Appl. Probab. 23 1841-1878. · Zbl 1287.60110
[6]	Feitelson, D. and Jette, M. A. (1997). Improved utilization and responsiveness with gang scheduling. In IPPS ’97 Proceedings of the Job Scheduling Strategies for Parallel Processing 238-261.
[7]	Gamarnik, D., Tsitsiklis, J. N. and Zubeldia, M. (2018). Delay, memory, and messaging tradeoffs in distributed service systems. Stoch. Syst. 8 45-74. · Zbl 1446.60066
[8]	Harchol-Balter, M., Crovella, M. E. and Murta, C. D. (1999). On choosing a task assignment policy for a distributed server system. J. Parallel Distrib. Comput. 59 204-228.
[9]	Hellemans, T. and Van Houdt, B. (2018). On the power-of-d-choices with least loaded server selection. Proc. ACM Meas. Anal. Comput. Syst. 2 Article No. 27.
[10]	Lenzen, C. and Wattenhofer, R. (2016). Tight bounds for parallel randomized load balancing. Distrib. Comput. 29 127-142. · Zbl 1356.68018
[11]	Lu, Y., Xie, Q., Kliot, G., Geller, A., Larus, J. R. and Greenberg, A. (2011). Join-idle-queue: A novel load balancing algorithm for dynamically scalable web services. Perform. Eval. 68 1056-1071.
[12]	Mitzenmacher, M. D. (1996). The Power of Two Choices in Randomized Load Balancing. ProQuest LLC, Ann Arbor, MI. Thesis (Ph.D.)—Univ. California, Berkeley.
[13]	Mitzenmacher, M., Prabhakar, B. and Shah, D. (2002). Load balancing with memory. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science.
[14]	Mukherjee, D., Borst, S., van Leeuwaarden, J. and Whiting, P. (2016). Universality of power-of-d load balancing schemes. In Workshop on Mathematical Performance Modeling and Analysis (MAMA). · Zbl 1356.60149
[15]	Stamoulis, G. D. and Tsitsiklis, J. N. (1991). Optimal distributed policies for choosing among multiple servers. In Proceedings of the 30th Conference on Decision and Control 815-820.
[16]	Stolyar, A. L. (2015). Pull-based load distribution in large-scale heterogeneous service systems. Queueing Syst. 80 341-361. · Zbl 1317.90073
[17]	Vvedenskaya, N. D., Dobrushin, R. L. and Karpelevich, F. I. (1996). Queueing system with selection of the shortest of two queues: An asymptotic approach. Probl. Inf. Transm. 32 15-27. · Zbl 0898.60095
[18]	Winston, W. (1977). Optimality of the shortest line discipline. J. Appl. Probab. 14 181-189. · Zbl 0357.60023
[19]	Ying, L. · Zbl 1420.68028