Comparison of on Demand Routing Protocols

Published Online February 2013 in MECS

Routing [1] is the process in which a route from a source to a destination node is identified. In order to facilitate communication within MANET, a routing protocol is used to discover routes between nodes. The primary goal of such a routing protocol is to ensure correct and efficient route establishment between a pair of nodes so that messages are delivered in a timely manner. The routing protocols for mobile ad hoc network can be categorized on the basis of how routing information is acquired and maintained by mobile nodes [1-2] into three categories as follows:

• •    Proactive routing or Table driven routing

• •    Reactive routing or On demand routing

• •    Hybrid routing

In proactive routing protocol, nodes of ad hoc network continuously evaluate routes to all reachable nodes and attempt to maintain consistent, up-to-date routing information. Therefore, a source node can get a routing path immediately if it needs one. In proactive routing protocols, all nodes need to maintain a consistent view of the network topology. When a network topology change occurs, respective updates must be propagated throughout the network to notify the change. Most proactive routing protocols proposed for mobile ad hoc networks have inherited properties from algorithms used in wired net-works. To adapt to the dynamic features of mobile ad hoc networks, necessary modifications have been made on traditional wired network routing protocols. Using proactive routing algorithms, mobile nodes proactively update network state and maintain a route regardless of whether data traffic exists or not, the overhead to maintain up-to-date net-work topology information is very high.

In a reactive routing protocol, routing paths are searched only when needed. A route discovery operation invokes a route-determination procedure. The discovery procedure terminates either when a route has been found or no route available after examination for all route permutations. In comparison to table driven routing protocols this routing strategy has very low computational and memory requirements and hence are very much suitable for ad hoc networks.

Hybrid routing protocols are proposed to combine the merits of both proactive and reactive routing protocols and overcome their drawbacks. Normally, hybrid routing protocols for mobile ad hoc networks exploit hierarchical network architectures. Proper pro-active routing approach and reactive routing approach are exploited in different hierarchical levels, respectively.

This paper surveys the impact of three on demand routing protocols at application layer and compares their performance using QualNet simulator. To compare these routing protocols a constant bit rate application for all possible combination of source and destination nodes were taken (at a time only one CBR application was used) and the average of these values is calculated.

The rest of the paper is divided as follows: Section 2 gives the detailed description of on demand routing protocols used in the simulation process. Section 3 gives the simulation setup parameters of the simulation process. Section 4 gives the results followed by conclusion and references.

• II.    Routing Protocols Taken Into Consideration

• 2.1    Ad hoc On Demand distance Vector (AODV)

Routing Protocol

The Ad Hoc On-demand Distance Vector Routing [3] protocol is a reactive unicast routing protocol for mobile ad hoc networks. As a reactive routing protocol, AODV only needs to maintain the routing information about the active routes. In AODV, routing information is maintained in routing tables at nodes. Every mobile node keeps a next-hop routing table, which contains the destinations to which it currently has a route. A routing table entry expires if it has not been used or reactivated for a pre-specified expiration time. Moreover, AODV adopts the destination sequence number technique used by DSDV in an on-demand way.

Fig. 1: Flooding RREQ in AODV

In AODV, when a source node wish to send packets to the destination but route is not available, it initiates a route discovery operation. In the route discovery operation, the source node broadcast route request (RREQ) packets as shown in Figure 1. A RREQ includes addresses of the source and the destination, the broadcast ID which is used as its identifier, the last seen sequence number of the destination as well as the source node’s sequence number. Sequence numbers are important to ensure freshness of the up-to-date routes. To reduce the flooding overhead, a node discards RREQs that it has seen before and the expanding ring search algorithm is used in route discovery operation. The RREQ starts with a small TTL (Time-To-Live) value. If the destination is not found, the TTL is increased in following RREQs.

In AODV, each node maintains a cache to keep track of RREQs it has received. The cache also stores the path back to each RREQ originator. When the destination or a node that has a route to the destination receives the RREQ, it checks the destination sequence numbers it currently knows and the one specified in the RREQ. To guarantee the fresh-ness of the routing information, a route reply (RREP) packet is created and forwarded back to the source (see Figure. 2) only if the destination sequence number is equal to or greater than the one specified in RREQ. AODV uses only symmetric links and a RREP follows the reverse path of the respective RREP. Upon receiving the RREP packet, each intermediate node along the route updates its nexthop table entries with respect to the destination node. The redundant RREP packets or RREP packets with lower destination sequence number will be dropped.

Fig 2: Route reply in AODV

