Transcript Routing for MANET

Routing in Mobile Ad Hoc Networks
(from Ad Hoc Networking by Charles Perkins)
Thanks to Prof. Yu at Cleveland State Univ.
Contents
Network layer solutions in infrastructure-less networks
 What is MANET: Mobile ad hoc (multihop) networks?
 Routing algorithms for MANETs
 Flooding
 Dynamic Source Routing (DSR)
 Ad-hoc On-Demand Distance Vector (AODV)
2
Mobile Ad Hoc Networks (MANETs)
 A collection of mobile hosts may form a temporary
network without the aid of any established
infrastructure or centralized administration (base
station)
 Routes between nodes may potentially contain
multiple hops, thus also called multihop networks
 Better space utilization than direct communication
 Requires a longer latency as for a single communication pair
due to more number of hops
 But the overall performance improves because simultaneous
transmissions are allowed as long as they are separated in
space
 Better energy utilization3than direct communication
Mobile Ad Hoc Networks
 Multihop
communication
 May need to traverse
multiple links to reach
a destination
 C is not reachable from E
A but can
communicate via B
A graph can be used
to model a MANET
C
C
E
B
B
A
 Major difficulty
A
 Mobility causes route
changes
4
Why Ad Hoc Networks ?
Advantages
 Applications
 Personal area networking
 cell phone, laptop, ear
phone, wrist watch
 Ease of deployment
 Speed of
deployment
 Decreased
dependence on
infrastructure
 Military environments
 soldiers, tanks, planes
 Civilian environments




taxi cab network
meeting rooms
sports stadiums
boats, small aircraft
 Emergency operations
 search-and-rescue
 policing and fire fighting
5
Characteristics of MANET
 Characteristics





Dynamic topology
Broadcast transmission: overhearing is possible
Bidirectional connection
Limited resources: bandwidth, CPU, battery
Higher link error rate
 Assumptions
 Moderate movement with respect to packet transmission
latency
 Promiscuous receive mode
 Enough number of mobile hosts: no network partitioning
6
Hierarchical architecture
Internet
802.11a
(5GHz)
Router/
Gateway
Router/
Gateway
Router
Wireless Mesh
Backhaul
Router
Router
Router
Router
AP/
Router
Router
AP
Router
802.11b/g
(2.4GHz)
AP
AP
AP
Mobile Path
Handoff
New Route
Old Route
7
Contents
Network layer solutions in infrastructure-less networks
 What is MANET: Mobile ad hoc (multihop) networks?
 Routing algorithms for MANETs
 Flooding
 Dynamic Source Routing (DSR)
 Ad-hoc On-Demand Distance Vector (AODV)
8
Flooding of Control Packets
How to reduce the scope of the route request
flood ?
 LAR (Localized Area Routing)
 Query localization
How to reduce redundant broadcasts ?
 The Broadcast Storm Problem
9
Flooding for Data Delivery
 Sender S broadcasts data packet P to all its neighbors
 Each node receiving P forwards P to its neighbors
 Sequence numbers used to avoid the possibility of forwarding the
same packet more than once
 Packet P reaches destination D provided that D is reachable
from sender S
 Node D does not forward the packet
10
Flooding for Data Delivery
Y
Broadcast transmission
Z
S
E
F
B
C
M
J
A
L
G
H
K
D
I
N
Represents transmission of packet P
11
Flooding for Data Delivery
Y
Z
S
E
F
B
C
M
J
A
L
G
H
K
D
I
N
• Node H receives packet P from two neighbors:
potential for collision
12
Flooding for Data Delivery
Y
Z
S
E
F
B
C
M
J
A
L
G
H
K
I
D
N
• Node C receives packet P from G and H, but does not forward
it again, because node C has already forwarded packet P once
13
Y
Flooding for Data Delivery
Z
S
E
F
B
C
M
J
A
L
G
H
K
D
I
N
• Nodes J and K both broadcast packet P to node D
• Since nodes J and K are hidden from each other, their
transmissions may collide
=> Packet P may not be delivered to node D at all,
despite the use of flooding
14
Flooding for Data Delivery
Y
Z
S
E
F
B
C
M
J
A
L
G
H
K
D
I
N
• Node D does not forward packet P, because node D
is the intended destination of packet P
15
Y
Flooding for Data Delivery
Z
S
E
F
B
C
M
J
A
L
G
H
K
I
D
N
• Flooding completed
• Nodes unreachable from S do not receive packet P (e.g., node Z)
• Nodes for which all paths from S go through the destination D
also do not receive packet P (example: node N)
16
Flooding for Data Delivery
Y
Z
S
E
F
B
C
M
J
A
L
G
H
K
I
D
N
• Flooding may deliver packets to too many nodes
(in the worst case, all nodes reachable from sender
may receive the packet)
17
Flooding for Data Delivery:
Advantages & Disadvantages
Advantages
 Simplicity
 May be more efficient than other protocols when
