Implementing dynamic querying search in k-ary DHT-based overlays

Trunfio, Paolo and Talia, Domenico and Ghodsi, Ali and Haridi, Seif (2008) Implementing dynamic querying search in k-ary DHT-based overlays. In: Grid Computing: Achievements and Prospects. Springer, USA, pp. 275-286. ISBN 978-0-387-09456-4


Official URL:


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.

Item Type:Book Section
ID Code:3454
Deposited By:Seif Haridi
Deposited On:30 Jan 2009
Last Modified:18 Nov 2009 16:22

Repository Staff Only: item control page