What is Ad hoc On Demand Distance Vector (AODV) Routing Protocol

April 27, 2018 Author: munishmishra04_3od47tgp
Print Friendly, PDF & Email

Routing is an important function in any network; it be wired or wireless. Routing is the act of moving information from a source to a destination in an internetwork. During this process, at least one intermediate node within the internetwork is encountered. Traditional wireless communication networks require a fixed infrastructure over which communication takes place. Therefore, considerable resources and effort are required to set up such networks, even before they can actually be used. Routing is the process of selecting paths in a network along which to send network traffic



Overview of AODV

In order to facilitate communication within the network, a routing protocol is used to discover routes between nodes. The primary goal of such an ad-hoc network routing protocol is correct and efficient route establishment between a pair of nodes so that messages may be delivered in a timely manner. Route construction should be done with a minimum of overhead and bandwidth consumption. An Ad-hoc routing protocol is a convention or standard that controls how nodes come to agree which way to route packets between computing devices in a MANET.

AODV is a very simple, efficient, and effective routing protocol for Mobile Ad-hoc Networks which do not have fixed topology. This algorithm was motivated by the limited bandwidth that is available in the media that are used for wireless communications. It borrows most of the advantageous concepts from DSR and DSDV algorithms. The on demand route discovery and route maintenance from DSR and hop-by-hop routing, usage of node sequence numbers from DSDV make the algorithm cope up with topology and routing information. Obtaining the routes purely on-demand makes AODV a very useful and desired algorithm for MANETs.

Table: Routing Table Fields

Destination IP address
Destination Sequence Number
Valid Destination Sequence Number Flag
Valid Destination Sequence Number Flag
Other state and routing flags
Network Interface
Hop Count (needed to reach destination)
Next Hop
Precursor List
Lifetime (route expiration or deletion time)




The basic message set consists in AODV:

RREQ – Route request

RREP – Route reply

RERR – Route error

HELLO – For link status monitoring

RREQ Messages

  • While communication routes between nodes are valid, AODV does not play any role.
  • A RREQ message is broadcasted when a node needs to discover a route to a destination.
  • As a RREQ propagates through the network, intermediate nodes use it to update their routing tables (in the direction of the source node).
  • The RREQ also contains the most recent sequence number for the destination.
  • A valid destination route must have a sequence number at least as great as that contained in the RREQ.

RREP Messages

  • When a RREQ reaches a destination node, the destination route is made available by unicasting a RREP back to the source route.
  • A node generates a RREP if:
  1. It is itself the destination.
  2. It has an active route to the destination. Ex: an intermediate node may also respond with an RREP if it has a “fresh enough” route to the destination.
  • As the RREP propagates back to the source node, intermediate nodes update their routing tables (in the direction of the destination node).

RERR Messages

  • This message is broadcast for broken links
  • Generated directly by a node or passed on when received from another node

Hello Messages

  • Hello Message = RREP with TTL = 1
  • This message is used for broadcasting connectivity information.

Ex: If a neighbor node does not receive any packets (Hello messages or otherwise) for more than ALLOWED_HELLO_LOSS * HELLO_INTERVAL milliseconds, the node will assume that the link to this neighbor is currently lost.

  • A node should use Hello messages only if it is part of an active route.

AODV-route-discovery

Figure Route Discovery process

Why AODV

