# Fault Tolerant DHT-Based Routing in MANET
## 4 Fault Tolerant DHT Network (FTDN)
### Partition Detection and Occasional Node Failure  
A leaving/faulty node can cause two important events, i.e., partition detection and occasional node failure events. How to detect and differentiate these events need knowledge about network dynamics; we exploit network dynamics (critical/non-critical node/links) and the key-invariant property to effectively detect/differentiate these events.  
CASE-I: Occasional node failure or node failure w.o.t causing partition (Finding alternate path avoiding the failed node)  
FTDN uses a cross-design approach and finds alternate routing paths avoiding the failed node. Specifically, we consider logical network knowledge (i.e., key invariant property) and physical network connectivity information (i.e., critical/non-critical status). The cross-layer design approach finds and ensures a guaranteed available alternate path avoiding the failed node. FTDN finds an alternate path without creating any extra overhead and relies on the existing periodic hello messages. The parameters (i.e., key invariant and critical/non-critical) are computed independently at each node without any network-wide control information dissemination.  
Key idea: if the leaving/fail node is non-critical, then there exists an alternate route in the physical network to reach across the failure, i.e., bypass the faulty node. Particularly, if an adjacent node u of a node v fails/moves, this would result in two rooted sub-trees in the logical network, i.e., T(r) and T(u). Node u and its siblings share a common prefix by the key invariant property and form a connected sub-tree rooted at node u, i.e., T(u). FTDN investigates the failure further in the physical topology using k-hop topological information and checks node u status as critical/non-critical. In occasional node failure (contrast to partition detection event), node v will find node u as non-critical; therefore, there exist common neighbors (i.e., in other words, there exist alternate paths avoiding the failure to reach nodes in T(u)). Algorithm 3 (lines: 3-5): finds such common neighbors and selects an appropriate next hop, k\(\in\)T(u). If there exist more than one common neighbor, the neighbor closest to the intended destination is chosen based on the logical distance in the logical network, i.e., k \(\in\) ( N(u) \(\cap\) N(v) 1(u,k) \(\in\) E \(\wedge\) \(\delta\)(k, d) = min\({}_{\text{j}\in\) N(u)\(\cap\) N(v) (\(\delta\)(j, d))).  
```
1:for each node v \(\in\) G do
2: u = v.nexthop()
3:if (N[u]\(\cap\)(N[v]\(\setminus\)(u,v) \(\
eq\) {}) then
4: return k\(\in\)(N(u)\(\cap\) N(v) 1(u,k)\(\in\) E \(\wedge\)\(\delta\)(k, d)=min\({}_{\text{j}\in\) N(u)\(\cap\) N(v) (\(\delta\)(j, d)))
5:endif
6:endfor
```  
**Algorithm 3** failure_handler(u,v,d) [Finding alternate path avoiding the failure]  
The key invariant property and network dynamicity measurement (i.e., critical/non-critical) confirm the guaranteed availability of node k. FTDN finds alternate paths and bypasses the failing node in a fully distributed manner. As shown in Figure 4, nodes compute LIDs and form a logical tree over the Adhoc physical topology using the joining algorithm [14]. For instance, if the link(c,d) fails, node c finds node d as non-critical (since there exists a common neighbor, i.e., node e) and by the key-invariant node e and node d share a common prefix (i.e., 10x) thus form a connected subtree. In this manner, the proposed algorithm returns node e as the next hop to reach the subtree across the failure.