Improving peer connectivity in wide-area overlays of virtual workstations

Self-configuring virtual networks rely on structured P2P rout- ing to provide seamless connectivity among nodes through overlay routing of virtual IP packets, support decentral- ized hole-punching to establish bi-directional communica- tion links among nodes behind network address translators, and dynamic configuration of virtual IP addresses. Our ex- periences 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 ap- proaches which are generally applicable and fully decen- tralized, and show that they improve routability of struc- tured P2P networks in such connectivity constrained envi- ronments: (1) a fault-tolerant routing algorithm based on simulated annealing from optimization theory, and (2) tun- neling of connections between adjacent nodes (in the P2P identifier space) over common neighbors when direct com- munication is not possible. Simulation-based analyses show that when pairs of nodes only have 70% chance of being able to communicate directly, the described approaches im- prove all-to-all routability of the network from 90% to 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 con- nected to the pool, compared to only 160 nodes in the ab- sence of these techniques.