階層式結構化點對點覆蓋網路之研究

A Study on Hierarchical Structured Peer to Peer Overlay Networks

李飛鴻(Fei-Hung Li)

指導教授 ： 周信宏

長榮大學/資訊暨工程學院/資訊管理研究所/碩士(2008年)

https://doi.org/10.6833/CJCU.2008.00090

摘要

近年來由於網路頻寬的提升，吸引學術界與企業對於點對點系統進行探討，因此如何建構一個具有高效率的點對點系統成為熱門的討論議題。根據點對點網路覆蓋結構的分類，早期是以非結構化為主，節點與節點之間互相連接但無特定的連線方式，搜尋檔案是採用洪流的方式，搜尋效率不佳並且浪費大量的網路頻寬。於是學界引進連結網路拓樸結構，提出具有特定連線方式的點對點系統，稱為結構化點對點系統，著名的結構化點對點系統有CAN、Chord、Pastry、Tapestry、Viceroy、Cycloid…等。結構化點對點系統大都利用DHT技術將資料散佈到節點中，獲得良好的網路擴展性和搜尋繞徑效率的提升。除了採用結構化拓樸，另外還有使用階層分群的方式縮短繞徑長度，稱之為階層式點對點系統。
本論文中，我們對於結構化點對點系統的拓樸結構進行整理與比較。另外，我們也提出一種以立方體互連圖、折疊超立方體和完整二元樹為主要架構的常數分支度階層式結構化點對點系統，CHS系統。與其它結構化系統比較，當節點數為n，CHS系統具有相同的平均繞徑長度O(log n)，僅需維護常數個數鄰居節點，並且擁有較佳的容錯性。

關鍵字

結構化點對點系統 ； 立方體互連圖 ； 折疊超立方體 ； 完整二元樹

並列摘要

Due to the upgrade of Internet bandwidth in recent years, P2P systems have attracted increasing attention from researchers and enterprises. How to construct efficient P2P systems has become an popular research issue. According to a classification on the structures of P2P overlay networks, the early network structures were unstructured in which peers were randomly connected and a flooding mechanism was used to send queries across the overlay network. They were inefficient and consumed a large part of Internet bandwidth. Therefore, the researchers renovated the interconnected network architecture with a kind of P2P overlay network, in which peers are connected in a specific graph topology, also known as structured P2P system, notably including CAN, Chord, Pastry, Tapestry, Viceroy, Cycloid, etc. Most structured P2P systems utilize DHT technology to map data items onto the nodes for enhancing the scalability and efficiency of routing. In addition to applying the structured topology, hierarchical clustering is another way to shorten the routing path length, named hierarchical P2P systems.
In this study, we surveyed and compared the structured and hierarchical P2P systems. Moreover, we proposed a constant-degree hierarchical structured P2P architecture, called CHS, which was built based on a Cube-Connected-Cycle graph, a folded hypercube and a complete binary tree. Comparing with other constant-degree P2P systems, in a CHS with n nodes, it requires the same O(log n) hops per lookup, only maintains O(1) neighbors per node, and offers a better fault tolerance.

並列關鍵字

Structured P2P System ； Cube-Connected-Cycle ； Folded Hypercube ； Complete Binary Tree

參考文獻

[2] I. Gupta, K. Birman, P. Linga, A. Demers, and R. V. Renesse, “Kelips: building an efficient and stable P2P DHT through increased memory and background overhead”, Proc. of the 2 ndInternational Workshop on Peer-to-Peer Systems (IPTPS’03), 2003.

[9] X. Li and J. Wu. Searching techniques in peer-to-peer networks. In J. Wu, editor, Handbook of Theoretical and Algorithmic Aspects of Ad Hoc, Sensor, and Peer-to-Peer Networks. Auerbach, New York,USA, 2006.

[11] M. Ripeanu, , “Peer-to-Peer Architecture Case Study : Gnutalla Network”, In Peer-to-Peer Computing Proceeding, Pages: 99-100, 2001.

[13] A. Rowstron and P. Druschel, “Pastry: Scalable, Distributed Object Location and Routing for Large-scale Peer-to-peer Systems,”Proc. Middleware, 2001.

[14] H. Shen, C.-Z. Xu, and G. Chen, “Cycloid: a constant-degree and lookup-efficient P2P overlay network”, Proc. of the 18thIEEE International Parallel & Distributed Processing Symposium (IPDPS’04), 2004.