林宗男臺灣大學：電信工程學研究所王欣平WANG, HSINPINGHSINPINGWANG2007-11-272018-07-052007-11-272018-07-052004http://ntur.lib.ntu.edu.tw//handle/246246/58571In 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.Chapter 1.........................................................1 Introduction....................................................................................................................................1 Chapter 2........................................................................................................................................5 Related Work.................................................................................................................................5 Chapter 3........................................................................................................................................7 Dynamic Search.............................................................................................................................7 3.1 Design Rationale.....................................................................................................7 3.2 Probability Model...................................................................................................8 3.3 Algorithm..............................................................................................................10 3.4 Operation...............................................................................................................11 3.5 Knowledge Based Dynamic Forwarding..............................................................14 Chapter 4......................................................................................................................................18 Dynamic P2P Modeling................................................................................................................18 4.1 Network Modeling................................................................................................18 4.2 Dynamic Peer Behavior Modeling........................................................................19 Chapter 5......................................................................................................................................22 A Unified Metric in Searching Networks: Search Efficiency......................................................22 5.1 Introduction...........................................................................................................22 5.2 Search Efficiency..................................................................................................25 5.3 STRICTLY BINARY TREE................................................................................30 5.4 POWER-LAW RANDOM GRAPH.....................................................................38 5.5 Dynamic Search....................................................................................................50 5.6 NON-UNIFORM OBJECT DISTRIBUTION.....................................................54 5.7 Conclusion............................................................................................................59 Chapter 6......................................................................................................................................60 Performance Evaluation................................................................................................................60 6.1 Search Evaluation without Knowledge.................................................................60 6.2 Search Evaluation with Knowledge Base.............................................................64 Chapter 7......................................................................................................................................69 Conclusion...................................................................................................................................69 Bibliography................................................................................................................................71 Appendix: Simulation Results......................................................................................................75en-US系統模型搜尋程序效能分析對等式網路Peer-to-PeerMetrics designSimulated annealingGnutellaPerformance evaluationSystem modelingSearch processthesis