Asymptotically optimal load balancing topologies

Research output: Contribution to journalArticleAcademic

116 Downloads (Pure)


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 λ . 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 λ<1 , the fraction of servers with two or more tasks vanishes in the limit as N→∞ . 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 N − − √ -optimal when the occupancy process on G N is equivalent to that on a clique on an N -scale or N − − √ -scale, respectively. We prove that if G N is an Erd\H{o}s-R\'enyi random graph with average degree d(N) , then it is with high probability N -optimal and N − − √ -optimal if d(N)→∞ and d(N)/(N − − √ log(N))→∞ as N→∞ , respectively. This demonstrates that optimality can be maintained at N -scale and N − − √ -scale while reducing the number of connections by nearly a factor N and N − − √ /log(N) compared to a clique, provided the topology is suitably random. It is further shown that if G N contains Θ(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 .
Original languageEnglish
Article number1707.05866
Number of pages25
Issue number1707.05866
Publication statusPublished - 2017


Dive into the research topics of 'Asymptotically optimal load balancing topologies'. Together they form a unique fingerprint.

Cite this