Transcript Document

AODVjr
A Simplified Version of AODV
Luke Klein-Berndt & Ian Chakeres
National Institute of Standards and Technology
University of California at Santa Barbara
Ad hoc On-Demand Distance Vector (AODV) Routing
AODV is an ad-hoc routing protocol. It is able to discover a route
through a network of computers.
•Creates routes on-demand
•Built for mobile networks
•Loop free with quick convergence
•Can scale to handle a few hundred nodes
•Can be integrated into the existing protocol stack
When AODV was designed it incorporated many features designed to
maximize performance at the cost of added complexity.
Simplicity
The goal of AODVjr is simplicity. Unlike AODV it does not
require:
•RERR messages
•Sequence numbers
•Precursor lists
•Gratuitous RREP
•Hop count
•Hello messages
It is able to do this by requiring only destinations to reply to
RREQ and uses end-to-end hello messages to maintain routes.
Link Layer Detection
• Link layer detection allows a sending node to detect if a unicast
packet is successfully received.
• In simulations AODV using link layer detection provides
amazing performance.
• Currently it is impossible to access link layer feedback
information in off the shelf hardware.
• Current implementations use periodic hello messages to detect
local link connectivity.
• Hello messages cause a large amount of control overhead.
Each node must periodically send broadcast packets. Each
receiving node must also process them.
Route Discovery
AODVjr
RREQ
1
RREQ
2
RREQ
3
RREP
RREQ
4
RREP
5
RREP
RREP
Only the
route dest
can
respond
3 Sends RREP
because it has
an active route
to 5
RREQ
1
RREQ
2
RREP
3
RREP
AODV
4
5
Route Maintenance
AODVjr
Data
Source
1
2
3
4
5
Dest
Connect
Message
•The source route is kept alive by data traveling along it.
•If the destination has received data in the past few
seconds and has not sent data to the source, it sends a
Connect message to the source, maintaining the reverse
route.
Route Maintenance
AODV
Data
1
2
3
4
Hello Message
•Periodic Hello messages are used to detect link
connectivity along the source route.
•In simulation it is possible to use link layer feedback to
sense link breaks.
•The source route is kept alive by data traversing it.
5
Route Maintenance
AODVjr
Dest
Data
Source
1
2
3
4
• The route source will stop receiving Connect
messages and detects link break.
5
Connect
Message
AODV
Data
1
2
3
4
RERR
• Upstream node detects a link break and sends a RERR.
5
Simulations
•
•
•
•
•
•
•
•
NS-2
AODV from Mahesh Marina
AODVjr developed by us
Random waypoint
802.11 2Mbps
900 seconds
Five runs averaged
Ten sources (unless otherwise noted), five
512-byte packets per second
Performance
1.01
1
0.99
Packet Delivery
0.98
AODV
0.97
AODVjr
AODV LL
0.96
0.95
0.94
0.93
1
2
5
10
Meters / Sec
Network of 25 Nodes
15
20
50 Nodes
1.02
1
Packet Delivery
0.98
0.96
0.94
0.92
0.9
0.88
1
2
5
10
15
20
10
15
20
Meters / Sec
100 Nodes
1.05
1
Packet Delivery
0.95
0.9
0.85
0.8
0.75
1
2
5
Meters / Sec
Normalized Routing Load
0.8
0.7
Normalized Routing Load
0.6
0.5
AODV
0.4
AODVjr
AODV LL
0.3
0.2
0.1
0
1
2
5
10
15
20
Meters / Sec
In a network of 25 nodes, with 10 sources, AODVjr
maintains a much lower normalized routing load
compared to AODV with hello messages.
Control Overhead
AODV with hello messages
•Every node in the network must broadcast a Hello
message and every receiving node must process it.
Routing overhead is controlled by the total number of
nodes.
•If a route breaks a RERR message must be sent to
each node using that route, eventually reaching the
source.
AODVjr
• Connect packets are unicast from destination to source
along active routes; routing overhead is affected by the
number of active routes.
Route Maintenance Packets
100000
90000
Number of Connection Packets
80000
70000
60000
AODV
50000
AODVjr
40000
30000
20000
10000
0
25
50
75
100
Number of Nodes
The number of nodes in the network
determines the number of route maintenance
packets in AODV (with hello messages)
generates.
Route Maintenance Packets
30000
Number of Connection Packets
25000
20000
AODV
15000
AODVjr
10000
5000
0
1
5
10
15
Number of Route Sources
In AODVjr the number of route maintenance
packets is directly related to the number of
active routes.
20
Route Discovery Latency
45
40
35
Percent Distribution
30
25
AODV
AODVjr
20
15
10
5
0
0
0.01
0.02
0.03
0.04
0.05
Seconds
Since AODVjr discovers the entire route, it has a
slightly higher route discovery latency compared to
AODV.
0.06
Conclusion
•With currently available hardware AODVjr is as good
as AODV with hello messages.
•Routing overhead in AODVjr is related to the
number of active routes, not the number of nodes.
•RERR messages, sequence numbers and other
optimizations could be added optionally to further
improve performance.
•Security can easily be added as there are no
mutable fields in the control packets.
•AODVjr is much simpler than AODV.