Publication: Enhancing the power of two choices load balancing algorithm using round robin policy
Loading...
Identifiers
Publication date
2020-06-22
Defense date
Advisors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
Springer
Impact
Export
Abstract
This paper proposes a new version of the power of two choices, SQ(d), load balancing algorithm. This new algorithm improves the performance of the classical model based on the power of two choices randomized load balancing. This model considers jobs that arrive at a dispatcher as a Poisson stream of rate lambdan,lambda<1, at a set of n servers. Using the power of two choices, the dispatcher chooses some d constant for each job independently and uniformly from the n servers in a random way and sends the job to the server with the fewest number of jobs. This algorithm offers an advantage over the load balancing based on shortest queue discipline, because it provides good performance and reduces the overhead in the servers and the communication network. In this paper, we propose a new version, shortest queue of d with randomization and round robin policies, SQ-RR(d). This new algorithm combines randomization techniques and static local balancing based on a round-robin policy. In this new version, the dispatcher chooses the d servers as follows: one is selected using a round-robin policy, and the d−1 servers are chosen independently and uniformly from the n servers in a random way. Then, the dispatcher sends the job to the server with the fewest number of jobs. We demonstrate with a theoretical approximation of this approach that this new version improves the performance obtained with the classical solution in all situations, including systems at 99% capacity. Furthermore, we provide simulations that demonstrate the theoretical approximation developed.
Description
Keywords
the power of two choices, load balancing, distributed systems
Bibliographic citation
Garcia-Carballeira, F., Calderon, A. & Carretero, J. Enhancing the power of two choices load balancing algorithm using round robin policy. Cluster Comput 24, 611–624 (2021). https://doi.org/10.1007/s10586-020-03139-6