Paper Info
Title
Enhancing The Power Of Two Choices Load Balancing Algorithm Using Round Robin Policy
Abstract
This paper proposes a new version of thepower 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 lambda n, lambda < 1, at a set of n servers. Using the power of two choices, the dispatcher chooses somedconstant for each job independently and uniformly from thenservers 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 thedservers as follows: one is selected using a round-robin policy, and the d - 1 servers are chosen independently and uniformly from thenservers 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.
Year
DOI
Venue
2021
10.1007/s10586-020-03139-6
CLUSTER COMPUTING-THE JOURNAL OF NETWORKS SOFTWARE TOOLS AND APPLICATIONS
Keywords
DocType
Volume
The power of two choices, Load balancing, Distributed systems
Journal
24
Issue
ISSN
Citations 
2
1386-7857
2
PageRank 
References 
Authors
0.38
0
3
Name
Order
Citations
PageRank
Felix Garcia-Carballeira111211.32
Alejandro Calderón217617.28
Jesús Carretero355269.87