在結構化點對點網路的架構中，對於已知檔案名稱的搜尋能提供快速搜尋，然而對於只知道部份關鍵字或相關名稱之查詢，僅能透過非結構化網路的洪流法方式。在目前眾多點對點的研究中，支援關鍵字查詢的結構化架構已經有相關方法的提出，但是這些方式需要事先建立欲提供哪些關鍵字的查詢，因此可能造成檔案存在而無法查詢到此檔案的所在位置。不僅如此，鄰近節點需要記錄這些資訊，因而造成額外的負擔。有鑑於在點對點中結構化和非結構化網路各自具有其最佳的搜尋方式，所以在本篇我們將提出以檔案╱服務分類的階層式重疊網路架構來建構出點對點的網路環境，利用群組的概念使大部份的查詢都座落在同一個重疊網路中，透過在DNS上加入DNS-Agent的方式，在每一個群組的類別中扮演SuperPeer的角色，來輔助一般節點進行群組類別之外的外部查詢，而在內部查詢中，則是利用可變動式重疊網路來建構單一類別，不論使用者是否知道其完整的檔案名稱，在我們的方法中都能夠達到快速搜尋之目的。在此架構下，除了已知檔案名稱能提供快速的搜尋外，在僅知部份關鍵字或相關類別之搜尋更能優於傳統洪流法的搜尋速度，並且也不需額外定義欲提供查詢的關鍵字，因此提高搜尋的成功率。最後經由實驗的驗證，我們可以發現在整體搜尋的速度上，不僅較結構化和非結構化還來的快速，對於一般使用者通常會抓取目前已有的相關或相似類型之檔案，能提供更快速的搜尋。此外，在整個網路間的節點詢問封包的傳送、維護封包的傳送都較結構化點對點網路有明顯的降低，最後我們再模擬網路中不同的節點錯誤率，實驗顯示不論是在何種錯誤率的情況下，我們的方法也都較結構化點對點網路來得有效率。

The most significant challenge in designing a P2P file sharing system is providing a keyword search mechanism that allows users to efficiently locate desired files with short duration. DHT-based systems are highly scalable for locating data items with unique item identifier; however, DHTs do not support keyword search. While unstructured P2P systems like Gnutella are flexible enough to support keyword search, however, this system achieve poor scalability due to query flooding. As described above, structured and unstructured P2P networks are lack with the ability to achieve both scalability and keyword search capability simultaneously. In this paper, we proposed a Hierarchical Resource Classification Overlay Networks (HRCON) on top of DHT where each overlay is responsible for particular category of files. In our scheme, when a peer need a file that type related to belonging group, desired files could be obtained from the peers inside the group, which are topologically close. Clearly, content caching inside groups can further increase the efficiency of peer to peer communications by reduce the number of messages that need to get out of the group. Since there are often a large number of possibilities in keyword search, HRCON can greatly increase the performance by narrowed down the searching area.

摘要………………………………….…………………………………………III
ABSTRACT……………………………………………..……………………...V
第一章 緒論………………………….………..……………….……..….…..1
1.1　P2P系統概述………………………………………………………….…..2
1.1.1　系統定義………………………..…….………………………..………..2
1.1.2　P2P系統的特性………………………………...……………..………...5
1.1.3　P2P系統的分類……………………………...…………………..…….17
1.1.4　P2P系統的發展…………………………...………………….………..20
1.2　分散式雜湊表與P2P系統的關係………………………………….……24
1.2.1　分散式雜湊表的介紹和技術原理…………………………….…….24
1.2.2　以分散式雜湊表為基礎的P2P系統……………….………………….28
1.2.3　DHT P2P系統的特性………………………………………………….29
1.3　本研究的介紹…………………………...……………………………….30
1.3.1　研究動機以及問題描述……………….………………………………30
1.3.2　主要的研究內容以及貢獻………………...…………………………..31
1.4　章節簡介……………………………………………………………….34
第二章　相關研究………………………………………………………..…36
2.1　DNS跟階層式P2P的相關研究………………………………….….…..36
2.1.1　DNS的簡介……………………...…………………………….……….36
2.1.2　階層式P2P系統的相關研究…………………………….…………….39
2.2 P2P系統中檔案分類的相關研究………..……….……………………..45
2.3 P2P系統的典型代表………………...………………………….……….49
2.3.1　Variable-Degree DHT P2P系統 ………...…………...………………..49
2.4.2　Constant-Degree DHT P2P系統………….………..……..……………58
第三章　階層式資源分類重疊網路…………...……………………………..62
3.1　動機跟問題陳述……………….……..………………………………….62
3.1.1　描述Bootstrap Server的缺點………….……..………………………..62
3.1.2　描述分類的法則以及好處………………...…………………………..63
3.2　建構分類的重疊網路…………………..………….…………….………64
3.2.1　系統架構圖的描述…………………...………………………….…….65
3.2.2 　HRCON的整體架構圖…………………...…………………..………68
3.2.3 　DNS-Agent 和 Peer的路由架構………...…………………….……69
3.2.4　節點及檔案的編碼方式…………………...…………………….…….71
3.3 　HRCON的路由方法: (內部，外部)……………….……………..……..72
3.3.1　描述查詢的方式…………………………...…………………….…….72
3.3.2　字串比對演算法…………………………...………………….……….73
3.3.3　系統路由演算法…………………………...…………………..………74
3.4 自我組織 (Self-Organization)…...…..……..………………….…..………76
3.4.1節點加入(Node Join) ……………….…………………………….………76
3.4.2節點離開/錯誤……………………………………….……………………78
3.4.3節點路由表的維護…………………………………….….………………79
3.4.4 DNS-Agent的設置……….………….…………………..………………..79
第四章　實驗模擬……………...………………..………………….………….81
4.1　分析………………………………….…………..…..…………………...81
4.2　實驗模擬…………………………………….……..…………………….82
4.2.1　節點路由的效能評估…………………….…………..…….………….83
4.2.2　節點加入及離開的效能評估………………….…………..….……….85
4.2.3　路由維護的效能評估……………………….………..…….….………86
4.2.4　節點錯誤率的效能評估……………………….…..…………………..88
第五章　結論……………………………..…….………………………..……92

