莊裕澤臺灣大學：資訊管理學研究所周亦方Chou, Yi-FangYi-FangChou2007-11-262018-06-292007-11-262018-06-292005http://ntur.lib.ntu.edu.tw//handle/246246/54210DHT(Distributed Hash Table) 是非常受歡迎的P2P結構，它提供了有效率的繞送(routing)和保證有結果的搜尋。然而，它有兩個主要的缺點：上層邏輯網路和下層實體網路的不一致性，以及混亂編碼(hashing)導致珍貴的資訊遺失。前者使得在上層邏輯網路的繞送變得成本高昂，後者則限制了DHT支援複雜搜尋方法的能力。因此，儘管DHT保證了在邏輯網路上有效率的關鍵字搜尋，真正在實體網路上所發生的成本可能很高。此外，簡單的關鍵字搜尋無法滿足各式各樣搜尋的需求。 在這篇論文中，我們提出了Donuts。這個系統利用了鄰近性，且負載平衡，並同時可以支援範圍查詢。我們建立了考慮鄰近性的繞送表格來減少繞送成本，並且使點(Peer)加入系統時考慮鄰近性來建立和實體網路類似的邏輯網路。為了要保存資訊以支援範圍查詢，Donuts使用一個機率性的架構來代替DHT。另外，我們介紹了“Group”的概念來將實體網路中靠近的點群聚在數個邏輯網路的區域。這個概念不但解決了鄰近性、負載平衡和範圍查詢間的衝突，同時更明顯的利用緩衝儲存(cache)增進了搜尋的效率。透過模擬實驗，我們證明了Donuts是一個成功結合鄰近性，負載平衡以及範圍查詢的系統，它也具備了能容錯和能支援大量使用者等P2P網路的特性。Distributed Hash Table (DHT) is a popular P2P structure because of efficient routing and guaranteed search. However, it has two main drawbacks: incongruence between overlay and IP-network, and the lost of information due to hashing. The first makes overlay routing become expensive due to high routing stretch while the second restricts DHTs to support complex query. Therefore, even though DHT guarantees efficient keyword search in overlay, the actual cost might still be high and the limited keyword search is not enough to fulfill different needs. In this paper, we propose Donuts, which exploits proximity, achieves load balance, and supports range query. We build proximity routing table to reduce routing stretch, and adopt proximity join to exploit overlay proximity. A probabilistic structure is used instead of DHT so Donuts is able to support range query. Moreover, we introduce the "Group" concept which clusters physically nearby nodes into several overlay sections. It not only solves the conflict among proximity, load balance, and range query, but also improves search efficiency by cache. Through simulations, we prove that Donuts is a scalable and fault-tolerant system which successfully achieves proximity, load balance, and range query simultaneously.1 Introduction 1 1.1 Background 1 1.2 Motivation 3 1.3 Research Objectives 4 2 Related Work 5 2.1 Structured Peer-to-Peer Overlay 5 2.1.1 Hash Function Based Overlay 5 2.1.2 Non Hash Function Based Overlay 9 2.1.3 Brief Summary 12 2.2 Proximity Approach 14 2.2.1 Proximity Join 14 2.2.2 Proximity Routing Table Construction 16 2.2.3 Proximity Routing 17 2.2.4 Adaptive Proximity 17 2.2.5 Brief Summary 18 2.3 Hybrid Systems 19 2.3.1 Network-aware and Load-balanced System 19 2.3.2 Load-balanced System for Range Query 19 2.3.3 Network-aware System for Range Query 20 2.3.4 Network-aware and Load-balanced System for Range Query 20 2.4 Summary 21 3 System Model 22 3.1 Query Model 22 3.2 Basic Donuts Structure 22 3.2.1 Approaching Proximity 24 3.2.2 Load Balance 25 3.3 Enhancement 25 3.3.1 The Affinity of Proximity Table 27 3.3.2 Link Pattern and Cache 27 3.3.3 Fault-tolerance 29 3.4 Donuts 29 3.4.1 The Features of Donuts 29 3.4.2 System Algorithm 29 4 Experimental Results 38 4.1 Simulation Methodology 38 4.2 Proximity Join Performance 39 4.2.1 Locating a physically nearby node 39 4.2.2 Deciding the overlay position 42 4.2.3 Overlay Proximity 43 4.3 Proximity and Group 44 4.3.1 The Impact of Group on Overlay Proximity 44 4.3.2 The Impact of Group on Proximity Table 45 4.4 Load Balance 48 4.5 Cache, Group, and Search Performance 50 5 Conclusion and Future Work 58 5.1 Conclusion 58 5.2 Future Work 59 Bibliography 60974749 bytesapplication/pdfen-US點對點網路鄰近性負載平衡範圍查詢Peer-to-PeerProximityLoad BalanceRange Query[SDGs]SDG16otherhttp://ntur.lib.ntu.edu.tw/bitstream/246246/54210/1/ntu-94-R92725016-1.pdf