Edith Cohen
Scott Shenker
ABSTRACT
The Peer-to-Peer (P2P) architectures that are most prevalent in today's Internet are decentralized and unstructured. Search is blind in that it is independent of the query and is thus not more effective than probing randomly chosen peers. One technique to improve the effectiveness of blind search is to proactively replicate data. We evaluate and compare different replication strategies and reveal interesting structure: Two very common but very different replication strategies - uniform and proportional - yield the same average performance on successful queries, and are in fact worse than any replication strategy which lies between them. The optimal strategy lies between the two and can be achieved by simple distributed algorithms. These fundamental results o.er a new understanding of replication and show that currently deployed replication strategies are far from optimal and that optimal replication is attainable by protocols that resemble existing ones in simplicity and operation.
- Boeing proxy logs. http://www.web-caching.com/traces-logs.html.Google Scholar
- Open Source Community. The free network project - rewiring the internet. In http://freenet.sourceforge.net/, 2001.Google Scholar
- Open Source Community. Gnutella. In http://gnutella.wego.com/, 2001.Google Scholar
- KaZaA file sharing network. KaZaA. In http://www.kazaa.com/, 2002.Google Scholar
- Morpheus file sharing system. Morpheus. In http://www.musiccity.com/, 2002.Google Scholar
- Napster Inc. The napster homepage. In http://www.napster.com/, 2001.Google Scholar
- J. Kangasharju, K. W. Ross, and D. A. Turner. Optimal content replication in P2P communities. Manuscript, 2002.Google Scholar
- L. Kleinrock. Queueing Systems, Volume II: Computer Applications. Wiley-Interscience, New York, 1976.Google Scholar
- Q. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker. Search and replication in unstructured peer-to-peer networks. In Proceedings of the 16th annual ACM International Conference on supercomputing, 2002. Google ScholarDigital Library
- S. Ratnassamy, P. Francis, M. Handley, R. Karp, and S. Shenker. A scalable content-addressable network. In Proceedings of the ACM SIGCOMM'01 Conference, 2001. Google ScholarDigital Library
- A. Rowstron and P. Druschel. Storage management and caching in past, a large-scale, persistent peer-to-peer storage utility. In Proceedings of SOSP'01, 2001. Google ScholarDigital Library
- I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnana. Chord: A scalable peer-to-peer lookup service for internet applications. In Proceedings of the ACM SIGCOMM'01 Conference, 2001. Google ScholarDigital Library
- FastTrack Peer-to-Peer technology company. FastTrack. In http://www.fasttrack.nu/, 2001.Google Scholar
- N. H. Vaidya and S. Hameed. Scheduling data broadcast in asymmetric communication environments. ACM/Baltzer Wireless Networks, 5, 1999. Google ScholarDigital Library
- B. Y. Zhao, J. Kubiatowicz, and A. Joseph. Tapestry: An infrastructure for fault-tolerant wide-area location and routing. Technical Report UCB/CSD-01-1141, University of California at Berkeley, Computer Science Department, 2001. Google ScholarDigital Library
Index Terms
- Replication strategies in unstructured peer-to-peer networks
Recommendations
Replication strategies in unstructured peer-to-peer networks
Proceedings of the 2002 SIGCOMM conferenceThe Peer-to-Peer (P2P) architectures that are most prevalent in today's Internet are decentralized and unstructured. Search is blind in that it is independent of the query and is thus not more effective than probing randomly chosen peers. One technique ...
Search and replication in unstructured peer-to-peer networks
ACM International Conference on Supercomputing 25th Anniversary VolumeDecentralized 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 ...
Analysis of search and replication in unstructured peer-to-peer networks
SIGMETRICS '05: Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systemsThis paper investigates the effect of the number of file replicas on search performance in unstructured peer-to-peer networks. We observe that for a search network with a random graph topology where file replicas are uniformly distributed, the hop ...
Comments