On the Analysis and Evaluation of Proximity-based Load-balancing Policies
On the Analysis and Evaluation of Proximity-based Load-balancing Policies
复制标题
基于邻近负载均衡策略的分析与评估
DOI：
--
复制
发表时间：
2022
影响因子：
0.6
通讯作者：
K. Leung
中科院分区：
文献类型：
--
作者：
Nitish K. Panigrahy;Thirupathaiah Vasantam;P. Basu;D. Towsley;A. Swami;K. Leung
分布式负载平衡是在一组服务器之间尽可能均匀地分配作业的行为。分布式负载平衡的静态解释导致将负载平衡问题制定为经典的球和箱问题，其中作业（球）永远不会离开系统并在服务器（箱）处积累。虽然大多数以前的工作在静态设置集中在研究分配给服务器或最大负载的作业的最大数量，很少的重要性已被赋予的实施成本，或移动作业/数据到/从其分配的服务器的成本，这样的政策。本文设计和评估服务器邻近感知静态负载平衡策略，目标是降低实现成本。我们考虑一类接近意识的权力的两个（POT）的选择为基础的分配政策，工作分配到服务器，工作和服务器都位于一个二维的欧几里得平面。在这个框架中，我们研究了不同的分配策略的实现成本和负载平衡性能之间的权衡。为此，我们首先设计和评估的空间电源的两个（sPOT）的政策，其中每个作业被分配到负载最少的服务器之间的两个地理上最近的服务器。我们提供的表达式上的服务器上的渐近预期的最大负载的下限，并证明sPOT不实现经典的POT负载平衡的好处。然而，实验结果表明，sPOT的预期实施成本方面的功效。我们还提出了两个非统一的服务器采样为基础的POT政策，实现最好的实现成本和负载均衡性能。然后，我们扩展我们的分析的情况下，服务器互连的n-顶点图G（S，E）。我们假设每个作业都到达一个服务器u，该服务器u是从顶点集S中随机均匀选择的。然后，我们将每个作业分配给服务器u和v中负载最小的服务器，其中v是根据以下两个策略之一选择的：（i）Unif-POT（k）：从u的k跳邻域中随机均匀采样服务器v;（ii）InvSq-POT（k）：从k中采样服务器v-跳跃邻域的概率与u和v之间的距离的平方反比成比例。在广泛的拓扑结构上进行的广泛模拟验证了有效性这两种政策。我们的模拟结果表明，这两种政策始终产生的负载分布，是非常相似的一个经典的POT。根据拓扑结构，我们观察到的总变化距离的顺序为0.002-0.08的政策，同时实现了8%-99%的实现成本降低相比，经典的POT。
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 or maximum load, little importance has been given to the implementation cost, or the cost of moving a job/data to/from its allocated server, for such policies. This article 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 validates the efficacy of both the policies. Our simulation results show that both policies consistently produce a load distribution that 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.
严格兼容性约束下的负载均衡
影响因子：
1.7
作者：
Rutten, Daan;Mukherjee, Debankur
通讯作者：
Mukherjee, Debankur