Asymptotically Optimal Load Balancing Topologies
share
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ős-Rényi 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)(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) / (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 c N + o(N) for any 0 < c < 1/2.
READ FULL TEXT