Search and replication in unstructured peer-to-peer networks

Qin Lv, Pei Cao, Edith Cohen, Kai Li, Scott Shenker

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

Abstract

Decentralized and unstructured peer-to-peer networks such as Gnutella are attractive for certain applications because they require no centralized directories and no precise control over network topology or data placement. However, the flooding-based query algorithm used in Gnutella does not scale;eac h query generates a large amount of traffic and large systems quickly become overwhelmed by the queryinduced load. This paper explores, through simulation, various alternatives to Gnutella's query algorithm, data replication strategy, and network topology. We propose a query algorithm based on multiple random walks that resolves queries almost as quickly as Gnutella's flooding method while reducing the network traffic by two orders of magnitude in many cases. We also present simulation results on a distributed replication strategy proposed in [8]. Finally, we find that among the various network topologies we consider, uniform random graphs yield the best performance. Copyright

Original languageEnglish (US)
Title of host publicationICS 2014 - Proceedings of the 28th ACM InternationaI Conference on Supercomputing
EditorsUtpal Banerjee
PublisherAssociation for Computing Machinery
Pages335-346
Number of pages12
ISBN (Electronic)9781450328401
DOIs
StatePublished - Jun 10 2014
Event25th ACM International Conference on Supercomputing, ICS 2014 - Munich, Germany
Duration: Jun 10 2014Jun 13 2014

Publication series

NameProceedings of the International Conference on Supercomputing

Other

Other25th ACM International Conference on Supercomputing, ICS 2014
CountryGermany
CityMunich
Period6/10/146/13/14

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Peer-to-peer
  • Replication
  • Search
  • Unstructured

Fingerprint Dive into the research topics of 'Search and replication in unstructured peer-to-peer networks'. Together they form a unique fingerprint.

  • Cite this

    Lv, Q., Cao, P., Cohen, E., Li, K., & Shenker, S. (2014). Search and replication in unstructured peer-to-peer networks. In U. Banerjee (Ed.), ICS 2014 - Proceedings of the 28th ACM InternationaI Conference on Supercomputing (pp. 335-346). (Proceedings of the International Conference on Supercomputing). Association for Computing Machinery. https://doi.org/10.1145/2591635.2667182