AODV Protocol Improvement For Multi Path Routing Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

AODV is a well established reactive routing protocol which is well affected in large and multi-hop networks. Although the performance of AODV protocol is well as compared to other reactive protocol,

We are proposed an extension in the AODV by which AODV supports Multi-path routing with path accumulation. The performance of extended AODV will be compared with existing AODV protocol & other reactive protocol.

AODV, Path Accumulation, RREQ, RREP, Route Discovery.

I. Introduction:


"AODV is a single channel, Flat structured, Event- driven updated, Multi path routed , Dynamic , Self starting , Multi hop & On demand Routing Protocol ."

AODV Operations

A. Route Discovery

When a node wants to communicate with another node it first

Checks its own routing table if an entry for this destination node exists. If this is not the case, the source node has to initialize a route discovery. This is done by creating a RREQ message, including

The hop count to destination, the IP address of the source and the destination, the sequence numbers of both of them, as well as the broadcast ID of the RREQ. This ID and the IP address of the source node together form a unique identifier of the RREQ. When the RREQ is created the source node broadcasts it and sets a timer to wait for reply [1].

All nodes which receive the RREQ first check by comparing the identifier of the message with identifiers of messages already received. If it is not the first time the node sees the message, it discards silently the message. If this is not the case the node processes the RREQ by updating its routing table with the reverse route. If a node is the destination node or has already an active route to the destination in its routing table with sequence number of the destination host which is higher than the one in the RREQ, it creates a RREP message and unicasts it to the source node. This can be done by analyzing the reverse route for the next hop. Otherwise it increments the RREQ's hop count and then broadcasts the message to its neighbors.

When the source node receives no RREP as a response on its RREQ a new request is initialized with a higher TTL and wait value and a new ID. It retries to send a RREQ for a fixed number of times after which, when not receiving a response, it declares that the destination host is unreachable [1].

Figure 1, shows the propagation of the RREQ through the network and the path taken by the RREP from the destination to the source node.

Figure 1: Propagation of RREQ and Route Determination

B. Route Maintenance

When a route has been established, it is being maintained by the source node as long as the route is needed. Movements of nodes affect only the routes passing through this specific node and thus do not have global effects. If the source node moves while having an active session, and loses connectivity with the next hop of the route, it can rebroadcast an RREQ. If though an intermediate station loses connectivity with its next hop it initiates an Route Error (RERR) message and broadcasts it to its precursor nodes and marks the entry of the destination in the route table as invalid, by setting the distance to infinity. The entry will only be discarded after a certain amount of time, since routing information may still be used [1].

When the RERR message is received by a neighbor it also marks its route table entry for the destination as invalid and sends again RERR messages to its precursors.

C. Hello Messages

If no broadcast has been send within, by default, one second, each node broadcasts Hello Message to its neighbors in order to keep connectivity up to date. These messages contain the node's IP address and its current sequence number. So that these messages are not forwarded from the node's neighbors to third parties the Hello message has a TTL value of one.

Limitations of AODV

Unused routes expire even if topology is unchanged.

Implementation of AODV is needed symmetrical links.

The overhead of the discovery of the new route and form the updates of the usable routes.

AODV does not support Path - Accumulation.

AODV does not support multi-path routing for each pair of Source - Destination. It only supports single - path routing during route discovery operation.

II. Proposed Extension

After reviewing the limitations of AODV, we are proposing the extension in AODV protocol that will be adding following feature in AODV.

Path Accumulation.

Multi- Path Routing.

By this extension we are suggesting that Performance of AODV Protocol will be more improved from the Normal AODV.

Path Accumulation

Path accumulation feature enables to append all discovered paths between source and destination nodes to the control messages. Hence, at any intermediate node the RREQ packet contains a list of all nodes traversed. Each node receiving these control messages, updates its routing table. It adds paths to each node contained in these messages [2].

Multi Path Routing

Multi-Path routing consists of finding multiple routes between a source and destination node. These multiple paths between source and destination node pairs can be used to compensate for the dynamic and unpredictable nature of ad hoc networks [3].

III. Analysis & Design of Extension

Path Accumulation in AODV

