具侷限以以及資源相關性的覆蓋網路

Locality and Resource Aware Overlay Networks

巫駿宏(Chun-Hung Wu)

指導教授 ： 王勝德

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

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

摘要

近年來有很多研究想要改進點對點網路上面的覆蓋網路(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.

並列關鍵字

overlay network ； locality ； gorup ； node ； DHT

參考文獻

[1] B. Yang and H. Garcia-Molina, “Efficient Search in Peer-to-Peer Networks,” in Proc. Int. Conf. Distributed Computing Systems, 2002, pp. 5 – 15.

[2] Yunhao Liu, Zhenyun Zhuang, Li Xiao and Lionel M. Ni, “A Distributed Approach to Solving Overlay Mismatching Problem” in Proc. ICDCS Conf., 2004, pp. 132 – 139.

[3] Xin Yan Zhang, Qian Zhang, Zhensheng Zhang, Gang Song, and Wenwu Zhu, “A Construction of Locality-Aware Overlay Network: mOverlay and Its Performance,” IEEE JNL. Selected Areas in Communications, vol. 22, no. 1, Jan. 2004, pp. 18 – 28.

[4] Chi-Hong Chao,“AN INTEREST-BASED ARCHITECTURE FOR PEER-TO-PEER NETWORK SYSTEMS,” in Proc. Int. Conf. AINA, April. 2006.

[5] Shang-Feng Chiang, Chun-Hung Wu, and Sheng-De Wang , “Active Index Diffusion in Multilayer Unstructured Peer-to-Peer Networks,” in CTHPC Conf., 2007.