Designing Low-Complexity Heavy-Traffic Delay-Optimal Load Balancing Schemes: Theory to Algorithms

Abstract

In this paper, we establish a unified analytical framework for designing load balancing algorithms that can simultaneously achieve low latency, low complexity, and low communication overhead. We first propose a general class \Pi of load balancing policies and prove that they are throughput optimal and heavy-traffic delay optimal. This class \Pi includes popular policies such as join-shortest-queue (JSQ) and power-of-d as special cases, but not the recently proposed join-idle-queue (JIQ) policy. In fact, we show that JIQ is not heavy-traffic delay optimal even for homogeneous servers. By exploiting the flexibility offered by the class \Pi, we design a new load balancing policy called join-below-threshold (JBT-d), in which the arrival jobs are preferably assigned to queues that are no greater than a threshold, and the threshold is updated infrequently. JBT-d has several benefits: (i) JBT-d belongs to the class \Pi and hence is throughput optimal and heavy-traffic delay optimal. (ii) JBT-d has zero dispatching delay, like JIQ and other pull-based policies, and low message overhead due to infrequent threshold update. (iii) Extensive simulations show that JBT-d has excellent delay performance, comparable to the JSQ policy in various system settings.

References

1. Jeffrey Dean and Sanjay Ghemawat. 2008. MapReduce: simplified data processing on large clusters. Commun. ACM 51, 1 (2008), 107--113.
2. Atilla Eryilmaz and R Srikant. 2012. Asymptotically tight steady-state queue length bounds implied by drift conditions. Queueing Systems 72, 3--4 (2012), 311--359.
3. G Foschini and JACK Salz. 1978. A basic dynamic routing problem and diffusion. IEEE Transactions on Communications 26, 3 (1978), 320--327.
4. Ian Foster, Yong Zhao, Ioan Raicu, and Shiyong Lu. 2008. Cloud computing and grid computing 360-degree compared. In 2008 Grid Computing Environments Workshop. Ieee, 1--10.
5. Lars George. 2011. HBase: the definitive guide. " O'Reilly Media, Inc.".
6. Varun Gupta, Mor Harchol Balter, Karl Sigman, and Ward Whitt. 2007. Analysis of join-the-shortest-queue routing for web server farms. Performance Evaluation 64, 9 (2007), 1062--1081.
7. Bruce Hajek. 1982. Hitting-time and occupation-time bounds implied by drift analysis with applications. Advances in Applied probability (1982), 502--525.
8. Yi Lu, Qiaomin Xie, Gabriel Kliot, Alan Geller, James R Larus, and Albert Greenberg. 2011. Join-Idle-Queue: A novel load balancing algorithm for dynamically scalable web services. Performance Evaluation 68, 11 (2011), 1056--1071.
9. Siva Theja Maguluri, R Srikant, and Lei Ying. 2014. Heavy traffic optimal resource allocation algorithms for cloud computing clusters. Performance Evaluation 81 (2014), 20--39.
10. Michael Mitzenmacher. 2001. The power of two choices in randomized load balancing. IEEE Transactions on Parallel and Distributed Systems 12, 10 (2001), 1094--1104.
11. Michael Mitzenmacher, Balaji Prabhakar, and Devavrat Shah. 2002. Load balancing with memory. In Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on. IEEE, 799--808.
12. Debankur Mukherjee, Sem C Borst, Johan SH Van Leeuwaarden, Philip A Whiting, et al. 2016. Universality of load balancing schemes on the diffusion scale. Journal of Applied Probability 53, 4 (2016), 1111--1124.
13. Rajesh Nishtala, Hans Fugal, Steven Grimm, Marc Kwiatkowski, Herman Lee, Harry C Li, Ryan McElroy, Mike Paleczny, Daniel Peek, Paul Saab, et al. 2013. Scaling memcache at facebook. In Presented as part of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13). 385--398.
14. Devavrat Shah and Balaji Prabhakar. 2002. The use of memory in randomized load balancing. In Information Theory, 2002. Proceedings. 2002 IEEE International Symposium on. IEEE, 125.
15. Alexander L Stolyar. 2015. Pull-based load distribution in large-scale heterogeneous service systems. Queueing Systems 80, 4 (2015), 341--361.
16. John N Tsitsiklis and Kuang Xu. 2013. Queueing system topologies with limited flexibility. In ACM SIGMETRICS Performance Evaluation Review, Vol. 41. ACM, 167--178.
17. Nikita Dmitrievna Vvedenskaya, Roland L'vovich Dobrushin, and Fridrikh Izrailevich Karpelevich. 1996. Queueing system with selection of the shortest of two queues: An asymptotic approach. Problemy Peredachi Informatsii 32, 1 (1996), 20--34.
18. Weina Wang, Kai Zhu, Lei Ying, Jian Tan, and Li Zhang. 2016. MapTask scheduling in MapReduce with data locality: Throughput and heavy-traffic optimality. IEEE/ACM Transactions on Networking 24, 1 (2016), 190--203.
19. Richard R Weber. 1978. On the optimal assignment of customers to parallel servers. Journal of Applied Probability (1978), 406--413.
20. Lei Ying, R Srikant, and Xiaohan Kang. 2015. The power of slightly more than one sample in randomized load balancing. In 2015 IEEE Conference on Computer Communications (INFOCOM). IEEE, 1131--1139.
21. Xingyu Zhou, Fei Wu, Jian Tan, Yin Sun, and Ness Shroff. 2017. Designing Low-Complexity Heavy-Traffic Delay- Optimal Load Balancing Schemes: Theory to Algorithms. http://arxiv.org/abs/1710.04357. (Oct. 2017).

Index Terms

• Mathematics of computing

  • Probability and statistics

    • Statistical paradigms

      • Queueing theory

• Networks

  • Network performance evaluation

    • Network performance analysis

    • Network performance modeling