# Fault Tolerant DHT-Based Routing in MANET
## 4 Fault Tolerant DHT Network (FTDN)
### Address Publication  
The address publication and lookup query resolution play vital roles in DHT networks and define overall network performance. Similarly, the resolution of lookup queries with minimum possible delay is imperative for successful communication. However, network dynamics such as AN failure, network partition prohibit resolution of lookup queries and exacerbate the delay. We believe that effectively replicating index information during the address publication at appropriate locations (i.e., based on network dynamics) would guarantee successful resolution of lookup requests; further, it would help to reduce lookup delays. However, replication should be dynamic, distributed, and scalable with minimum possible cost.  
For this purpose, FTDN replicates index information in the address publication process across the critical regions (identified by Algorithm 1). FTDN performs replication and forwarding decisions at each node independently along the path to the intended AN using k-hop topological information (connectivity/dis-connectivity). Particularly, consider a newly joining node j; after computing LID node, j publishes and stores its index information (LID, UID pair) on AN. Node j determines its AN by applying a hash function over its UID, say v, generating a hashed value, say h(v), and stores index information on a node (i.e., A.N) with LID closest to h(v). For this purpose, node j broadcasts SMI (or SII) packets to be forwarded towards the intended AN. FTDN takes care of the SMI packets and replicates index information across all the critical links/nodes along the path to AN. If the actual AN fails/moves or the network gets partitioned, the index information remains accessible in the disjoint partitions, and nodes in the network could access node j's index information from the replicas despite the actual AN. Algorithm 2 performs replication decisions using k-hop topological information. (line: 1): when an SMI/SII packet is received at node (i.e., k). (lines: 2-3): If node k finds itself closest to the hash valued (i.e., intended AN) then node k stores the mapping information and starts acting as designated AN. (lines: 4-6): otherwise, if there exists another node (i.e., \(m\in\) N(k)) closest to the intended AN and if the link (k,m) is critical, then node k keeps a copy of mapping information and forwards SMI to m. lines (7-9): alternatively, the SMI is forwarded to node m without making any replica.  
```
0: When SII/SMI message is received at node k from a newly joining node j along the path to intended anchor node(AN), where N[k] and N(k) denote closed and open neighborhood of node k, respectively.
1: On the reception of SII/SMI at a node k from node j\(\in\)N[k]
2:if (\(\delta\)(k, h(v))= min\({}_{i\
eq j\in\) N[j]}(\delta(i,h(v))\)then
3:k\(\leftarrow\)SII
4:elseif (\(\exists m\in\) N(k) \(\delta\)(m, h(v)) = min\({}_{i\
eq j\in\) N(j)}(\delta(\), h(v))then
5:if ( N[u] \(\cap\) (N[v] \(\setminus\)(u,v) == \(\{\}\) ) then
6: Replicate SII at k and forward SII to m
7:else
8: Forward SII to m without making replica at k
9:endif
10:endif
```  
**Algorithm 2** Address Publication  
Impact on lookup: It is observed that the replication scheme significantly reduces lookup delays and improves lookup success ratio. The proposed address-publication targets critical regions (i.e., critical nodes/links) in the network, where these regions are more prone to failure (i.e., AN failure, partition, etc.); therefore, a trivial way is to replicate the index information across the critical regions so that index information would remain reachable despite actual AN fails or move/partition, etc. This ensures guaranteed access to index information in the adversarial environment and significantly improves the lookup success ratio with minimal delay. It is pertinent to mention that impact of the dynamic replication has been evaluated (using 3D and Chord structures) and found significant gains [25].