2004/11/15 by Jesse S. A. Bridgewater, Bridgewater, Jesse S. A., P. Oscar Boykin +4
Computer Science · Engineering · #Advanced Optical Network Technologies #C.2.4 #Distributed #Distributed and Parallel Computing Systems #FOS: Computer and information sciences #Parallel #Peer-to-Peer Network Technologies #and Cluster Computing (cs.DC) #cs.DC
paper · pdf · doi:10.48550/arxiv.cs/0411046
13 pages, 12 figures. Draft submitted to IEEE TPDS
openalex publication_date 2004/11/15 · arxiv created 2006/01/16 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.