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

On probabilistic flooding search over unstructured peer-to-peer networks

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

Abstract

Probabilistic flooding has been proposed as a means of reducing the excessive message overheads induced by plain flooding in unstructured peer-to-peer network search. We propose here Advanced Probabilistic Flooding (APF), a novel strategy which operates differently from other known strategies. In particular, the decision of a node to propagate a message (or not) is based on both the popularity of resources and the hop distance from the node that initiated the query. The latter is used to estimate the number of nodes reached by the query message. Based on these parameters we adjust the forwarding probability at the time a node receives the query message so as to reduce the duplicate message overhead while maintaining a high probability of query success. The primary goal of our approach is to minimize the cost of search associated with excessive message transmissions. Our claims are supported by detailed experiments in various network topologies

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
£29.99 /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 (United Kingdom)

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
Fig. 11

Similar content being viewed by others

References

  1. Banaei-Kashani F, Shahabi C (2003) Criticality-based analysis and design of unstructured peer-to-peer networks as “complex systems”. In: Proceedings of the 3st International Symposium on Cluster Computing and the Grid CCGRID ’03, IEEE Comput Soc, p 351

  2. Bisnik N, Abouzeid A (2005) Modeling and analysis of random walk search algorithms in p2p networks. In: Hot Topics in Peer-to-Peer Systems, 2005. HOT-P2P 2005. Second International Workshop on, pp 95–103

  3. Chandra J, Ganguly N (2011) On coverage bounds of unstructured peer-to-peer networks. A Compl Syst 14(4):611–633

    Article  MATH  MathSciNet  Google Scholar 

  4. Chandra J, Shaw SK, Ganguly N (2009) Analyzing network coverage in unstructured peer-to-peer networks: a complex network approach. Netw: 690–702

  5. Chang NB, Liu M (2007) Controlled flooding search in a large network. IEEE/ACM Trans Netw 15(2):436–449

    Article  MathSciNet  Google Scholar 

  6. Cohen E, Shenker S (2002) Replication strategies in unstructured peer-to-peer networks. SIGCOMM Comput Commun Rev 32(4):177–190. doi:10.1145/964725.633043

    Article  Google Scholar 

  7. Crisóstomo S, Schilcher U, Bettstetter C, Barros Ja (2009) Analysis of probabilistic flooding: how do we choose the right coin? In: Proceedings of the 2009 IEEE international conference on Communications, ICC’09. IEEE Press, USA, pp 2080– 2085

    Google Scholar 

  8. Crisóstomo S, Udo S, Christian B, Joao B (2012) Probabilistic flooding in stochastic networks: analysis of global information outreach. Comput Netw 56(1):142–156. doi:10.1016/j.comnet.2011.08.014

    Article  Google Scholar 

  9. Dimakopoulos VV, Pitoura E (2006) On the performance of flooding-based resource discovery. IEEE Trans Parallel Distrib Syst 17(11):1242–1252. doi:10.1109/TPDS.2006.161

    Article  Google Scholar 

  10. Erdös P, Rényi A (1959) On random graphs, I. Publ Mathm Debr 6:290–297. http://www.renyi.hu/p_erdos/Erdos.html#1959-11

    MATH  Google Scholar 

  11. Gaeta R, Balbo G, Bruell SC, Gribaudo M, Sereno M (2005) A simple analytical framework to analyze search strategies in large-scale peer-to-peer networks. Perform Eval 62(1–4):1–16

    Article  Google Scholar 

  12. Gaeta R, Sereno M (2011) Generalized Probabilistic Flooding in Unstructured Peer-to-Peer Networks. IEEE Trans Parallel Distrib Syst 2(12):2055–2062

    Article  Google Scholar 

  13. Gkantsidis C, Mihail M, Saberi A (2005) Hybrid search schemes for unstructured peer-to-peer networks. In: INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE 3:1526–1537. doi:10.1109/INFCOM.2005.1498436

    Google Scholar 

  14. Gkantsidis Christos MM, Amin S (2004) Random walks in peer-to-peer networks. In: INFOCOM

  15. Heath LS, Parikh N (2011) Generating random graphs with tunable clustering coefficients. Phys A Stat Mech Appl 390(2324):4577–4587. doi:10.1016/j.physa.2011.06.052

    Article  MathSciNet  Google Scholar 

  16. Himali DR, Prasad SK (2011) Spun: A p2p probabilistic search algorithm based on successful paths in unstructured networks. 2012 IEEE 26th Int Parallel Distrib Process Symp Work PhD Forum 0:1610–1617. doi:10.1109/IPDPS.2011.316

    Google Scholar 

  17. Kalogeraki V, Gunopulos D, Zeinalipour-Yazti D (2002) A local search mechanism for peer-to-peer networks. In: Proceedings of the eleventh international conference on Information and knowledge management CIKM ’02, pp 300–307. ACM

  18. Klemm A, Lindemann C, Vernon MK, Waldhorst OP (2004) Characterizing the query behavior in peer-to-peer file sharing systems. In: Proceedings of IMC ’04, 4th ACM SIGCOMM conference internet meas, Sicily, pp 55–67,

  19. Leskovec J (2011) Stanford network analysis project. http://snap.stanford.edu/index.html

  20. Leskovec J, Kleinberg J, Faloutsos C (2007) Graph evolution: densification and shrinking diameters. ACM Trans Knowl Discov Data 1(1). doi:10.1145/1217299.1217301

    Google Scholar 

  21. Li S, Lou L, Hong L (2013) Directional probabilistic broadcast in wireless mobile ad hoc networks. In: Proceedings of the 2013 international conference on computational and Information Sciences, ICCIS ’13. IEEE Computer Society, USA, pp 1421–1424

    Google Scholar 

  22. Lv Q, Cao P, Cohen E, Li K, Shenker S (2002) Search and replication in unstructured peer-to-peer networksIn: ICS, pp 84–95

  23. Makino N, Arakawa S, Murata M (2005) A flooding method for exchanging routing information in power-law networks. In: APCC 2005, Asia-Pacific Conference on Communications, pp 812– 816

  24. Newman MEJ (2009) Random Graphs with Clustering. Phys Rev Lett 103(5):058,701. doi:10.1103/PhysRevLett.103.058701

    Article  Google Scholar 

  25. Newman MEJ, Strogatz SH, Watts DJ (2001) Random graphs with arbitrary degree distributions and their applications. Phys Rev E 64(2):026,118

    Article  Google Scholar 

  26. Ni SY, Tseng YC, Chen YS, Sheu JP (1999) The broadcast storm problem in a mobile ad hoc network. In: Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, MobiCom ’99, pp 151–162. ACM, USA

    Book  Google Scholar 

  27. Oikonomou K, Kogias D, Stavrakakis I (2010) Probabilistic flooding for efficient information dissemination in random graph topologies. Comput Netw 54:1615–1629. doi:10.1016/j.comnet.2010.01.007

    Article  MATH  Google Scholar 

  28. Park H, Ratzin R I (2011) vdSM: peer-to-peer networks: protocols, cooperation and competition. In: Zhu C, Li Y (eds) X.N. Streaming media architectures, techniques, and applications: recent advances. Hershey, pp 262–294

  29. Reka A, Barabási (2002) Statistical mechanics of complex networks. Rev Mod Phys 74:47–97. http://arxiv.org/abs/cond-mat/0106096

    Article  Google Scholar 

  30. Rhea S, Kubiatowicz J (2002) Probabilistic location and routing. In: INFOCOM 2002. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. Proc IEEE 3:1248–1257. doi:10.1109/INFCOM.2002.1019375

    Google Scholar 

  31. Serrano Ángeles M, Boguñá M (2005) Tuning clustering in random networks with arbitrary degree distributions. Phys Rev E 72(036,133). doi:10.1103/PhysRevE.72.036133

    Google Scholar 

  32. Stauffer A, Barbosa V (2007) Probabilistic heuristics for disseminating information in networks. IEEE/ACM Trans Netw 15(2):425–435. doi:10.1109/TNET.2007.892877

    Article  Google Scholar 

  33. Tsoumakos D, Roussopoulos N (2003) Adaptive probabilistic search for peer-to-peer networks. In: Proceedings of the 3rd International Conference on Peer-to-Peer Computing, P2P ’03,. IEEE Computer Society, USA, p 102

    Google Scholar 

  34. Yang B, Garcia-Molina H (2002) Improving search in peer-to-peer networks. In: Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS’02), ICDCS ’02, vol 45. IEEE Computer Society. http://dl.acm.org/citation.cfm?id=850928.851859

  35. Zhang H, Zhang L, Shan X, Li V (2007) Probabilistic search in p2p networks with high node degree variation. In: ICC ’07, IEEE International Conference on Communications, 2007, pp 1710–1715

Download references

Author information

Authors and Affiliations

  1. Department of Computer Engineering, T.E.I. of Epirus, Arta, GR-47100, Greece

    Spiridoula V. Margariti

  2. Department of Computer Science and Engineering, University of Ioannina, Ioannina, GR-45110, Greece

    Spiridoula V. Margariti & Vassilios V Dimakopoulos

Authors
  1. Spiridoula V. Margariti
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Vassilios V Dimakopoulos
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Vassilios V Dimakopoulos.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Margariti, S.V., Dimakopoulos, V.V. On probabilistic flooding search over unstructured peer-to-peer networks. Peer-to-Peer Netw. Appl. 8, 447–458 (2015). https://doi.org/10.1007/s12083-014-0267-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12083-014-0267-1

Keywords

Search

Navigation