AODV is one of the most popular routing protocols, which is a simple and efficient on-demand MANET routing protocol. The concepts of AODV that makes it desirable for MANETs with limited bandwidth include the following:

  • Minimal space complexity: The algorithm makes sure that the nodes that are not in the active path do not maintain information about this route. After a node receives the RREQ and sets a reverse path in its routing table and propagates the RREQ to its neighbors, if it does not receive any RREP from its neighbors for this request, it deletes the routing info that it has recorded.
  • Maximum utilization of the bandwidth: This can be considered the major achievement of the algorithm. As the protocol does not require periodic global advertisements, the demand on the available bandwidth is less. And a monotonically increased sequence number counter is maintained by each node in order to supersede any stale cached routes. All the intermediate nodes in an active path updates their routing tables also make sure of maximum utilization of the bandwidth. Since, these routing tables will repeatedly be used if that intermediate node receives any RREQ from another source for the same destination. Also, any RREPs that are received by the nodes are compared with the RREP that was propagated last using the destination sequence numbers and are discarded if they are not better than the already propagated RREPs
  • Simple: It is simple with each node behaving as a router, maintaining a simple routing table, and the source node initiating path discovery request, making the network self-starting.
  • Most effective routing info: After propagating a RREP message, if a node receives RREP with smaller hop-count, it updates its routing info with this better path and propagates it.
  • Most current routing info: The route info is obtained on demand. Also, after propagating an RREP, if a node receives RREP with greater destination sequence number, it updates its routing info with this latest path and propagates it.
  • Loop-free routes: The algorithm maintains loop-free routes by using the simple logic of nodes discarding the packets for same broadcast-id.
  • Coping up with dynamic topology and broken links: When the nodes in the network move from their places and the topology is changed, or the links in the active path are broken, the intermediate node that discovers this link breakage propagates an RERR message. And the source node re-initializes the path discovery if it still desires the route. This ensures quick response to broken links.
  • Highly Scalable: The algorithm is highly scalable because of the minimum space complexity and broadcasts avoided.

Limitations of AODV

  • Requirement on broadcast medium: The algorithm expects/requires that the nodes in the broadcast medium can detect each other’s’ broadcasts.
  • Overhead on the bandwidth: Overhead on bandwidth will be occurred compared to DSR, when an RREQ travels from node to node in the process of discovering the route info on demand, it sets up the reverse path in itself with the addresses of all the nodes through which it is passing and it carries all this info all its way.
  • No reuse of routing info: AODV lacks an efficient route maintenance technique. The routing info is always obtained on demand, including for common cause traffic.
  • It is vulnerable to misuse: The messages can be misused for insider attacks including route disruption, route invasion, node isolation, and resource consumption.
  • AODV lacks support for high throughput routing metrics: AODV is designed to support the shortest hop count metric. This metric favors long, low bandwidth links over short, high-bandwidth links.
  • High route discovery latency: AODV is a reactive routing protocol. This means that AODV does not discover a route until a flow is initiated. This route discovery latency result can be high in large-scale mesh networks.




References

[1] C.M barushimana, A.Shahrabi, “Comparative Study of Reactive and Proactive Routing Protocols Performance in Mobile Ad Hoc Networks,” Workshop on Advance Information Networking and Application, Vol. 2, pp. 679-684, May, 2003.

[2] C. Perkins, E. Belding-Royer, and S. Das, “Ad Hoc On demand Distance Vector (AODV) Routing,” IETF RFC 3561, July 2003.

[3] Ahmed, Asma, A. Hanan, and Izzeldin Osman. “AODV routing protocol working process.” Journal of Convergence Information Technology 10, no. 2 (2015): 1.

[4] Junaid Arshad and Mohammad Ajmal Azad, “Performance Evaluation of Secure on-Demand Routing Protocols for Mobile Ad-hoc Networks”, IEEE 2006.

5 Comments

  • Excellent way of explaining, and fastidious piece of writing to
    take facts on the topic of my presentation topic, which i
    am going to present in college.

  • Teknoloji May 6, 2018 at 12:27 am

    Hello there! Would you mind if I share your blog with my
    zynga group? There’s a lot of people that I think would really appreciate your content.
    Please let me know. Thank you

    • Facebook Profile photo
      munishmishra04_3od47tgp May 6, 2018 at 11:46 am

      no problem thanks

  • +905443535397 May 6, 2018 at 12:46 am

    I truly love your website.. Excellent colors & theme. Did you develop this amazing site yourself?
    Please reply back as I’m attempting to create
    my very own site and want to find out where you got this from or just what the theme is called.
    Appreciate it!
    +905443535397

  • Ssd disk Almali miyim May 8, 2018 at 5:24 am

    It’s truly very difficult iin this active life to lsten news
    on TV, thus I just uuse the web for that reason, and obtain the latest information.

Leave a Reply

Your email address will not be published. Required fields are marked *

Insert math as
Block
Inline
Additional settings
Formula color
Text color
#333333
Type math using LaTeX
Preview
\({}\)
Nothing to preview
Insert