Search and replication in unstructured peer-to-peer networks

Decentralized and unstructured peer-to-peer networks such as Gnutella are attractive for certain applications because they require no centralized directories and no precise con-trol over network topology or data placement. However, the ooding-based query algorithm used in Gnutella does not scale; each query generates a large amount of trac and large systems quickly become overwhelmed by the query-induced load. This paper explores, through simulation, var-ious alternatives to Gnutella's query algorithm, data repli-cation strategy, and network topology. We propose a query algorithm based on multiple random walks that resolves queries almost as quickly as Gnutella's ooding method while reducing the network trac by two orders of magnitude in many cases. We also present simulation results on a dis-tributed replication strategy proposed in [8]. Finally, we nd that among the various network topologies we consider, uniform random graphs yield the best performance