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 Elsevier B.V. All rights reserved.

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

GRIBAUDO, MARCO;
2005

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 Elsevier B.V. All rights reserved.
Analytical modeling; Generalized random graphs; Generating functions; Peer-to-peer; Search strategies; Computer Networks and Communications; Software; Modeling and Simulation; Statistics and Probability
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/11311/1005039
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 29
  • ???jsp.display-item.citation.isi??? 23
social impact