臺灣博碩士論文加值系統

點對點系統是一個分散式的系統，完全不需要任何集中式的控管以及任何的階層式組織。目前點對點應用有著下列的特點：儲存、效能、匿名性、查詢、可信性的認證與階層式的命名等優點。P2P網路可區分為結構化與非結構化兩大類型的架構，其中結構化的架構，利用相同的雜湊函數將資源名稱對應到某個網路上的節點位址進而將分享資源或是位置資訊配置在該資訊所對應的節點上，而且擁有較為快速的繞送訊息機制來取得資源。
不過由於結構化的點對點架構下的分享/搜尋機制依賴於利用雜湊函數將資源的名稱明確對應到對等式網路上的節點位址，而造成此種架構無法提供關鍵字搜尋機制。
因此本研究將實際提出一個在結構化對等式網路架構下提供關鍵字搜尋並且支援範圍關鍵字的搜尋的機制，並且與其他學者所提出的關鍵字搜尋機制分別進行模擬實驗。實驗結果驗證本研究對於結構化對等式的關鍵字搜尋機制能夠在使用雜湊函數直接對應檔案資源的系統下提供較少的網路流量；以及在能夠支援範圍查詢機制的系統下對於網路內檔案有著較高的檔案可取用度。

Peer-to-peer systems are a special type of decentralized systems which don’t need centralized control and class hierarchies. Current peer-to-peer applications have the following characteristics: storage, efficiency, anonymity, searches, credibility and the advantages of the class naming. P2P networks can be divided into two types: structured and unstructured. The structured P2P networks ,using a hash function to map a resource to a node IP address where the resource is to be placed. Besides, rapid routing mechanisms are designed to facilitate resource lookups.
However, because structured P2P networks exploit hash functions to share and search resource, the cryptographic characteristics of hash functions render keyword-based searches unfeasible in structured P2P networks.
This research aims to provide a novel search mechanism for structured Peer-to-Peer networks to search by keywords and ranges. Our simulation results show the proposed mechanism enables a more efficient keyword-based search in the system which use hash functions share and search resource directly , as well as maintaining a higher level of availability in the mechanism which provide search by ranges.

第壹章 緒論 1
1.1 研究背景 1
1.2 研究動機 3
1.3研究目的 4
第貳章 文獻探討 6
2.1 Peer-to-Peer 網路架構 7
2.1.1 非結構化對等式網路：Gnutella 7
2.1.2結構化對等式網路：Chord 9
2.2 Peer-to-Peer 網路的關鍵字查詢 15
2.2.1 Squid 15
2.2.2 Panache 18
2.3小結 22
第參章 研究方法 24
3.1 問題定義與分析 24
3.2 方法設計 26
3.2.1 系統建置 26
3.2.2關鍵字檔案發佈 26
3.2.3範圍屬性檔案發佈 28
3.2.4關鍵字搜尋機制 32
3.2.5範圍屬性搜尋機制 34
3.3 研究模型與分析 37
3.3.1 關鍵字詞的抽樣分析 37
3.3.2 研究模型 39
3.4 研究設計 41
第肆章 模擬實驗之設計與結果 43
4.1 實驗環境設定 43
4.1.1 模擬實驗輸入參數 43
4.1.2 模擬實驗輸出參數 44
4.1.3 模擬實驗之流程 45
4.2 實驗環境設定 47
4.2.1非關鍵字的搜尋機制演算法 47
4.2.2關鍵字的搜尋機制演算法 49
4.2.3範圍關鍵字的搜尋機制演算法 50
4.3 關鍵字查詢機制實驗與分析 52
4.3.1結構化對等式網路Chord模擬與分析 53
4.3.2結構化對等式網路關鍵字查詢機制模擬與分析 56
4.3.3結構化對等式網路範圍關鍵字查詢機制模擬與分析 59
4.4模擬實驗小結 62
第伍章 結論與未來展望 64
5.1結論 64
5.2研究建議 65
5.3研究限制 65
5.4未來展望 66
參 考 文 獻 68
附 錄 72

