The role of the network layer is to route packets to their intended destinations. In a traditional network, a node implements a routing table that maps the destination address of a packet to a rule for forwarding that packet. In a wired network, the routing table specifies the outgoing link on which to forward a packet. In a wireless network in which the physical medium is a broadcast channel, the routing table may specify the intended next recipient of a packet.
In wired networks, link topology changes are infrequent and routing tables tend to be fairly static. This is reinforced by the use of policy-based routing in which the routing of packets depends on negotiated agreements among the operators of autonomous systems [51].
By contrast, wireless networks enable node mobility which can induce a stochastic process of link connection and disconnection. In response, mobile ad hoc networks implement specialized routing algorithms in the network layer [88, 147] that adapt to these frequent topology changes. These routing algorithms have been the starting point for mobile networking research. Changes in wireless link topology result in frequent routing table updates and necessitate distributed algorithms for route discovery and route repair, as well as appropriate metrics for choosing efficient routes.
In the mobile networking community, Dynamic Source Routing (DSR) [88] and Ad hoc On-demand Distance Vector (AODV) [147] routing have emerged as de facto standards for mobile network routing. Each has open-source implementations for linux [30, 42, 129, 155] and the ns-2 simulator [8, 21, 130, 177]. Both protocols implement route discovery, route caching, and route maintenance in response to time variations in link connectivity. The protocols differ in how the routing information is stored. Here we describe these protocols in detail to convey the complexity of the task, even if the network is limited to store-and-forward operations. We start with DSR and then describe how AODV differs.
DSR
DSR is a source routing protocol that adds to each data packet a header specifying the complete route (a sequence of nodes) that the packet must follow to the destination. Each mobile node maintains a cache that holds source routes that it has learned. When a node wants to send a packet to another node, it first checks its route cache for a source route to the destination. If no route is found, the source will invoke the route discovery procedure.
A node initiating route discovery (called the initiator) broadcasts a route request (RREQ) packet which may be received by those nodes within range. The RREQ packet identifies the intended destination, referred to as the target node and contains a unique request id set by the initiator from a locally maintained sequence number. In addition to the addresses of the initiator and target of the request, each RREQ packet contains a route record, the accumulated sequence of hops taken by the RREQ packet as it is forwarded.
When a node receives a RREQ packet, it processes the request according to the following steps:
• If the pair (initiator address, request id) of the RREQ packet is found in this node’s list of recently seen requests, the request is discarded. This removes later copies of the request that arrive at this node by alternate routes.
• If this node’s address is already in the route record, the RREQ packet is discarded. This guarantees that no single copy of the request can propagate around a loop.
• If the target of the request matches this node’s own address, then the route record contains the route from the initiator by which the request reached this node. In this case, this node returns a copy of this route in a route reply (RREP) packet to the initiator.
• If this node has a route cache entry for the target, it appends this cached route to the accumulated route record in the packet, and returns this route in a RREP packet to the initiator without re-broadcasting the RREQ.
• Otherwise, this node appends its own address to the route record in the RREQ packet, and re-broadcasts the request.
The RREQ thus propagates through the ad hoc network until it reaches the target host, which then replies to the initiator. Effectively, route discovery is implemented by controlled flooding of the RREQ packet. If the route discovery is successful, the initiator receives a RREP packet listing a sequence of network hops through which it may reach the target.
In conventional routing protocols, nodes exchange periodic routing updates. If the status of a link or a node changes, the periodic updates eventually reflect the changes to all other nodes, resulting in the computation of new routes. However DSR does not have periodic messages of any kind from any of the mobile nodes. Instead, while a route is in use, the route maintenance procedure monitors the operation of the route and informs the source of any routing errors.
Since wireless links are generally less reliable than wired links, many wireless networks, including 802.11, utilize a hop-by-hop acknowledgment at the data link layer in order to provide early detection and retransmission of lost or corrupted packets. In these networks, route maintenance can be easily provided, since over each link, the transmitting node can determine if the link is up. If the data link layer reports an unrecoverable transmission problem, the transmitting node sends a route error (RRER) packet to the original source of the packet. The RRER packet contains the addresses of the nodes at both ends of the link in error. When a RRER packet is received, the link in error is removed from this node’s route cache, and all routes that contain this link are truncated.
We note that a node can add entries to its route cache whenever it learns a new route. In particular, when a node forwards a data packet as an intermediate link on the route in that packet, the forwarding node is able to observe the entire route in the packet. If a node forwards an RREP packet, it can also add the route information from the route record being returned in that route reply, to its own route cache. Finally, since all wireless network transmissions are inherently broadcast, a node may be able to configure its network interface into promiscuous receive mode, and can then add to its route cache the route information from any overheard data or RREP packet.
In order to return the RREP packet to the initiator of the route discovery, the target reverses the route in the route record from the RREQ packet, and use this route to send the RREP packet. This, however, requires the wireless network communication between each of these pairs of hosts to work equally well in both directions, which may not be true in some environments or with some MAC-layer protocols.
AODV
AODV uses a broadcast route discovery mechanism, as is also used by DSR. Instead of source routing however, AODV relies on dynamically establishing route table entries at intermediate nodes. This difference pays off in networks with many nodes, where a larger overhead is incurred by carrying source routes in each data packet. AODV uses destination sequence numbers, as in destination-sequenced distance-vector (DSDV) routing [146], to maintain the most recent routing information. Each node maintains a monotonically increasing sequence number which is used to supersede stale cached routes. AODV also features timer-based states in each node. A routing entry is deleted if not used during a specific amount of time.
Route discovery in AODV is very similar to DSR. The main difference is the use of sequence numbers. In addition to the similar fields in the DSR RREQ, the AODV RREQ contains the pair (source sequence number, last destination sequence number known to the source). The source sequence number is used to maintain freshness information about the reverse route to the source and the destination sequence number specifies how fresh a route to the destination must be in order to be accepted by the source.
As the RREQ is flooded, it automatically sets up the reverse path from all nodes back to the source. To set up a reverse path, a node records the address of the neighbor from which it received the first copy of the RREQ. These reverse path route entries are maintained long enough for the RREQ to traverse the network and produce a reply to the source.
When an RREQ arrives at a node (possibly the destination itself) that has a routing table entry for the destination, it checks the freshness of that entry by comparing the destination sequence number of the route entry with that in the RREQ. If the sequence number of the RREQ is strictly greater, the routing table entry cannot be used to respond to the RREQ; instead, the node rebroadcasts the RREQ. Otherwise, if the RREQ has not been processed previously, the node then unicasts a RREP packet back to the sender of the RREQ. As the RREP travels back to the source, each node along the path sets up a forward pointer to the node from which the RREP came, updates its timeout information for route entries to the source and destination, and records the latest destination sequence number for the requested destination.
A node receiving an RREP propagates the first RREP for a given source node toward that source. If further RREPs are received, the node updates its routing information and propagates the RREP only if the RREP contains either a greater destination sequence number than the previous RREP or the same destination sequence number with a smaller hop count.
When a link fails, the node upstream of the break sends a RRER packet with a fresh sequence number (i.e., a sequence number that is one greater than the previously known sequence number) and a hop count of infinity to all active upstream neighbors. Then these nodes repeat the same process and so on. This process continues until all active source nodes are notified and then terminates because AODV maintains only loop free routes and there are only a finite number of nodes in the network. We note that this is unlike DSR in which broken link information may not be propagated to all route caches with that link.
Properties of Ad Hoc Routing Algorithms
It is important to note that the DSR and AODV algorithms are based on IP packets. Logically, mobile ad hoc IP networks differ from ordinary IP networks only in the network layer. In particular, the model abstraction of point-to-point links is preserved; only link state (up/down) changes become more frequent. The cooperation between nodes is limited strictly to packet store-and-forward. Despite this relative simplicity, the deployment of ad hoc routing at all nodes in a mobile wireless network results in a network with a very large state space. Whether in the form of a DSR cache or an AODV routing table, every node maintains its best guesses regarding available routes. As mobility causes link topology changes, these guesses will be outdated and likely have conflicts from node to node. As a result, the analysis of routing algorithms in mobile environments can do little more than verify correctness in quasistatic environments.
Instead, a large literature of experimental evaluation has emerged. Much of this is simulation-based [21, 38, 74, 130, 155, 194] but there has also been testing with small networks of nodes and 802.11 radio interfaces [95, 131, 142]. Much of this mobile ad hoc routing literature has focused on certain fundamental problems. In particular, route discovery and route maintenance generate a flurry of packets and unnecessary route discovery should be avoided [21, 38, 155]. On the other hand, when mobility induces link failures, fast route maintenance and discovery are vital. In addition, there are non-trivial cross-layer inter actions between the MAC, the routing protocol and the transport layer [140, 142]. For example, excess consumption of bandwidth resources by TCP can cause congestion in the 802.11 CSMA protocol, which can cause route maintenance to be invoked [140].
Additional issues arise with interactions with transport layer protocols. Consider an 802.11 ad hoc wireless network with stationary nodes such that the PHY layer radio connectivity is adequate. Suppose that these nodes are supporting a TCP file transfer over a multihop radio path. In this case, data packets in the forward direction (from sender to receiver) contend for the channel with RTS/CTS messages at the PHY layer as well as with TCP ACK messages in the reverse direction. These contending data packets cause self interference to the multihop route and can disrupt timely control message exchanges. This condition can be perceived as a link failure, triggering inappropriate route repair or route discovery mechanisms, ultimately resulting in transport layer timeouts and dramatic reductions in throughput [64]. This deficiency is in addition to the problems caused by PHY layer outages induced by fading on a single link, for which transport layer solutions [15, 16] have been developed.
Finally, we recall that DSR and AODV were designed to use only IP packets. As a result, simple hop metrics are the primary basis for routing. Frequently, the fastest route reply is equated with the best route. When links have variable rates, this is not necessarily correct. Since the RREQ and RREP packets are small, they travel faster across long distance hops at lower communication rates. Moreover, in an 802.11 environment which employs uncoded packets, these short control packets can be received on marginal links that are useless for longer data packets. Thus, longer data packets generally benefit from routes with shorter-distance higher-data-rate links. MAC-layer and network-layer enhanced routing algorithms have emerged to address such issues [13, 39]. We will see that these approaches have analogies to the cooperative approaches described in topic 6.
