# Fault Tolerant DHT-Based Routing in MANET
###### Abstract
Address Publication/ Anchor Request: After computing LIDs, nodes store their index information, also called mapping information (i.e., (LID, UID) pair), by sending store mapping information (SMI) packets, at certain nodes in the network referred to as an anchor node (AN). A node determines its AN by applying a hash function over its UID and generates a hashed value, h(v). The hashed value h(v) is drawn from the same LS used to assign LIDs to nodes. For example, a node p would act as the AN for node q if either h(v) falls in the LSP of node p or node p's LID is closest to h(v), depending on the protocol specification. The SMI packet is unicasted in the logical network to node q, and node q stores index information for node p. (i.e., node q starts acting as a designated AN for node p). The address publication process is shown in Figure 1, dotted line in the figure represents the address publication process. 3. Lookup phase and actual data forwarding: To send a data packet, a source node s retrieves the destination node q's LID from q's AN, i.e., node p, (Flow 1 and Flow 2 in Figure 1 shows the lookup process). For this purpose, node s applies a hash function over q's UID that gives the LID of node q's AN, i.e., node p. Based on the computed LID, node s sends a mapping request message (MREQ) towards node p forwards to get the index information of node q. Upon receiving the index information of node q on the mapping reply message (MREP), node s then sends the data packet towards node q based on the node q LID; Flow 3 in Figure 1 shows data packet routing. Greedy forwarding is used in the logical, structured network, i.e., the neighbor with the closest LID to the intended destination node is selected as the next hop. However, successful resolution of lookup queries, with minimum possible delay, is imperative for optimal network performance. The terms used in the paper are defined in Table 1.  
In DHT networks, logical network construction, address publication, and lookup processes are the main factors and define overall network performance. Therefore, sophisticated techniques are needed to keep the system in function, especially in the adversarial environment offered by MANETs. MANETs are entirely self-organized, mobile, distributed, and infrastructure-less networks. Nodes in the network with limited transmission ranges use wireless broadcasting mechanisms in a multi-hop fashion to achieve end-to-end connectivity. Limited radio range, mobility, faulty nodes, and lack of infrastructure introduce frequent and unpredictable changes to network topology, i.e., connectivity/dis-connectivity (can cause occasional nodes failures, network partition, frequent merging, etc.). Therefore, an end-to-end path that is believed optimal at a given time might not be available just after a moment. The case is more severe in DHT networks, where a logical, structured network is built over the ad hoc physical topology, and routing needs an evenly distributed and connected logical network. Similarly, access to the index information stored at ANs (i.e., lookup queries resolution) is imperative for successful routing. Another correlated problem is the longer lookup delay in DHT routing, where network dynamics significantly exacerbate the delay. Furthermore, frequent merging is common in MANETs, but DHT needs extra effort to merge logical structures/LSs (i.e., LIDs reconfigurations, etc.) in a distributed manner. The impact of network dynamics on DHT networks with a detailed explanation is discussed in Section 2. It is worth mentioning that the problem of fault tolerance, in the context of DHT networks, has not yet been fully explored. There exist no explicit and direct solutions to the problem. To the best of author's knowledge, existing DHT-based routing protocols in MANETs [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18] mainly consider routing and resilience of the address spaces used.