A distributed virtual hypercube algorithm for maintaining scalable and dynamic network overlays

摘要

Network overlays support the execution of distributed applications, hiding lower level protocols and thernphysical topology. This work presents DiVHA: a distributed virtual hypercube algorithm that allows thernconstruction and maintenance of a self-healing overlay network based on a virtual hypercube. DiVHA keepsrnlogarithmic properties even when the number of nodes is not a power of two, presenting a scalable alternativernto connect distributed resources. DiVHA assumes a dynamic fault situation, in which nodes fail and recoverrncontinuously, leaving and joining the system. The algorithm is formally specified, and the latency for detectingrnchanges and the subsequent reconstruction of the topology is proved to be bounded. An actual overlayrnnetwork based on DiVHA called HyperBone was implemented and deployed in the PlanetLab. HyperBonernoffers services such as monitoring and routing, allowing the execution Grid applications across the Internet.rnHyperBone also includes a procedure for detecting groups of stable nodes, which allowed the executionrnof parallel applications on a virtual hypercube built on top of PlanetLab.