In AODV, a source that has a packet to a destination needs first to discover a route to this destination. If the source has no route already in its routing table to that destination, it sends a route request (RREQ) which is flooded to the whole network. When the destination or a node that has a route to the destination receives this RREQ, it replies back with a RREP. When the source receives the RREP it can start sending data packets along the route from which the RREP arrived. Intermediate nodes receiving the RREQ create entries in their routing table to the source; similarly nodes receiving the RREP create entries to the destination. The routing table entry contains the next-hop to the corresponding node. Accordingly, a route between a source and a destination is constructed hop-by-hop along the path taken by the RREP and data packets do not need to contain the whole route.

The idea of path accumulation is to allow nodes receiving and forwarding control packets to record their identity in the packet and eventually learn about other nodes in the path between the source and destination. Each RREQ and RREP contains a source route for the nodes along the path, so that each node can have a routing table entry to the rest of the nodes.

The main benefit of obtaining the additional routing entries is to reduce the route discovery overhead by eliminating some of the RREQs that would be required to discover these nodes. Since RREQs are the major source of control overhead due to flooding the whole network, any reduction in RREQs is expected.

Figure 2.1 & 2.2 clarifies the difference between route discoveries without path accumulation and route discovery with path accumulation. Without path accumulation, intermediate nodes learn only about the source and destination, while with path accumulation each node learns about every other node in the path.

Figure 2.1: Route Discovery without Path Accumulation

Figure 2.2: Route Discovery with Path Accumulation

Multi-Path Routing in AODV

A. Overview of AODV

AODV is a single path on-demand routing protocol for a mobile ad-hoc network. It is composed of two phases; route discovery process and route maintenance process, using next three packets (1) RREQ (Route Request) (2) RREP (Route Reply) (3)RERR (Route Error) .

Figure 3 denotes usage of these packets. In route discovery process, a source node firstly broadcasts a RREQ packet towards a destination node. An intermediate node that receives the first RREQ packet records a reverse route to the source node and re-broadcasts the packet. When the intermediate node receives duplicate RREQ packets, it simply discards them. In response to the firstly arrived RREQ packet, the destination node returns a RREP packet to the source node by unicast. An intermediate node that receives the packet records a forward route to the destination and forwards the packet to a neighbor node on the reverse route. The RREP packet finally returns back to the source node and a data transfer route is established [4].

In route maintenance process, when a node detects a link failure, it generates a RERR packet by broadcast. This RERR packet is propagated over the routes while simultaneously invalidating the corresponding routes. When a RERR packet is sent back to a source node, the source node initiates new route discovery process. In Figure 3 node 7 moves away and a link failure happens between nodes 6 and 7. Then, node 6 detects the link failure and broadcasts a RERR packet.

A problem happens when this route re-discovery process is too frequently initiated due to node mobility or bad channel condition. It causes huge routing overheads and data transfer interruptions, resulting in serious performance degradation.

Figure 3 Overview of AODV Model

B. Multiple Route discovery in AODV

We extend the route discovery process by letting each intermediate node select reverse routes and forward routes in a distributed manner according to a specified metric. Instead of special fields such as the first-hop field of AOMDV and the Joint-count field of AODVM, a source route list is attached to the RREQ/RREP packets. Figure 4 summarizes our extensions. Details are as follows.

1. RREQ Extension

Similar to AODV, a source node broadcasts a RREQ packet. When an intermediate node receives the first RREQ packet, it records a reverse route in its routing table and re-broadcasts the packet. On the other hand, when the intermediate node receives a delayed RREQ packet from other neighbors, it firstly checks a source route list in the packet and discards the packet when a routing loop is detected. If this address check is passed, the intermediate node then checks reverse routes already stored in its routing table. According to the metric composed of delay, hop count and disjoint-ness, the intermediate node determines acceptance of the delayed RREQ packet and, when accepting it, updates the reverse routes. When we apply a metric of hop count minimization, for example, the reverse route selection is carried out as follows. When the hop count of the duplicate packet is equal to or less than the minimal hop count plus m hops (typically zero) in a routing table, the packet is accepted as a new reverse route candidate. When the packet does not satisfy the update condition, it is simply discarded. Irrespective of this decision, the duplicated packet is not re-broadcasted. In practice, the number of reverse routes stored in a routing table is limited to k, of which typical value is two. Figure 4.1 presents an example of routing table extension of our proposal, which is managed by each intermediate node. Route information and an expiration timeout field are stored for each reverse route [5].

