淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


  查詢圖書館館藏目錄
系統識別號 U0002-2007200720135500
中文論文名稱 同儕網路中一種使用最小生成樹拓樸的搜尋機制
英文論文名稱 A Search Mechanism of Building a Minimum Cost Spanning Tree on Peer-to-Peer Network
校院名稱 淡江大學
系所名稱(中) 資訊工程學系碩士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 95
學期 2
出版年 96
研究生中文姓名 李裕民
研究生英文姓名 U-Ming Li
電子信箱 694192450@s94.tku.edu.tw
學號 694192450
學位類別 碩士
語文別 中文
口試日期 2007-06-20
論文頁數 62頁
口試委員 指導教授-陳瑞發
委員-林偉川
委員-王英宏
中文關鍵字 同儕網路  覆蓋拓樸  分散式方法  Sollin演算法  最小生成樹 
英文關鍵字 Peer-to-Peer (P2P)  Overlay Topology  Distributed Approach  Sollin Algorithm  Minimum Cost Spanning Tree (MST) 
學科別分類 學科別應用科學資訊工程
中文摘要 在非結構化的peer-to-peer系統中,大部分最被普遍使用的搜尋機制為Gnutella的blind flooding。在此機制中,節點將所收到的詢問訊息透過廣播的方式傳遞給其他logic neighbor。此詢問方式簡單,容易達成。然而,在搜尋過程中卻造成了大量不必要的流量以及節點收到多餘訊息等問題。
  Li Xiao等學者在2005年提出Adaptive Connection Establish (ACE) 方法透過建構最小生成樹的overlay topology來增進搜尋的效率。ACE減少了傳遞訊息的流量而節點間亦不會收到多餘訊息,然而為了達到較好的效能,ACE需要大量額外的資訊交換以及龐大的運算量,因此造成節點相當大的負擔。
  本論文提出了一個以Sollin演算法概念為基礎的方法來建構最小生成樹的overlay topology。透過本論文提及的演算法,每個節點只須針對logic neighbor進行資訊的交換和運算,而不須考慮logic neighbor以外的節點,因此可以大幅降低ACE中節點建構最小生成樹的負擔也使其能以較快的速度建構一個peer-to-peer環境下的最小生成樹overlay topology。
英文摘要 In unstructured P2P system, the most popular search mechanism being used is blind flooding of Gnutella. In this mechanism, nodes receive query messages and forward to other logic neighbor by broadcasting. This method is simple and easy to implement. However, there is a large amount of unnecessary traffic and will receive a lot of redundant messages in search process.
In 2005, Li Xiao and other scholars propose the Adaptive Connection Establishment (ACE) to improve the search performance by building a Minimum Cost Spanning Tree (MST) in overlay network. ACE reduces the traffic cost and the nodes do not receive duplicate messages. However, to get a good performance, ACE needs a large amount of extra information exchanging and mass computation. Thus, ACE will has a high overhead on nodes.
In this thesis, we propose an approach based on the concept of Sollin algorithm to build a MST in overlay network. By this approach, each node simply exchanges information and computes with all of its logic neighbors instead of considering other nodes. Thus, this approach can reduce the overhead of ACE significantly and build a MST more instantly.
論文目次 第一章 緒論……………………………………1
1.1 研究動機…………………………………………………………1
1.2 研究目的…………………………………………………………2
1.3 研究方法…………………………………………………………2
1.4 論文架構…………………………………………………………3
第二章 相關研究……………………………………4
2.1 Sollin演算法……………………………………………4
2.2 Blind Flooding…………………………………………5
2.3 Depth-First Search (DFS)……………………………………6
2.4 K-Walker.…………………………………………………………7
2.5 Adaptive Connection Establishment (ACE)………7
2.5.1 Flooding所造成的不必要流量………………………8
2.5.2 Topology Mismatch問題……………………………9
2.5.3 ACE方法步驟和內容………………………………10
2.5.4 最佳化深度……………………………………………13
第三章 Grouping演算法及其搜尋機制…………………………18
3.1 Grouping演算法基本概念……………………………………18
3.1.1 Phase 1:節點的訊息交換…………………………………19
3.1.2 Phase 2:節點的Group Expansin…………………………20
3.2 Grouping演算法………………………………………………30
3.2.1 Grouping演算法參數定義與前置動作……………………30
3.2.2 Grouping演算法內容………………………………………31
3.3 Grouping演算法及其收尋機制的範例………………………32
3.3.1 範例前提假設以及預先準備………………………………32
3.3.2 演算法第一回合……………………………………………34
3.3.3 演算法第二回合……………………………………………38
第四章 演算法效能分析與比較……………………………………42
4.1 分析前提假設………………………………………………42
4.2 時間複雜度分析……………………………………………42
4.3 封包量的分析………………………………………………44
4.4 Grouping演算法與ACE的比較……………………………46
第五章 結論…………………………………………………48
5.1 評估與討論………………………………………………48
5.2 未來發展方向……………………………………………49
參考文獻……………………………………………………………51
附錄—英文論文…………………………………………………53