In AODV, a node uses hello messages to notify its existence to its neighbors. Therefore, the link status to the next hop in an active route can be monitored. When a node discovers a link disconnection, it broadcasts a route error (RERR) packet to its neighbors, which in turn propagates the RERR packet towards nodes whose routes may be affected by the disconnected link. Then, the affected source can re-initiate a route discovery operation if the route is still needed.

• 2.2    Dynamic Source Routing (DSR)

• 2.2.1    The Route Discovery Phase

• 2.2.2    The Route Maintenance Phase

The Dynamic Source Routing (DSR) [4] is a reactive unicast routing protocol which utilizes source routing algorithms. In source routing algorithm, each data packet contains complete routing information to reach its target. Additionally, in DSR each node uses caching technology to maintain route information that it has accumulated. There are two major phases in DSR:

In this phase when a source node wishes to send a packet, it firstly consults its route cache. If the required route is available, the source node includes the routing information inside the data packet before sending it. Otherwise, the source node initiates a route discovery operation by broadcasting RREQ packets. RREQ packet contains addresses of both the source and the target and a unique number to identify the request. Receiving a route request packet, a node checks its route cache. If the node doesn’t have routing information for the requested destination, it appends its own address to the route record field of the RREQ packet. Then, the request packet is forwarded to its neighbors. To limit the communication overhead of route request packets, a node processes route request packets either it has not seen before or its address is not presented in the route record field. If the route request packet reaches the destination or an intermediate node has routing information to the destination, a route reply packet RREP is generated. When the route reply packet is generated by the destination, it comprises addresses of nodes that have been traversed by the route request packet. Otherwise, the route reply packet comprises the addresses of nodes the route request packet has traversed concatenated with the route in the intermediate node’s route cache.

Fig. 3: Route Reply with Route Record in DSR

After being created, either by the destination or an intermediate node, a RREP packet needs a route back to the source. There are three possibilities to get a backward route. The first possibility is that the node already has a route to the source. The second possibility is that the network has symmetric (bi-directional) links. The route reply packet is sent using the collected routing information in the route record field, but in a reverse order as shown in Figure 3. In the last case, there exists asymmetric (unidirectional) links and a new route discovery procedure is initiated to the source. The discovered route is piggybacked in the RREQ packet.

In this phase, when the data link layer detects a link disconnection, a ROUTE_ERROR packet is sent backward to the source node. After receiving the ROUTE_ERROR packet, the source node initiates another route discovery operation. Additionally, all routes containing the broken link should be removed from the route caches of the immediate nodes when the ROUTE_ERROR packet is sent to the source.

DSR has increased traffic overhead by containing complete routing information into each data packet deteriorating its routing performance.

• 2.3    Dynamic MANET On-Demand (DYMO) Routing Protocol

• 2.3.1    DYMO Operations

• 2.3.2    Route Discovery

DYMO [5-8] is simplified combination of the AODV and DSR routing protocols. It operates similarly to AODV and maintains the basic functionality of route discovery phase and route maintenance phase. In DSR this operates such that every node that forwards an RREQ or an RREP and adds its own address to the data packet.

DYMO performs operations of route discovery and route maintenance. Route discovery is performed on on-demand basis when a node sends packet to a destination not in its routing table. Broadcasting is used to flood the network with the route request. If the destination is discovered then a reply message containing the discovered path is sent back. A routing table with information about nodes is maintained by each node.

Figure 4 illustrates the route discovery process. The source node 2 wants to communicate with destination node 9. The source generates a RREQ message which includes its own its sequence number, address, a hop count for the originating node set to an initial value of 1, and the target address. This RREQ message is broadcast throughout the network. A node will forward the RREQ if it has not done so previously. Sequence numbers provide the information. Each additional node that forwards the RREQ can add its address and sequence number to the RREQ. This is shown in the figure, as nodes 4 and 6 add information to the RREQ they broadcast.

The source node waits for RREP message, If RREP is not received within a specified period, the RREQ may be resent. On reception of RREQ, the node can create reverse routes to the nodes which have forwarded the RREQ by using the addresses the RREQ has accumulated.

Fig. 4: DYMO route discovery

• 2.3.3    Route Maintenance

To do Route maintenance operations, nodes must continuously monitor the active links and maintain latest routing information within their tables. A route error message must be sent by a node if it receives a packet with a destination for which it does not have an active route. The RERR process is depicted in Figure 5.

In this example, node 6 has received a packet that needs to go to node 9, but the link between nodes 6 and 9 is broken. Because of this broken link, node 6 creates an RERR message and propagates this message towards the source node (2). Nodes which receive the RERR message update their routing tables with the new information [7].

Fig. 5: DYMO route maintenance

Fig. 6: Snapshot of simulation process

• III.    Simulation Set Up

• 3.1    Set up parameters

• 3.2    Performance Metrics Used