Finally, RREQ packets are delivered to a destination node with different source routes. In Figure 4.2, an example of the source route lists attached to RREQ packets is presented.

Figure 4.1 Multiple route discoveries by the proposed method.

Figure 4.2 Routing table extension of the proposed method, when the maximum number of reverse routes is two.

2. RREP Extension

A destination node receiving RREQ packets generates multiple RREP packets toward a source node by unicast. The first arriving RREQ packet is unconditionally accepted and a RREP packet is immediately generated to create a primary route, which is usually equal to the AODV route. Delayed RREQ packets are conditionally accepted according to the specified metric. We limit the number of RREP packets to n, of which typical value is set to two.

Operation of an intermediate node is slightly complicated. In principle, the intermediate node receiving a RREP packet forwards it to any neighboring nodes over the reverse routes using bi-cast (multiple uni-casts).

Routing loops can be easily solved by setting the hop-count limitation m≤1 or using an attached source route list. Against the multiple arrivals of RREP packets, we apply a following procedure.

When the intermediate node that has multiple reverse routes receives the first RREP packet, it immediately carries out bicasting of the packet. This is valid because reverse route determination in the RREQ process implicitly determines bicasting operation at the intermediate node. When the intermediate node receives a delayed RREP packet, it checks a specified metric condition and decides acceptance of the packet. When the packet is accepted, forward routes are updated in a routing table. Re-bicasting of the packet may be carried out according to the metric definition. Similar to the RREQ process, we limit the number of forward routes to k, of which typical value is two.

Figure 5 summarizes operations of the intermediate node, which may happen during the RREQ/RREP process.

Figure 5: Operations of an Intermediate node of the proposed Method

(a) Basic case similar to AODV

(b) Multiple forward Route (delayed update)

(c)Multiple Reverse routes (Bicasting)

(d) Multiple reverse routes and multiple forward routes (bicasting and delayed update)

IV. Performance Evaluation

A. Simulation Model

We evaluated our proposal using OMNeT++ simulator. In the simulation model, we have used network size which is defined by number of nodes in the particular network area. Here we have defined the area of 500m X 500m with X and Y coordinates. The Simulation time is kept 10 minutes i.e. 600sec.

In node configuration for a wireless network, the AODVPA routing algorithm has been assigned as its routing protocol. The link layer uses IEEE802.11 MAC protocol for broadcasting data packets. The maximum queue size is 14 and the bit rate is 2 Mbps. The transmitter power is taken 2mW. The threshold value of signal to noise ratio is 4db and the sensitivity is -90dBm and thermal noise parameter is -110dBm.

B. Simulation Results

1. Average Delay

This is defined as the delay between the time at which the data packet was originated at the source and the time it reaches the destination. Data packets that get lost in route are not considered. Delays due to route discovery, queuing and retransmissions are included in the delay metric. It is a metric which is very significant with multimedia and real-time traffic. It is very important for any application where data is processed online

Comparison of Average delay has been done in between the figure number 6(a) and figure number 6(b).

In figure 6(a), we see that Average delay is increasing and then after it is decreasing. After it is increasing with slight values then it is decreasing down to zero when in the area no. of nodes is increasing.

The reason behind it that in the no. of nodes configure such that there are immediate available for the receiving the packets.

In figure number 6(b), we see that Average delay is increasing as compared to AODV Protocol with fewer amounts. Then it reaches its maximum value then it is decreasing to the zero, then after it is increasing.

After comparison we conclude that Average delay in AODVPA Protocol is less than AODV Protocol, Thus performance of AODVPA protocol is much high from AODV protocol .

2. Packet delivery ratio

The ratio between the number of packets received by the TCP sink at the final destination and the number of packets originated by the "application layer" sources. It is a measure of efficiency of the protocol.

Comparison of Packet Delivery Ratio has been done in between the figure number 7(a) and figure number 7(b).

