Enhancing the power of two choices load balancing algorithm using round robin policy

摘要

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.