… load-balancing is achieved by rewiring load originators from the overutilized nodes to the underutlized nodes.
ERGO, the Enhanced Reconfigurable Gnutella Overlay project, concerns a load-balancing mechanism for unstructured peer-to-peer overlay networks. Such networks can be organized in an unstructured topology that is an abstract or random interconnection between the nodes of the network. Because of their topology, unstructured overlays experience a highly heterogeneous load among their nodes. ERGO focuses on the load of application queries generated and answered by the nodes of an unstructured peer-to-peer network, e.g. a Gnutella network. The queries may be related to a keyword search for resource sharing, a distributed database or other applications that generate a heterogeneous load among the nodes of an overlay network.

A two-level overlay hierarchy for load-balancing in ERGO

ERGO achieves a balanced load by introducing the concept of a virtual server or superpeer. These nodes, elected based on their performance profile, are organized in another overlay network that manages the load of the nodes in the network. More specifically, virtual servers index (i) underutilized nodes, (ii) overutilized nodes and (iii) the nodes that are the load originators of the overutilized nodes. The state of the load in the nodes is defined by thresholds related to the number of received queries. Based on this information, load-balancing is achieved by rewiring load originators from the overutilized nodes to the underutlized nodes.

The load thresholds of the nodes in ERGO.

The rewiring of ERGO is achieved in a cooperative fashion between the virtual servers. This means that virtual servers communicate to explore underutilized nodes about which they may not have knowledge. This makes the load balancing mechanism of ERGO decentralized and more robust to single node failures.

A load-balancing in ERGO by rewiring the load originator from an overloaded to an underloaded node.

ERGO has been evaluated qualitatively and quantitatively through simulations. Results show that load-balancing in unstructured overlay networks is feasible and cost-effective.

ERGO was the project of my MSc thesis and is published in a journal paper.

Related Publications