Universality of Power-of-d Load Balancing in Many-Server Systems
Universality of Power-of-d Load Balancing in Many-Server Systems
复制标题
多服务器系统中 Power-of-d 负载平衡的普遍性
DOI：
10.1287/stsy.2018.0016
复制
发表时间：
2016
影响因子：
--
通讯作者：
P. Whiting
中科院分区：
文献类型：
--
作者：
Debankur Mukherjee;S. Borst;J. V. van Leeuwaarden;P. Whiting
我们考虑一个系统的$N$并行单服务器队列与单位指数服务率和一个单一的调度器的任务到达率$\lambda（N）$的泊松过程。当一个任务到达时，调度器将它分配给$d（N）$随机选择的服务器（$1 \leq d（N）\leq N$）中队列最短的服务器。这种负载平衡策略被称为JSQ（$d（N）$）方案，标志着它将著名的加入最短队列（JSQ）策略作为$d（N）= N$的关键特殊情况。
我们构造了一个随机耦合来限制JSQ策略和一个任意值d（N）的方案之间的队长过程的差异。我们使用耦合来推导出其中$\lambda（N）/ N \to \lambda 0$ as $N \to \infty$ with $d（N）/（\sqrt{N} \log（N））\to\infty$对应于JSQ策略的状态中的流体限制。这些结果表明，JSQ策略的最优性可以保持在流体级和扩散级，同时分别将开销减少近一个因子O（$N$）和O（$\sqrt{N}/\log（N）$）。
We consider a system of $N$ parallel single-server queues with unit exponential service rates and a single dispatcher where tasks arrive as a Poisson process of rate $\lambda(N)$. When a task arrives, the dispatcher assigns it to a server with the shortest queue among $d(N)$ randomly selected servers ($1 \leq d(N) \leq N$). This load balancing strategy is referred to as a JSQ($d(N)$) scheme, marking that it subsumes the celebrated Join-the-Shortest Queue (JSQ) policy as a crucial special case for $d(N) = N$.
We construct a stochastic coupling to bound the difference in the queue length processes between the JSQ policy and a scheme with an arbitrary value of $d(N)$. We use the coupling to derive the fluid limit in the regime where $\lambda(N) / N \to \lambda 0$ as $N \to \infty$ with $d(N)/(\sqrt{N} \log (N))\to\infty$ corresponds to that for the JSQ policy. These results indicate that the optimality of the JSQ policy can be preserved at the fluid-level and diffusion-level while reducing the overhead by nearly a factor O($N$) and O($\sqrt{N}/\log(N)$), respectively.
影响因子：
1.6
作者：
Brightwell G
通讯作者：
Brightwell G