Power of Random Choices Made Efficient for Fog Computing

In this article, we consider a load balancing protocol based on the power of random choices that is adapted to a fog deploy in which several independent fog nodes equipped with a set of servers or VM are serving the same geographical area. The protocol is based on a simple but effective mechanism based on a threshold
$T$
. When a fog node receives a unit of computation or a job, it immediately executes the job if the number of its occupied servers is lower than
$T$
, otherwise the node executes a randomized algorithm by probing
$F$
other fog nodes in the area, and delegates the execution of the job to the least loaded one, provided the workload is lower than the probing node. Through a mathematical analysis we show that probing just one node (
$F=1$
) when there are less than two free VMs provides the same performance of the well known power-of-two random choices centralized algorithm, but at a much lower delay and control overhead costs. Also, simulations are used to address the node heterogeneity and, with a real testbed, we offer results that prove the effective benefit of the proposed solution in practical applications.