Balanced Overlay Network (BON): Decentralized Load Balancing And Resource Discovery via Self-Organized Random Networks

University Of California-Los Angeles, Los Angeles CA

Investigators

Abstract

Proposal Title: Balanced Overlay Network (BON): Decentralized Load Balancing And Resource Discovery via Self-Organized Random Networks PI: Vwani Roychowdhury Institution: UCLA Abstract: The convergence of advanced P2P systems and grid computing is creating the possibility of decentralized enterprise-grade computing platforms. However, a key missing technology concerns the development of tools for distributed resource discovery, and balanced utilizations of such heterogeneous sets of resources, especially in the limit of very large-scale systems, where centralized approaches will prove to be inadequate. In this proposal we introduce a novel network-based dynamic resource discovery and utilization paradigm, Balanced Overlay Networks (BON), which can (i) Provide almost-optimal balanced utilization of resources, (ii) Scale to support networks with millions of nodes, (iii) Provide resource-offering nodes/agents the flexibility to dynamically vary and set the amount of shareable free resources, (iv) Evolve and form its structure based on local and self-organization rules, and without any central coordination and monitoring, (v) Provide protection against any disruption of the networks due to large-scale failures of participating nodes or attacks, and (vi) be readily incorporated into existing grid computing and web server platforms, such as the Condor project and the Apache web servers. BON utilizes a completely new approach, where the level of free resources of every resource server is encoded as its degree in a P2P overlay network. Nodes with high levels of free resources are found by performing short random walks on this overlay network. The network maintenance protocols guarantee that the underlying structure corresponds to that of random graphs, and short random walks will be sufficient to find servers that have the most resources to offer at any time.