Optimal Resource Discovery Paths of Gnutella2
Authors:
- Mikko VapaMVMikko Vapa
- Annemari AuvinenAAAnnemari Auvinen
- Yevgeniy IvanchenkoYIYevgeniy Ivanchenko
- Niko KotilainenNKNiko Kotilainen
- Jarkko VuoriJVJarkko Vuori
- 1 January 2008
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 1550445X,p. 546-553
Abstract
This paper shows that the performance of peer-to-peer resource discovery algorithms is upper bounded by a k-Steiner minimum tree and proposes an algorithm locating near-optimal query paths for the peer-to-peer resource discovery problem. Global knowledge of the topology and the resources from the peer-to-peer network are required as an input to the algorithm. The algorithm provides an objective measure for defining how good local search algorithms are. The performance is evaluated in simulated peer-to-peer scenarios and in the measured Gnutella2 P2P network topology with four local search algorithms: breadth-first search, self-avoiding random walker, highest degree search and Dynamic Query Protocol.Keywords
This publication has 15 references indexed in Scilit:
- P2PRealm - Peer-to-Peer Network Simulator2006
- Routing indices for peer-to-peer systems2003
- Scalable P2P searchIEEE Internet Computing, 2003
- A local search mechanism for peer-to-peer networks2002
- Search and replication in unstructured peer-to-peer networks2002
- Path finding strategies in scale-free networksPhysical Review E, 2002
- The Steiner Tree Problem2002
- Approximate k-MSTs and k-Steiner Trees via the Primal-Dual Method and Lagrangean Relaxation2001
- Resource discovery in distributed networks1999
- A faster approximation algorithm for the Steiner problem in graphsInformation Processing Letters, 1988