在非結構化的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.