Asymptotically Optimal Load Balancing Topologies
Asymptotically Optimal Load Balancing Topologies
复制标题
渐进最优负载均衡拓扑
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
J. V. Leeuwaarden
中科院分区：
文献类型：
--
作者：
Debankur Mukherjee;S. Borst;J. V. Leeuwaarden
我们考虑了由一些基础图形拓扑与单位均值处理时间相互连接的N服务器的系统。在GN中出现的邻居的数量是在大规模的云网络和数据中心中出现的在这种情况下，服务器是可交换的，均值范围限制，尤其是在任何λ<1中，具有两个或多个任务的服务器的分数在n→∞的极限中消失。 ，含义场技术分解，使分析复杂化，而队列长度的过程往往比集团更糟。 GN等同于在N级或√n规模上的集团上，我们证明，如果GN是eRdöos-s-rényi随机图，则具有平均程度D（n），那么具有很高的可能性如果d（n）→∞和d（n）/√nlog（n））→∞为n→∞，则最佳和√n-最佳状态。与集团相比，将连接数量降低了几乎一个因子n和√n/log（n），只要拓扑是合适的随机性。除此之外，我们确定最小程度为n-o（n）时，我们确定任意图是N-的，即使其最小程度为CN + O ）对于任何0 <c <1/2，都会进行各种情况，以证实渐近结果。
We consider a system of N servers inter-connected by some underlying graph topology GN. Tasks with unit-mean exponential processing times arrive at the various servers as independent Poisson processes of rate λ. Each incoming task is irrevocably assigned to whichever server has the smallest number of tasks among the one where it appears and its neighbors in GN. The above model arises in the context of load balancing in large-scale cloud networks and data centers, and has been extensively investigated in the case GN is a clique. Since the servers are exchangeable in that case, mean-field limits apply, and in particular it has been proved that for any λ < 1, the fraction of servers with two or more tasks vanishes in the limit as N → ∞. For an arbitrary graph GN, mean-field techniques break down, complicating the analysis, and the queue length process tends to be worse than for a clique. Accordingly, a graph GN is said to be N-optimal or √N-optimal when the queue length process on GN is equivalent to that on a clique on an N-scale or √N-scale, respectively. We prove that if GN is an Erdöo s-Rényi random graph with average degree d(N), then with high probability it is N-optimal and √N-optimal if d(N) → ∞ and d(N)/√Nlog(N)) → ∞ as N → ∞, respectively. This demonstrates that optimality can be maintained at N-scale and √N-scale while reducing the number of connections by nearly a factor N and √N/log(N) compared to a clique, provided the topology is suitably random. It is further shown that if GN contains Θ(N) bounded-degree nodes, then it cannot be N-optimal. In addition, we establish that an arbitrary graph GN is N-optimal when its minimum degree is N - o(N), and may not be N-optimal even when its minimum degree is cN + o(N) for any 0 < c < 1/2. Simulation experiments are conducted for various scenarios to corroborate the asymptotic results.