# Fault Tolerant DHT-Based Routing in MANET
## 4 Fault Tolerant DHT Network (FTDN)
### Network Dynamics  
FTDN measures physical network dynamics (connectivity/dis-connectivity) using the concept of critical node(s)/link(s) [25; 26] and adaptively makes arrangements (i.e., replicating data, partition detection, finding alternate paths avoiding the failed node(s), and reliable forwarding) in the logical networks to tolerate the faults. A node/link is said to be critical if its failure causes network partition. FTDN identifies critical nodes/links in a distributed manner by using k-hop common neighboring nodes. For example, as shown in Figure 3, the link(x,y) is said to be k-hop critical if its failure leaves node x and node y with disjoint k-hop neighboring nodes. For k = 1, the link(x,y) is 1-hop critical because 1-hop neighbors of node x and node y are disjoint. For k = 2, the link(x,y) is 2-hop critical, as there exist no common neighbors in the 2-hop neighbors of node x and node y. In this manner, the link(x,y) is considered a globally critical link because for k \(\geq\) 1 there exist no common neighbors at all. Likewise, node p in Figure 3 is globally critical because there exists no common neighbor for k \(\geq\) 1. If we increase the value of k then still there exist no common neighbors. Moreover, a globally critical node/link is always locally critical. Similarly, the failure of globally critical nodes triggers a partition event.  
FTDN employs a k-hop localized distributed algorithm and computes critical nodes/links using k-hop topological information. For this purpose, nodes need to exchange the list of their k-1 hop neighbors' information. In the simplest implementation (i.e., relying on the existing hello messages), nodes in the network periodically exchange the list of 1-hop physically connected neighbor nodes besides other information. In this manner, nodes attain 2-hop topological information. Formally, for a network G = (V, E), the neighborhood of a vertex v\(\in\)V is the induced subgraph of G consisting of all vertices adjacent to v and all edges connecting two such vertices. Similarly, the open neighborhood, N(v), of the vertex v consists the set of vertices adjacent to v excluding v, i.e., N(v) = {w\(\in\)N(v) :vw\(\in\) E} and the closed neighborhood of v is N[v] = N(v)\(\cup\)  
Figure 3: k-hop critical node/link scenario.  
Algorithm 1 computes critical nodes/links based on the localized knowledge available at nodes despite network-wide control information dissemination. For this purpose, (line: 1): nodes periodically exchange their open neighborhood in hello message. For any two adjacent nodes u and v across the link (u,v), node u and node v periodically exchange N(u) and N(v), respectively. (lines: 4-7): Node u and node v independently compare the exchanged lists, and if there exist common node(s), i.e., ( N[u]\(\cap\) N[v]\(\setminus\) (u, v))\(\
eq\){}, then node u and node v declare their status as non-critical (lines: 8-11): otherwise critical. The link between two critical nodes is treated as critical.  
```
0: Each node in the network exchanges the list of its 1-hop neighbors in the periodic hello message.
1: Each node u periodically broadcasts its closed neighborhood N[u] and waits to listen messages from other nodes
2:for each node u \(\in\)V in the network do
3:for each node v \(\in\)adj[u] do
4:if ( N[u]\(\cap\) (N[v]\(\setminus\)(u,v) == {}) then
5: STATUS (u) \(\leftarrow\) critical
6: STATUS (v) \(\leftarrow\) critical
7: link(u, v) \(\leftarrow\) critical
8:else if ( N[u]\(\cap\)(N[v]\(\setminus\)(u,v) \(\
eq\) {}) then
9: STATUS (u) \(\leftarrow\) noncritical
10: STATUS (v) \(\leftarrow\) noncritical
11:endif
12:endfor
13:endfor
```  
**Algorithm 1** Critical node/link detection