首页    期刊浏览 2024年11月06日 星期三
登录注册

文章基本信息

  • 标题:Universality of Power-of-d Load Balancing in Many-Server Systems
  • 本地全文:下载
  • 作者:Debankur Mukherjee ; Sem C. Borst ; Johan S. H. van Leeuwaarden
  • 期刊名称:Stochastic Systems
  • 印刷版ISSN:1946-5238
  • 出版年度:2018
  • 卷号:8
  • 期号:4
  • 页码:265-292
  • DOI:10.1287/stsy.2018.0016
  • 语种:English
  • 出版社:Institute for Operations Research and the Management Sciences (INFORMS), Applied Probability Society
  • 摘要: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 λ(N). When a task arrives, the dispatcher assigns it to a server with the shortest queue among d(N) randomly selected servers (1≤d(N)≤N). This load balancing strategy is referred to as a JSQ(d(N)) scheme, noting 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 JSQ(d(N)) scheme with an arbitrary value of d(N). We use the coupling to derive the fluid limit in the regime where λ(N)/N→λ<1 as N→∞ with d(N)→∞, along with the associated fixed point. The fluid limit turns out not to depend on the exact growth rate of d(N) and in particular coincides with that for the JSQ policy. We further leverage the coupling to establish that the diffusion limit in the critical regime where (N-λ(N))/N→β>0 as N→∞ with d(N)/(Nlog(N))→∞ 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(N/log(N)), respectively.
  • 关键词:load balancing; power-of-d scheme; join the shortest queue; stochastic coupling; functional limit theorems; fluid limit; diffusion limit; many-server asymptotics
国家哲学社会科学文献中心版权所有