论文标题
与多个调度员的大规模异质系统中的渐近最佳负载平衡
Asymptotically Optimal Load Balancing in Large-scale Heterogeneous Systems with Multiple Dispatchers
论文作者
论文摘要
我们考虑具有多个调度员的大规模异质系统中的负载平衡问题。我们介绍了一个名为“局部估计驱动”（LED）的通用框架。在此框架下，每个调度员都将所有服务器的队列长度的本地（可能过时）估计，并且派遣决定纯粹是基于这些本地估计。本地估计值是通过调度程序和服务器之间的不经常通信进行更新的。我们为LED政策提供了足够的条件，以分别在重型流量中实现吞吐量的最优性和延迟最佳性。这些条件直接暗示着许多以前基于本地记忆的政策的最优性。此外，结果使我们能够为具有多个调度程序的异质系统设计新的延迟最佳政策。最后，LED框架的繁重流量延迟最优性直接解决了如何使用延迟信息设计最佳负载平衡方案的最新开放问题。
We consider the load balancing problem in large-scale heterogeneous systems with multiple dispatchers. We introduce a general framework called Local-Estimation-Driven (LED). Under this framework, each dispatcher keeps local (possibly outdated) estimates of queue lengths for all the servers, and the dispatching decision is made purely based on these local estimates. The local estimates are updated via infrequent communications between dispatchers and servers. We derive sufficient conditions for LED policies to achieve throughput optimality and delay optimality in heavy-traffic, respectively. These conditions directly imply delay optimality for many previous local-memory based policies in heavy traffic. Moreover, the results enable us to design new delay optimal policies for heterogeneous systems with multiple dispatchers. Finally, the heavy-traffic delay optimality of the LED framework directly resolves a recent open problem on how to design optimal load balancing schemes using delayed information.