In figure number 7(a), we see that Packet delivery ratio is increasing and then after it is decreasing. After it is increasing up to one then it is decreasing down to zero when in the area no. of nodes is increasing.

In figure number 7(b), we see that Packet delivery Ratio is increasing as compared to AODV Protocol with more fractions. Then it reaches its maximum value then it is decreasing to the zero, then after it is increasing.

After comparison we conclude that Packet Delivery Ratio in AODVPA Protocol is much higher than AODV Protocol.

3. Throughput

It is defined as total number of packets received by the destination. It is the total amount of application layer data in bps that is successfully transmitted in the network. It is a measure of effectiveness of a routing protocol.

Comparison of Throughput has been shown in between the figure number 8(a) and figure number 8(b).

In figure 8 (a), we see that Throughput is increasing up to 100% and then after it is decreasing. After it is increasing up to 100% then it is decreasing down to zero when in the area no. of nodes is increasing.

In figure 8(b), we see that Throughput is increasing up to 100% and then after it is decreasing. After it is increasing up to 100% then it is decreasing down to zero when in the area no. of nodes is increasing. After this a sudden increment meet into Throughput and it reaches again 100%.

After comparison we conclude that Throughput in AODVPA Protocol is much higher than AODV Protocol, Thus performance of AODVPA protocol is high from AODV protocol.

Figure 6(a) Average Delay of AODV

Figure 7(a) Packet Delivery Ratio of


Figure 8(a) Throughput of AODV

Figure 6(b) Average Delay of AODVPA

Figure 7(b) Packet Delivery Ratio of


Figure 8(b) Throughput of AODVPA

V. Conclusion

We conclude the following results

Average delay in AODVPA Protocol is less than AODV Protocol.

Packet Delivery Ratio in AODVPA Protocol is much higher than AODV Protocol.

Throughput in AODVPA Protocol is much higher than AODV Protocol.

Thus performance of AODVPA protocol is higher from AODV protocol in every performance parameter comparison.

VI. References

[1]. Karim Seada, C´edric Westphal,

Charles Perkins "Analyzing Path

Accumulation for Route Discovery in

Ad hoc Networks", In IEEE WCNC

2007 Vol -II number 4 in year August

2007 from page number 145 to 151.

[2]. Sumit Gwalani, Elizabeth M. Belding-Royer, and Charles Perkins. AODV-PA: AODV with Path Accumulation", IEEE International Conference on Communication, ICC'03.

[3] Jack Tsai and Tim Moors A Review of Multipath Routing Protocols: From Wireless Ad Hoc to Mesh Networks

[4] A. Nasipuri and S. R. Das, "On demand multipath routing for mobile ad-hoc networks," Computer Communications and Networks, 1999.

[5] Abderrahmen Mtibaa , Farouk Kamoun "MMDV: Multi path and MPR based AODV routing protocol" IEEE Fifth Annual Med hoc Net May 2006.

[6]. Rui Xi "AODV Protocol: Evolution and Future Directions" In Mobile computing Forum in year June 2004 from page number 1 to 39.

[7]. Abderrahmen Mtibaa, Farouk Kamoun "MMDV: Multi path and MPR based AODV routing protocol" In CRISTAL Lab., ENSI .Campus Univ. Manouba, tn-2010 Tunisia Forum in year June 2006 from page number 139 to 147.

[8]. Mario Cagalj and Jean-Pierre Hubaux "Performance Evaluation of AODV Routing Protocol: Real-Life Measurements" In LCA, EPFL, Alexander Zurkinden, SCC ,In year June 2003 from page number 1 to 36.

[9] Jack Tsai and Tim Moors "A Review of Multi-path Routing Protocols: From Wireless Ad Hoc to Mesh Networks "National ICT Australia (NICTA) 1/ University Of New South Wales, Australia in year July 2006 from page number 167 to 173.

[10]. S. Corson and J. Macker: "Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations", In Internet community RFC- 2501 in year January 1999 from page number 1 to 10.

[11]. C. Perkins, E. Belding-Royer, S. Das "RFC3561 - Ad hoc On-Demand DistanceVector (AODV) routing" in Internet community RFC - 3561 in year June 2003.