Heavy-traffic Delay Optimality in Pull-based Load Balancing Systems
Heavy-traffic Delay Optimality in Pull-based Load Balancing Systems
复制标题
基于拉动的负载平衡系统中的大流量延迟最优性
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
N. Shroff
中科院分区：
文献类型：
--
作者：
Xingyu Zhou;Jian Tan;N. Shroff
在本文中，我们考虑一个负载平衡系统下的一般拉式的政策。特别地，每个到达被随机分派到队列长度低于阈值的服务器之一;如果不存在，则该到达被随机分派到整个服务器集合中的一个。我们感兴趣的是在繁忙的交通系统的阈值和延迟性能之间的基本关系。为此，我们首先建立以下必要条件来保证重交通延迟最优：当外源到达率接近容量区域的边界时，阈值将增长到无穷大（即，负载强度接近1），但是增长率应当慢于系统中任务的平均数量的多项式函数。作为这一结果的一个特殊情况下，我们直接表明，流行的拉为基础的政策加入空闲队列（JIQ）的延迟性能严格之间的任何重交通延迟的最优策略和随机路由。我们进一步表明，繁忙的交通延迟最优的一个充分条件是，阈值的增长与系统中的任务的平均数。这个结果直接解决了Kelly和Laws猜想的一个推广版本。
In this paper, we consider a load balancing system under a general pull-based policy. In particular, each arrival is randomly dispatched to one of the servers with queue length below a threshold; if none exists, this arrival is randomly dispatched to one of the entire set of servers. We are interested in the fundamental relationship between the threshold and the delay performance of the system in heavy traffic. To this end, we first establish the following necessary condition to guarantee heavy-traffic delay optimality: the threshold will grow to infinity as the exogenous arrival rate approaches the boundary of the capacity region (i.e., the load intensity approaches one) but the growth rate should be slower than a polynomial function of the mean number of tasks in the system. As a special case of this result, we directly show that the delay performance of the popular pull-based policy Join-Idle-Queue (JIQ) lies strictly between that of any heavy-traffic delay optimal policy and that of random routing. We further show that a sufficient condition for heavy-traffic delay optimality is that the threshold grows logarithmically with the mean number of tasks in the system. This result directly resolves a generalized version of the conjecture by Kelly and Laws.
具有按比例公平带宽共享的连接级数据传输模型中的大流量延迟不敏感
DOI：
10.1145/3199524.3199565
发表时间：
2018
期刊：
ACM SIGMETRICS Performance Evaluation Review
影响因子：
--
作者：
Wang, Weina;Maguluri, Siva Theja;Srikant, R.;Ying, Lei
通讯作者：
Ying, Lei