The impact of DHT routing geometry on resilience and proximity

ABSTRACT

The various proposed DHT routing algorithms embody several different underlying routing geometries. These geometries include hypercubes, rings, tree-like structures, and butterfly networks. In this paper we focus on how these basic geometric approaches affect the resilience and proximity properties of DHTs. One factor that distinguishes these geometries is the degree of flexibility they provide in the selection of neighbors and routes. Flexibility is an important factor in achieving good static resilience and effective proximity neighbor and route selection. Our basic finding is that, despite our initial preference for more complex geometries, the ring geometry allows the greatest flexibility, and hence achieves the best resilience and proximity performance.

REFERENCES

• 1: M. Castro, M. Jones, Anne-Marie Kermarrec, A. Rowstron, M. Theimer, H. Wang, and A. Wolman. An Evaluation of Scalable Application-Level Multicast Built Using Peer-To-Peer Overlays. In Proceedings of the INFOCOM 2003, San Francisco, April 2003.
• 2: Miguel Castro, Peter Drushel, Y.C. Hu, and Antony Rowstron. Exploiting Network Proximity in Peer-to-peer Networks. Technical Report MSR-TR-2002-82, Microsoft Research, 2002.
• 3: Frank Dabek , M. Frans Kaashoek , David Karger , Robert Morris , Ion Stoica, Wide-area cooperative storage with CFS, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 4: Antony Rowstron , Peter Druschel, Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 5: IRIS: Infrastructure for Resilient Internet Systems. http://iris.lcs.mit.edu, May 2002.
• 6: David Karger Frans Kaashoek. Simple Constant-Space Distributed Hash Tables. In Proceedings of the IPTPS 2003, Berkeley, February 2003.
• 7: Anjali Gupta, Barbara Liskov, and Rodrigo Rodrigues. One Hop Lookups for Peer-to-Peer Overlays. In Proceedings of the HotOS-IX 2003, Hawaii, May 2003.
• 8: Kirsten Hildrum , John D. Kubiatowicz , Satish Rao , Ben Y. Zhao, Distributed object location in a dynamic network, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564877]
• 9: Sushant Jain, Ratul Mahajan, and David Wetherall. A Study of Performance Potential of DHT-based Overlays. In Proceedings of the 4th Usenix Symposium on Internet Technologies and Systems (USITS), Seattle, WA, USA, March 2003.
• 10: David R. Karger , Matthias Ruhl, Finding nearest neighbors in growth-restricted metrics, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510013]
• 11: Jon Kleinberg, The small-world phenomenon: an algorithm perspective, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.163-170, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335325]
• 12: John Kubiatowicz , David Bindel , Yan Chen , Steven Czerwinski , Patrick Eaton , Dennis Geels , Ramakrishna Gummadi , Sean Rhea , Hakim Weatherspoon , Chris Wells , Ben Zhao, OceanStore: an architecture for global-scale persistent storage, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.190-201, November 2000, Cambridge, Massachusetts, United States
• 13: Dmitri Loguinov , Anuj Kumar , Vivek Rai , Sai Ganesh, Graph-theoretic analysis of structured peer-to-peer systems: routing distances and fault resilience, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863999]
• 14: Dahlia Malkhi , Moni Naor , David Ratajczak, Viceroy: a scalable and dynamic emulation of the butterfly, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571857]
• 15: Petar Maymounkov , David Mazières, Kademlia: A Peer-to-Peer Information System Based on the XOR Metric, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.53-65, March 07-08, 2002
• 16: C. Greg Plaxton , Rajmohan Rajaraman , Andréa W. Richa, Accessing nearby copies of replicated objects in a distributed environment, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.311-320, June 23-25, 1997, Newport, Rhode Island, United States [doi>10.1145/258492.258523]
• 17: CAIDA: The Skitter Measurement Project. www.caida.org/tools/measurement/skitter/index.html, 2002.
• 18: Sylvia Paul Ratnasamy , Scott Shenker , Ion Stoica, A scalable content-addressable network, 2002
• 19: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 20: Sylvia Ratnasamy , Mark Handley , Richard M. Karp , Scott Shenker, Application-Level Multicast Using Content-Addressable Networks, Proceedings of the Third International COST264 Workshop on Networked Group Communication, p.14-29, November 07-09, 2001
• 21: Sylvia Ratnasamy, Mark Handley, Richard Karp, and Scott Shenker. Topologically-Aware Overlay Construction and Server Selection. In Proceedings of the INFOCOMM, 2002.
• 22: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 23: Stefan Saroiu, P. Krishna Gummadi, and Steven D. Gribble. A Measurement Study of Peer-to-peer File Sharing Systems. In Proceedings of the Multimedia Computing and Networking Conference (MMCN), San Jose, CA, USA, January 2002.
• 24: John Kubiatowicz Sean Rhea, Timothy Roscoe. DHTs Need Application-Driven Benchmarks. In Proceedings of the IPTPS 2003, Berkeley, February 2003.
• 25: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 26: Marcel Waldvogel and Roberto Renaldi. Efficient Topology-Aware Overlay Network. In Proceedings of the HotNets-I 2002, Princeton, October 2002.
• 27: Ben Y. Zhao, Anthony Joseph, and John D. Kubiatowicz. Locality Aware Mechanisms for Large-scale Networks. In Proceedings of the FuDiCo 02, Bertinoro, Italy, June 2002.
• 28: Ben Y. Zhao , John D. Kubiatowicz , Anthony D. Joseph, Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and, University of California at Berkeley, Berkeley, CA, 2001
• 29: Shelley Q. Zhuang , Ben Y. Zhao , Anthony D. Joseph , Randy H. Katz , John D. Kubiatowicz, Bayeux: an architecture for scalable and fault-tolerant wide-area data dissemination, Proceedings of the 11th international workshop on Network and operating systems support for digital audio and video, p.11-20, January 2001, Port Jefferson, New York, United States [doi>10.1145/378344.378347]

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
DHT, flexibility, routing geometry