[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Design and Analysis of a Bio-inspired Search Algorithm for Peer to Peer Networks

  • Conference paper
Self-star Properties in Complex Information Systems (SELF-STAR 2004)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3460))

Included in the following conference series:

Abstract

Decentralized peer to peer (p2p) networks like Gnutella are attractive for certain applications because they require no centralized directories and no precise control over network topology or data placement. The greatest advantage is the robustness provided by them. However, flooding-based query algorithms used by the networks produce enormous amounts of traffic and substantially slow down the system. Recently, flooding has been replaced by more efficient k-random walkers and different variants of such algorithms. In this paper, we report immune-inspired algorithms for searching peer to peer networks. The algorithms use the immune-inspired mechanism of affinity-governed proliferation to spread query message packets in the network. Through a series of experiments, we compare the proliferation mechanism with different variants of random walk algorithms.The detailed experimental results show message packets undergoing proliferation spread much faster in the network and consequently proliferation algorithms produce better search output in p2p networks than random walk algorithms. Moreover, theoretical results by calculating the packet spreading speeds are reported which provide an understanding of the improved performance of the proliferation based search algorithm.

This work was partially supported by the Future & Emerging Technologies unit of the European Commission through Project BISON (IST-2001-38923).

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Ganguly, N., Canright, G., Deutsch, A.: Design of a Robust Search Algorithm for P2P Networks. In: Bougé, L., Prasanna, V.K. (eds.) HiPC 2004. LNCS, vol. 3296, pp. 222–231. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  2. Ganguly, N., Canright, G., Deutsch, A.: Design of An Efficient Search Algorithm For P2P Networks Using Concepts From Natural Immune Systems. In: Yao, X., Burke, E.K., Lozano, J.A., Smith, J., Merelo-Guervós, J.J., Bullinaria, J.A., Rowe, J.E., Tiňo, P., Kabán, A., Schwefel, H.-P. (eds.) PPSN 2004. LNCS, vol. 3242, pp. 491–500. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  3. Ganguly, N., Deutsch, A.: Developing Efficient Search Algorithms for P2P Networks Using Proliferation and Mutation. In: Nicosia, G., Cutello, V., Bentley, P.J., Timmis, J. (eds.) ICARIS 2004. LNCS, vol. 3239, pp. 357–371. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  4. Jovanovic, M.A., Annexstein, F.S., Berman, K.A.: Scalability Issues in Large Peer-to-peer Networks - A Case Study of Gnutella. Technical Report University of Cincinnati (2001)

    Google Scholar 

  5. Lee, D.L., Chuang, H., Seamons, K.: Document ranking and the vector-space model. IEEE Softw. 14(2), 67–75 (1997)

    Article  Google Scholar 

  6. Medina, A., Lakhina, A., Matta, I., Byers, J.: BRITE: An Approach to Universal Topology Generation. In: Proceedings of the International Workshop on Modeling, Analysis and Simulation of Computer and Telecommunications Systems- MASCOTS (August 2001)

    Google Scholar 

  7. Murray, J.D.: Mathematical Biology. Springer, Heidelberg (1990)

    MATH  Google Scholar 

  8. Oram, A. (ed.): Peer-to-Peer: Harnessing the Power of Disruptive Technologies. O Reilly Books (2001)

    Google Scholar 

  9. Pandurangan, G., Raghavan, P., Upfal, E.: Building low-diameter peer-to-peer networks. IEEE Journal on Selected Areas in Communications (JSAC) 21(6) (2003)

    Google Scholar 

  10. Zipf, G.K.: Psycho-Biology of Languages. Houghton-Mifflin, Boston (1935)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Center for High Performance Computing, Dresden University of Technology, Dresden, Germany

    Niloy Ganguly, Lutz Brusch & Andreas Deutsch

Authors
  1. Niloy Ganguly
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lutz Brusch
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Andreas Deutsch
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Università di Bologna, Bologna, Italy

    Ozalp Babaoglu

  2. Szeged University, Hungary

    Márk Jelasity

  3. University of Trento, Italy

    Alberto Montresor

  4. Department of Computer Science, Technische Universtät Dresden, Dresden, Germany

    Christof Fetzer

  5. University of Rome “La Sapienza”, Rome, Italy

    Stefano Leonardi

  6. School of Computing Science, Newcastle University, Newcastle upon Tyne, UK

    Aad van Moorsel

  7. Department of Computer Science, Vrije Universiteit Amsterdam, The Netherlands

    Maarten van Steen

Rights and permissions

Reprints and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Ganguly, N., Brusch, L., Deutsch, A. (2005). Design and Analysis of a Bio-inspired Search Algorithm for Peer to Peer Networks . In: Babaoglu, O., et al. Self-star Properties in Complex Information Systems. SELF-STAR 2004. Lecture Notes in Computer Science, vol 3460. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11428589_23

Download citation

  • DOI: https://doi.org/10.1007/11428589_23

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-26009-7

  • Online ISBN: 978-3-540-32013-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation