This paper investigates the effect of the number of file replicas on search performance in unstructured peer-to-peer networks. We observe that for a search network with a random graph topology where file replicas are uniformly distributed, the hop distance to a replica of a file is logarithmic in the number of replicas. Using this observation we show that flooding-based search is optimized when the number of replicas is proportional to the file request rates. This replica distribution is also optimal for download time and since flooding has logarithmically better search time than random walk under its optimal replica distribution, we investigate the query-processing load using this distribution. Categories and Subject Descriptors C.4 [Performance of Systems]: Design studies Performance, Design. Peer-to-peer, Replication, Search Performance, Random Graphs, Unstructured Networks, Flooding, Optimal File Replication. In fully distributed unstructured peer-to-peer networks, the content index of a node is maintained only at that node and hence, a search for a file must probe individual peers to find the location of the file. Since these networks are usually very large and highly dynamic, each node only stores the addresses for a subset of peers and other nodes are reached via these neighbors. Given this search overlay network, in the absence of any information about the location of the queried object, the two main alternatives for search are flooding search and random walk search. As the name implies, in flooding search, the query is sent to all the neighbors and if they do not have the object they forward the query to all their neighbors and so on. In contrast, in random walk search, the querying node sends the query to one randomly selected neighbor and if that neighbor does not have the desired object, it will forward the query to one of its neighbors (selected randomly). The performance metrics for any search mechanism are the (average) search time, i.e. how long does it take to find a file, and the (average) query-processing load, i.e. the number of nodes that have to be queried per search. The performance depends on many factors including the search overlay network, the search mechanism and the number of available copies for the file being searched. In this paper, we restrict ourselves to search overlay networks that can be modeled as Erdos-Renyi random graphs, although the results are similar for a variety of other topologies [4] . We focus on the search time in flooding search and derive results on the effect of the number of replicas of a file on the search time for that file assuming that the file replicas are uniformly distributed over the entire network. The search time for a file is approximated by the hop distance to the replica of that file that is nearest to the node requesting the file. After finding the search time for a file under aforementioned assumptions, we explore the performance of controlled flooding search (flooding that terminates as soon as the first replica is found) and provide results on the optimal replica distribution, the average search distance and the query-processing load for this optimal replica distribution. Since this replica distribution also ensures fairness in download load distribution and minimizes the download time [3], we compare the query-processing load at this replica distribution to the optimal query-processing load. Finally, we compare the controlled flooding search and the random-walk search at the replica distributions that minimize their respective search times. We are interested in the shortest distance from a "querying" node (the node searching for a file) to a replica of the file measured in number of hops (i.e. the number of hops taken by a breadth-first search from the "querying" node). Let τ i (n i ) be the expected shortest distance from a querying node to a replica of file i when there are n i replicas of the file in the network and n i ≥ 1. We simulated a number of Erdos-Renyi random graph topologies with a varying number of nodes and varying per-node average degree. The results are shown in Figures 1 and 2 . As we can see, τ i (n i ), is negative-logarithmically related to n i /M, the fraction of nodes that have the file, independent of the total number of nodes and increasing the per-node average degree decreases the slope of the relation betweenτ i (n i ) and −ln(n i /M). Upon further investigation, we found this slope to be inversely proportional to the per-node average degree (see [4] ). Thus, we get: This can be analytically shown for finite n i with M → ∞ [4]. To investigate the search performance optima, we use the peer-topeer system model described earlier and add the following description. There are N unique files in the system, each with an associated request rate λ i for file i per node. Each file is assumed to be of equal size. Nodes have finite local storage space to store file replicas. The storage space at each node is assumed to be
We use the file replication distribution shown to be optimal for controlled flooding search in REF as our starting point as we seek a replication distribution to minimize the download time.
Analysis of search and replication in unstructured peer-to-peer networks
SIGMETRICS '05
Computer Science