  Distributed load balancing is the act of allocating jobs among a set of
servers as evenly as possible. There are mainly two versions of the load
balancing problem that have been studied in the literature: static and dynamic.
The static interpretation leads to formulating the load balancing problem as a
case with jobs (balls) never leaving the system and accumulating at the servers
(bins) whereas the dynamic setting deals with the case when jobs arrive and
leave the system after service completion. This paper designs and evaluates
server proximity aware job allocation policies for treating load balancing
problems with a goal to reduce the communication cost associated with the jobs.
We consider a class of proximity aware Power of Two (POT) choice based
assignment policies for allocating jobs to servers, where servers are
interconnected as an n-vertex graph G(V, E). For the static version, we assume
each job arrives at one of the servers, u. For the dynamic setting, we assume G
to be a circular graph and job arrival process at each server is described by a
Poisson point process with the job service time exponentially distributed. For
both settings, we then assign each job to the server with minimum load among
servers u and v where v is chosen according to one of the following two
policies: (i) Unif-POT(k): Sample a server v uniformly at random from k-hop
neighborhood of u (ii) InvSq-POT(k): Sample a server v from k-hop neighborhood
of u with probability proportional to the inverse square of the distance
between u and v. Our simulation results show that both the policies
consistently produce a load distribution which is much similar to that of a
classical proximity oblivious POT policy.
