Speaker: |
Debankur Mukherjee (Technische Universiteit Eindhoven Department of Mathematics and Computer Science 5612 AZ Eindhoven Netherlands) |

Organiser: |
Sandeep K Juneja |

Date: |
Wednesday, 21 Dec 2016, 16:00 to 17:00 |

Venue: |
AG-80 |

(Scan to add to calendar)

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 < 1$ as $N \to \infty$ with $d(N) \to\infty$, 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 ordinary JSQ policy. We further leverage the coupling to establish that the diffusion limit in the critical regime where $(N - \lambda(N)) / \sqrt{N} \to \beta > 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.