Ad hoc On-demand Distance Vector Routing Protocol
Active In SP
Joined: Feb 2011
02-03-2011, 11:00 AM
pdesertation.ppt (Size: 337.5 KB / Downloads: 187)
Mobile Ad Hoc Networks
A collection of wireless mobile hosts forming a temporary network without the aid of any established infrastructure.
Dynamic topology of interconnections
Short transmission range- routes between nodes has one or more hops
Nodes act as routers or depend on others for routing
movement of nodes invalidates topology information
Applications of MANET
Useful where geographical or terrestrial constrains demand totally distributed network without fixed base station.
Disaster and Rescue Operations
Peer to Peer Networks
Security Design Issues in MANET
Do not have any centrally administered secure routers.
Attackers from inside or outside can easily exploit the network.
Passive eavesdropping, data tampering, active interfering, leakage of secret information, etc.
Open peer-to-peer architecture.
Shared Wireless Medium.
Routing protocols in Mobile Adhoc Networks are majorly of two categories:
- Proactive Protocols
- Reactive Protocols
Reactive Routing protocols are based on finding routes between two nodes, when it is required. This is different from traditional Proactive Routing Protocols in which nodes periodically sends messages to each other in order to maintain routes
Network with nodes, edges
Goal: Devise scheme for transferring message from one node to another
Who decides – source or intermediate nodes?
Generally try to optimize something:
Shortest path (fewest hops)
Shortest time (lowest latency)
Shortest weighted path (utilize available bandwidth)
Who determines route?
Two general approaches:
Source (“path”) routing
Source specifies entire route: places complete path to destination in message header: A – D – F – G
Intermediate nodes just forward to specified next hop: D would look at path in header, forward to F
Like airline travel – get complete set of tickets to final destination before departing…
Destination (“hop-by-hop”) routing
Source specifies only destination in message header: G
Intermediate nodes look at destination in header, consult internal tables to determine appropriate next hop
Like postal service – specify only the final destination on an envelope, and intermediate post offices select where to forward next…
Ad Hoc Routing
Every node participates in routing: no distinction between “routers” and “end nodes”
No external network setup: “self-configuring”
Especially useful when network topology is dynamic (frequent network changes – links break, nodes come and go)
Ad Hoc On Demand Distance Vector Routing Protocol
Reactive Protocol: discovers a route on demand.
Nodes do not have to maintain routing information.
used to determine local connectivity.
can reduce response time to routing requests.
can trigger updates when necessary.
AODV uses a broadcast route discovery mechanism
AODV relies on dynamically establishing route table entries at intermediate nodes
Each ad-hoc node maintains a monotonically increasing sequence number counter which is used to supersede stale cached routes
The Ad-hoc On-Demand Distance Vector Algorithm
Pure on-demand route system
Node does not have to discover and maintain a route to another node until the two need to communicate
Nodes that do not lie on active paths neither maintain any routing information
AODV Protocol Activities
Undertaken whenever a node needs a “next hop” to forward a packet to a destination
Used when link breaks, rendering next hop unusable
Source broadcasts Route Request (RREQ) message for specified destination
Forwards (broadcasts) message toward destination
Creates next-hop entry for reverse path to source, to use when sending reply (assumes bidirectional link…)
Destination unicasts Route Reply (RREP) message to source
RREP contains sequence number, hop-count field (initialized to 0)
Will be sent along “reverse” path hops created by intermediate nodes which forwarded RREQ
Create next-hop entry for destination as RREP is received, forward along “reverse path” hop
Increment hop-count field in RREP and forward
If multiple replies, uses one with lowest hop count
Used when link breakage occurs
Link breakage may be detected using link-layer ACKs, “passive ACKs”, DSR ACK request
Route Error message sent to source of message being forwarded when break detected
Intermediate nodes “eavesdrop”, adjust cached routes
Source deletes route; tries another if one cached, or issues new Route Request
Piggybacks Route Error on new Route Request to clear intermediate nodes’ route caches, prevent return of invalid route
Discovery messages broadcast throughout network
Broadcast / Multicast
Use Route Request packets with data included
Duplicate rejection mechanisms prevent “storms”
Multicast treated as broadcast; no multicast-tree operation defined
AODV – RREQ
RREQ packet contains: destination and source IP address, broadcast ID, source node’s sequence number and destination node’s sequence number.
Node 1 wants to send data packet to node 7. Node 6 knows a current route to node 7. Node 1 sends a RREQ packet to its neighbors.
broadcast_id = broadcast_id +1
source_sequence_# = source_sequence_# + 1
dest_sequence_# = last dest_sequence_# for node 7
Traditional AODV (RREQ)
Nodes 2 and 4 verify that this is a new RREQ (source_sequence_# is not stale) with respect to the reverse route to node 1.
Forward the RREQ, and increment hop_cnt in the RREQ packet.
RREQ reaches node 6 from node 4, which knows a route to 7.
Node 6 verify that the destination sequence number is less than or equal to the destination sequence number it has recorded for node 7.
Nodes 3 and 5 will forward the RREQ packet to node 6, but it recognizes the packets as duplicates.
Traditional AODV (RREP)
Node 6 has a route to destination. It sends a route reply RREP to the neighbor that sent the RREQ packet.
Intermediate nodes propagate RREP towards the source using cached reverse route entries.
Other RREP packets discarded unless, dest_seq_# is higher than the pervious, or same but hop_cnt is smaller.
Cached reverse routes timeout in nodes that do not see RREP packet.
Traditional AODV (RREP)
Node 6 sends RREP to node 4
Source_addr=1, dest_addr=7, dest_sequence_# = maximum (sequence no. stored for node 7, dest_sequence_# in RREQ), hop_cnt =1.
Node 4 finds out it is a new route reply and propagates the RREP packet to Node 1.
In AODV, only one route is maintained per destination
DSR makes use of multiple paths
This is a major weakness of AODV
Whenever a path breaks, AODV has to perform a route discovery
The source broadcasts a route request packet
Increases contention, significant overhead
We want to avoid frequent route discoveries
Maintain multiple paths learned from a route discovery
When a path breaks, try to use an alternate path instead of initiating a new route discovery
Maintain multiple paths at the source (AOMDV)
Enhance local repair (ELRAODV)
AOMDV – Motivation
AOMDV set up multiple link-disjoint routes from source node to destination node.
AOMDV does not predict the link failure between the nodes.
AOMDV improve performance in many aspect like packet delivery ratio, end-to-end delay and control overhead of the network.
ELRAODV – Motivation
Local repair generate more traffic to repair route.
The extra information of the local neighbors allow ELRAODV to repair a route by sending a unicast request instead of broadcast in original AODV.
Ad Hoc networks pose an interesting problem in networking with dynamic routing and highly insecure working environment
Need of Secure, Scalable, Reliable and Efficient algorithms for Key management and Routing
Joined: Apr 2012
05-07-2012, 04:09 PM
Ad Hoc On-Demand Distance-Vector Protocol
4Ad Hoc On-Demand Distance-.ppt (Size: 102 KB / Downloads: 32)
DSDV and DSR mainly support unicast routing.
If multicasting is required, a node must establish unicast routes to each node in the multicast group.
A more efficient approach will maintain multicast routing trees for each multicast group.
Non-uniform Packet Size in DSR
Though DSR is a reactive or on-demand routing protocol, a major problem with DSR is its non-uniform packet size.
When a source node S sends a packet to a destination node D, S should send the entire route to D along with the packet.
This is necessary for the intermediate nodes to forward the packet.
Problem with Non-uniform Packet Size
Usually all media support packets of uniform size. If a packet is large, it has to be split into smaller packets.
This may cause problems in the wireless medium as packets that are split into smaller parts may not arrive in correct order.
Intermediate nodes may not be able to forward packets correctly.
Main Features of the AODV Protocol (I)
The Ad hoc On-Demand Distance Vector protocol is both an on-demand and a table-driven protocol.
The packet size in AODV is uniform unlike DSR. Unlike DSDV, there is no need for system-wide broadcasts due to local changes.
AODV supports multicasting and unicasting within a uniform framework.
Unicast Route Establishment
Unicast route is a route from a source node to a destination node.
Like DSR, we use two types of messages, route request (RREQ) and route reply (RREP).
Like DSDV, we use sequence numbers to keep track of recent routes. Every time a node sends a new message, it uses a new sequence number which increases monotonically.
Joined: Apr 2012
07-07-2012, 11:04 AM
Ad hoc On Demand Distance Vector Routing Protocol
Ad hoc On Demand Distance Vector.docx (Size: 19.37 KB / Downloads: 28)
In November 2001 the MANET (Mobile Ad-hoc Networks) Working Group for routing of the IEFT community has published the first version of the AODV Routing Protocol (Ad hoc On Demand Distance Vector).
AODV belongs to the class of Distance Vector Routing Protocols (DV). In a DV every node knows its neighbors and the costs to reach them. A node maintains its own routing table, storing all nodes in the network, the distance and the next hop to them. If a node is not reachable the distance to it is set to infinity. Every node sends its neighbors periodically its whole routing table. So they can check if there is a useful route to another node using this neighbor as next hop. When a link breaks a Count-To-Infinity could happen.
AODV is an ‘on demand routing protocol’ with small delay. That means that routes are only established when needed to reduce traffic overhead. AODV supports Uncast, Broadcast and Multicast without any further protocols. The Count-To-Infinity and loop problem is solved with sequence numbers and the registration of the costs. In AODV every hop has the constant cost of one. The routes age very quickly in order to accommodate the movement of the mobile nodes. Link breakages can locally be repaired very efficiently. To characterize the AODV with the five criteria used by Keshav AODV is distributed, hop-by-hop, deterministic, single path and state dependent.
For uncast routing three control messages are used: RREQ (Route Reply), RREP (Route Reply), RERR (Route Error). If a node wants to send a packet to a node for which no route is available it broadcasts a RREQ to find one. A RREP includes a unique identifier, the destination IP address and sequence number, the source IP address and sequence number as well as a hop count initialized with zero and some flags.
If a node receives a RREQ which it does not have seen before it sets up a reverse route to the sender. If it does not know a route to the destination it rebroadcasts the updated RREQ especially incrementing the hop count. If it knows a route to the destination it creates a RREP.
The RREP is uncased to the origin node taking advantage of the reverse routes. A RREP contains the destination IP address and sequence number, the source IP address, a time to life, a hop count as well as a prefix only used for subnets and some flags. When a node receives a RREP it checks if the hop counts in the RREP for the emitter of the message is lower than the one in its own routing table or the destination sequence number in the message is higher than the one in its own routing table. If none of them is true it just throws the package away. Otherwise it updates its routing table and if it is not the destination it reunicasts the RREP.
One of the grate advantages of AODV is its integrated multicast routing. In a multicast routing table the IP address and the sequence number of the group are stored. Also the leaders IP address and the hop count to him are stored as well as the next hop in the multicasting tree and the lifetime of it. To join a multicast group a node has to send an RREQ to the group address with the join flag set. Any node in the multicast tree which receives the RREQ can answer with a RREP. Like this a requester could receive several RREP from which he can choose the one with the shortest distance to the group. A MACT (Multicast Activation) Message is send to the chosen tree node to activate this branch. If a requester does not receive a RREP, the node supposes that there exists no multicast tree for this group in this network segment and it becomes the group leader. A multicast RREP contains additional the IP of the group leader and the hop count to the next group member. The group leader broadcasts periodically a group hello message (a RREP) and increments each time the sequence number of the group.
There are two types of different implementations, user space daemons and kernel modules. The first of them requires to maintain an own routing table and was first implemented in the Mad-hoc Implementation by Fredrik Lilieblad, Oskar Mattson, Petra Nylon, Dan Ouchterlony, Anders Roxana running on a Linux 2.2 kernel but does not supports multicast. The University of Uppsala also published an user space daemon implementation called AODV-UU which runs on Linux with a 2.4 kernel. The newest daemon Moment was published on the 2nd of April 2002 by the University of California, Santa Barbara also running on a Linux with a 2.4 kernel. The only kernel implementation was done by the NIST, Department of Commerce's Technology Administration U.S., Wireless Communications Technologies Group running on a Linux with a 2.4 kernel. It is very fast and efficient reaching the best performance of all implementations.
Joined: Apr 2012
01-09-2012, 01:00 PM
Ad hoc On-demand Distance Vector (AODV) Routing Protocol
AODV.ppt (Size: 964.5 KB / Downloads: 188)
AODV is a packet routing protocol designed for use in mobile ad hoc networks (MANET)
Intended for networks that may contain thousands of nodes
One of a class of demand-driven protocols
The route discovery mechanism is invoked only if a route to a destination is not known
UDP is the transport layer protocol
Source, destination and next hop are addressed using IP addressing
Each node maintains a routing table that contains information about reaching destination nodes.
Each entry is keyed to a destination node.
Routing Table Fields
Destination IP address
Destination Sequence Number
Valid Destination Sequence Number Flag
Other state and routing flags
Hop Count (needed to reach destination)
Lifetime (route expiration or deletion time)
AODV Operation – Message Types
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.
Other possible methods to improve AODV congestion handling:
A route may predict when congestion is about to occur and try to avoid it by reduce the transmission rate.
Schedule the requests so that it will not overload the network.
Information “Freshness” Assured
AODV depends on each node in the network to own and maintain its destination sequence number.
A destination node increments its own sequence number immediately before it originates a route discovery
A destination node increments its own sequence number immediately before it originates a RREP in response to a RREQ
The node treats its sequence number as an unsigned number when incrementing accomplishing sequence number rollover.
Destination information is assured by comparing the sequence number of the incoming AODV message with its sequence number for that destination.