Asymptotically optimal load balancing topologies

Research output: Contribution to journalArticleAcademic

54 Downloads (Pure)

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 λ . 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
JournalarXiv
Issue number1707.05866
Publication statusPublished - 2017

Fingerprint

Asymptotically Optimal
Load Balancing
Topology
Clique
Server
Queue Length
Minimum Degree
Graph in graph theory
Exchangeability
Arbitrary
Poisson process
Random Graphs
Completion
Vanish
Optimality
Tend
Unit
Vertex of a graph
Demonstrate

Cite this

@article{870c3ef530bd411296620e599a0e017d,
title = "Asymptotically optimal load balancing topologies",
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 λ . 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 .",
author = "D. Mukherjee and S.C. Borst and {van Leeuwaarden}, J.S.H.",
year = "2017",
language = "English",
journal = "arXiv",
publisher = "Cornell University Library",
number = "1707.05866",

}

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

In: arXiv, No. 1707.05866, 1707.05866, 2017.

Research output: Contribution to journalArticleAcademic

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 -