Balanced Overlay Networks (BON): Decentralized Load Balancing via Self-Organized Random Networks

Details Balanced Overlay Networks (BON): Decentralized Load Balancing via Self-Organized Random Networks Balanced Overlay Networks (BON): Decentralized Load Balancing via Self-Organized Random Networks

2004-11-15

arxiv.org/abs/cs/0411046v2

Computer Science

Distributed, Parallel, and Cluster Computing

13 pages, 12 figures. Draft submitted to IEEE TPDS

Scientific paper

We present a novel framework, called balanced overlay networks (BON), that provides scalable, decentralized load balancing for distributed computing using large-scale pools of heterogeneous computers. Fundamentally, BON encodes the information about each node's available computational resources in the structure of the links connecting the nodes in the network. This distributed encoding is self-organized, with each node managing its in-degree and local connectivity via random-walk sampling. Assignment of incoming jobs to nodes with the most free resources is also accomplished by sampling the nodes via short random walks. Extensive simulations show that the resulting highly dynamic and self-organized graph structure can efficiently balance computational load throughout large-scale networks. These simulations cover a wide spectrum of cases, including significant heterogeneity in available computing resources and high burstiness in incoming load. We provide analytical results that prove BON's scalability for truly large-scale networks: in particular we show that under certain ideal conditions, the network structure converges to Erdos-Renyi (ER) random graphs; our simulation results, however, show that the algorithm does much better, and the structures seem to approach the ideal case of d-regular random graphs. We also make a connection between highly-loaded BONs and the well-known ball-bin randomized load balancing framework.

Affiliated with

Also associated with

No associations

Rating

Balanced Overlay Networks (BON): Decentralized Load Balancing via Self-Organized Random Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Balanced Overlay Networks (BON): Decentralized Load Balancing via Self-Organized Random Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Balanced Overlay Networks (BON): Decentralized Load Balancing via Self-Organized Random Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-212212