Universality of power-of-d load balancing schemes

Debankur Mukherjee, Sem Borst, Johan Van Leeuwaarden, Phil Whiting

Research output: Contribution to journalConference articlepeer-review

40 Citations (Scopus)
2 Downloads (Pure)

Abstract

We consider a system of N parallel 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) ≤ N randomly selected servers. This load balancing policy is referred to as a power-of-d(N) or JSQ(d(N)) scheme, and subsumes the Join-the-Shortest Queue (JSQ) policy as a crucial special case for d(N) = N. We construct a coupling to bound the difference in the queue length processes between the JSQ policy and an arbitrary value of d(N). We use the coupling to derive the fluid limit in the regime where Λ(N)/N → Λ < 1 and d(N) Λ ∞ as N → ∞, along with the corresponding 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 regime where (N-Λ(N))/√N → β > 0 and d(N)/√N log N → ∞ as N → ∞ 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(N) and O(√N), respectively.

Original languageEnglish
Pages (from-to)36-38
Number of pages3
JournalPerformance Evaluation Review
Volume44
Issue number2
DOIs
Publication statusPublished - Sep 2016
Event18th Workshop on MAthematical Performance Modeling and Analysis (MAMA 2016) - Antibes Juan-les-Pins, France
Duration: 14 Jun 2016 → …

Keywords

  • Diffusion limit
  • Fluid limit
  • Join-the-shortest queue policy
  • Load balancing
  • Many-server asymptotics
  • Power-of-d scheme
  • Scaling limits
  • Stochastic coupling

Fingerprint Dive into the research topics of 'Universality of power-of-d load balancing schemes'. Together they form a unique fingerprint.

Cite this