Dynamic Search and Performance Analysis in Unstructured Peer-to-Peer Networks
Date Issued
2004
Date
2004
Author(s)
WANG, HSINPING
DOI
en-US
Abstract
In recent years, Peer-to-Peer networks (P2P) have gained great attention and popularity thanks to their flexibility and ease of use. However, one key challenging aspect in a P2P resource sharing environment is the scalability problem, which involves the design of efficient searching algorithms. This is especially important for Gnutella-like decentralized and unstructured networks since they have power-law degree distributions—highly connected networks that tend to generate graph redundancy. In this paper, we propose a dynamic search algorithm that decides the number of running walkers dynamically with respect to peers’ topological information and search time state. The dynamic search is able to control the extent of messages generating temporally by the simulated annealing mechanism, thus being a scalable search. Furthermore, we present a unified search performance metric, Search Efficiency, to objectively capture dynamic behavior of various search algorithms in terms of scalability, reliability and responsiveness. We quantitatively characterize, through mathematic analysis and simulations in realistic P2P environment, the performance of various existing searching algorithms with and without knowledge building mechanisms. The proposed dynamic search outperforms other search algorithms in terms of Search Efficiency in both local and long-term search spaces.
Subjects
系統模型
搜尋程序
效能分析
對等式網路
Peer-to-Peer
Metrics design
Simulated annealing
Gnutella
Performance evaluation
System modeling
Search process
Type
thesis