Making gnutella-like P2P systems scalable

ABSTRACT

Napster pioneered the idea of peer-to-peer file sharing, and supported it with a centralized file search facility. Subsequent P2P systems like Gnutella adopted decentralized search algorithms. However, Gnutella's notoriously poor scaling led some to propose distributed hash table solutions to the wide-area file search problem. Contrary to that trend, we advocate retaining Gnutella's simplicity while proposing new mechanisms that greatly improve its scalability. Building upon prior research [1, 12, 22], we propose several modifications to Gnutella's design that dynamically adapt the overlay topology and the search algorithms in order to accommodate the natural heterogeneity present in most peer-to-peer systems. We test our design through simulations and the results show three to five orders of magnitude improvement in total system capacity. We also report on a prototype implementation and its deployment on a testbed.

REFERENCES

• 1: Adamic, L. A., Lukose, R. M., Puniyani, A. R., and Huberman, B. A. Search in Power-law Networks. Physical Review E 64 (2001).
• 2: Adar, E., and Huberman, B. A. Free Riding on Gnutella. First Monday, Internet Journal (Oct. 2000). Available at http://www.firstmonday.dk/issues/issue5_10/adar/index.html.
• 3: Bhagwan, R., Savage, S., and Voelker, G. Understanding Availability. In Proceedings of the 2nd International Workshop on Peer-to-Peer Systems (IPTPS '03). (Berkeley, CA, Feb. 2003).
• 4: c---net News. Napster among fastest-growing Net technologies, Oct. 2000. http://news.com.com/2100-1023-246648.html.
• 5: Gnucleus. The Gnutella Web Caching System, 2002. http://www.gnucleus.net/gwebcache/.
• 6: Gnutella Development Forum. The Gnutella v0.6 Protocol, 2001. http://groups.yahoo.com/group/the_gdf/files/.
• 7: Gnutella Development Forum. The Gnutella Ultrapeer Proposal, 2002. http://groups.yahoo.com/group/the_gdf/files/Proposals/Ultrapeer/.
• 8: gnutella.wego.com. Gnutella: Distributed Information Sharing, 2000. http://gnutella.wego.com/.
• 9: Pawan Goyal , Harrick M. Vin , Haichen Chen, Start-time fair queueing: a scheduling algorithm for integrated services packet switching networks, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.157-168, August 28-30, 1996, Palo Alto, California, United States
• 10: Balachander Krishnamurthy , Jia Wang , Yinglian Xie, Early measurements of a cluster-based architecture for P2P systems, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505216]
• 11: Li, J., Loo, B. T., Hellerstein, J., Kaashoek, F., Karger, D. R., and Morris, R. On the Feasibility of Peer-to-Peer Web Indexing and Search. In Proceedings of the 2nd International Workshop on Peer-to-Peer Systems (IPTPS '03). (Berkeley, CA, Feb. 2003).
• 12: Qin Lv , Pei Cao , Edith Cohen , Kai Li , Scott Shenker, Search and replication in unstructured peer-to-peer networks, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA [doi>10.1145/514191.514206]
• 13: Qin Lv , Sylvia Ratnasamy , Scott Shenker, Can Heterogeneity Make Gnutella Scalable?, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.94-103, March 07-08, 2002
• 14: 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
• 15: Metamachine. The Overnet File-sharing Network, 2002. http://www.overnet.com/.
• 16: Osokine, S. The Flow Control Algorithm for the Distributed 'Broadcast-Route' Networks with Reliable Transport Links., Jan. 2001. http://www.grouter.net/gnutella/flowcntl.htm.
• 17: Peterson, L., Anderson, T., Culler, D., and Roscoe, T. A Blueprint for Introducing Disruptive Technology into the Internet. In Proceedings of the ACM HotNets-I Workshop (Princeton, NJ, Oct. 2002). See also http://www.planet-lab.org/.
• 18: 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
• 19: Reynolds, P., and Vahdat, A. Efficient Peer-to-Peer Keyword Searching. Technical report, Duke University, Durham, NC, 2002. Available at http://issg.cs.duke.edu/search/.
• 20: Matei Ripeanu , Adriana Iamnitchi , Ian Foster, Mapping the Gnutella Network, IEEE Internet Computing, v.6 n.1, p.50-57, January 2002 [doi>10.1109/4236.978369]
• 21: Stefan Saroiu , Krishna P. Gummadi , Richard J. Dunn , Steven D. Gribble , Henry M. Levy, An analysis of internet content delivery systems, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060319]
• 22: Saroiu, S., Gummadi, P. K., and Gribble, S. D. A Measurement Study of Peer-to-Peer File Sharing Systems. In Proceedings of Multimedia Computing and Networking 2002 (MMCN'02) (San Jose, CA, Jan. 2002).
• 23: Subhabrata Sen , Jia Wang, Analyzing peer-to-peer traffic across large networks, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637222]
• 24: Sharman Networks Ltd. KaZaA Media Desktop, 2001. http://www.kazaa.com/.
• 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: Tang, C., Xu, Z., and Mahalingam, M. pSearch: Information Retrieval in Structured Overlays. In Proceedings of the ACM HotNets-I Workshop (Princeton, NJ, Oct. 2002).
• 27: 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

INDEX TERMS

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

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
Gnutella, distributed hash tables, peer-to-peer