A Note on Load Balancing in Many-Server Heavy-Traffic Regime

Xingyu Zhou, Ness Shroff

Published 2020-04-20Version 1

In this note, we apply Stein's method to analyze the performance of general load balancing schemes in the many-server heavy-traffic regime. In particular, consider a load balancing system of $N$ servers and the distance of arrival rate to the capacity region is given by $N^{1-\alpha}$ with $\alpha > 1$. We are interested in the performance as $N$ goes to infinity under a large class of policies. We establish different asymptotics under different scalings and conditions. Specifically, (i) if the second moments of total arrival and total service processes approach to constants $\sigma_{\Sigma}^2$ and $\nu_{\Sigma}^2$ as $N\to \infty$, then for any $\alpha > 3$, the distribution of the sum queue length scaled by $N^{1-\alpha}$ converges to an exponential random variable with rate $\frac{\sigma_{\Sigma}^2 + \nu_{\Sigma}^2}{2}$. (2) If the second moments linearly increase with $N$ with coefficients $\sigma_a^2$ and $\nu_s^2$, then for any $\alpha > 2$, the distribution of the sum queue length scaled by $N^{-\alpha}$ converges to an exponential random variable with rate $\frac{\sigma_a^2 + \nu_s^2}{2}$. (3) If the second moments quadratically increase with $N$ with coefficients $\tilde{\sigma}_a^2$ and $\tilde{\nu}_s^2$, then for any $\alpha > 1$, the distribution of the sum queue length scaled by $N^{-\alpha-1}$ converges to an exponential random variable with rate $\frac{\tilde{\sigma}_a^2 + \tilde{\nu}_s^2}{2}$. All the results are simple applications of our previously developed framework of Stein's method for heavy-traffic analysis in [9].