This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.
Ad-hoc network's nodes can easily run routing protocols planned for wired networks, given the nodes contain proper protocol stacks. Nevertheless, special features like low bandwidth and high rates of interference present a design problem and this design problem is very dissimilar from routing in wired networks. A huge body of research persists to undertake these specific issues.
1.1 Routing in wireless ad-hoc networks
Move on ad-hoc network routing started early 70's with research on the DARPA PRNET project [14, 46, 30]. Since then, they developed numerous protocols that take into account the properties of wireless networks. Wireless ad-hoc networks routing can be categorized into either table-driven (proactive) routing or on-demand (reactive) routing.
Table driven routing protocols are used to maintain up-to-date routing information about the distance to every other node in the network. According to topology changes these protocols react anticipatory by sending updated messages. Destination Sequenced Distance Vector Protocol (DSDV)  and Wireless Routing Protocol (WRP)  are two famous table driven routing protocols for wireless networks. DSDV is based on the classic Bellman-Ford routing mechanism , in adjunct to Bellman-Ford routing it uses sequence numbers to differentiate stale routes from new routes, in this manner avoiding the formation of loops. WRP, on the other hand avoids the "counting-to-infinity" problem by asserting second-to-last hop information about every destination node. However, as shown in , table driven routing protocols that aim to assert compatible information at all times regularly suffer from high control overhead.
The IETF working group for Mobile, Ad hoc Networking (MANET) has provided stimulation for routing protocols in ad-hoc networks. Almost on-demand routing protocols are MANET working group. On-demand routing protocols were implemented with the aim of decreasing control overhead, accordingly increasing bandwidth and preserving power at the mobile stations. These protocols bound the amount of bandwidth taken by maintaining routes to only those destinations for which a source has data traffic. As a result, the routing is source-initiated as opposed to table-driven routing protocols and these are destination initiated. Most of these on-demand routing protocols do non-optimum routing, that means a route doesn't have to be the shortest path from a source to a destination in order to be used for forwarding packets; a route can be used as long as it is valid. The control overhead will be reduced by this feature.
Now there are various recent examples on on-demand routing approach. The Ad-Hoc On-Demand Distance Vector (AODV), Associativity Based Routing (ABR), Dynamic Source Routing (DSR) , Temporally Ordered Routing Algorithm (TORA)  and Zone Routing Protocol (ZRP)  are comes under these examples. The routing protocols are un similar to the specific vitalism used to circulate flood-search packets and their responses, cache the information heard from other nodes' searches, calculate the cost of a link, and finding the existence of a neighbor. nevertheless, all the on-demand routing proposals use flood search messages, which are either: (a) give sources the whole paths to destinations, which are after used in source-routed data packets (e.g., DSR); or (b) producing only the distances and next hops to destinations, and they are validated by sequence numbers (e.g., AODV) or time stamps (e.g., TORA).
1.2 Issues specific to wireless ad-hoc networks
To design a routing solution for wireless ad-hoc networks we need five key issues. First, changes in topology could leads to routing protocol to create permanent loops in its tables. The permanent looping caused in Routing Information Protocol (RIP) is a considerable example. Data packets keep passing across the loop when the loop is formed, leading overcrowding and using up resources like buffer space and link bandwidth. Because of the high rate of topology change a wireless network running an algorithm cannot prevent permanent loops are more susceptible. A byproduct of overcrowding is the decrease of battery life of routers, leading to partition of the network.
Secondly, most of on-demand routing protocols, when a destination fails or becomes unreachable from a network component, the flood-search for the destination fails when a source trying to obtain a path, but is unable to decide that it should or shouldn't start another flood search. The search might have failed simply because of temporary link failures induced by fading or node mobility, for example. There are no inherent methods in these on-demand routing protocols that may prevent a source from repeating its search in the event that the destination is not reachable, which is called searching-to-infinity problem. This problem also makes the (wired or wireless) network running an on-demand routing protocol impressionable to a unique form of attack, where a malicious router can inexactly query a network for a destination which does not exist, accordingly causing congestion due to queries. As a result, external mechanisms are used now in order to stop sources from sending unnecessary queries. In DSR and AODV, routers do not keep state about the search queries in progress, and the application accessing the on-demand routing service should implement a hold-down time after a search fails; nevertheless, just as is the case in Cisco's IGRP, it is difficult to determine an adequate length of hold-down time or how many times a source should persist requesting a path to a destination. In supplement, every source has to go through the process independently.
Thirdly, the solutions that rely on sequence numbers to maintain loop-freedom (AODV) or prevent searching to infinity (TORA) are not fault-tolerant. When a node fails and restarts, it resets its sequence number and it leads to a situation where its updates are get rid of until the sequence number catches up to the highest advertised value. Mentioned that there will be higher rates of node failures in ad-hoc networks, it is absolutely necessary that a routing solution should not stop working when nodes fail.
Fourthly, wireless networks suffer from low bandwidth and high rates of interference. To gain on valuable bandwidth, routing protocols has to generate few updates as possible. Mobility also increases the bandwidth used for control packets. To maintain correct topology information more updates have to be sent when links go up and down regularly. The convergence time of the routing algorithm increases when congestion due to control overhead increasing and leads to more and more data packets to travel along wrong paths and waste more bandwidth. As a result, bandwidth efficiency is very important in wireless networks. Higher bandwidth efficiency needs to get higher battery life.
Lastly, the quality of service metrics like delay and jitter become important issues in wireless networks when the number of multimedia applications increases. Multipath routing has been shown as a favorable alternative both for circuit switched and packet switched networks as it provides an easy mechanism to dispense traffic, balance network load as well as increase probability of delivery. These protocols use table-driven routing algorithms to find multiple routes. On-demand routing protocols contribute themselves very naturally to multipath routing because the route discovery process could be tuned to return multiple paths and hence are key to QoS routing in ad-hoc wireless networks.
1.3 Organization of Thesis
My target in this thesis is to design protocols that specifically handle issues encountered in wireless networks. The first design issue I handled was the "searching to infinity" problem. I designed
The Routing On-Demand Acyclic Multipath Protocol (ROAM), which is only on-demand routing
Protocol that handles the searching to infinity problem and has correct behavior in network
Partitions. ROAM uses only distances and internodal coordination to maintain loop-freedom at all
times. ROAM doesn't depends on sequence numbers so its inherently fault-tolerant. For not allowing searching to infinity we provided the first correctness proof for an on-demand routing
protocol. My work on ROAM is presented in Chapter2.
On demand Routing using Diffusing Computations
Prior work in on-demand routing has followed three main techniques or approaches to ensure that these routes obtained are free of long-term loops. When a router picks an up-stream neighbor as the next hop towards a destination, then the loops are formed.
The Dynamic Source Routing (DSR) protocol  is an example of using entire path info to avoid these loops. In DSR, the network is flooded with questions or queries when a source requests a search for a route to a destination. Finding a route will result in a packet being sent back in a route reply packet and the resultant routes are stored in a route cache at the sender. The entire route is then put in the header of a picketed data and this route is used to forward packets.
The ad-hoc on-demand distance vector routing algorithm (AODV) is an example of using sequential numbers to avoid loops in the long-run. In AODV, each and every destination maintains a sequence number, which updates every time when there is a connectivity change with its neighbor. The router accepts these routes for a destination that are associated with the largest sequence number received for that destination. In turn, the odd sequence numbers are used by these destinations, and the routers whose routes to the destination break increase these sequence number for the destination and in turn it report an infinite distance to it. AODV uses a query flooding technique similar to DSR.
The Temporally-Ordered Routing Algorithm (TORA)  is an example of using time stamps and internodal coordination to avoid looping. This method uses a link-reversal algorithm  to maintain loop-free multi-paths which are created by a query reply process similar to the above two algorithms and it relies on synchronized clocks to create timestamps that maintain the relative ordering of events.
Both AODV and DSR suffer from a problem called the "searching to infinity", which is described in Chapter 1. TORA provides a solution for searching to infinity, but this method uses logical sync that may not perform correctly in the presence of partitions unless clocks are synchronized across the network. This was the most hardest requirement to fulfill in an ad-hoc network.
The work presented in this section introduces a new approach to establish, maintenance of loop-free routes on demand in either of wireless or wired networks. We present the ROAM (Routing On-demand Acyclic Multipath) algorithm , which uses internodal co-ordination along with directed acyclic sub graphs that defined solely on the routers' distance to destination. We call the operations used to coordinate nodes "diffusing computations". The diffusing update algorithm (DUAL)  is used by ROAM to extend the provide routing on demand.
A search query in ROAM, in a connected component results in either the source requesting a route to a destination obtaining its answer, or with all the routers in determining if the destination is unreachable. Thus, ROAM eliminates the need of application-level operations to prevent excessive flooding of searches in the event destinations are not reachable.