[1] Aimster, http://computer.howstuffworks.com/question587.htm
[2] S. Androutsellis-Theotokis and D. Spinellis. A survey of peer-to-peer content distribution technologies. ACM Comput. Surv., 36(4):335–371, 2004.
[3] G. Bolcer. Magi: An architecture for mobile and disconnected workflow. In White paper (www.endeavors.com), 2001.
[4] M. Castro, P. Druschel, Y. C. Hu, and A. Rowstron. Topology-aware routing in structured peer-to-peer overlay networks. In Future Directions in Distributed Computing, 2003.
[5] N. Daswani and H. Garcia-Molina. Query-flood dos attacks in gnutella. In Proc. Ninth ACM Conference on Computer and Communications Security, 2002.
[6] FastTrack, http://www.fasttrackdcn.net/
[7] Gnutella., http://www.gnutella.com.
[8] I. Gupta, K. Birman, P. Linga, A. Demers, and R. van Renesse. Kelips: building an efficient and stable p2p dht through increased memory and background overhead. In Proc. of the 2nd International Workshop on Peer-to-Peer Systems (IPTPS), pages 81–86, 2003.
[9] Groove Networks. Groove networks product backgrounder, groove networks white paper, 2001. www.groove.net/pdf/groove product backgrounder.pdf.
[10] A. Grimshaw, W. Wulf, J. French, A. Weaver, and Reynolds Jr. P. Legion: The next logical step toward a nation-wide virtual computer. Technical report, Department of Computer Science, University of Virginia, 1994.
[11] Steven D. Gribble, Eric A. Brewer, Joseph M. Hellerstein, and David Culler. Scalable, Distributed Data Structures for Internet Service Construction. 2000. Proceedings of the Fourth Symposium on Operating Systems Design and Implementation (OSDI 2000).
[12] iMesh, http://www.imesh.com/
[13] Jxta 2001. JXTA home page: http://www.jxta.org.
[14] Joltid, http://www.joltid.com
[15] KaZaA, http://www.kazaa.com
[16] M. Kleis, E. K. Lua, X. Zhou, “Hierarchical Peer-to-Peer Networks using Lightweight SuperPeer Topologies”, In IEEE Symposium on Computers and Communications (ISCC), 2005.
[17] LimeWire, http://www.limewire.com/english/content/home.shtml
[18] D. Liben-Nowell, H. Balakrishnan, and D. Karger. Observations on the dynamic evolution of peer-to-peer networks. In Proc. of the 1st International Workshop on Peer-to-Peer Systems (IPTPS), 2002.
[19] J. Ledlie, J. Taylor, L. Serban, and M. Seltzer. Self-organization in peer-to-peer systems. In Proc. of the ACM SIGOPS European Workshop, 2002.
[20] P. Linga, I. Gupta, and K. Birman. A churn-resistant peer-to-peer web caching system. In Proc. of the 2nd International Workshop on Peer-to-Peer Systems (IPTPS), 2004.
[21] J. Li, J. Stribling, T.M. Gil, R. Morris, and F. Kaashoek. Comparing the performance of distributed hash tables under churn. In Proc. of the 2nd International Workshop on Peer-to-Peer Systems (IPTPS), 2004.
[22] N. A. Lynch. Distributed algorithms. Morgan Kaufmann Publisher, 1996.
[23] S. M. Lui and S. H. Kwok. Interoperability of peer-to-peer file sharing protocols. ACM SIGecom Exchanges, 3(3):25–33, 2002.
[24] Witold Litwin and Marie-Anna Neimat and Donovan A. Schneider. LH* -- a scalable, distributed data structure. 1996. ACM Trans. Database Syst., 21(4):480--525.
[25] F.T. Leighton, “Introduction to Parallel Algorithms and Ar- chitectures: Arrays, Trees, Hypercubes,” Academic Press Morgan Kaufmann, 1991.
[26] D. Loguinov, A. Kumar, V. Rai, S. Ganesh, Graph-Theoretic Analysis of Structured Peer-to-Peer Systems—Routing Distances and Fault Resilience. In Proc. of the SIGCOMM 2003. 2003.
[27] Morpheus, http://morpheus.com/.
[28] D. Molnar, R. Dingledine, and M. Freedman. Chapter 12: Peer-to-Peer: Harnessing the Power of Disruptive Technologies. O’Reilly & Associates, 2001.
[29] A. T. Mizrak, Y. Cheng, V. Kumar, S. Savage, “Structured Superpeers: Leveraging Heterogeneity to Provide Constant-Time Lookup”, in The Third IEEE Workshop on Internet Applications San Jose, California, 2003.
[30] Napster, http://www.napster.com.
[31] A. Oram, editor. Peer-to-Peer: Harnessing the Power of Disruptive Technologies. O’Reilly & Associates, March 2001.
[32] Peer-to-peer working goup, 2001. www.p2pwg.org.
[33] G. Pandurangan, P. Raghavan, and E. Upfal. Building low-diameter peer-to-peer networks. In IEEE FOCS, 2001.
[34] Peer-to-peer working goup, 2001. www.p2pwg.org.
[35] C. Greg Plaxton, Rajmohan Rajaraman, and Andrea W. Richa. Accessing nearby copies of replicated objects in a distributed environment. In Proceedings of ACM SPAA. ACM, June 1997.
[36] S. Ratnasamy, M. Handley, R. Karp, and S. Shenker. Topologically-aware overlay construction and server selection. In Proc. of IEEE Conference on Computer Communications (INFOCOM), 2002.
[37] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker. A scalable content-addressable network. In Proc. of ACM SIGCOMM, pages 329–350, 2001.
[38] SoftWax, http://www.softwax.com/
[39] C. Shirky. What is p2p...and what isn’t? The O’Reilly Netowrk, 2000.
[40] Haiying Shen, Aharon S. Brodie, Cheng-zhong Xu, and Weisong Shi, Scalable and Secure P2P Overlay Networks, a chapter of the book "Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless and Peer-to-Peer Networks," Editted by Jie Wu, CRC press, June 2005.
[41] J. Saia, A. Fiat, S. Gribble, A.R. Karlin, and S. Saroiu. Dynamically Fault-Tolerant Content Addressable Networks. In Proc. of the 1st International Workshop on Peer-to-Peer Systems (IPTPS), 2002.
[42] I. Stoica, R. Morris, D. Liben-Nowell, Kaashoek M. F. Karger, D. R. Karger, F. Dabek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup protocol for Internet applications. In IEEE/ACM Trans. on Networking, 2002.
[43] M. Satyanarayanan, J. Kistler, P. Kumar, M. Okasadi, E. Siegel, and D. Steere. Coda: A highly available file system for a distributed workstation environment. In IEEE Transactions on Computers, pages 447–459, 1990.
[44] K.N. Sivarajan and R. Ramaswami, “Lightwave Networks Based on de Bruijn Graphs,” IEEE/ACM Trans. on Net- working, vol. 2, no. 1, 1994.
[45] A. Veytsel. There is no p-to-p market... but there is a market for p-to-p. In Aberdeen Group Presentation at the P2PWG, 2001.
[46] B. Wiley. Chapter 19: Peer-to-Peer: Harnessing the Power of Disruptive Technologies. O’Reilly & Associates, 2001.
[47] M. Waldman, A. Rubin, and L. Cranor. Publius: A robust, tamper-evident, censorshipresistant web publishing system. In Proc. of the USENIX Security Symposium, 2000.
[48] Z. Xu, C. Tang, and Z. Zhang. Building topology-aware overlays using global soft-state. In Proc. of the 23rd International Conference on Distributed Computing Systems (ICDCS), 2003.
[49] B. Yang, H. Garcia-Molina, “Designing a Super-Peer Network”, in: IEEE International Conference on Data Engineering. San Jose, California, 2003.