Implementing dynamic querying search in k-ary DHT-based overlays
Number of Authors: 4
2008 (English)In: Grid Computing: Achievements and Prospects, USA: Springer , 2008, 1, , 12 p.275-286 p.Chapter in book (Refereed)
Distributed Hash Tables (DHTs) provide scalable mechanisms for implementing resource discovery services in structured Peer-to-Peer (P2P) networks. However, DHT-based lookups do not support some types of queries which are fundamental in several classes of applications. A way to support arbitrary queries in structured P2P networks is implementing unstructured search techniques on top of DHT-based overlays. This approach has been exploited in the design of DQDHT, a P2P search algorithm that combines the dynamic querying (DQ) technique used in unstructured networks with an algorithm for efficient broadcast over a DHT. Similarly to DQ, DQ-DHT dynamically adapts the search extent on the basis of the desired number of results and the popularity of the resource to be found. Differently from DQ, DQ-DHT exploits the structural constraints of the DHT to avoid message duplications. The original DQ-DHT algorithm has been implemented using Chord as basic overlay. In this paper we focus on extending DQ-DHT to work in k-ary DHT-based overlays. In a k-ary DHT, broadcast takes only O(logkN) hops using O(logkN) pointers per node. We exploit this “k-ary principle” in DQ-DHT to improve the search time with respect to the original Chord-based implementation. This paper describes the implementation of DQ-DHT over a k-ary DHT and analyzes its performance in terms of search time and generated number of messages in different configuration scenarios.
Place, publisher, year, edition, pages
USA: Springer , 2008, 1. , 12 p.275-286 p.
Computer and Information Science
IdentifiersURN: urn:nbn:se:ri:diva-22921DOI: 10.1007/978-0-387-09457-1_23ISBN: 978-0-387-09456-4OAI: oai:DiVA.org:ri-22921DiVA: diva2:1042486