Degree of Queue Imbalance: Overcoming the Limitation of Heavy-traffic Delay Optimality in Load Balancing Systems
Degree of Queue Imbalance: Overcoming the Limitation of Heavy-traffic Delay Optimality in Load Balancing Systems
复制标题
队列不平衡程度：克服负载均衡系统中大流量时延最优性的限制
DOI：
10.1145/3179424
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Shroff, Ness
中科院分区：
文献类型：
--
作者：
Zhou, Xingyu;Wu, Fei;Tan, Jian;Srinivasan, Kannan;Shroff, Ness
重流量延迟最优性被认为是衡量负载均衡方案延迟性能的一个重要指标。在本文中，我们认为，繁忙的交通延迟最优性是一个粗略的度量，并不一定意味着良好的延迟性能。具体来说，我们表明，任何负载平衡方案是重流量延迟最优的，只要它满足一个相当弱的条件。这个条件只要求调度程序在长期内倾向于使用较短的队列，即使是稍微倾向于使用较长的队列。因此，虽然负载均衡方案可以是重流量延迟最优的，但重流量延迟最优方案的经验延迟性能可以从非常好（加入最短队列的延迟性能）到非常差（任意接近随机路由的延迟性能）。为了克服这一局限性，我们引入了一个新的度量称为队列不平衡度，它衡量的队列长度之间的差异，在稳定状态的所有服务器。给定一个大流量延迟的最优负载均衡方案，我们可以描述队列不平衡的结果程度，这反过来又允许我们明确区分好的和差的负载均衡方案。因此，本文建议，在设计良好的负载平衡方案时，它们不仅应该是重流量延迟最优的，而且还应该具有较低的队列不平衡程度。
Heavy-traffic delay optimality is considered to be an important metric in evaluating the delay performance of load balancing schemes. In this paper, we argue that heavy-traffic delay optimality is a coarse metric that does not necessarily imply good delay performance. Specifically, we show that any load balancing scheme is heavy-traffic delay optimal as long as it satisfies a fairly weak condition. This condition only requires that in the long-term the dispatcher favors, even slightly, shorter queues over longer queues. Hence, although a load balancing scheme could be heavy-traffic delay optimal, the empirical delay performance of heavy-traffic delay optimal schemes can range from very good (that of join-shortest-queue) to very bad (arbitrarily close to the performance of random routing). To overcome this limitation, we introduce a new metric calleddegree of queue imbalance,which measures the queue length difference between all the servers in steady-state. Given a heavy-traffic delay optimal load balancing scheme, we can characterize the resultantdegree of queue imbalance.This, in turn, allows us to explicitly differentiate between good and poor load balancing schemes. Thus, this paper suggests that when designing good load balancing schemes, they should not only be heavy-traffic delay optimal, but also have a low degree of queue imbalance.