臺灣博碩士論文加值系統

近年來，由於P2P對等式資源分享系統的便利與普及，使得運用此類軟體搜尋與下載其他使用者所分享的數位文件與資源已成為網際網路Web 2.0時代中最顯著的主流文化。然而，隨著P2P系統架構從集中目錄式演進至分散目錄式，搜尋時間與系統資源的耗費也隨之劇增。目前的非結構化分散式P2P對等式資源分享系統皆採取被動式搜尋機制，每次查詢必須搜遍大半的電腦主機後，才能找到目標檔案，不僅搜尋時間過長，也耗費大量的網路頻寬。為了解決這些效能問題，本研究結合傳播領域的創新擴散理論、Web 2.0的使用者自訂類別、標籤等概念，提出主動擴散式點對點搜尋演算法（ADP）。透過網路導向式電腦模擬實驗，發現在各種理論的複雜網絡中，主動擴散式點對點搜尋法在不同的網路規模下依舊保持著高效率的搜尋效能穩定性。並在搜尋時間與搜尋過程耗費的網路頻寬明顯優於過去數種主流的非結構化分散式被動搜尋機制。最後，本研究基於過去文獻尚未考量的搜尋公平性議題，透過網路節點間訊息處理量的差異，證明主動擴散式點對點搜尋法擁有極佳的搜尋公平性。

In recent year, because it becomes more and more convenience and common in Peer-to-Peer file sharing Systems, using this kind of software to search and download other users’ digital files has become the most popular culture in the period of Web 2.0 now. However, the search time and cost are increasing strongly along with the Peer-to-Peer file sharing systems transformed from centralize directory to decentralize directory. The previously search algorithms in Unstructured Peer-to-Peer file sharing Systems are all using passive search machine, and it often find the objective peers when it search the mostly hops in the network. It must wastes lots of not only search time but also network bandwidth cost. For solving this kind of problems, we propose Active Diffusion Peer-to-Peer Search Algorithm (ADP) which combined the diffusion of innovations in communication studies field and the concept of user tag defined in Web 2.0. From the network simulation experiment, we found that ADP has kept highly search stably when the network scale has variously changed in all kinds of theoretic complex networks, and had better search performance than the passive search algorithms. Finally, this paper based on the search fair issue which others didn’t consider to prove the highly search fair of ADP by the different numbers of message computing between network peers.

論文目錄
指導教授推薦書
口試委員會審定書
授權書
誌謝 v
中文摘要vi
英文摘要 vii
目錄viii
表目錄 xi
圖目錄 xii
第一章 序論 1
1.1 研究動機 1
1.2 問題描述 3
1.3 研究目標 6
1.4 論文結構 8
第二章 相關理論及文獻探討 9
2.1相關理論 9
2.1.1網路拓樸特性 9
2.1.2隨機網路 12
2.1.3無尺度網路 13
2.1.4小世界網路 14
2.2非結構化分散式P2P對等資源搜尋演算法 16
2.2.1廣播搜尋法 16
2.2.2隨機遊走搜尋法 18
2.2.3最大度搜尋法 19
2.2.4拓展環 20
2.2.5 K個散步者隨機遊走 21
2.2.6區域性廣播的短距離隨機搜尋法 23
2.2.7對等式系統中基於興趣的有效率之文件定址法 24
2.3創新的擴散 26
2.4研究定位與探討 28
第三章 搜尋架構 29
3.1基本架構及功能說明 29
3.2主動擴散式點對點資源搜尋演算法執行流程 31
3.2.1基本參數設定 31
3.2.2資訊同步演算法 33
3.2.3資訊清單替換策略 38
3.2.4強化式廣播搜尋演算法 39
3.3設計理念與特色 41
3.4搜尋效能的時間複雜度計算 45
第四章 實驗設計與結果分析 50
4.1實驗設計 50
4.1.1實驗環境 50
4.1.2模擬方式 51
4.1.3效能評估指標 52
4.1.4實驗目的與相關參數設定 54
4.2實驗流程 57
4.2.1整體模擬流程 57
4.2.2資訊同步模擬流程 62
4.2.3強化式廣播搜尋法模擬流程 63
4.3實驗結果分析 64
4.3.1拓樸特性、可接受率對資訊擴散及搜尋效率的影響性分析 64
4.3.2網路規模變動對資訊擴散與搜尋效率的影響性分析 70
4.3.3效能評估與公平性比較分析 84
4.4各種搜尋法之綜合比較 94
第五章 結論 95
5.1研究結論 95
5.2研究限制 97
5.3未來展望 98
參考文獻 99
附錄 102


