Transcript Ad-hoc On-Demand Distance Vector Routing (AODV) and

Ad-hoc On-Demand
Distance Vector Routing
(AODV) and simulation in
network simulator
Content





Introduction to ad-hoc networks
AODV : Concept
AODV : Mechanism
Simulation in Network Simulator
Conclusions
Introduction to ad-hoc networks

Network of mobile wireless nodes
 No infrastructure (e.g., base stations, fixed routers, centralized
servers)
Dynamic topology
 Routing infrastructure created dynamically at intermediate
node
 Data can be relayed by intermediate nodes
 Limited battery power and transmission range resources in the
nodes
Usage:
 Military environments, emergency and rescue operations,
meeting rooms, etc


AODV : Concept





Reactive routing
 Pure on-demand route acquisition system
 The routes are created when needed, so called “on-demand”
A broadcast route discovery mechanism
 RREQ (Route Request packet) broadcasting to find a route
 RREP (Route Reply packet) is used to set up forward path
Dynamic establishment of route table entries
 Nodes lie on active paths only maintain routing information
Destination sequence number
 Prevention of routing loops
 Avoidance of old and broken routes
Maintenance of timer-based states
 A routing table entry is expired if not used recently
AODV : Mechanism

Path discovery
Every node maintains two separate counters
 Sequence number
 Broadcast-id (increments whenever the suorce issues a new
RREQ)
 The source requests using RREQ broadcasting
 <source_addr, source_sequence#, broadcast_id, dest_addr,
dest_sequence#, hop_cnt>
 Destination number of RREQ is the last known number to the
source
 The destination replies using RREP (Route Reply) unicasting
 <source_addr, dest_addr, dest_sequence#, hop_cnt, lifetime>
 The sequence number is first incremented if it is equal to the
number in the request
 RREP contains the current sequence number, hop count = 0,
full lifetime
 Intermediate nodes
 Discard duplicate requests
 Replies if it has an active route with higher destination
sequence number
 Otherwise broadcasts the request on all interfaces
AODV : Mechanism

Path discovery
 Intermediate nodes
 Setup reverse path
 A node records the address of the neighbor who send
RREQ
 Keep track of some information
 Destination IP address, Source Ip address, Broadcast_id,
Expiration time for reverse path route entry, Source node’s
sequence number
 Setup forward path
 Unicast RREP (Route reply) back to the reverse path
 Each node along the path sets up a forward pointer to
the node from which the RREP came
 Update its routing table entry


Propagate the first RREP or the RREP if contains a greater
destination sequence# or the same sequence# with a smaller
hop count then contained in RREQ
Nodes that are not along the path determined by the RREP will
timeout and will delete the reverse pointers
Example
A
L
Y
F
J
B
K

G
C
S
D
P
<S, 11, 1, D, 0, 1>
E
H
I
T
Z
RREQ
Example
A
L
Y
F
J
B
K
G
C
S
D
P
E
H
I
T
Z
Reverse
Path Setup
Example
A
L
Y
F
J
B
K
G
C
S
D
P
E
H
I
T
Z
Example
A
L
Y
F
J
B
K
G
C
S
D
P
E
H
I
T
Z
Example
A
L
Y
F
J
B
K
G
C
S
D
P
E
H
I
T
Z
RREP
Example
A
L
Y
F
J
B
K
G
C
S
D
P
E
H
I
T
Z
Forward
path setup
Example
A
L
Y
F
J
B
K
G
C
S
D
P
E
H
I
T
Z
Example
A
L
Y
F
J
B
K
G
C
S
D
P
E
H
I
T
Z
Example
A
L
Y
F
J
B
K
G
C
S
D
P
E
H
I
T
Z

Route table management
 Soft-state associated with the entry (useful information stored in
route table management):
 Route request expiration time (purpose of this timer is to erase
reverse path routing entries from those nodes that do not lie
on the path)
 Route caching timeout (or the time after which the route is
considered to be invalid)
 Active route timeout (this information is maintained so that all
active source nodes can be notified when a link breaks)
 A neighbor is considered active if it originates or relays at least
one packet to the destination

Path maintenance
 Neighboring nodes with active routes periodically exchange
hello messages
 If a next hop link in the routing table fails, the active neighbors are
informed
 The RERR (unsolicited RREP) indicates the unreachable
destinations
 <source_addr, dest_addr, current sequence# + 1, infinity,
lifetime>
 The source performs a new route request when it receives a RERR
Simulation in network simulator


Now we are going to start simulation in Network Simulator
This example contains 30 nodes which are moving and use AODV
routing protocol
Conclusion




AODV -- efficient algorithm for ad-hoc networks
Need for broadcast is minimized
Quick response to link breakage in active routes
Loop free routes
THE END