6533b7d9fe1ef96bd126ca75

RESEARCH PRODUCT

Optimal Resource Discovery Paths of Gnutella2

M. VapaA. AuvinenY. IvanchenkoJ. VuoriNiko Kotilainen

subject

Theoretical computer sciencebusiness.industryComputer scienceNetwork topologyComputer Science::Digital LibrariesSteiner tree problemTree (graph theory)symbols.namesakeRandom walker algorithmSearch algorithmBounded functionsymbolsResource allocationLocal search (optimization)Gnutella2business

description

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.

yearjournalcountryeditionlanguage
2008-01-0122nd International Conference on Advanced Information Networking and Applications (aina 2008)
https://doi.org/10.1109/aina.2008.89