This paper presents an analytical framework to study search strategies in large-scale decentralized unstructured peer-to-peer (P2P) networks. The peers comprising the P2P network and their application-level connections are modeled as generalized random graphs (GRGs) whose simple and efficient analysis is accomplished using the generating function of the graph’s degree distribution. The framework we defined allows the computation of several interesting performance indexes to be used to compare different search strategies: in particular, the average number of messages sent throughout the P2P network and the probability that a query is successful are used as examples. Furthermore, assuming that the cumulative distribution function (CDF) of the time required by a peer to positively reply to a query is known, we show how to derive the CDF of the time it takes for a randomly chosen peer to obtain at least one positive reply from other peers. The approach is validated through simulation showing that the accuracy of the proposed model improves as the size of the P2P network increases making it a suitable tool for the analysis of search strategies in large-scale systems.

A simple analytical framework to analyze search strategies in large-scale peer-to-peer networks

GAETA, Rossano;BALBO, Gianfranco;SERENO, Matteo
2005-01-01

Abstract

This paper presents an analytical framework to study search strategies in large-scale decentralized unstructured peer-to-peer (P2P) networks. The peers comprising the P2P network and their application-level connections are modeled as generalized random graphs (GRGs) whose simple and efficient analysis is accomplished using the generating function of the graph’s degree distribution. The framework we defined allows the computation of several interesting performance indexes to be used to compare different search strategies: in particular, the average number of messages sent throughout the P2P network and the probability that a query is successful are used as examples. Furthermore, assuming that the cumulative distribution function (CDF) of the time required by a peer to positively reply to a query is known, we show how to derive the CDF of the time it takes for a randomly chosen peer to obtain at least one positive reply from other peers. The approach is validated through simulation showing that the accuracy of the proposed model improves as the size of the P2P network increases making it a suitable tool for the analysis of search strategies in large-scale systems.
2005
The 24th International Symposium on Computer Performance, Modeling, Measurements and Evaluation (Performance 2005)
Juan-les-Pins (Francia)
October 3-7, 2005
Volume 62 , Issue 1-4 (October 2005)
1
16
Analytical modeling; Peer-to-peer; Generalized random graphs; Search strategies; Generating functions
R. GAETA; G. BALBO; S. C. BRUELL; M. GRIBAUDO; M. SERENO
File in questo prodotto:
File Dimensione Formato  
Analytic-2005.pdf

Accesso riservato

Tipo di file: POSTPRINT (VERSIONE FINALE DELL’AUTORE)
Dimensione 364.45 kB
Formato Adobe PDF
364.45 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/43252
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 29
  • ???jsp.display-item.citation.isi??? 23
social impact