Improving the dependability of prefix-based routing in DHTs

Sabina Serbu, Peter Kropf & Pascal Felber

Résumé Under frequent node arrival and departure (churn) in an overlay network structure, the problem of preserving accessibility is addressed by maintaining valid entries in the routing tables towards nodes that are alive. However, if the system fails to replace the entries of dead nodes with entries of live nodes in the routing tables soon enough, requests may fail. In such cases, mechanisms to route around failures are required to increase the tolerance to node failures. Existing Distributed Hash Tables (DHTs) overlays include extensions to provide fault tolerance when looking up keys, however, these are often insufficient. We analyze the case of greedy routing, often preferred for its simplicity, but with limited dependability even when extensions are applied. The main idea is that fault tolerance aspects need to be dealt with already at design time of the overlay. We thus propose a simple overlay that offers support for alternative paths, and we create a routing strategy which takes advantage of all these paths to route the requests, while keeping maintenance cost low. Experimental evaluation demonstrates that our approach provides an excellent resilience to failures.
Mots-clés fault tolerance, reliability, DHT, routing
Citation S. Serbu, et al., "Improving the dependability of prefix-based routing in DHTs," in On the Move to Meaningful Internet Systems 2007: CoopIS, DOA, ODBASE, GADA, and IS, Vilamoura, Portugal, 2007, p. 206-225.
Type Actes de congrès (Anglais)
Editeur Robert Meersman, Zahir Tari
Nom de la conférence On the Move to Meaningful Internet Systems 2007: CoopIS, DOA, ODBASE, GADA, and IS (Vilamoura, Portugal)
Date de la conférence 2007
Editeur commercial Springer-Verlag Berlin
Pages 206-225
URL http://dx.doi.org/10.1007/978-3-540-76848-7_14