表目錄
表格1：集中式與分散式擴散系統的特性比較表 27
表格2：初始設定演算法之虛擬碼 32
表格3：資訊同步傳送端演算法之虛擬碼 34
表格4：資訊同步接收端演算法之虛擬碼 36
表格5：強化式廣播搜尋演算法之虛擬碼 39
表格6：搜尋效能計算之各種相關變數設定表 45
表格7：各種搜尋法之搜尋效能時間複雜度比較表 49
表格8：複雜網路拓樸特性比較表 51
表格9：擴散模擬實驗的網路規模設定表 55
表格10：效能評估及公平性比較模擬實驗的網路規模設定表 56
表格11：在不同節點數下之隨機網路的擴散曲線檢定表 72
表格12：在不同節點數下之隨機網路的搜尋曲線檢定表 73
表格13：在不同分支度下之隨機網路的擴散曲線檢定表 74
表格14：在不同分支度下之隨機網路的擴散曲線檢定表 74
表格15：在不同節點數下之無尺度網路的擴散曲線檢定表 76
表格16：在不同節點數下之無尺度網路的搜尋曲線檢定表 77
表格17：在不同分支度下之無尺度網路的擴散曲線檢定表 78
表格18：在不同分支度下之無尺度網路的搜尋曲線檢定表 79
表格19：在不同節點數下之小世界網路的擴散曲線檢定表 80
表格20：在不同節點數下之小世界網路的搜尋曲線檢定表 81
表格21：在不同分支度下之小世界網路的擴散曲線檢定表 83
表格22：在不同分支度下之小世界網路的搜尋曲線檢定表 83
表格23：以系統導向的觀點之搜尋效能比較表 94
表格24：以使用者導向的觀點之搜尋效能比較表 94

圖目錄
圖表1：小世界模型建構圖 15
圖表2：加入捷徑的Gnutella概念圖 25
圖表3：捷徑選擇圖 25
圖表4：各種分散式非結構化P2P對等網路的搜尋法之領域界定 28
圖表5：資訊同步傳送端與接收端資訊傳輸示意圖 33
圖表6：資訊同步傳送端演算法執行流程圖 35
圖表7：資訊同步接收端演算法執行流程圖 37
圖表8：強化式廣播搜尋演算法的執行流程圖 40
圖表9：廣播搜尋法查詢訊息傳遞示意圖 41
圖表10：主動式檔案資訊擴散搜尋模式示意圖 42
圖表11：過去被動式搜尋機制的模擬流程圖 58
圖表12：主動擴散式搜尋機制的模擬流程圖 61
圖表13：資訊同步模擬流程圖 62
圖表14：強化式廣播搜尋法模擬流程圖 63
圖表15：各種網路下的搜尋效能曲線圖 65
圖表16：隨機網路在不同可接受率下的搜尋效能比較圖 67
圖表17：無尺度網路在不同可接受率下的搜尋效能比較圖 68
圖表18：小世界網路在不同可接受率下的搜尋效能比較圖 68
圖表19：造訪低於總節點數0.1%的擴散時間點與累積成本統計圖 70
圖表20：不同節點數下之隨機網路的搜尋效能統計圖 72
圖表21：不同分支度下之隨機網路的搜尋效能統計圖 74
圖表22：不同節點數下之無尺度網路的搜尋效能統計圖 76
圖表23：不同分支度下之無尺度網路的搜尋效能統計圖 78
圖表24：不同節點數下之小世界網路的搜尋效能統計圖 80
圖表25：不同分支度下之小世界網路的搜尋效能統計圖 82
圖表26：隨機網路下搜尋效能比較圖 86
圖表27：隨機網路下累積成本比較圖 87
圖表28：隨機網路下公平性比較圖 87
圖表29：無尺度網路下搜尋效能比較圖 89
圖表30：無尺度網路下累積成本比較圖 90
圖表31：無尺度網路下公平性比較圖 90
圖表32：小世界網路下搜尋效能比較圖 92
圖表33：小世界網路下累積成本比較圖 93
圖表34：小世界網路下公平性比較圖 93

