论文标题
使用稀疏通信的负载平衡
Load Balancing Using Sparse Communication
论文作者
论文摘要
跨平行服务器的负载平衡是服务系统中出现的一系列拥塞控制问题。有效的负载平衡器在很大程度上依赖于准确的实时拥塞信息来做出路由决策。但是，获取此类信息可以施加大量的沟通开销，尤其是在现代数据中心中发现的苛刻应用中。 我们引入了一个框架，用于通信感知负载平衡并设计新的负载平衡算法，即使在具有稀疏通信模式的情况下，它们的表现也出色。我们方法的核心是状态近似，其中负载平衡器首先通过通信协议估算服务器均表示。随后，它利用负载平衡算法中的这些近似状态来确定路由决策。 我们证明，通过使用新颖的通信协议，可以在稀疏通信的情况下实现准确的队列长度近似：对于x的最大近似误差，通信频率仅需要是o（1/x^2）。我们通过扩散分析进一步表明，恒定的最大近似误差足以实现渐近最佳性能。综上所述，这些结果表明，通过很少的沟通，高性能的负载平衡是可能的。通过模拟，我们观察到拟议的设计与最先进的负载平衡算法的性能相匹配，同时将通信速率大幅降低了90％。
Load balancing across parallel servers is an important class of congestion control problems that arises in service systems. An effective load balancer relies heavily on accurate, real-time congestion information to make routing decisions. However, obtaining such information can impose significant communication overheads, especially in demanding applications like those found in modern data centers. We introduce a framework for communication-aware load balancing and design new load balancing algorithms that perform exceptionally well even in scenarios with sparse communication patterns. Central to our approach is state approximation, where the load balancer first estimates server states through a communication protocol. Subsequently, it utilizes these approximate states within a load balancing algorithm to determine routing decisions. We demonstrate that by using a novel communication protocol, one can achieve accurate queue length approximation with sparse communication: for a maximal approximation error of x, the communication frequency only needs to be O(1/x^2). We further show, via a diffusion analysis, that a constant maximal approximation error is sufficient for achieving asymptotically optimal performance. Taken together, these results therefore demonstrate that highly performant load balancing is possible with very little communication. Through simulations, we observe that the proposed designs match or surpass the performance of state-of-the-art load balancing algorithms while drastically reducing communication rates by up to 90%.