rate of information transmission is low enough
 Potentially higher reliability of data delivery
 Because packets may be delivered to the destination on
multiple paths
18
Flooding for Data Delivery:
Advantages & Disadvantages
Disadvantages
 Potentially, very high overhead
 Data packets may be delivered to too many nodes who do
not need to receive them
 Potentially lower reliability of data delivery
 Flooding uses broadcasting -- hard to implement reliable
broadcast delivery without significantly increasing
overhead
• Broadcasting in IEEE 802.11 MAC is unreliable (no
ACK)
 In our example, nodes J and K may transmit to node D
simultaneously, resulting in loss of the packet
• in this case, destination would not receive the packet
19
at all
Dynamic Source Routing (DSR)
Source determines the entire path to the
destination when it has data packet to send
 On-demand or reactive protocols
 No periodic advertisements
Three control packets: RREQ, RREP, RERR
Procedures
(1) Route discovery procedure
(2) Route maintenance procedure
(3) DSR Optimizations (Route cache)
20
Assumption:
Cooperative nodes
Moderate speed of node
Relatively small network diameter (5-10 hops)
Detectable packet error
Unidirectional or bidirectional link
A single IP address
Promiscuous mode (optional)
21
Route Discovery
B
A-B-D-G
A-B-D-G
A-B-D-G
Initiator ID
G
Initiator seq#
A-B
A
RREQ FORMAT
A-B-D
D
Target ID
Partial route
A
A-C-E
A
H
E
A-C-E
Route Request (RREQ)
A-C-E
C
A-C
Route Reply (RREP)
F
- Each node appends own identifier when forwarding
RREQ
- RREQ is broadcast, while22
RREP is unicast
Route Discovery: at source A
A needs to send to G
Lookup Cache for route A to G
Start Route
Discovery
Protocol
wait
Route
Discovery
finished
no
Buffer
packet
Continue
normal
processing
Route
found?
yes
yes
Packet
in
buffer?
Write route in
packet header
no
23don
e
Send
packet to
next-hop
Route Discovery: At an intermediate node
<src,id> in
recently
seen
requests
list?
Accept route
request
packet
yes
Discard
route
request
no
Host’s
address
already in
partial
route
Append
myAddr to
partial route
Store <src,id>
in list
Broadcast packet
no
no
myAdd
r=targ
et
yes
Send route
reply packet
24done
yes
Discard
route
request
Route Reply in DSR
 Route Reply can be sent by reversing the route in
Route Request (RREQ) only if links are guaranteed to
be bi-directional
 To ensure this, RREQ should be forwarded only if it
received on a link that is known to be bi-directional
 If unidirectional (asymmetric) links are allowed, then
RREP may need a route discovery for A from node G
 Unless node G already knows a route to node A
 If a route discovery is initiated by G for a route to A, then
the Route Reply is piggybacked on the Route Request
from G.
 If IEEE 802.11 MAC is used to send data, then links
have to be bi-directional25
(since Ack is used)
Now, Route is Discovered
 Node A on receiving RREP, caches the route
included in the RREP
 When node A sends a data packet to G, the
entire route is included in the packet header
 hence the name source routing
 Intermediate nodes use the source route
included in a packet to determine to whom a
packet should be forwarded
26
Route Maintenance
B
RERR
RERR
G
D
G
A
Route Cache (A)
G: A, B, D, G G:
A, C, E, H, G
F: C, E, F
H
E
C
F
27
Additional feature #1: Caching
Overheard Routes
Node C Cache
E:
E:C,
C,D,
D,EE
A:
C, B, A
Z: C,
X, Y, Z V: C,
X, W, V
Node A Cache
E: A, B, C, D, E
A
B
C
D
E
V
W
X
Y
Z
28
Route Caching: Beware!
 When sending a RREQ
 Send first with TTL=1 hoping that nearby hosts have
an entry: non-propagating route request
 If no reply for some time, send RREQ with maximum
TTL
 This is called “Expand Ring Search”
 Beware
 Stale caches can adversely affect performance
 With passage of time and host mobility, cached routes
may become invalid
 A sender host may try several stale routes (obtained
from local cache, or replied from cache by other
nodes), before finding a good route
 Adverse impact on TCP
