Faculté des sciences

Fault-Tolerant P2P Networks: How Dependable is Greedy Routing

Serbu, Sabina ; Kropf, Peter ; Felber, Pascal

In: Workshop on Dependable Application Support in Self-Organising Networks (DASSON'07), 2007, p. 1

Under churn, the problem of preserving accessibility is addressed by maintaining valid entries in the routing tables towards live nodes. However, if the system fails to replace the entries of dead nodes with entries of live nodes soon enough, requests may fail. In such cases, mechanisms to route around failures are required to increase the tolerance to node failures. Existing DHTs include... Plus

Ajouter à la liste personnelle
    Summary
    Under churn, the problem of preserving accessibility is addressed by maintaining valid entries in the routing tables towards live nodes. However, if the system fails to replace the entries of dead nodes with entries of live nodes soon enough, requests may fail. In such cases, mechanisms to route around failures are required to increase the tolerance to node failures. Existing DHTs include extensions to provide fault tolerance when looking up keys, however, these are often insufficient. We analyze the case of greedy routing, which is a routing algorithm that is preferred for its simplicity, however with limited dependability even when extensions are applied. The main idea is that fault tolerance aspects need to be dealt with already from the design of the overlay. We 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.