參考文獻
[1] Gallagher, D., & Wilkerson, R. (2001). Network performance statistics for university of south carolina. from http://eddie.csd.sc.edu.
[2] Plonka, D. (2000). Uw-madison napster traffic measurement. from http://net.doit.wisc.edu/data/Napster.
[3] Cohen, B. (2003). Incentives Build Robustness in BitTorrent. Workshop on Economics of Peer-to-Peer Systems, 6.
[4] Napster. from http://www.napster.com.
[5] Lv, Q., Cao, P., Cohen, E., Li, K., & Shenker, S. (2002). Search and replication in unstructured peer-to-peer networks. Proceedings of the 16th international conference on Supercomputing, 84-95.
[6] Adar, E., & Huberman, B. A. (2000). Free Riding on Gnutella. First Monday, 5(10), 2.
http://firstmonday.org/issues/issue5_10/adar/index.html.
[7] Ratnasamy, S., Francis, P., Handley, M., Karp, R., & Schenker, S. (2001). A scalable content-addressable network. Paper presented at the Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications.
[8] Stoica, I., Morris, R., Karger, D., Kaashoek, M. F., & Balakrishnan, H. (2001). Chord: A scalable peer-to-peer lookup service for internet applications. Proceedings of the 2001 SIGCOMM conference, 31(4), 149-160.

[9] Rowstron, A., & Druschel, P. (2001). Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility. Proceedings of the eighteenth ACM symposium on Operating systems principles, 188-201.
[10] Zhao, B. Y., Kubiatowicz, J., & Joseph, A. D. (2001). Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and Routing. Computer, 74.
[11] Gnutella. from http://gnutella.wego.com.
[12] Clip, D. S. S. (2000). Gnutella Protocol Specification v0. 4. http//www. clip2. com/GnutellaProtocol04. pdf
[13] Saroiu, S., Gummadi, P. K., & Gribble, S. D. (2002). A measurement study of peer-to-peer file sharing systems. Proceedings of Multimedia Computing and Networking, 2002.
[14] Ripeanu, M. (2001). Peer-to-Peer Architecture Case Study: Gnutella Network. Proceedings of International Conference on Peer-to-peer Computing, 101.
[15] Freenet. from http://freenet.sourceforge.net.
[16] Adamic, L. A., Lukose, R. M., & Huberman, B. A. (2002). Local Search in Unstructured Networks. Arxiv preprint cond-mat/0204181.
[17] Newman, M. E. J 2003 The structure and function of complex networks. SIAM Review, 45, 167-256
[18] Erdos, P., & Renyi, A. (1960). On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5, 17-61.
[19] Barabasi, A. L., & Albert, R. (1999). Emergence of Scaling in Random Networks. Science, 286(5439), 509.
[20] Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of small-world networks. Nature, 393(6684), 440-442.
[21] Iamnitchi, A., Ripeanu, M., & Foster, I. (2002). Locating data in (small-world) peer-to-peer scientific collaborations. 1st International Workshop on Peer-to-Peer Systems (IPTPS’02).
[22] Noh, J. D., & Rieger, H. (2004). Random Walks on Complex Networks. Physical Review Letters, 92(11), 118701.
[23] Hughes, B. D. (1995). Random walks and random environments: Oxford University Press New York.
[24] Yang, B., & Garcia-Molina, H. (2002). Improving search in peer-to-peer networks. Distributed Computing Systems, 2002. Proceedings. 22nd International Conference on, 5-14.
[25] Gkantsidis, C., Mihail, M., & Saberi, A. (2005). Hybrid search schemes for unstructured peer-to-peer networks. INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, 3.
[26] Rogers, E. M. (2003). Diffusion of Innovations. 5th: Simon and Schuster.
[27] Sripanidkulchai, K., Maggs, B., & Zhang, H. Efficient content location using interest-based locality in peer-to-peer systems. INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies. IEEE, 3.
[28] Zhu, Y., & Hu, Y. (2006). Enhancing Search Performance on Gnutella-Like P2P Systems. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 17(12), 1482-1495.