(3.238.173.209) 您好!臺灣時間:2021/05/15 16:46
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

: 
twitterline
研究生:張俊盛
研究生(外文):Chun-Sheng Chang
論文名稱:在DHT點對點網路下關鍵字搜尋的路由策略研究
論文名稱(外文):The Study of Routing Strategy on Keyword Search in DHT-based Peer-to-Peer Networks
指導教授:蔡國煇蔡國煇引用關係
指導教授(外文):Kuo-Hui Tsai
學位類別:碩士
校院名稱:國立臺灣海洋大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2010
畢業學年度:98
語文別:中文
論文頁數:45
中文關鍵詞:點對點網路關鍵字搜尋超立方體隨機路由
外文關鍵詞:Peer-to-Peer (P2P)Keyword SearchHypercubeRandom Routing
相關次數:
  • 被引用被引用:0
  • 點閱點閱:271
  • 評分評分:
  • 下載下載:33
  • 收藏至我的研究室書目清單書目收藏:0
在DHT架構下的點對點的網路中,使用者可以針對檔案名稱作搜尋,但是當所擁有的資訊不夠完整時,便無法找到所要的檔案,因而發展出較有彈性的關鍵字搜尋法。它是將檔案的各個關鍵字透過雜湊函數產生出來的組合,對應到網路中的某個節點,而檔案名稱搜尋法則是利用檔案名稱來做對應。所以關鍵字搜尋法在尋找檔案上,更加的方便、實用。
關鍵字搜尋法的其中一種,就是在超立方體的架構下,每種關鍵字組合僅會由單一節點負責,並且越接近的兩個節點其負責的關鍵字組合也越相似,因此搜尋的效率會更加提升。
當搜尋請求只需要部分節點回應時,搜尋訊息的路由策略就會決定訊息經過哪些節點,因此也影響到搜尋的效率、訊息的多寡、節點的負載平衡。我們在超立方體的結構下,提出了一種介於BFS與DFS間的隨機路由策略,在部分搜尋時,讓搜尋請求能較平均的尋訪同層節點,並且最底層的節點也有機會被搜尋到。以系統整體而言,也能讓各節點的總尋訪次數差距縮小。
Users can search for the information they need by file name in Peer-to-Peer (P2P) networks. When the information we have is not sufficient to fully describe an object, then it is possible that the object will not be found. Therefore, keyword search, which is a flexible search service, has been developed. It is hashing the object’s keyword set to obtain a key that maps to a unique node in the network. File name search is hashing the object’s name to obtain a key. As a result, keyword search is more convenient and practical than file name search in finding an object.
The hypercube structure has been proposed to be used in keyword search. Each object is mapped a vector according to it’s keyword set, and stored in the node corresponding to the vector. Objects with similar keywords are likely to be stored in close nodes, thus provides an efficient search scheme.
When a search request simply demands some nodes in response, search message of routing strategy will determine that the message through which node, and hence affect the search efficiency, the amount of messages, and the node load balancing. We propose a random routing strategy based on hypercube structure in keyword search. It’s shown the request can be processed evenly through each node, and objects containing user’s keyword will have equal opportunity to be found.

