Skip to main content

Research Repository

Advanced Search

On the Analysis and Evaluation of Proximity Based Load Balancing Policies

Panigrahy, Nitish K.; Vasantam, Thirupathaiah; Basu, Prithwish; Towsley, Don; Swami, Ananthram; Leung, Kin K.

On the Analysis and Evaluation of Proximity Based Load Balancing Policies Thumbnail


Authors

Nitish K. Panigrahy

Prithwish Basu

Don Towsley

Ananthram Swami

Kin K. Leung



Abstract

Distributed load balancing is the act of allocating jobs among a set of servers as evenly as possible. The static interpretation of distributed load balancing leads to formulating the load balancing problem as a classical balls and bins problem with jobs (balls) never leaving the system and accumulating at the servers (bins). While most of the previous work in the static setting focus on studying the maximum number of jobs allocated to a server ormaximum load, little importance has been given to theimplementation cost, or the cost of moving a job/data to/from its allocated server, for such policies. This paper designs and evaluates server proximity aware static load balancing policies with a goal to reduce the implementation cost. We consider a class of proximity aware Power of Two (POT) choice based assignment policies for allocating jobs to servers, where both jobs and servers are located on a two-dimensional Euclidean plane. In this framework, we investigate the tradeoff between the implementation cost, and load balancing performance of different allocation policies. To this end, we first design and evaluate a Spatial Power of two (sPOT) policy in which each job is allocated to the least loaded server among its two geographically nearest servers. We provide expressions for the lower bound on the asymptotic expected maximum load on the servers and prove that sPOT does not achieve classical POT load balancing benefits. However, experimental results suggest the efficacy of sPOT with respect to expected implementation cost. We also propose two non-uniform server sampling based POT policies that achieve the best of both implementation cost and load balancing performance. We then extend our analysis to the case where servers are interconnected as an n-vertex graph G(S, E). We assume each job arrives at one of the servers, u, chosen uniformly at random from the vertex set S. 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. An extensive simulation over a wide range of topologies validate the efficacy of both the policies. Our simulation results show that both policies consistently produce a load distribution which is much similar to that of a classical POT. Depending on topology, we observe the total variation distance to be of the order of 0.002 − 0.08 for both the policies while achieving a 8%−99% decrease in implementation cost as compared to the classical POT.

Citation

Panigrahy, N. K., Vasantam, T., Basu, P., Towsley, D., Swami, A., & Leung, K. K. (2022). On the Analysis and Evaluation of Proximity Based Load Balancing Policies. ACM Transactions on Modeling and Performance Evaluation of Computing Systems, 7(2-4), Article 6. https://doi.org/10.1145/3549933

Journal Article Type Article
Online Publication Date Jul 21, 2022
Publication Date 2022-12
Deposit Date Sep 16, 2022
Publicly Available Date Sep 16, 2022
Journal ACM Transactions on Modeling and Performance Evaluation of Computing Systems
Print ISSN 2376-3639
Electronic ISSN 2376-3647
Publisher Association for Computing Machinery (ACM)
Peer Reviewed Peer Reviewed
Volume 7
Issue 2-4
Article Number 6
DOI https://doi.org/10.1145/3549933

Files

Accepted Journal Article (2.3 Mb)
PDF

Copyright Statement
© 2022 Association for Computing Machinery This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in ACM Transactions on Modeling and Performance Evaluation of Computing Systems, https://doi.org/10.1145/3549933







You might also like



Downloadable Citations