Figure 6 shows the snapshot of the simulation process carried out in QUALNET simulator.

In Table 1 the various parameters used in the simulation process are shown.

Table 1: Set up Parameters

Parameter	Description
Size of Region	1500*1500 Sq. Units
Shape of Region	Square
Mobility Model Used	Random Way Point(RWP)
Number of Nodes deployed	40, 50 and 60
Battery Model	Linear
Placement of Nodes	Random
No of Iterations	780, 1225 and 1770 for 40, 50 and 60 number of nodes
Energy Model	Mica Motes
Antenna	Omni direction
Total Bytes Sent	12288
Total Packet Sent	24
Throughput	4274

Various performance metric [12-16] used for the simulation process are as follows:

Average End-to-End Delay: Defined as the time taken by a packet to travel across a network from source to destination node and it includes all possible delays caused during route discovery latency, retransmission delays at the MAC layer, propagation and transfer times.

Throughput: Defined as the average rate of successful message delivery over a communication channel.

Average Jitter: Defined as the standard deviation from true periodicity of an assumed periodic signal in electronics and telecommunications, often in relation to a reference clock source.

Packet Delivery Ratio: Defined as the Ratio of Total Packet Received to the Total Packet Sent.

Probability of Reachability (POR): Defined [9-11] as fraction of reachable routes to all possible routes between all pairs of source and destination nodes.

• IV.    Experimental Results4.1    Impact on End to End Delay

Figure 7 shows the impact of end to end delay versus number of nodes. The following inference can be drawn:

• •    There is no significant impact on end to end delay as the number of nodes increases.

• •    The AODV has lowest end to end delay followed by DSR and DYMO routing protocol

0.05 0.045 0.04 0.035 0.03 0.025 0.02 0.015 0.01 0.005

AVERAGE DELAY

3 ш Q

□ AODV

□ DSR

□ DYMO

NUMBER OF NODES

Fig. 7: Result of Number of nodes vs. Average end to end delay

• 4.2    Impact on Throughput

Figure 8 shows the impact of throughput versus number of nodes. The following inference can be drawn:

• •    The throughput increases slightly with increase in the number of nodes for all the on demand routing protocols.

• •    The throughput of DSR is highest followed by DYMO and AODV in every case.

  AVERAGE THROUGHPUT

  о ZD s

  

  NUMBER OF NODES

  Fig. 8: Result of Average Througput vs. Number of Nodes

  
  

• 4.3    Impact on Jitter

Figure 9 shows the impact of jitter versus number of nodes. The following inference can be drawn:

• •    There is not much variation in the value of jitter as the number of nodes increases.

• •    The AODV has lowest jitter followed by DSR and DYMO routing protocol in every case.

  AVERAGE JITTER

  

  NUMBER OF NODES

  Fig. 9: Result of Average Jitter vs. Number of Nodes

  
  

• 4.4    Impact on Packet Delivery Ratio (PDR)

Figure 10 shows the impact of PDR versus number of nodes. The following inferences can be drawn:

• •    As the number of nodes increases the neighbor density increases hence the value of PDR increases for all on demand routing protocols.

• •    The DSR has the highest value of PDR followed by AODV and DYMO routing protocol.

  PACKET DELIVERY RATIO

  

  NUMBER OF NODES

  Fig. 10: Result of PDR vs. Number of Nodes

  
  

• 4.5    Impact on Probability of Reachability (PoR)

Figure 11 shows the impact of PoR versus number of nodes. The following inferences can be drawn:

• •    As the number of nodes increases the neighbor density increases, hence the value of PoR increases for all on demand routing protocols.

• •    The DSR has the highest value of PoR followed by AODV and DYMO routing protocol.

  PERCENTAGE PROBABILITY OF REACHABILITY

  

  NUMBER OF NODES

  Fig. 11: Result of PoR vs. Number of Nodes

  
  

• V.    Conclusion

This paper compares the performance of on demand routing protocols for different QoS metrics. From the above results the following inference can be made:

• 1.    For a scenario in which the priority is to have minimum delay such as video transmission then AODV protocol is the best choice.

• 2.    For a scenario that requires better connectivity and packet delivery ratio DSR protocol is the best.

• 3.    The choice of protocol that should be used for MANET is totally dependent on the type of application required.

The overall comparison is shown in Table 2

The above points can be very useful for researchers while choosing a routing protocol for a particular application for ad hoc network.

Table 2: Overall Comparison of On Demand Routing Protocols

Protocols "^ JL Parameters	AODV	DSR	DYMO
End to End delay	Low	Medium	High
Jitter	Low	Medium	High
Throughput	Medium	High	Low
PDR	Medium	High	Low
PoR	Medium	High	Low