摘要 I
Abstract II
目錄 III
圖目錄 V
第一章 序論 1
1.1 研究背景 1
1.2 研究動機 2
1.3 研究成果 2
1.4 論文架構 3
第二章 背景知識與相關研究 4
2.1 點對點網路架構 4
2.1.1 分散式雜湊表(Distributed Hash Table,DHT) 5
2.1.2 非結構化 5
2.1.3 結構化 6
2.2 現有關鍵字搜尋法的問題 6
2.3 超立方體結構 7
2.3.1 系統架構 7
2.3.2 關鍵字及檔案的對應方式 9
2.3.3 搜尋方法 10
第三章 研究方法與設計 12
3.1 基本參數定義 12
3.2 系統流程 13
3.3 隨機路由策略流程 13
3.4 隨機路由策略基本概念 14
3.5 filled_level、t與t`的計算方式 19
3.6 組合的種類 21
3.7 挑選組合的方式 25
3.8 挑選適當的節點 27
3.9 無法完全平衡的原因分析 27
第四章 實驗模擬與分析 29
4.1 實驗介紹 29
4.2 實驗I:單一子超立方體尋訪次數 29
4.2.1 實驗一:子超立方體大小為128 29
4.2.2 實驗二:子超立方體大小為256 32
4.2.3 實驗三:子超立方體大小為512 36
4.3 實驗II:系統整體尋訪次數 40
4.3.1 完全搜尋 40
4.3.2 部分搜尋 41
第五章 結論與未來展望 43
5.1 結論 43
5.2 未來展望 43
參考文獻 44
[1] RFC1 http://www.ietf.org/rfc/rfc1.txt
[2] Y. Joung, L. Yang, and C. Fang ,”Keyword Search in DHT-based Peer-to-Peer Networks”, IEEE Journal On Selected Areas In Communication, Vol. 25, No. 1, January. 2007
[3] Gnutella http://rfc-gnutella.sourceforge.net/
[4] KaZaA, available at http://www.kazaa.com/
[5] Freenet, available at http://freenet.sourceforge.net/
[6] C. Gkantsidis, M. Mihail, and A. Saberi, “Random Walks in Peer to Peer Networks”, Proc. INFOCOM, pages 120 – 130, 2004
[7] S. Ratnasamy, P. Francis, M. Handley, R. Karp and S. Shenker, “A scalablecontent-addressable network”, in Proc. ACM SIGCOMM, Pages: 161-172, 2001.
[8] Stoica I., Morris R., Liben-Nowell D., Karger D.R., Kaashoek M.F., Dabek F. and Balakrishnan H., ”Chord :a scalable peer-to-peer lookup protocol for Internet applications”, in Networking, IEEE/ACM Transactions on, Pages: 17 -32, 2003.
[9] A. Rowstron and P. Druschel, ”Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems”, in Proc. 18th IFIP/ACM Int. Conf. Distributed Systems Platforms (Middleware 2001), Pages: 329-350, 2001
[10] B. Zhao, J. Kubiatowicz, and A. Joseph, “Tapestry:An infrastructure for fault-tolerant wide-area location and routing”, in Comput. Sci. Div., Univ. California, Berkeley, Tech. Rep. UCB/CSD-01-1141, 2001.
[11] O. D. Gnawali, “A keyword-set search system for peer-to-peer networks”, Master’s thesis, Massachusetts Institute of Technology, Cambridge, Massachusetts, United States, June 2002
[12] F. Zhou, L. Zhuang, B. Y. Zhao, L. Huang, A. D. Joseph, and J. Kubiatowics, “Approximate object location and spam filtering on peer-to-peer systems”, in Proceedings of the 2003 ACM/IFIP/USENIX International Middleware Conference (Middleware 2003), ser. Lecture Notes in Computer Science, vol. 2672. Springer-Verlag, 2003, pp. 1–20.
[13] P. Reynolds and A. Vahdat, “Efficient peer-to-peer keyword searching”, in Proceedings of the 2003 ACM/IFIP/USENIX International Middleware Conference (Middleware 2003), ser. Lecture Notes in Computer Science, vol. 2672. Springer-Verlag, 2003, pp. 21–40.
[14] C. Tang and S. Dwarkadas, “Hybrid global-local indexing for efficient peer-to-peer information retrieval”, in Proceedings of the First Symposium on Networked Systems Design and Implementation (NSDI 2004). USENIX, 2004, pp. 211–224.
[15] S. Shi, G. Yang, D. Wang, J. Yu, S. Qu, and M. Chen, “Making peer-to-peer keyword searching feasible using multi-level partitioning”, in Proceedings of the 3rd International Workshop on Peer-to-Peer Systems (IPTPS 2004)., ser. Lecture Notes in Computer Science, vol. 3279. Springer-Verlag, 2005, pp. 151–161
[16] P. Ganesan, Q. Sun, and H. Garcia-Molina, “Adlib: A self-tuning index for dynamic peer-to-peer systems”, in Proceedings of the 21st International Conference on Data Engineering (ICDE’05). IEEE Computer Society, 2005, pp. 256–257.

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top