Asymptotically optimal load balancing in large-scale heterogeneous systems with multiple dispatchers
Asymptotically optimal load balancing in large-scale heterogeneous systems with multiple dispatchers
复制标题
具有多个调度器的大规模异构系统中的渐近最优负载均衡
DOI：
10.1016/j.peva.2020.102146
复制
发表时间：
2021
影响因子：
2.2
通讯作者：
Wierman, Adam
中科院分区：
文献类型：
--
作者：
Zhou, Xingyu;Shroff, Ness;Wierman, Adam
本文研究了具有多个调度器的大规模异构系统的负载平衡问题。我们介绍了一个通用的框架，称为本地估计驱动（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 the 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 also sheds light on a recent open question on how to design optimal load balancing schemes using delayed information.