Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/38155
Title: | Donuts:考慮地域鄰近性且負載平衡的點對點範圍查詢系統 Donuts: A Network-Aware and Load-Balanced System for Range Query |
Authors: | Yi-Fang Chou 周亦方 |
Advisor: | 莊裕澤(Yuh-Jzer Joung) |
Keyword: | 點對點網路,鄰近性,負載平衡,範圍查詢, Peer-to-Peer,Proximity,Load Balance,Range Query, |
Publication Year : | 2005 |
Degree: | 碩士 |
Abstract: | DHT(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. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/38155 |
Fulltext Rights: | 有償授權 |
Appears in Collections: | 資訊管理學系 |
Files in This Item:
File | Size | Format | |
---|---|---|---|
ntu-94-1.pdf Restricted Access | 951.9 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.