成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	陳炳誠 Chen, Ping-Cheng
論文名稱：	利用完全差距網路建構之拓樸提升P2P網路資源搜尋效率 Increase P2P Resource Search Efficiency by Topology Construction Using Perfect Difference Networks
指導教授：	李忠憲 Li, Jung-Shian
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 電腦與通信工程研究所 Institute of Computer & Communication Engineering
論文出版年：	2007
畢業學年度：	95
語文別：	中文
論文頁數：	50
中文關鍵詞：	點對點網路、類神經網路、完全差距網路、非結構化點對點網路、疊加網路
外文關鍵詞：	Perfect Difference Networks, unstructured P2P networks, Neural Networks, resource searching
相關次數：	點閱：139 下載：3
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

點對點網路系統是繼主從架構後新興的網路應用模式，在點對點網路中，使用者能同時扮演用戶端及伺服端等多重角色，任兩個使用者之間不需要透過伺服器而直接連結，進行有效率的資訊分享或內容交換。另外，由於使用者能自我組織並動態重組，使得點對點網路系統具有極高的擴充性與容錯性。此易於資源分享且分散式的系統本質，也引起學術界與產業界的重視。
查詢是點對點網路系統中，使用者搜尋網路資源最基本的核心功能，各節點以自我組織的方式形成疊加網路，利用類似廣播或路由的方式來進行查詢訊息的傳遞。目前使用最為廣泛的點對點網路系統是屬於非結構化的點對點網路系統，包括Gnutella、KaZaA、BitTorrent、eDonkey2000等應用系統。然而，在非結構化點對點網路系統中，存在著無法很有效率進行網路資源搜尋的問題。
因此，我們提出利用完全差距網路控制點對點網路系統拓樸的方法，並且提出一個基於類神經網路的搜尋方法，來改善非結構化點對點網路的搜尋效率，並且分析完全差距網路對於不同搜尋方法所產生的效能影響。

In recent years, peer-to-peer applications emerge as a new massively distributed computing system. Peers participating in the system can directly distribute tasks, exchange or share resources. There are currently several peer-to-peer systems in operation and many more are under development.
Resource searching has played an essential algorithm in this kind of network system. Unstructured P2P networks are the mostly popular in a variety of P2P network systems. However, it often suffers from resource searching inefficiency in an unstructured P2P network.
Therefore, we propose a topology control algorithm and novel searching method which is based on Neural Networks to improve the searching efficiency. We will also analyze the searching efficiency for different searching methods on the Perfect Difference Networks.

目錄
第一章  簡介	1
1.1  論文概要	1
1.2  論文動機	2
1.3  論文架構	2
第二章  相關研究	3
2.1  完全差距網路(Perfect Difference Networks)	3
2.1.1  循環差集(cyclic difference sets)	3
2.1.2  完全差集(perfect difference sets)	4
2.1.3  完全差距網路(perfect difference networks，PDN)	5
2.1.4  完全差距網路的特性	7
2.1.5  完全差距網路的廣播(the broadcasting in PDN)	7
2.2  P2P網路的概述	8
2.2.1  結構化P2P網路概述	9
2.2.2  非結構化P2P網路概述	9
2.2.3  結構化與非結構化P2P網路比較	9
2.3  非結構化P2P網路的搜尋方法	10
2.3.1  Gnutella(BFS) [19]	10
2.3.2  改良式的BFS(Modified-BFS) [20]	11
2.3.3  Random Walks [21]	12
2.3.4  APS (Adaptive Probabilistic Search) [22]	13
2.4  類神經網路	13
2.4.1  類神經網路簡介 [1]	13
2.4.2  感知機網路(Perceptron) [1]	15
第三章  系統描述	16
3.1  相關名詞與定義	16
3.1.1  網路直徑D(network diameter)	17
3.1.2  平均節點距離Δ(Average internode dis-tance)	17
3.1.3  分支度d(degree)	18
3.2  建立完全差距網路	18
3.3  節點加入與離開和搜尋方法的對應	21
3.3.1  節點加入	21
3.3.2  節點離開	22
3.3.3  討論節點加入或離開的影響	23
3.3.4  把不同的搜尋方法對應到完全差距網路	24
3.4  運用類神經網路進行搜尋	25
3.4.1  運作原理	25
3.4.2  演算法運作流程圖	26
第四章  實驗結果與分析討論	27
4.1  系統參數	27
4.2  模擬設定與網路模型	28
4.2.1  系統假設	28
4.3  搜尋結果的評估	29
4.4  網路為完整的完全差距網路的情況	30
4.5  網路為不完整的完全差距網路的情況	34
4.5.1  討論完全差距網路完整與否的影響	34
4.5.2  重新建置完全差距網路的影響	38
4.6  節點不斷離開的狀況	41
4.6.1  不做處理的狀況	41
4.6.2  重新安排拓樸的狀況	44
第五章  結論	48
參考資料	49

