莊裕澤臺灣大學:資訊管理學研究所黃曉梅Huang, Hsiao-MeiHsiao-MeiHuang2010-05-052018-06-292010-05-052018-06-292008U0001-1208200815544400http://ntur.lib.ntu.edu.tw//handle/246246/179839點對點系統近年來成為大規模分散式資訊系統的強大平台，搜尋系統資源是此種平台的一種十分重要的功能，並且已經有不少的研究提出改善系統搜尋效能的方法；然而，點對點平台並不是對於任何類型的查詢都能有效的支援，例如對於範圍查詢的支援仍然有限。要在點對點平台上有效的支援範圍查詢，首先我們必須解決影響效能的相關問題﹕系統內部的高通訊成本、點與點之間的負載不平衡以及維持系統裡物件的有效性。Donuts是滿足上述效能要求的點對點範圍查詢系統，它可以維持物件的有效性及有效地支援範圍查詢，利用群組化的概念來解決地域鄰近性與負載平衡之間的衝突；然而Donuts提供的搜尋演算法-“先搜尋鄰居列表與群組成員鄰居列表、再利用繞路表搜尋”的方式所花費的搜尋成本過於昂貴，且模擬的搜尋樣式與真實點對點系統的情形並不相符。本篇論文裡我們提出與實際搜尋行為較相似的搜尋樣式-“考量地域性與物件受歡迎程度的搜尋樣式”，並以之為基礎研究搭配Donuts特性的搜尋與快取策略。我們的實驗結果證明了Chordal Ring是適合Donuts的系統資料結構，並且比較了傳統快取方法-本地端快取與沿路快取的搜尋效能；最後比較搭配Donuts特性的合作式鄰居搜尋的快取方式與傳統快取的效能，深入討論最適合的搜尋與快取策略。Peer-to-peer systems have emerged as a powerful platform for large-scale distributed information systems in recent years; important functionalities, such as searching, have been added to improve the system''s lookup capability. The efficient support of range queries in a P2P system is still a challenging problem. To resolve this problem, some other related issues must first be addressed, such as high communication overheads, load imbalance among peers and preservation of object availability. Donuts satisfies above requirement and maintain object availability and effectively range queries. Within a grouping environment, peers are divided into several groups to provide the flexibility of proximity and feasibility of load balance in a range queries system. However, Donuts'' search algorithm with cooperative search is not efficient. The search cost is tremendous. Also the query pattern in Donuts is not similar to real word.his thesis provide more factual query pattern to simulate search behavior. Considering locality and popularity, we try to find the best search and cache strategy. The result of experiment prove that chordal ring is the better system data structure. We also compare the performance of local cache with the one of cache by path. Finally, we compare cooperative neighbor cache with traditional cache and make a conclusion for best search and cache method.第一章 簡介 - 9 -.1背景介紹 - 9 -.2 動機 - 12 -.3 研究目標 - 14 -二章 文獻探討 - 15 -.1結構化點對點系統 - 15 -.1.1 CAN - 15 -.1.2 Chord - 16 -.1.3 Pastry - 17 -.1.4 Skip graph - 18 -.1.5 總結 - 19 -.2 搜尋樣式的相關議題 - 20 -.3 快取 - 20 -.3.1本地端快取 - 21 -.3.2 合作式快取 - 22 -.3.3 快取取代策略 - 23 -三章 系統模型 - 25 -.1系統概述 - 25 -.2基礎環狀結構 - 26 -.3鄰近性 - 27 -.4錯誤容忍機制 - 29 -.4.1 鄰居列表 - 29 -.4.2 繞路表 - 30 -.5物件的可利用性 - 31 -.6負載平衡機制 - 31 -.6.1鄰居平衡(NB) - 31 -.6.2節點重排(PR) - 32 -.7搜尋 - 32 -.7.1鄰近表(Proximity Table) - 33 -.7.2 快捷表(Express Table) - 34 -.7.3 搜尋與快取 - 34 -四章 實驗結果 - 42 -.1模擬方法 - 42 -.1.1實體網路 - 42 -.1.2動態環境模擬 - 43 -.2衡量指標 - 46 -.3 搜尋與快取的效能 - 47 -.3.1 系統資料結構的影響 - 51 -.3.2 快取空間對搜尋效能的影響 - 54 -.3.3 傳統快取對搜尋鄰近表的影響 - 55 -.3.3 本地端快取對鄰居搜尋加鄰近表繞路的影響 - 59 -.3.4 合作式快取加沿路快取與傳統快取的比較 - 62 -.4總結 - 64 -五章 結論 - 66 -考目錄 - 67 -application/pdf1216107 bytesapplication/pdfen-US點對點網路範圍查詢鄰近性群組化負載平衡快取P2P networkrange queryproximitygroupingload balancecachehttp://ntur.lib.ntu.edu.tw/bitstream/246246/179839/1/ntu-97-R95725028-1.pdf