圖目錄
圖2.1 Sollin演算法範例 ………………………………………5
圖2.2 一個P2P overlay topology………………………8
圖2.3 Topology mismatch問題………………………………9
圖2.4 Underlying physical overlay………………………10
圖2.5 S節點經由和節點E,F,G交換NCT資訊後獲得邏輯鏈結
的cost資訊………………………………………11
圖2.6 S節點所建構的最小生成樹overlay topology………12
圖2.7 節點以blind flooding方式傳遞訊息…………………12
圖2.8 節點以最小生成樹的邏輯鏈結傳傳遞詢問訊息………13
圖2.9 在 1-neighbor closure 下各節點所建構的最小生成
樹overlay topology………………………15
圖2.10 在2-neighbor closure下各節點所建構的最小生成樹和
傳遞詢問訊息的情形……………………………………16
圖3.1 節點間的訊息交換………………………………………20
圖3.2 i節點的NCT中neighbor cost值最小的neighbor為jx…21
圖3.3 i節點Case1的處理結果………………………21
圖3.4 i節點的NCT中neighbor cost值最小的neighbor為jx…22
圖3.5 i節點Case2的處理結果………………………23
圖3.6 jx節點的NCT中neighbor cost值最小的neighbor為iy…24
圖3.7 iy節點Case3的處理結果………………………………24
圖3.8 jx節點的NCT中neighbor cost值最小的neighbor為iy…25
圖3.9 iy節點Case4的處理結果………………………26
圖3.10 iy節點NCT中neighbor cost 值最小的logic
neighbor不為jx節點,而jx節點NCT中neighbor
cost值最小的logic neighbor亦不為iy………27
圖3.11 iy節點Case5的處理結果……………………………27
圖3.12 iy節點NCT中neighbor cost值最小的logic neighbor不
為jx節點,而jx節點NCT中neighbor cost值最小的
logic neighbor亦不為iy………………………28
圖3.13 iy節點Case6的處理結果………………………29
圖3.14 overlay topology……………………………32
圖3.15 A節點探測其週遭所有的logic neighbor和自己之間
的cost值………………………………………33
圖3.16 圖左為A節點的overlay topology圖右為其相對應的
NCT…………………………………………………33
圖3.17 A節點第一回合中傳遞和接收訊息的情形…………35
圖3.18 A節點針對其NCT中箭頭所指的最小值對象E進行判斷…35
圖3.19 A節點針對E進行判斷後所得之結果………………36
圖3.20 A節點針對B進行判斷………………36
圖3.21 A節點針對B進行判斷後所得之結果………………37
圖3.22 A節點針對C進行判斷………………37
圖3.23 A節點針對C進行判斷後所得之結果………………37
圖3.24 A節點針對D進行判斷………………38
圖3.25 A節點針對D進行判斷後所得之結果………………38
圖3.26 A節點第二回合中傳遞和接收訊息的情形………………40
圖3.27 A節點針對C進行判斷………………40
圖3.28 A節點針對C進行判斷後所得之結果………………40
圖3.29 A節點針對D進行判斷………………41
圖3.30 A節點針對D進行判斷後所得之結果………………41
圖3.31 所有節點執行完Grouping演算法所得之結果……41
圖5.1 原始的overlary topo;ogy 50
圖5.2 粗實線為query flooding path 50

表目錄
表1 在1-neighbor closure下詢問訊息的傳遞路徑和其所花費
流量………………………………………………16
表2 在 2-neighbor closure 下詢問訊息的傳遞路徑和其所花費
的流量………………………………………………17
表3 Grouping演算法參數定義與先置動作………………30
表4 Grouping演算法內容………………………………31
表5 最佳狀況的Grouping演算法時間複雜度分析………………43
表6 最差狀況的Grouping演算法時間複雜度分析………………44
表7 Grouping演算法最佳與最差情況下的封包量分析……………45
表8 Grouping演算法和ACE的時間複雜度比較………………46
表9 Grouping演算法和ACE的時間複雜度比較………………47



參考文獻 [Aho 83] Alfred V. Aho, Jeffrey D. Ullman , John E. Hopcroft, Data Structures and Algorithms, Addison Wesley,1983.

[Cormen 90] Thomas H. Cormen, Charles E.Leiserson, Ronald L.Rivest, Introduce to Algorithms, The MIT Press, 1990.

[eDonkey 03] Available:http://www.edonkey2000.com, 2003.

[eMule 02] Available:http://www.emule-project.net/home/perl/general.cgi?
1=16, 2002.

[Freenet 03]
Available:http://freenet.sourceforge.net, 2003.

[Gnutella 00]
Available:http://gnutella.wego.com, 2000.

[KaZaA 03]
Available:http://www.kazaa.com, 2003.

[Liu 03]
Yunhao Liu, Zhenyun Zhuang, Li Xiao and Lionel M. Ni, “ AOTO : Adaptive Overlay Topology Optimization in Unstructured P2P Systems,” IEEE GLOBECOM, 2003, pp4186-4190.

[Liu 04]
Yunhao Liu, Li Xiao, Lionel M. Ni and Yunhuai Liu, “ Building Efficient Overlays,” Springer, vol.2, 2004, pp183-192.

[Lv 02]
Q. Lv, et al., “Search and replication in unstructured peer-to-peer
networks , ” In Proc.16th , ACM International Conference on Supercomputing, 2002, pp84-95.

[Morpheus 02]
Available:http://www.musiccity.com, 2002.

[Napster 03]
Available:http://www.napster.com, 2003.

[Sen 02]
Subhabrata Sen, Member, IEEE, and Jia Wang, Member, IEEE, “Analyzing peer-to-peer traffic across large networks ,” IEEE/ACM Trans. on Networking, vol.12, 2004, pp219-232.

[Xiao 05]
Li Xiao, Member, IEEE, Yunhao Liu, Member, IEEE, and Lionel M. Ni , Fellow , IEEE, “Improving Unstructured Peer-to- Peer Systems by Adaptive Connection Establishment,” IEEE Trans. on Computer , vol.54, 2005, pp1091-1103.

[Zhuang 03]
Zhenyun Zhuang, Yunhao Liu, Li Xiao and Lionel M. Ni, “ Hybrid Periodical Flooding in Unstructured Peer-to-Peer Networks,” Proc.of the 2003 International Conference on Parallel Processing, 2003, pp171-178.















論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2012-07-31公開。
  • 不同意授權瀏覽/列印電子全文服務。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信