nach oben

Peer-to-Peer Networking and Applications

Erschienen in:

01.05.2015

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

verfasst von: Spiridoula V. Margariti, Vassilios V Dimakopoulos

Erschienen in: Peer-to-Peer Networking and Applications | Ausgabe 3/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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

Vorheriger Artikel Analysis of user’s behavior and resource characteristics for private trackers

Nächster Artikel Exploring the policy selection of the P2P VoD system: A simulation-based research

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

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

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

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

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

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

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 CrossRef

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

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 CrossRef

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 CrossRef

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

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–16CrossRef

12.

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

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

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 CrossRefMathSciNet

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

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

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

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 CrossRef

25.

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

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, USACrossRef

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 CrossRefMATH

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 CrossRef

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

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

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 CrossRef

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

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

Titel: On probabilistic flooding search over unstructured peer-to-peer networks
verfasst von: Spiridoula V. Margariti
Vassilios V Dimakopoulos
Publikationsdatum: 01.05.2015
Verlag: Springer US
Erschienen in: Peer-to-Peer Networking and Applications / Ausgabe 3/2015
Print ISSN: 1936-6442
Elektronische ISSN: 1936-6450
DOI: https://doi.org/10.1007/s12083-014-0267-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 3/2015

Analysis of user’s behavior and resource characteristics for private trackers

A comprehensive study of the resource discovery techniques in Peer-to-Peer networks

SBDP: Bandwidth prediction mechanism towards server demands in P2P-VoD system

Resource allocation in underprovisioned multioverlay peer-to-peer live video sharing services

A taxonomy of decentralized online social networks

A hierarchical HRRP(k) network and its application