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 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%. 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.

REFERENCES

• 1: "the bamboo dht -- introduction". http://bamboo-dht.org/.
• 2: "the bamboo dht -- introduction". http://bamboo-dht.org/.
• 3: D. P. Anderson, J. Cobb, E. Korpella, M. Lebofsky, and D. Werthimer. Seti@home: An experiment in public-resource computing. Communications of the ACM, 11(45):56--61, 2002.
• 4: J. Aspnes, Z. Diamadi, and G. Shah. Fault-tolerant routing in peer-to-peer systems. In Proc. of the Symp. on Principles of Distributed Computing (PODC), Monterey, CA, Jul 2002.
• 5: B. Calder, A. A. Chien, J. Wang, and D. Yang. The entropia virtual machine for desktop grids. In CSE technical report CS2003-0773, University of California, San Diego, San Diego, CA, Oct 2003.
• 6: M. Castro, M. Costa, and A. Rowstron. Performance and dependability of structured peer-to-peer overlays. In Proc. of the Conf. on Dependable Systems and Networks, Jun 2004.
• 7: M. Castro, P. Druschel, Y. C. Hu, and A. Rowstron. Topology-aware routing in structured peer-to-peer overlay networks. In Microsoft Research MSR-TR-2002-82, Sep 2002.
• 8: W. Chen and X. Liu. Enforcing routing consistency in structured peer-to-peer overlays: Should we and could we? In In Proc. of the Workshop on Peer-to-Peer Systems (IPTPS), Santa Barbara, CA, Feb 2006.
• 9: B. Chun, D. Culler, T. Roscoe, A. Bavier, L. Peterson, M. Wawrzoniak, and M. Bowman. Planetlab: An overlay testbed for broad-coverage services. ACM SIGCOMM Computer Communication Review, 33(3), 2003.
• 10: B. Ford. Unmanaged Internet Protrocol: Taming the edge network management crisis. In Proc. of the Workshop on Hot Topics in Networks (HotNets), Cambridge, MA, Nov 2003.
• 11: B. Ford, P. Srisuresh, and D. Kegel. Peer-to-peer communication across network address translators. In Proc. of the USENIX Annual Technical Conference, Anaheim, California, Apr 2005.
• 12: I. Foster, C. Kesselman, and S. Tuecke. The anatomy of the grid: Enabling scalable virtual organizations. Intl. Journal of Supercomputer Applications, 15(3), 2001.
• 13: M. J. Freedman, K. Lakshminarayanan, S. Rhea, , and I. Stoica. Non-transitive connectivity and DHTs. In Proc. of the USENIX WORLDS, San Francisco, CA, Dec 2005.
• 14: M. J. Freedman, K. Lakshminarayanan, S. Rhea, , and I. Stoica. Non-transitive connectivity and DHTs. In Proc. of the USENIX WORLDS, San Francisco, CA, Dec 2005.
• 15: A. Ganguly, A. Agrawal, P. O. Boykin, and R. J. Figueiredo. Wow: Self-organizing wide area overlay networks of virtual workstations. In Proc. of Intl. Symp. on High Performance Distributed Computing, Paris, France, Jun 2006.
• 16: A. Ganguly, D. Wolinsky, P. O. Boykin, and R. J. Figueiredo. Decentralized dynamic host configuration in wide-area overlays of virtual workstations. In Proc. of the Workshop on Desktop Grids and Volunteer Computing Systems, with IPDPS, Long Beach, CA, Mar 2006.
• 17: S. Gerding and J. Stribling. Examining the trade-offs of structrured overlays in dynamic non-transitive network, Dec 2003. Class project: http://pdos.lcs.mit.edu/ strib/doc/networking_fall2003.ps.
• 18: K. Gummadi, R. Gummadi, S.Gribble, S. Ratnasamy, S. Shenker, and I. Stoica. The impact of DHT routing geometry on resilience and proximity. In Proc. of ACM SIGCOMM, Karlsruhe, Germany, Aug 2003.
• 19: J. Kleinberg. Nature, 406:845, 2000.
• 20: J. Li, J. Stribling, R. Morris, M. F. Kaashoek, and T. M. Gil. A performance vs. cost framework for evaluating DHT design tradeoffs under churn. In Proc. IEEE INFOCOM, 2005.
• 21: J. Liang, R. Kumar, and K. Ross. The fasttrack overlay: A measurement study. In Computer Networks (Special Issue on Overlays), 2005.
• 22: M. Litzkow, M. Livny, and M. Mutka. Condor - a Hunter of Idle Workstations. In Proc. of Intl. Conference on Distributed Computing Systems, Jun 1988.
• 23: V. Lo, D. Zappala, D. Zhou, Y. Liu, and S. Zhao. Cluster computing on the fly: P2P scheduling of idle cycles in the internet. In Proc. of the 3rd Intl. Workshop on Peer-to-Peer Systems (IPTPS), San Diego, CA, Feb 2004.
• 24: J. Maassen and H. E. Bal. Smartsockets: Solving the connectivity problems in grid computing. In Proc. of Symp. on High Performance Distributed Computing Symposium, Monterey Bay, CA, Jun 2007.
• 25: P. Maymounkov and D. Mazières. Kademlia: A peer-to-peer information system based on the xor metric. In Proc. of the Workshop on Peer-to-Peer Systems (IPTPS), Cambridge, MA, Mar 2002.
• 26: A. Mislove and P. Druschel. Providing administrative control and autonomy in structured peer-to-peer overlays. In Proc. of the Workshop on Peer-to-peer systems, San Diego, CA, Feb 2004.
• 27: A. Mislove, A. Post, A. Haeberlen, and P. Druschel. Experiences in building and operating epost, a reliable peer-to-peer application. In Proc. of European Conf. on Computer Systems, Leuven, Belgium, Apr 2006.
• 28: S. Rhea, D. Geels, T. Roscoe, and J. Kubiatowicz. Handling churn in a DHT. In Proc. of USENIX Technical Conference, Jun 2004.
• 29: S. Rhea, B. Godfrey, B. Karp, J. Kubiatowicz, S. Ratnasamy, S. Shenker, I. Stoica, and H. Yu. Opendht: A public DHT service and its uses. In Proc. of ACM SIGCOMM, Philadelphia, PA, Aug 2005.
• 30: A. Rowstron and P. Druschel. Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems. In Proc. of the Intl. Conf. on Distributed Systems Platforms (Middleware), Heidelberg, Germany, Nov 2001.
• 31: I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F. Kaashoek, F. Dabek, and H. Balakrishnan. Chord: a scalable peer-to-peer lookup protocol for internet applications. IEEE/ACM Transactions on Networking, 11(1):17--32, 2003.
• 32: D. Wolinsky, A. Agrawal, P. O. Boykin, J. Davis, A. Ganguly, V. Paramygin, P. Sheng, and R. Figueiredo. On the design of virtual machine sandboxes for distributed computing in wide area overlays of virtual workstations. In Proc. of the Workshop on Virtualization Technology in Distributed Computing, with Supercomputing, Tampa, FL, Nov 2006.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Algorithms, Design, Experimentation

Keywords:
DHT, overlay, p2p, virtual network