Nodes in an ad-hoc network can easily run routing protocols designed for wired networks, provided the nodes contain proper protocol stacks. However, specific features like low bandwidth and high rates of interference present a design problem which is very different from routing in wired networks. A large body of research exists to tackle these specific issues.
Routing In Wireless Ad-Hoc Networks
Work on ad-hoc network routing started as early as the 70's with research on the DARPA PRNET project. Since then, numerous protocols have been developed that take into account the characteristics of wireless networks. Routing for wireless ad-hoc networks can generally be categorized as either table-driven (proactive) or on-demand (reactive) routing.
Table driven routing protocols attempt to maintain consistent up-to-date routing information about the distance to every other node in the network. These protocols react proactively by sending update messages in response to topology changes. Destination Sequenced Distance Vector Protocol (DSDV) and Wireless Routing Protocol (WRP) are two widely known table driven routing protocols for wireless networks. DSDV is based on the classic Bellman-Ford routing mechanism, in addition to which it uses sequence numbers to distinguish stale routes from new routes, thus avoiding the formation of loops. WRP, on the other hand avoids the "counting-to-infinity" problem by maintaining second-to-last hop information about every destination node. However, as shown in , table driven routing protocols that aim to maintain consistent information at all times usually suffer from high control overhead.
The IETF working group for Mobile, Ad hoc Networking (MANET) has provided impetus for routing protocols in ad-hoc networks. Most of the routing protocols proposed in the MANET working group are on-demand routing protocols. On-demand routing protocols were designed with the aim of reducing control overhead, thus increasing bandwidth and conserving power at the mobile stations. These protocols limit the amount of bandwidth consumed by maintaining routes to only those destinations for which a source has data traffic. Therefore, the routing is source-initiated as opposed to table-driven routing protocols that are destination initiated. Most on-demand routing protocols do non-optimum routing, i.e., a route does not necessarily have to be the shortest path from a source to a destination in order to be used for forwarding packets; a route is used as long as it is valid. This feature also reduces control overhead.
There are several recent examples of the on-demand routing approach. These examples include 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). The routing protocols differ on the specific mechanisms used to disseminate flood-search packets and their responses, cache the information heard from other nodes' searches, determine the cost of a link, and determine the existence of a neighbor. However, all the on-demand routing proposals use flood search messages that either: (a) give sources the entire paths to destinations, which are then used in source-routed data packets (e.g., DSR); or (b) provide only the distances and next hops to destinations, validating them with sequence numbers (e.g., AODV) or time stamps (e.g., TORA).
Issues Specific To Wireless Ad-Hoc Networks
Five key issues need to be addressed when designing a routing solution for wireless ad-hoc networks. First, changes in topology may cause a routing protocol to create permanent loops in its tables. A classic example of this is the permanent looping caused in Routing Information Protocol (RIP). When a loop is formed, data packets keep traversing the loop, causing congestion and using up resources like buffer space and link bandwidth. A wireless network running an algorithm that does not prevent permanent loops is even more susceptible because of the high rate of topology change. A by product of congestion is the reduction of battery life of routers, causing partition of the network in extreme cases.
Second, with most of today's on-demand routing protocols, when a destination fails or becomes unreachable from a network component, a source trying to obtain a path to the destination finds that its flood-search for the destination fails, but is unable to determine whether or not it should start another flood search. The search could have failed simply due to temporary link failures induced by fading or node mobility, for example. There are no inherent mechanisms in these on-demand routing protocols that would prevent a source from repeating its search in the event that the destination is not reachable, which we call the searching-to-infinity problem. This problem also makes the (wired or wireless) network running an on-demand routing protocol susceptible to a unique form of attack, where a malicious router can indefinitely query a network for a destination that does not exist, thus causing congestion due to queries. Consequently, external mechanisms are used today 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 must implement a hold-down time after a search fails; however, 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 addition, each source must go through the process independently.
Third, solutions that depend on sequence numbers to maintain loop-freedom (AODV) or prevent searching to infinity (TORA) are usually not fault-tolerant. When a node fails and restarts, it resets its sequence number and this will lead to a situation where its updates are discarded until the sequence number catches up to the highest advertised value. Given that there will be higher rates of node failures in ad-hoc networks, it is imperative that a routing solution should not stop working when nodes fail.
Fourth, wireless networks suffer from low bandwidth and high rates of interference. To conserve on precious bandwidth, routing protocols should generate as few updates as possible. Mobility also increases the bandwidth used for control packets. As links go up and down frequently, more updates need to be sent to maintain correct topology information. When congestion due to control overhead increases, the convergence time of the routing algorithm increases, causing more and more data packets to travel along wrong paths and waste more bandwidth. Therefore, bandwidth efficiency is very important in wireless networks. Higher bandwidth efficiency results in higher battery life.
Lastly, as the number of multimedia applications increases, quality of service metrics like delay and jitter become important issues in wireless networks. Multipath routing has been shown as a favorable alternative both for circuit switched and packet switched networks as it provides an easy mechanism to distribute traffic, balance network load as well as increase probability of delivery. These protocols use table-driven routing algorithms (link state or distance vector) to compute multiple routes. On-demand routing protocols lend themselves very naturally to multipath routing because the route discovery process can be tuned to return multiple paths and hence are key to QoS routing in ad-hoc wireless networks.
Organization Of Thesis
Our aim in this thesis is to design protocols that specifically tackle issues encountered in wireless networks. The first design issue we tackled was the "searching to infinity" problem. We designed the Routing On-Demand Acyclic Multipath Protocol (ROAM), which is the only on-demand routing protocol that tackles the searching to infinity problem and has correct behavior in the presence of network partitions. ROAM uses only distances and internodal coordination to maintain loop-freedom at
all times. ROAM does not rely on sequence numbers and hence is inherently fault-tolerant. We also provide the first correctness proof for an on-demand routing protocol that does not allow searching to infinity. Our work on ROAM is presented.
On Demand Routing Using Diffusing Computations
Prior work in on-demand routing has followed three main approaches to ensuring that the routes obtained are free of long-term loops. Loops are formed when a router picks an upstream neighbor from it as the next hop towards a destination.
The Dynamic Source Routing (DSR) protocol is an example of using complete path information to avoid loops. In DSR, the network is flooded with queries when a source requests a search for a route to a destination. Finding a route results in a reply 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 put in the header of a data packet and this route is used to forward packets.
The ad-hoc on-demand distance vector routing algorithm (AODV) is an example of using sequence numbers to avoid long-term loops. In AODV, each destination maintains a sequence number that it updates every time there is a connectivity change with its neighbors. A router accepts those routes for a destination that are associated with the largest sequence number received for that destination. In turn, the destination always uses odd sequence numbers, and routers whose routes to the destination break increase the sequence number for the destination and 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. TORA uses a link-reversal algorithm to maintain loop-free multipaths that are created by a query-reply process similar to the above two algorithms. TORA relies on synchronized clocks to create timestamps that maintain the relative ordering of events.
Both AODV and DSR suffer from the "searching to infinity" problem which is described. TORA provides a solution for searching to infinity, but TORA uses logical synchronization which would not perform correctly in the presence of partitions unless clocks are sychronized across the network. This is a difficult requirement to fulfill in an ad-hoc network.
The work presented in this section introduces a new approach to the establishment and maintenance of loop-free routes on demand in either wireless networks or wired networks. We present the ROAM (Routing On-demand Acyclic Multipath) algorithm, which uses internodal coordination along directed acyclic subgraphs defined solely on the routers' distances to destinations. We call the operations used to coordinate nodes "diffusing computations". ROAM extends the diffusing update algorithm (DUAL) to provide routing on demand.
In ROAM, a search query in a connected component results in either the source requesting a route to a destination obtaining its answer, or all the routers determining that the destination is unreachable. Hence, ROAM eliminates the need for application-level mechanisms to prevent excessive flooding of searches in the event destinations are not reachable.