Efficient and scalable search on scale-free P2P networks | Peer-to-Peer Networking and Applications Skip to main content
Springer Nature Link
Log in

Efficient and scalable search on scale-free P2P networks

  • Published:
Peer-to-Peer Networking and Applications Aims and scope Submit manuscript

Abstract

Unstructured peer-to-peer (P2P) systems (e.g. Gnutella) are characterized by uneven distributions of node connectivity and file sharing. The existence of “hub” nodes that have a large number of connections and “generous” nodes that share many files significantly influences performance of information search over P2P file-sharing networks. In this paper, we present a novel Scalable Peer-to-Peer Search (SP2PS) method with low maintenance overhead for resource discovery in scale-free P2P networks. Different from existing search methods which employ one heuristic to direct searches, SP2PS achieves better performance by considering both of the number of shared files and the connectivity of each neighbouring node. SP2PS enables peer nodes to forward queries to the neighbours that are more likely to have the requested files and also can help in finding the requested files in the future hops. The proposed method has been simulated in different power-law networks with different forwarding degrees and distances. From our analytic and simulation results, SP2PS achieves better performance when compared to other related methods.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10

Similar content being viewed by others

References

  1. Adamic LA, Lukose RM, Puniyani AR, Huberman BA (2001) Search in power law networks. Phys Rev 64:046135–046131–046135-046138

    Google Scholar 

  2. Yang B, Garcia-Molina H (2002) Efficient search in peer-to-peer networks. International Conference on Distributed Computing Systems, Vienna

  3. Li X, Wu J (2005) A hybrid searching scheme in unstructured P2P networks. International Conference on Parallel Processing, Oslo

  4. Lv Q, Cao P, Cohen E, Li K, Shenker S (2002) Search and replication in unstructured peer-to-peer networks. ACM SIGMETRICS, Marina Del Rey

  5. Stoica I, Morris R, Karger D, Kaashoek MF, Balakrishnan H (2001) Chord: A scalable peer-to-peer lookup service for internet applications. ACM SIGCOMM, San Diego

  6. Antonopoulos N, Exarchakos G (2007) G-ROME: A semantic driven model for capacity sharing among P2P networks. J Internet Res 17:7–20

    Article  Google Scholar 

  7. Salter J, Antonopoulos N (2007) An optimised 2-Tier P2P architecture for contextualised keyword searches. Future Gener Comp Sy 23:241–251

    Article  Google Scholar 

  8. Rowstron A, Druschel P (2001) Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. IFIP/ACM International Conference on Distributed Systems Platforms, Heidelberg

  9. Ratnasamy S, Francis P, Handley M, Karp R, Shenker S (2001) A scalable content-addressable network. ACM SIGCOMM, San Diego

  10. Li J, Stribling J, Morris R, Kaashoek MF (2005) Bandwidth-efficient management of DHT routing tables. 2nd Symposium on Networked Systems Design and Implementation, Boston

  11. Maymounkov P, Mazi`eres D (2002) Kademlia: A peer to peer information system based on the XOR metric. Internation Workshop on Peer-to-Peer Systems, Cambridge

  12. Rhea S, Geels D, Roscoe T, Kubiatowicz J (2004) Handling churn in a DHT. USENIX Annual Technical Conference, Boston

  13. Vuong S, Li J (2003) Efa: an Efficient content routing algorithm in large peer-to-peer overlay networks. International Conference on Peer-to-Peer Computing, Linköping

  14. Liu L, Antonopoulos N, Mackin S (2007) Fault-tolerant peer-to-peer search on small-world networks. Future Gener Comp Sy 23:921–931

    Article  Google Scholar 

  15. Liu L, Antonopoulos N, Mackin S (2007) Small world peer-to-peer for resource discovery. International Conference on Information Networking, Lecture Notes in Computer Science, Estoril, Portugal

  16. Li J, Vuong S (2004) An efficient clustered architecture for P2P networks. 18th International Conference on Advanced Information Networking and Application, Fukuoka

  17. Chawathe Y, Ratnasamy S, Breslau L, Lanham N, Shenker S (2003) Making gnutella-like P2P system scalable. ACM SIGCOMM, Karlsruhe

  18. Xiao L, Liu Y, Ni LM (2005) Improving unstructured peer-to-peer systems by adaptive connection establishment. IEEE Trans Comp 54:176–184

    Article  Google Scholar 

  19. Liu Y, Xiao L, Liu X, Ni LM, Zhang X (2005) Location awareness in unstructured peer-to-peer systems. IEEE Trans Parallel and Distrib Syst 16:163–174

    Article  Google Scholar 

  20. Crespo A, Garcia-Molina H (2002) Routing indices for peer-to-peer systems. International Conference on Distributed Computing Systems, Vienna

  21. Sripanidkulchai K, Maggs B, Zhang H (2003) Efficient content location using interest-based locality in peer-to-peer systems. IEEE Infocom, San Francisco

  22. Liu L, Antonopoulos N, Mackin S, Xu J, Russell D (2009) Efficient resource discovery in self-organized unstructured peer-to-peer networks, Concurrency Computat: Pract Exper 23(2):159–183, February

    Google Scholar 

  23. Liu L, Antonopoulos N, Mackin S (2007) Social peer-to-peer for resource discovery. 15th Euromicro International Conference on Parallel, Distributed and Network-based Processing, Naples

  24. Marti S, Garcia-Molina H (2004) Limited reputation sharing in P2P systems. ACM Conference on Electronic Commerce, New York

  25. Barabasi AL, Albert R (1999) Emergence of scaling in random networks. Science 286:509–512

    Article  MathSciNet  Google Scholar 

  26. Robb J (2004) Scale-free networks. Global Guerrillas. http://globalguerrillas.typepad.com/globalguerrillas/2004/05/scalefree_terro.html

  27. Saroiu S, Gummadi PK, Gribble SD (2002) A measurement study of peer-to-peer file sharing systems. International Conference on Multimedia Networking and Computing, Santa Barbara

  28. Gummadi KP, Dunn RJ, Saroiu S, Gribble SD, Levy HM, Zahorjan J (2003) Measurement, modelling and analysis of a P2P file-sharing workload. ACM Symposium on Operating Systems Principles, Bolton Landing, New York

  29. Pauli C, Shepperd M (2005) An empirical investigation into P2P file-sharing user behaviour. Americas Conference on Information Systems, Omaha

  30. Perera G, Christensen K, Roginsky A (2005) Targeted search: Reducing the time and cost for searching for objects in multiple-server networks. International Performance Computing and Communications Conference, Phoenix

  31. Liu L, Antonopoulos N, Mackin S (2006) Directed information search and retrieval over unstructured peer-to-peer networks. The International Computer Engineering Conference, Cairo

  32. Banaei-Kashani F, Shahabi C (2003) Criticality-based analysis and design of unstructured peer-to-peer networks as complex systems. IEEE/ACM International Symposium on Cluster Computing and Grid, Tokyo

  33. Liu L, Antonopoulos N, Mackin S (2008) Managing peer-to-peer networks with human tactics in social interactions. J Supercomput 44(3):217–236, June

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computing, University of Leeds, Leeds, West Yorkshire, LS2 9JT, UK

    Lu Liu, Jie Xu, Duncan Russell, Paul Townend & David Webster

Authors
  1. Lu Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jie Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Duncan Russell
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Paul Townend
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. David Webster
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lu Liu.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Liu, L., Xu, J., Russell, D. et al. Efficient and scalable search on scale-free P2P networks. Peer-to-Peer Netw. Appl. 2, 98–108 (2009). https://doi.org/10.1007/s12083-008-0023-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12083-008-0023-5

Keywords

Search

Navigation