非結構化對等式網路之動態搜尋及效能評估

Dynamic Search and Performance Analysis in Unstructured Peer-to-Peer Networks

王欣平(HSINPING WANG)

指導教授 ： 林宗男

國立臺灣大學/電機資訊學院/電信工程學研究所/碩士(2004年)

https://doi.org/10.6342/NTU.2004.01263

摘要

無資料

關鍵字

系統模型 ； 搜尋程序 ； 效能分析 ； 對等式網路

並列摘要

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.

並列關鍵字

Peer-to-Peer ； Metrics design ； Simulated annealing ； Gnutella ； Performance evaluation ； System modeling ； Search process

參考文獻

[44] L. A. Adamic. The small world web. Proceedings of the 3rd European Conf. on Digital Libraries, volume 1696 of Lecture notes in Computer Science, pages 443-452. Springer, 1999. [45] M. Faloutsos, P. Faloutsos, and C. Faloutsos. On power-law relationships of the internet topology. SIGCOMM, 2001. [46] B. F. Cooper and H. Garcia-Molina. SIL: Modeling and measuring scalable peer-to-peer search networks. International Workshop on Databases, Information Systems and Peer-to-Peer Computing, Berlin, 2003. [47] W. Aiello, F. Chung, and L. Lu. A random graph model for massive graphs. Proceedings of the thirty-second annual ACM symposium on Theory of Computing, pages 171-180, 2000.

[1] Matei Ripeanu, Adriana Iamnitchi and Ian Foster. Mapping the Gnutella Network. IEEE Internet Computing, vol. 6, issue 1, Jan/Feb 2002, pp. 50-56. [2] K.Sripanidkulchai, The popularity of Gnutella Queries and its Implications on Scalability, white paper, Carnegie Mellon Univ. Pittsburgh, Feb. 2001. [3] D. Gallagher and R.Wilkerson. Network performance statistics for university of South Carolina. http://eddie.csd.sc.edu, Oct. 2001. [4] D. Plonka. Uw-madion napster traffic measurement. http://net.doit.wisc.edu/data/Napster, Mar. 2000. [5] FreeNet website. http://freenet.sourceforge.net. [6] Gnutella website. http://gnutella.wego.com. [7] Napster website. http://napster.com. [8] Morpheus website. http://www.morpheus-os.com. [9] L Kunwadee Sripanidkulchai. The popularity of gnutella queries and its implications on scalability. In O’Reilly’s www.openp2p.com, February 2001. [10] Q. Lv, P. Cao, E. Cohen, K. Li and S. Shenker. Search and replication in unstructured peer-to-peer networks. ICS, June 2002. [11] Beverly Yang and Hector Garcia-Molina. Improving Search in Peer-to-Peer Networks. ICDCS, 2002. [12] L. Adamic, R. Lukose, and B. Huberman. Local Search in Unstructured Networks. Handbook of Graphs and Networks: From the Genome to the Internet, S. Bornholdt and H.G. Schuster (eds.), Wiley-VCH, Berlin, 2002. [13] Clip2. Gnutella: To the bandwidth barrier and beyond. http://www.clip2.com/gnutella.html, 2000.