Donuts:考慮地域鄰近性且負載平衡的點對點範圍查詢系統

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.

並列關鍵字

Peer-to-Peer ； Proximity ； Load Balance ； Range Query

參考文獻

[1] James Aspnes, Jonathan Kirsch, and Arvind Krishnamurthy. Load balancing and locality in range-queriable data structures. In Proceedings of the twenty-third Annual ACM Symposium on Principles of Distributed Computing (PODC 2004), pages 115~124. ACM Press, July 2004.

[8] Prasanna Ganesan, Mayank Bawa, and Hector Garcia-Molina. Online balancing of range-partitioned data with applications to peer-to-peer systems. In Proceedings of the Thirtieth Conference on Very Large Databases (VLDB 2004), August 2004.

[10] Krishna Gummadi, Ramakrishna Gummadi, Sylvia Ratnasamy, Steve Gribble, Scott Shenker, and Ion Stoica. The impact of dht routing geometry on resilience and proximity. In Proceedings of ACM conference on Special Interest Group on Data Communications (SIGCOMM), Aug 2003.

[13] Frans Kaashoek and David R. Karger. Koorde: A simple degree-optimal hash table. In Proceedings of the 2nd International Workshop on Peer-to-Peer Systems (IPTPS'03), February 2003.

[14] David Karger, Eric Lehman, Tom Leighton, Rina Panigrahy, Matthew Levine, and Daniel Lewin. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing (STOC 1997), pages 654~663. ACM Press, May 1997.

國際替代計量

Donuts:考慮地域鄰近性且負載平衡的點對點範圍查詢系統

全文下載

主題瀏覽