# Fault Tolerant DHT-Based Routing in MANET
## 2 The Problem and Its Scope  
Generally in MANETs, existing literature [19; 20; 21; 22; 23] on the fault tolerance (an overview is provided in Section 3) targets the node(s) failure problem and assumes that a subset of nodes in the network fail. The routing process avoids such faulty nodes and makes packet delivery possible. The existing solution domain is based on the design philosophies of detection, avoidance, and redundancy. The employed mechanisms detect faulty nodes and avoid such nodes in the routing process. Similarly, in redundancy-based mechanisms, multiple routes are maintained between a source and destination pair, where a stable path, i.e., having no faulty nodes, is selected for routing. However, the case is different in DHT networks where a logical, structured network is built and maintained over the underline ad hoc physical topology. The relationship between the physical network and the logical network is tight. In other words, a change in the physical network has an associated impact on the logical, structured network. Similarly, node failure has an associated impact on the logical, structured network. For example, a single fault in the physical topology is directly associated with the loss of index information (if AN fails, AN holds index information), logical network partition (i.e., LS loss and disrupted LSs in the created instances), and indirectly with merging. These problems halt communication entirely and need to be addressed for optimal network performance. We further explore the problem in DHT networks. Our findings are summarized as below:  
* Existing solutions for the fault tolerance problem are purely designed for flooding-based infrastructure-less MANET and are not applicable in DHT-based MANET. * We found that existing solutions [19; 20; 21; 22; 23], including multi-path routing, blindly assume a fault ratio and do not investigate the failure (as not needed). However, in a DHT network, a node failure causes two different events: (i) occasional node failure without creating a partition, alternate paths avoid the failure, and routing processes should avoid the failure in forwarding decisions. Moreover, in (ii) node failure causing network partition, there exist no alternate paths at all. Similarly, both events have a different associated impact on the DHT network. For example, in case of event (i) if the failing node is AN, then the corresponding mapping information remains unreachable. Similarly, in case (ii), node failure would cause loss of mapping information and leave unevenly distributed and disrupted LSs (logical networks) in the disjoint instances. This halts communication in the disjoint partitions. Therefore, mechanisms are needed to detect and differentiate such events in DHT networks. Algorithms 3 and 4 address the problems using k-hop topological information, respectively. * Lookups and AN failure: In the lookup phase, source nodes retrieve routing information stored on ANs to initiate a data session with destination nodes. The lookup request initiated by the source node is routed towards intended ANs in the network. The designated AN resolves the query by forwarding the required routing information. Therefore, successful lookup resolution, with minimum possible delay, is imperative in DHT-based routing. Moreover, DHT inherently suffers from longer lookup delays in the lookup phase. However, network dynamics prohibit lookup resolution and introduce massive delays. For example, in the case of AN failure (due to occasional node failure or network partition), the mapping information is lost, and corresponding lookup queries would not be entertained. The requesting party will keep trying to resolve the query, even the AN is no longer available. This causes the failure of lookup and introduces massive lookup delays and overhead. A similar situation arises, for example, when a source and destination pair remains in one partition, and the corresponding AN resides in a disjoint partition after the network gets partitioned.