# Fault Tolerant DHT-Based Routing in MANET
## 4 Fault Tolerant DHT Network (FTDN)
### Merging Detection and Merging  
As discussed in Section 2, merging physical topologies causes physically connected but logically independent networks; routing is performed on the logical structure (i.e., tree). Therefore, extra effort is needed for merging the disjoint logical structures (i.e., trees); merging logical networks should produce an evenly distributed LS (a connected logical network, i.e., a single-rooted tree ). Therefore, the merging process should consider measures such as LIDs reconfiguration and new root election, etc. Moreover, a smooth network working needs an evenly distributed LS (i.e., single root with the most miniature LID where all other (n-1) nodes LIDs form the sibling trees), how to merge two disjoint LSs (i.e., sub-trees) into an evenly distributed LS (i.e., singly connected rooted tree) with minimum cost is a challenging issue.  
FTDN maintains root and rank information on every node in the network. FTDN exploits the existing periodically exchanging hello messages; the hello message contains root LID and rank value beside other information. If nodes across the network find different root LIDs in the periodic hello messages, nodes trigger merging detection events, and the actual merging process is initiated. Timely detection of merging detection events is needed to start a smooth merging process. The rank metric makes the merging process more efficient and cost-effective. Rank is an upper bound on the size of the rooted binary tree, and nodes compute rank value independently. Rank = (2h+1-1), h = L (height of the tree or address length, i.e., number of occupied address bits, excluding unused bits) is tree height. Similarly, the root node LID in a tree acts as representative/identity of a network, i.e., tree.  
Merging: The merging process should produce an evenly distributed single-rooted tree with minimal cost. FTDN merges the smaller tree with the more extended tree. In other words, nodes belong to the smaller tree re-compute LIDs and correspondingly update root and rank information. Merging a smaller tree with the longer one makes the process cost-effective (i.e., would cause minimum possible reconfiguration cost). For this purpose, FTDN exploits the rank information and performs rank-based merging causing at most log(n) reconfiguration operations, i.e., re-computing LIDs, updating root and rank information. Algorithm 5 performs merging detection and merging process in a distributed manner. The hello messages carrying root, rank, etc., information are periodically exchanged by the nodes in the network. (Lines: 2): If a node u discovers a node v with a different root LID, node u perceives a merging detection event. Furthermore, (Lines: 3-8): a rank-based merging process is initiated where nodes in the smaller tree change LIDs, root, and rank information.  
Rank-based merging significantly reduces reconfiguration costs. Since the ranks make sure to merge the smaller tree with the more enormous tree, smooth merging causes at most \(\log(n)\) operations (LIDs to be updated) for n number of nodes, particularly, consider a node x in the network, each time node x's LID was updated by the algorithm x must be in the smaller tree (due to rank metric). Therefore, the first time update in x's LID would cause a tree to have at least two nodes. Similarly, a subsequent update (i.e., LID are only updated in the merging process) in the x's LID at least double the size of nodes in the resulting tree, i.e., four nodes. In a tree implementation, at most \(\log(n)\), total union operations are needed to merge n number of nodes. Therefore, most \(\log(n)\) operations are needed to perform a smooth merging by the algorithm. In an arbitrary merging or blind merging (i.e., not ranked base), there can be at most \((n-1)\) merging events to unite n number of nodes, and at most \(\mathrm{O}(n^{2})\) operation would be required for reconfiguration/LIDs updates. In other words, at most \(\log(n)\) nodes would require reconfiguring LIDs.