Reactive Routing Protocols

Posted by arlene

Reactive protocols are designed to minimize routing overhead. Instead of tracking the changes in the network topology to continuously maintain shortest path routes to all destinations, these protocols determine routes only when necessary. Typically, these protocols perform a route discovery operation between the source and the desired destination when the source needs to send a data packet and the route to the destination is not known. As long as a route is live, reactive routing protocols only perform route maintenance operations and resort to a new route discovery only when the existing one breaks. The advantage of this on-demand operation is that it usually has a much lower average routing overhead in comparison to proactive protocols. However, it has the disadvantage that a route discovery may involve flooding the entire network with query packets. Flooding is wasteful, which can be required quite frequently in case of high mobility or when there are a large number of active source- destination pairs. Moreover, route discovery adds to the latency in packet delivery as the source has to wait till the route is determined before it can transmit. Despite these drawbacks, on-demand protocols receive comparatively more attention than proactive routing protocols, as the bandwidth advantage makes them more scalable.

Dynamic Source Routing (DSR)

DSR is a reactive routing protocol that uses a concept called source routing. Each node maintains a route cache where it lists the complete routes to all destinations for which the routes are known. A source node includes the route to be followed by a data packet in its header. Routes are discovered on demand by a process known as route discovery. When a node does not have a route cache entry for the destination to which it needs to send a data packet, it initiates a route discovery by broadcasting a route REQUEST or QUERY messageseeking a route to the destination. The REQUEST packet contains the identities of the source and the desired destination. Any node that receives a REQUEST packet first checks its route cache for an existing entry to the desired destination. If it does not have such an entry, the node adds its identity to the header of the REQUEST packet and transmits it. Eventually, the REQUEST packet will flood the entire network by traversing to all the nodes tracing all possible paths. When a REQUEST packet reaches the destination, or a node that has a known route to the destination, a REPLY is sent back to the source following the same route that was traversed by that REQUEST packet in the reverse direction. This is done by simply copying the sequence of node identities obtained from the header of the REQUEST packet. The REPLY packet contains the entire route to the destination, which is recorded in the source node’s route cache.

When an existing route breaks, it is detected by the failure of forwarding data packets on the route. Such a failure is observed by the absence of the link layer acknowledgement expected by the node where the link failure has occurred. On detecting the link failure, the node sends back an ERROR packet to the source. All nodes that receive the ERROR packet, including the source, delete all existing routes from their route caches that contain the specified link If a route is still needed, a fresh route discovery is initiated.

Ad Hoc On-Demand Distance-Vector Routing (AODV)

AODV can be described as an on-demand extension of the DSDV routing protocol. Like DSDV, each route maintains routing tables containing the next hop and sequence numbers corresponding to each destination. However, the routes are created on demand, that is, only when a route is needed for which there is no “fresh” record in the routing table. In order to facilitate the determination of the freshness of routing information, AODV maintains the time since an entry has been last utilized. A routing table entry is “expired” after a certain predetermined threshold of time.

The mechanism for creating routes in AODV is somewhat different from that used in DSR. Here, when a node needs a route to some destination, it broadcasts a route REQUEST packet in which it includes the last known sequence number for that destination. The REQUEST packet is forwarded by all nodes that do not have a fresher route (determined by the sequence numbers) to the specified destination. While forwarding the REQUEST packet, each node records the earlier hop taken by the REQUEST packet in its routing table entry for the source (originator of the route discovery). Hence, a propagating REQUEST packet creates reverse routes to the source in the routing tables of all forwarding nodes. When the REQUEST packet reaches the desired destination or a node that knows a fresher route to it, it generates a route REPLY packet that is sent back along the same path that was taken by the corresponding REQUEST packet. The REPLY packet contains the number of hops to the destination as well as the most recent sequence number. Each node that forwards the REPLY packet enters the routing information for the destination node in its routing table, thus creating the forward route to the destination.

Routing table entries are deleted when an ERROR packet is received from one of the intermediate nodes on the route forwarding a data packet to the destination. When such an ERROR packet reaches the source, it may initiate a fresh route discovery to determine a fresh route to the destination.

Issues in Reactive Routing

Since reactive routing protocols only transmit routing packets when needed, these protocols are comparatively more efficient when there are fewer link breakages, such as under low mobility conditions. In addition, when there are only a few communicating nodes in the network, the routing functions are only concerned with maintaining the routes that are active. Because of these benefits, reactive or on-demand routing protocols have received more attention than proactive protocols for mobile ad hoc networks.

The main concern with reactive routing protocols is the need for flooding the entire network in search of a route when needed. Many optimizations have been suggested to reduce the excessive number of routing packets transmitted throughout the network during such flooding operations in reactive protocols. For instance, DSR has the option of broadcasting a nonpropagating request packet for route discovery, which is then broken into two phases. In the first phase, the source broadcasts a nonpropagating route request packet that only queries its first-hop neighbors for a known route to the destination.

These packets are not forwarded by the neighbors. If none of the neighbors return a route, the source then proceeds to the second phase where a traditional propagating request packet is sent. The advantage of this scheme is that it avoids a networkwide flood of request packets when the route to the destination is known by one of the first-hop neighbors. A similar scheme is implemented in AODV using the concept of an expanding ring search. Here, increasingly larger neighborhoods, controlled by either hop-or time-constrained request packets, are searched to find the route to the destination. Some other techniques that perform similar optimizations are: salvaging, where an intermediate node in DSR uses an alternative route from its own cache when the original route is broken; and promiscuous listening, in which a node that overhears a packet not addressed to itself finds that it has a shorter route to the same destination and sends a gratuitous reply to the source with this new route. This increases the freshness of the route cache entries without additional route discoveries.

Possibly related posts: (automatically generated)
Reactive Routing Protocols

• Hybrid Routing Protocols
• Ad Hoc Routing
• Routing in Ad Hoc Networks
• Proactive Routing Protocols: Destination-Sequenced Distance-Vector Routing; Optimized Link-State Routing Protocol
• Providing Support for BOOTP Clients
• OSPF (Open Shortest Path First)
• Examining IP Datagram Header Information
• Blogging Wordpress Theme
• The Internet Protocol (IP) continue...
• IP Addressing