### Abstract

Original language | English |
---|---|

Article number | 1707.05866 |

Number of pages | 25 |

Journal | arXiv |

Issue number | 1707.05866 |

Publication status | Published - 2017 |

### Fingerprint

### Cite this

*arXiv*, (1707.05866), [1707.05866].

}

*arXiv*, no. 1707.05866, 1707.05866.

**Asymptotically optimal load balancing topologies.** / Mukherjee, D.; Borst, S.C.; van Leeuwaarden, J.S.H.

Research output: Contribution to journal › Article › Academic

TY - JOUR

T1 - Asymptotically optimal load balancing topologies

AU - Mukherjee, D.

AU - Borst, S.C.

AU - van Leeuwaarden, J.S.H.

PY - 2017

Y1 - 2017

N2 - 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 .

AB - 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 .

M3 - Article

JO - arXiv

JF - arXiv

IS - 1707.05866

M1 - 1707.05866

ER -