# Fault Tolerant DHT-Based Routing in MANET
## 4 Fault Tolerant DHT Network (FTDN)
### Logical Network Construction/LIDs Assignment and Key-Invariants  
For logical network construction (i.e., LIDs assignments), we are using existing algorithms in [14]. In network bootstrapping, joining nodes compute L-bit LIDs and build a virtual rooted binary tree, T(r), r represents the root of the tree, a node with the most miniature LID in the network is chosen as a root node in the tree. The L-bit longer LID forms a complete binary address tree with L + 1 levels. All the leaves remain at the same level in the address tree, and each inner vertex carries zero or two children. The leaves nodes represent the actual node (i.e., complete address), and the inner nodes, at a certain level, represent sub-trees (i.e., set of addresses with common prefix), as depicted in Figure 2. In general, an inner vertex in the address tree at a level-k represents a level-k sub-tree. The level-k sub-tree represents a set of network addresses/leaves (i.e., nodes) sharing a common prefix of (L-k) bits. A node can have at most L subtrees. Each node in the network belongs to one of these sub-trees(siblings). Similarly, all nodes that belong to a sub-tree share a common prefix. For example, a tree T(x), rooted at x, is shown in Figure 2, node x has different sub-trees at each level, for example, at level-0 the sub-tree is S\({}_{0}\)(x) = {000}, i.e., contains a single leaf node (node x by itself), level-1 sub-tree is S\({}_{1}\)(x) = {001}, level-2 is S\({}_{2}\)(x) = {010, 011} and level-3 sub-tree S\({}_{3}\)(x) = {100, 101, 110, 111}. Each sub-tree at a certain level share a common prefix, i.e., (L- k) bits, for example, nodes in S\({}_{1}\)(x), S\({}_{2}\)(x) and S\({}_{3}\)(x) have common prefixes 00x, 0 xx and 1 xx, respectively. Furthermore, in the binary address tree a level-k sub-tree can have at most two level-(k-1) sub-trees. The logical network construction algorithm (i.e., the address tree) preserves physical proximity and maintains a key invariant property called prefix sub-graph constraint. Key-invariant: Adjacent nodes in the logical network (i.e., address tree) share a common prefix and represent a connected sub-graph in the physical topology. In other words, non-empty adjacent (i.e., with common prefix) sub-trees must be connected in the physical topology. Formally, for a connected network, G = (V, E) with the address tree, T(x), rooted at x; there must be nodes, say, (i\(\,\)j \(\in\) V) where i\(\in\)S\({}_{k}\)(x) and j\(\in\)S\({}_{k-1}\)(x) such that (i,j)\(\in\)E, where  
\[\{\;\exists\;\text{i and j where i}\in\;\text{S}_{k}\text{(x)}\;\wedge\;\text{j }\in\;\text{S}_{k-1}\text{(x)}\;\;\mid\;\text{(i,j)}\in\;\text{E}\;\}\]  
If the prefix subgraph constraint violates, disjoint instances of the address tree (i.e., network partition) would exist. FTDN exploits the key invariant and physical topological information (i.e., critical/non-critical nodes) and makes arrangements to detect the partition event (i.e., prefix subgraph constraint violation event) and differentiate between occasional node failure and partition. The key-invariant and the topological information play a vital role in finding alternate routing paths avoiding the failing nodes (i.e., occasional nodes failure without causing network partition), see Section 4.4 for detail. Routing: FTDN exploits logical distances in the logical network and performs the forwarding decisions. For this purpose, a distance, \(\delta\), function based on Longest Common Prefix (LCP) match is used. The distance function \(\delta\)(x,y) = L-LCP(x,y) computes logical distance (in terms of bits) and identifies the most significant bit that differs between the current node and the destination. Then, the next hop is determined by looking up the  
Figure 2: The Address tree. routing entry at the identified index (sub-tree) and packets are sent there, where L represents a total number of address bits used in the LIDs assignment.