表目錄
表2-1 循環差集中的元素差	4
表2-2 Perfect Difference Sets of Orders Up to 16	5
表2-3 結構化與非結構化P2P網路的比較	10
表3-1 圖3-1中的節點間最短距離	17
表3-2 PDN的可能大小	19
表3-3 the table for recording the network member of tracker node	20
表3-4 節點所得到的搜尋鄰居列表	21
表4-1 模擬環境參數	27
表4-2 系統參數	29
表4-3 相關參數跟使用訊息數量的關係	30
表4-4 大小為91的完整的完全差距網路的模擬參數	30

圖目錄
圖2-1  的完全差距網路	6
圖2-2  的完全差距網路中節點0進行廣播	8
圖2-3 完全差距網路中節點 進行廣播	8
圖2-4 BFS的示意圖	11
圖2-5 Modified-BFS的示意圖	12
圖2-6 Random Walks的示意圖	12
圖2-7 類神經網路模型	15
圖2-8 感知機網路模型	15
圖3-1 說明網路參數的拓樸	16
圖3-2 新成員節點要加入網路的流程	19
圖3-3 完整的PDN示意圖	19
圖3-4 不完整的PDN示意圖	20
圖3-5 完整的PDN加上1個外插的節點示意圖	20
圖3-6 當節點離開時的狀況	22
圖3-7 不完整的完全差距網路加上若干外插在外面的節點	23
圖3-8 搜尋方法的運作	25
圖3-9 針對連結儲存的參數	26
圖3-10 搜尋機制的流程圖	26
圖4-1 建構完全差距網路與否對於找到檔案份數的影響	32
圖4-2 建構完全差距網路與否對於使用訊息數量的影響	32
圖4-3 建構完全差距網路與否對於搜尋效率的影響	33
圖4-4 建構完全差距網路與否對於搜尋成功率的影響	33
圖4-5 建構完全差距網路與否對於擊中數的影響	34
圖4-6 完全差距網路完整與否對於找到檔案份數的影響	36
圖4-7 完全差距網路完整與否對於使用訊息數量的影響	36
圖4-8 完全差距網路完整與否對於搜尋效率的影響	36
圖4-9 完全差距網路完整與否對於搜尋成功率的影響	37
圖4-10 完全差距網路完整與否對於擊中數的影響	37
圖4-11 重新建置完全差距網路對於找到檔案份數的影響	38
圖4-12 重新建置完全差距網路對於使用訊息數量的影響	39
圖4-13 重新建置完全差距網路對於搜尋效率的影響	39
圖4-14 重新建置完全差距網路對於搜尋成功率的影響	40
圖4-15 重新建置完全差距網路對於擊中數的影響	40
圖4-16 不同節點個數對於找到檔案份數的影響	42
圖4-17 不同節點個數對於使用訊息數量的影響	43
圖4-18 不同節點個數對於搜尋效率的影響	43
圖4-19 不同節點個數對於搜尋成功率的影響	43
圖4-20 不同節點個數對於擊中數的影響	44
圖4-21 重新安排拓樸對於找到檔案份數的影響	45
圖4-22 重新安排拓樸對於使用訊息數量的影響	45
圖4-23 重新安排拓樸對於搜尋效率的影響	46
圖4-24 重新安排拓樸對於搜尋成功率的影響	46
圖4-25 重新安排拓樸對於擊中數的影響	47
                                    

