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

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.