Asymptotically Optimal Load Balancing Topologies

DOI10.1145/3179417MaRDI QIDQ6289169zbMATH OpenWikidataFDO

Authors Debankur Mukherjee, Sem Borst, Johan S. H. van Leeuwaarden

Publication date 18 July 2017

Full work available at URL https://doi.org/10.1145/3179417

Abstract: We consider a system of $N$ servers inter-connected by some underlying graph topology $G_N$. Tasks arrive at the various servers as independent Poisson processes of rate $lambda$. Each incoming task is irrevocably assigned to whichever server has the smallest number of tasks among the one where it appears and its neighbors in $G_N$. Tasks have unit-mean exponential service times and leave the system upon service completion. The above model has been extensively investigated in the case $G_N$ is a clique. Since the servers are exchangeable in that case, the queue length process is quite tractable, and it has been proved that for any $lambda<1$, the fraction of servers with two or more tasks vanishes in the limit as $Noinfty$. For an arbitrary graph $G_N$, the lack of exchangeability severely complicates the analysis, and the queue length process tends to be worse than for a clique. Accordingly, a graph $G_N$ is said to be $N$-optimal or $sqrtN$-optimal when the occupancy process on $G_N$ is equivalent to that on a clique on an $N$-scale or $sqrtN$-scale, respectively. We prove that if $G_N$ is an ErdH{o}s-R'enyi random graph with average degree $d(N)$, then it is with high probability $N$-optimal and $sqrtN$-optimal if $d(N)oinfty$ and $d(N)/(sqrtNlog(N))oinfty$ as $Noinfty$, respectively. This demonstrates that optimality can be maintained at $N$-scale and $sqrtN$-scale while reducing the number of connections by nearly a factor $N$ and $sqrtN/log(N)$ compared to a clique, provided the topology is suitably random. It is further shown that if $G_N$ contains $Theta(N)$ bounded-degree nodes, then it cannot be $N$-optimal. In addition, we establish that an arbitrary graph $G_N$ is $N$-optimal when its minimum degree is $N-o(N)$, and may not be $N$-optimal even when its minimum degree is $cN+o(N)$ for any $0<c<1/2$.

This page was built for publication: Asymptotically Optimal Load Balancing Topologies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6289169)