[1] 葉怡成，類神經網路模式應用與實作，儒林圖書有限公司，1994三版。

[2] B. Parhami and M. Rakov, “Perfect Difference Networks and Related Interconnection Structures for Parallel and Distributed Systems,” IEEE Trans. Parallel and Distrib-uted Systems, vol. 16, no. 8,pp. 714-724, Aug. 2005.

[3] B. Parhami and M. Rakov, “Performance, Algo-rithmic, and Robustness Attributes of Perfect Difference Net-works,” IEEE. Trans. Parallel and Distributed Systems, vol. 16, no. 8, pp. 725-736, 2005.

[4] N. Biggs, Algebraic Graph Theory. Cambridge Univ. Press, 1993.

[5] Leonard D. Baumert, “Cyclic Difference Sets”, Lecture Notes in Mathematics. Springer-Verlag, volume 182, 1971.

[6] T.P. Kirkman, “On the Perfect r-Partitions of ,” Trans. Historical Soc. of Lancashire and Cheshire, vol. 9, pp. 127-142, 1857.

[7] Guy, R. K., Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 118-121, 1994.

[8] I. Stoica, R. Morris et al., “Chord: A Scalable Peer-to-Peer Lookup Protocol for Internet Applications,” IEEE/ACM Trans. Net., vol. 11, no. 1, pp. 17–32, 2003.

[9] S. Ratnasamy et al., “A Scalable Content Addressable Network,” Proc. ACM SIGCOMM, pp. 161–72, 2001.

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

[11] B. Y. Zhao et al., “Tapestry: A Resilient Global-Scale Overlay for Service Deployment,” IEEE JSAC, vol. 22, no. 1, pp. 41-53, Jan. 2004.

[12] P. Maymounkov and D. Mazieres, “Kademlia: A Peer-to-Peer Information System Based on the XOR Metric,” Proc. IPTPS, Cambridge, MA, USA, pp. 53–65, Feb. 2002.

[13] Gnutella development forum, the Gnutella v0.6 protocol, available at http://groups.yahoo.com/group/the gdf/files/, 2001.

[14] Kazaa Media Desktop, available at http://www.kazaa.com/,2001.

[15] Bittorrent, available at http://bitconjurer.org/BitTorrent/, 2003.

[16] The Overnet File-sharing Network, available at http://www.overnet.com/, 2002.

[17] Overnet/edonkey2000, available at http://www. edonkey2000.com/, 2000.

[18] K Lua, J Crowcroft, M Pias, R Sharma, S Lim - Communications Surveys & Tutorials, IEEE, A survey and comparison of peer-to-peer overlay network schemes, 2005.

[19] Gnutella website: http://gnutella.wego.com.

[20] V. Kalogeraki, D. Gunopulos, and D. Zeinalipour-Yazti, “A Local Search Mechanism for Peer-to-Peer Networks”, In CIKM, 2002.

[21] C. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker. “Search and Replication in Unstructured Peer-to-Peer Networks.” In ICS, 2002.

[22] D. Tsoumakos and N. Roussopoulos. “Adaptive Probabilistic Search for Peer-to-Peer Networks. ”, 3rd IEEE Intl Conference on P2P Computing, 2003.

[23] L Mathy, N Blundell, V Roca, A El-Sayed,“Impact of simple cheating in application-level multicast”,INFOCOM 2004. vol.2 pp1318- 1328, 2005.

[24] M. Vapa, N. Kotilainen, A. Auvinen, H. Kainulainen, and J. Vuori., “Resource discovery in P2P networks using evolutionary neural networks”, AISTA 2004, November 2004.

[25] J. Chu, K. Labonte, and B. Levine. Availability and Locality Measurements of Peer-to-Peer File Systems. In SPIE, 2002.

校內：2008-08-24公開
校外：2008-08-24公開

簡易檢索 / 詳目顯示

相關論文