Universality of Power-of-d Load Balancing Schemes
Universality of Power-of-d Load Balancing Schemes
复制标题
d 幂负载均衡方案的普遍性
DOI：
10.1145/3003977.3003990
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
P. Whiting
中科院分区：
文献类型：
--
作者：
Debankur Mukherjee;S. Borst;J. V. Leeuwaarden;P. Whiting
我们考虑了一个具有单位指数服务率的N个并行排队系统和一个调度器，其中任务的到达是一个速率为λ的泊松过程。当任务到达时，调度程序将其分配给≤随机选择的服务器中队列最短的服务器。该负载平衡策略被称为d的幂(N)或JSQ(JSQ)方案，并且将加入最短队列(JSQ)策略归类为d(N)=N的关键特例。
我们构造了一个耦合来限制JSQ策略和任意值<i>d</i>(<i>N</i>)之间的队列长度进程的差异。我们利用耦合得到了λ(N<sup>N</sup>)/N<sup>→λ</sup>1和<sup>d</sup>(N<sup>n</sup>)→∞作为<N</sup>N</sup>→∞的区域内的流体极限，以及相应的不动点。事实证明，流动性限制并不取决于(N)的确切增长率，特别是与JSQ政策的增长率一致。我们进一步利用耦合来确定在(N<sup>N</sup>--λ<sup>N</sup>)/√<sup>N</sup>→β&>0和<sup>d</sup>(N<sup>n</sup>)/√<sup>N</sup>N<sup>i>→∞</sup><sup>I</sup></sup><sup>√</sup><sup>→∞</sup><sup>Log</sup>N</sup><sup>→∞</sup>)中的扩散限制对应于jsq策略。这些结果表明，JSQ策略在流体层和扩散层都能保持随机最优性，而开销分别降低了O(N<sup>I</sup>)和O(√<i>N</i>)。
We consider a system of <i>N</i> parallel queues with unit exponential service rates and a single dispatcher where tasks arrive as a Poisson process of rate λ(<i>N</i>). When a task arrives, the dispatcher assigns it to a server with the shortest queue among <i>d</i>(<i>N</i>) ≤ <i>N</i> randomly selected servers. This load balancing policy is referred to as a power-of-<i>d</i>(<i>N</i>) or JSQ(<i>d</i>(<i>N</i>)) scheme, and subsumes the Join-the-Shortest Queue (JSQ) policy as a crucial special case for <i>d</i>(<i>N</i>) = <i>N</i>.
We construct a coupling to bound the difference in the queue length processes between the JSQ policy and an arbitrary value of <i>d</i>(<i>N</i>). We use the coupling to derive the fluid limit in the regime where λ(<i>N</i>)/<i>N</i> → λ < 1 and <i>d</i>(<i>N</i>)→ ∞ as <i>N</i> → ∞, along with the corresponding fixed point. The fluid limit turns out not to depend on the exact growth rate of <i>d</i>(<i>N</i>), and in particular coincides with that for the JSQ policy. We further leverage the coupling to establish that the diffusion limit in the regime where (<i>N</i>--λ(<i>N</i>))/ √<i>N</i> → β > 0 and <i>d</i>(<i>N</i>)/ √ <i>N</i> log<i>N</i> → ∞ as <i>N</i> → ∞ corresponds to that for the JSQ policy. These results indicate that the stochastic optimality of the JSQ policy can be preserved at the fluid-level and diffusion-level while reducing the overhead by nearly a factor O(<i>N</i>) and O(√ <i>N</i>), respectively.