29
Additional feature #2: RREP with
Cached Routes
B
RERR
RERR
RREQ
(! D-G)
D
G
A
Route Cache (A)
G: A, B, D, G
F: C, E, F
G:A,C,E,H,G
RREQ
(! D-G)
RREQ
(! D-G)
H
E
RREP
C
F
Route Cache (C)
G: C, E, D,
H, G
30
Additional feature #3: Packet
Salvage
B
RERR
RERR
G
D
A
G
Route Cache (D)
G: D, E, H, G
H
E
C
F
Caution: No double salvage
allowed !!!
31
A Summary of DSR
Entirely on-demand, potentially zero control message
overhead
Trivially loop-free with source routing
Conceptually supports unidirectional links as well as
bidirectional links
High packet delays/jitters associated with on-demand
routing
Space overhead in packets and route caches
Promiscuous mode operations consume excessive amount
of power
Network partition problem - Message explosion problem
(large number of route request packets)
 Use exponential backoff to limit the rate at which new route
32 for the same target
discoveries may be initiated
Contents
Network layer solutions in infrastructure-less networks
 What is MANET: Mobile ad hoc (multihop) networks?
 Routing algorithms for MANETs
 Flooding
 Dynamic Source Routing (DSR)
 Ad-hoc On-Demand Distance Vector (AODV)
33
Ad Hoc On-Demand Distance
Vector Routing (AODV)
* Explained very well in C.E.Perkins’ Ad Hoc Networking book
 DSR vs DSDV
 DSR typically outperforms DSDV because periodic control
messages are not needed
 A main drawback of DSR is the large packet header (entire
route information)
 AODV = DSR + DSDV
 Routes are discovered only when there are packets (ondemand) as in DSR
 Nodes main distance and next node vectors as in DSDV to
reduce the header size
34
Route Discovery in DSR
B
A-B-D-G
A-B-D-G
Initiator ID
G
Initiator seq#
A-B
A
A-B-D-G
RREQ FORMAT
A-B-D
D
Target ID
Partial route
A
A-C-E
A
H
E
A-C-E
Route Request (RREQ)
A-C-E
C
A-C
Route Reply (RREP)
F
- Each node appends own identifier when forwarding
RREQ
35
Route Discovery in AODV
B
G, A, 2
G, A, 3
G, A, 1
A, G, 1
RREQ FORMAT
Initiator ID
G
Target ID
A, G, 2
D
A
A, G, 3
Hop count
A, G, 3
A, G, 1
H
E
A, G, 3
Route Request (RREQ)
A, G, 3
C
A, G, 2
Route Reply (RREP)
F
- Each node remembers where the packet came from
(reverse path) during RREQ.
36 RREP.
- It set up forward path during
Reverse Path Setup in AODV
Y
Z
S
E
F
B
C
M
J
A
L
G
H
K
I
D
N
37
Forward Path Setup in AODV
Y
Z
S
E
F
B
C
M
J
A
L
G
H
K
D
I
N
Forward links are setup when RREP travels along
the reverse path
Those paths are not included in the header of each data packet
but stored in each node as a routing table or DV
38
Link State Routing
 LSR
 Each node periodically floods status of its links
 Each node re-broadcasts link state information received from
its neighbor
 Each node keeps track of link state information received from
other nodes
 Each node uses above information to determine next hop to
each destination
 Direct application of LSR in a MANET is difficult due
to a large control overhead
 Due to mobility, broadcast period cannot be reduced as in
wired network
39
Routing in MANET (Unicast)
 Many protocols have been proposed
 Some have been invented specifically for MANET
 Others are adapted from previously proposed protocols for wired
networks
 No single protocol works well in all environments
 some attempts made to develop adaptive protocols
 Proactive protocols (or called “Table-based”)
 Determine routes independent of traffic pattern
 Traditional LS and DV routing protocols are proactive
 Reactive protocols (or called “On-demand”)
 Maintain routes only if needed (DSR)
 Hybrid protocols
40
Reactive Routing Protocols
 Flooding
 Data packets are flooded to the destination
 But also to all other nodes => much overhead but more
reliable
 DSR (Dynamic Source Routing)
 First, small control packet is flooded to discover a route
 Then, unicast data packets along the discovered route
 But each data packet includes the information on the entire
path in its packet header => larger packet size
 AODV (Ad-hoc On-demand Distance Vector)
 Route discovery as in DSR but each node keeps a routing
table as in proactive algorithm to reduce the packet size
 Reactive + Proactive
41
Trade-Off between Proactive and
Reactive Protocols
 Latency of route discovery
 Proactive protocols may have lower latency since routes are
maintained at all times
 Reactive protocols may have higher latency because a route from X
to Y will be found only when X attempts to send to Y
 Overhead of route discovery/maintenance
 Reactive protocols may have lower overhead since routes are
determined only if needed
 Proactive protocols can (but not necessarily) result in higher
overhead due to continuous route updating
 Which approach achieves a better trade-off depends on the
traffic and mobility patterns
42