TPT-C: A Heuristic-Based Cache to Improve Range Queries over DHTs

Distributed Hash Tables (DHTs) provide the substrate to build large scale distributed applications over Peer-to-Peer networks. A major limitation of DHTs is that they only support exact-match queries. In order to offer range queries over a DHT it is necessary to build additional indexing structures. Prefix-based indexes, such as Prefix Hash Tree (PHT), are interesting approaches for building distributed indexes on top of DHTs. Nevertheless, the lookup operation of these indexes usually generates a high amount of unnecessary traffic overhead which degrades system performance by increasing response time. In this paper, we propose a novel distributed cache system called Tabu Prefix Table (TPT-C), aiming at improving the performance of the Prefix-trees. We have implemented our solution over PHT, and the results confirm that our approach outperforms traditional existing cache solutions for prefix-tree structures.Les tables de hachage distribuées (DHT pour Distributed Hash Table) sont un support efficace pour développer des applications à grande échelle sur des réseaux pair-à-pair. La principale limitation des DHT est leur faible pouvoir d'expression. Elles ne supportent que des requêtes pour localiser une information à partir de son identifiant exact. Pour offrir des requêtes par intervalle, il est nécessaire d'ajouter aux DHT des structures d'indexation. Les index par préfix tel que l'arbre de hachage par préfix (PTH pour Prefix Hash Tree) sont une approche intéressante pour construire des index sur des DHT. Cependant, les opérations sur ces index génèrent généralement un trafic important qui dégrade les performances du système et augmente les temps de réponse des requêtes. Dans cet article, nous proposons un nouveau cache distribué appelé Tabu Prefix Table (TPT-C) pour améliorer les performances des arbres de préfix. Nous avons développé notre solution sur PHT et les résultats confirment que notre approche améliore les solutions de cache proposées précédemment sur PHT