Improving peer connectivity in wide-area overlays of virtual workstations
Abstract Self-configuring virtual networks rely on structured P2P routing to provide seamless connectivity among nodes through overlay routing of virtual IP packets, support decentralized hole-punching to establish bi-directional communication links among nodes behind network address translators, and dynamic configuration of virtual IP addresses. Our experiences with deployments of virtual networks in support of wide-area overlays of virtual workstations (WOWs) reveal that connectivity constraints imposed by symmetric NATs and by Internet route outages often hinder P2P overlay structure maintenance and routability, subsequently limiting the ability of WOWs to deliver high-throughput computing through aggregation of resources in different domains. In this paper, we describe and evaluate two novel approaches which are generally applicable and fully decentralized, and show that they improve routability of structured P2P networks in such connectivity constrained environments: (1) a fault-tolerant routing algorithm based on simulated annealing from optimization theory, and (2) tunneling of connections between adjacent nodes (in the P2P identifier space) over common neighbors when direct communication is not possible. Simulation-based analyses show that (1) when pairs of nodes only have 70% chance of being able to communicate directly, the described approaches improve all-to-all routability of the network from 90% to 99%, and (2) even when only 70% of the nodes are behind NATs that include symmetric NATs, these techniques improve the all-to-all connectivity of the network from less than 95% to more than 99%. We have implemented these techniques in the IP-over-P2P (IPOP) virtual network and have conducted experiments with a 180-node WOW Condor pool, demonstrating that, at 81% probability of establishing a pair-wise connection, annealing and tunneling combined allow all nodes to be connected to the pool, compared to only 160 nodes in the absence of these techniques.