Abstract
A great deal of work has been done to improve peer-to-peer routing by strategically moving or replicating content. However, there are many applications for which a peer-to-peer architecture might be appropriate, but in which content movement is not feasible. We argue that even in such applications, progress can be made in developing techniques that ensure efficient searches. We present several such techniques. First, we show that organizing the network into a square-root topology, where peer degrees are proportional to the square root of the popularity of their content, provides much better performance than power-law networks. Second, we present routing optimizations based on the amount of content stored at peers, and tracking the “best” peers, that can further improve performance. These and other techniques can make searches efficient, even when content movement or replication is not feasible.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Adamic, L., Lukose, R., Puniyani, A., Huberman, B.: Search in power-law networks. Phys. Rev. E 64, 46135–46143 (2001)
Bawa, M., Bayardo Jr., R.J., Rajagopalan, S., Shekita, E.: Make it fresh, make it quick — searching a network of personal webservers. In: Proc. WWW (2003)
Chawathe, Y., Ratnasamy, S., Breslau, L., Lanham, N., Shenker, S.: Making Gnutella-like P2P systems scalable. In: Proc. SIGCOMM (2003)
Cohen, E., Shenker, S.: Replication strategies in unstructured peer-to-peer networks. In: Proc. SIGCOMM (2002)
Cooper, B.F.: A content model for evaluating peer-to-peer searching techniques. In: Jacobsen, H.-A. (ed.) Middleware 2004. LNCS, vol. 3231, pp. 18–37. Springer, Heidelberg (2004)
Cooper, B.F.: An optimal overlay topology for routing peer-to-peer searches. Technical report (April 2005), available at http://www.cc.gatech.edu/~cooperb/pubs/squareroot.pdf
Cooper, B.F., Garcia-Molina, H.: Studying search networks with SIL. In: Kaashoek, M.F., Stoica, I. (eds.) IPTPS 2003. LNCS, vol. 2735, Springer, Heidelberg (2003)
Crespo, A., Garcia-Molina, H.: Routing indices for peer-to-peer systems. In: Proc. ICDCS (2002)
Ge, Z., Figueiredo, D.R., Jaiswal, S., Kurose, J., Towsley, D.: Modeling peer-peer file sharing systems. In: Proc. INFOCOM (2003)
Gummadi, K.P., Dunn, R.J., Saroiu, S., Gribble, S.D., Levy, H.M., Zahorjan, J.: Measurement, modeling and analysis of a peer-to-peer file-sharing workload. In: Proc. SOSP (2003)
Lv, Q., Cao, P., Cohen, E., Li, K., Shenker, S.: Search and replication in unstructured peer-to-peer networks. In: Proc. Int’l Conf. on Supercomputing (ICS) (2002)
Lv, Q., Ratnasamy, S., Shenker, S.: Can heterogeneity make Gnutella scalable. In: Druschel, P., Kaashoek, M.F., Rowstron, A. (eds.) IPTPS 2002. LNCS, vol. 2429, p. 94. Springer, Heidelberg (2002)
Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, New York (1995)
Nejdl, W., Wolpers, M., Siberski, W., Schmitz, C., Schlosser, M., Brunkhorst, I., Loser, A.: Super-peer-based routing and clustering strategies for RDF-based peer-to-peer networks. In: Proc. WWW (2003)
Palmer, C., Steffan, J.: Generating network topologies that obey power laws. In: Proc. GLOBECOM (2000)
Pandurangan, G., Raghavan, P., Upfal, E.: Building low-diameter P2P networks. In: Proc. IEEE FOCS (2001)
Ratnasamy, S., Francis, P., Handley, M., Karp, R., Shenker, S.: A scalable content-addressable network. In: Proc. SIGCOMM (August 2001)
Rowstron, A., Druschel, P.: Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems. In: Guerraoui, R. (ed.) Middleware 2001. LNCS, vol. 2218, p. 329. Springer, Heidelberg (2001)
Stoica, I., Morris, R., Karger, D., Kaashoek, M.F., Balakrishnan, H.: Chord: A scalable peer-to-peer lookup service for internet applications. In: Proc. SIGCOMM (August 2001)
Yang, B., Garcia-Molina, H.: Efficient search in peer-to-peer networks. In: Proc. ICDCS (2002)
Yang, B., Garcia-Molina, H.: Designing a super-peer network. In: Proc. ICDE (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cooper, B.F. (2005). Quickly Routing Searches Without Having to Move Content. In: Castro, M., van Renesse, R. (eds) Peer-to-Peer Systems IV. IPTPS 2005. Lecture Notes in Computer Science, vol 3640. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11558989_15
Download citation
DOI: https://doi.org/10.1007/11558989_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29068-1
Online ISBN: 978-3-540-31906-1
eBook Packages: Computer ScienceComputer Science (R0)