王勝德臺灣大學：電機工程學研究所巫駿宏Wu, Chun-HungChun-HungWu2007-11-262018-07-062007-11-262018-07-062007http://ntur.lib.ntu.edu.tw//handle/246246/53318近年來有很多研究想要改進點對點網路上面的覆蓋網路(overlay network)架構，雖然結構式點對點網路系統採用分散式雜湊表(DHT)可以比非結構式點對點網路系統使用泛流的方式有效率，但是由於雜湊函數先天的方式，不適合用來提供關鍵字搜尋這項機制，因此我們的架構還是採用非結構式點對點網路系統。另外一方面，為了解決topology mismatch的問題，目前在建置覆蓋網路的時候，大部份的研究會考慮侷限性(locality)，我們把侷限性以及資源同時列入考慮。為了改進非結構式的點對點網路系統的搜尋效率，這邊同時利用檔案複製(Data Replication) 、選擇性傳送(Selective Search) 、叢集(Clustering)以及興趣群組(Interest Group)來改進系統效能。演算法分析說明了locating procedure的複雜度為 O(logN)，N為覆蓋網路中的節點個數。實驗結果可以證明在我們提出的LARO演算法會比mOverlay有更好的訊息花費以及搜尋命中率。P2P overlay architectures are gaining more and more attention. Structured P2P network systems that use Distributed Hashing Tables (DHTs) can be more efficient than flooding based unstructured P2P network systems. But DHTs did not suit for key word search, so we choose using unstructured P2P networks as our architecture. In order to solve the topology mismatch problem, many people take account of locality information when designing peer-to-peer overlay networks. Here, we not only exploit locality but also take resource features into account. Taking advantage of concepts of data replication, selective search, clustering, and interest group can improve the search performance of unstructured P2P networks. Our analysis shows that the overhead of locating procedure is O (log N), and N is the number of peers in the overlay network. Simulation proves that our algorithm is better than the mOverlay network in the number of messages per search and the hit ratio.第一章 緒論 1 1.1覆蓋網路(Overlay networks) 1 1.2 需要覆蓋網路的原因 3 1.3 在覆蓋網路中的Mismatch Problem 5 第二章 研究背景及相關研究 6 2.1 研究背景及相關研究 6 第三章 建立具侷限性以及資源相關性的覆蓋網路 9 3.1 基本概念 9 3.1.1 資源以及侷限性 9 3.1.2 兩層式的架構: 節點以及群組 10 3.1.3 混合式的架構: 檔案複製、選擇性的搜尋、叢集、以及興趣群組 11 3.2 Locating procedure 13 3.2.1 如何選取節點要加入的群組 13 3.2.2 演算法 14 第四章 基本的覆蓋網路運作 18 4.1加入到一個群組 18 4.2 形成一個新的群組 18 4.3 資訊的分享 19 第五章 搜尋方法 19 5.1 更改過的random walks 19 第六章 效能評估 20 6.1演算法分析 21 6.2效能分析 21 6.3覆蓋網路的強健度 23 6.4覆蓋網路的彈性度 24 第七章 模擬 25 7.1 檔案的分佈 25 7.2在不同檔案分佈下的模擬結果 26 7.2和亂數連接的覆蓋網路做比較 28 7.3和mOverlay做比較 29 第八章 結論 35462175 bytesapplication/pdfen-US覆蓋網路侷限性群組節點分散式雜湊表overlay networklocalitygorupnodeDHTthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53318/1/ntu-96-R94921109-1.pdf