[1]吳明蔚，林盈達，「對等式（P2P）網路技術」，電腦與通訊期刊第一零三期，工研院電通所，March 2003。
[2]吳晉賢，結合分散式及對等式的優點去實作檔案分享系統，台灣大學資訊工程學研究所碩士論文，2001。
[3]張俊傑，應用關鍵字搜尋於使用繞送為基準之資源定位方法的對等式資源分享網路，清華大學資訊工程學研究所碩士論文，2002。
[4]Androutsellis-Theotokis, S. , Spinellis, D. , ”A Survey of Peer-to- peer Content Distribution Technologies”, ACM Computing Surveys, Vol. 36, No. 4,2004, pp. 335-371.
[5]Bhattacharya, I. , Kashyap, S. R. , and Parthasarathy, S. , “Similarity Searching in Peer-to-peer Databases”, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems (ICDCS’05), 2005, pp. 329–338.
[6]Botros, S. , Waterhouse, S. , “Search in JXTA and Other Distributed Networks”, Proceedings of the First International Conference on Peer-to-Peer Computing, IEEE Press, 2002.
[7]Damiani, E. , Paraboschi, S. , Samarati, P. , and Violante, F. , “A Reputation-Based Approach for Choosing Reliable Resources in Peer-to-Peer Networks”, Proceedings of the Computer & Communications Security, 2002.
[8]Gai, A. T. , Viennot, L. , “Optimizing and Balancing Load in Fully Distributed p2p File Sharing Systems”, Proceedings of the Internet and Web Applications and Services/Advanced International Conference, 2006.
[9]Ganesan, P. , Gummadi, K. , and Garcia -Molina, H. , “Canon in G Major: Designing DHTs with Hierarchical Structure”, Proceedings of the 24th IEEE International Conference on Distributed Computing Systems, 2004.
[10]Gelbukh, A. , Sidorov, G. , “Zipf and Heaps Laws』 Coefficients Depend on Language”, Proc. CICLing-2001, Proceedings of the Conference on Intelligent Text Processing and Computational Linguistics, 2001. Lecture Notes in Computer Science 2004, ISSN 0302-9743, ISBN 3-540-41687-0, Springer-Verlag, pp. 332–335.
[11]How Peer-to-peer (p2p) and Kazaa Media Desktop Work, Kazaa Website: http://www.kazaa.com/us/help/guideaboutp2p.htm, 2003.
[12]Joung, Y. J. , Fang, C. T. , and Yang, L. W. , “Keyword Search in DHT-based Peer-to-peer Networks”, Proceedings of the Intertaional Conference on Distributed Computing Systems, 2005.
[13]Liu, L. , Ryu, K. D. , and Lee, K.W. , “Supporting Efficient Keyword-based File Search in Peer-to-peer file sharing systems”, Proceedings of the Global Telecommunications Conference, 2004.
[14]Li, W. , “Random Texts Exhibit Zipf's-law-like Word Frequency Distribution”, IEEE Transactions on Information Theory, 38(6), 1992, pp. 1842-1845.
[15]Lu, T. , Sinha, S. , and Sudan, A. , “Panache: A Scalable Distributed. Index for Keyword Search”, Technical Report, MIT, 2003.
[16]Ratnasamy, S. , Francis, P. , Handley, M. , and Karp, R. M. , “A Scalable Content-Addressable Network”, Proceedings of the ACM Special Interest Group on Data Communications, 2001, pp. 161–172.
[17]Rowstron, A. , Druschel, P. , “Pastry: Scalable, Distributed Object Location and Routing for Large-scale Peer-to-peer Systems”, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, 2001, p.329-350.
[18]Sahin, O. D. , Antony, S. , Agrawal, D. , and Abbadi, A. El, “PRoBe: Multi-Dimensional Range Queries in P2P Networks”, Lecture Notes in Computer Science, 2005.
[19]Schmidt, C., Parashar, M., “Enabling Flexible Queries with Quarantees in P2P Systems,” IEEE Internet Computing (Special Issue on Information Dissemination on the Web), vol. 8, no. 3, 2004, pp. 19-26.
[20]Shneiderman, B., “Universal Usability”, Communications of the ACM, Vol. 43, Issue. 5, 2000.
[21]Steinmetz, R. , Wehrle, K. , ”Peer-to-peer System and Application”, ISBN: 3-540-29192-X, Lecture Notes in Computer Science, Volume 3485, 2005.
[22]Stoica, I. , Morris, R. , Karger, D. , Kaashoek, M. F. , and Balakrishnan, H. , “Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications”, Proceedings of the ACM Special Interest Group on Data Communications, 2001.
[23]The Gnutella protocol specification, 2000,
http://www.gnutella.co.uk/library/pdf/gnutella_protocol_0.4.pdf.
[24]Zhao, B. Y. , Kubiatowicz, J. D. , and Joseph, A. D. , ”Tapestry: An Infrastructure for Fault-resilient Wide-area Location and Routing”, Technical Report UCB//CSD-01-1141, 2001.
[25]Zipf, G. K. , “Human Behavior and the Principle of Least- Effort”, Addison-Wesley, Cambridge, MA, 1949.
[26]Zhang, Z. , Zhou, S. , Qian, W. , and Zhou, A. , “KEYNOTE: Keyword Search by Node Selection for Text Retrieval on DHT - based P2P Networks”, Lecture Notes in Computer Science, 2006.