LM CCN Section 4.1: Mobile Ad-hoc Networks
Computer and Communication Networks
Mobile Ad-hoc Networks John Easton
1
Learning Objectives
o Mobile Ad-hoc Networks – Basics of MANETS
– Routing
o Flooding
oDynamic Source Routing (DSR)
oAd-hoc On-demand Distance Vector (AODV) routing
2
MANETs
o Mobile Ad-hoc Network
– Formed by (mobile) wireless
hosts
– Often no pre-existing infrastructure
– Routes may contain many hops o Multiple links to be traversed
between source – destination
– Mobility of nodes leads to route changes
Source
Destination
3
1
LM CCN Section 4.1: Mobile Ad-hoc Networks
MANETs (Cont.)
Source
Destination
4
MANETs (Cont.)
o Why use MANETs?
– Ease of deployment
– Speed of deployment
– Decreased infrastructure dependence
o Applications – PANs
o Phones, ear buds, watches – Civilian
o Vehicle networks – Emergency / military
o Search and rescue o Disaster zones
5
MANETs (Cont.)
o Maryvariants
– Fullysymmetric
o All nodes have identical capabilities – Asymmetric
o Capabilities
o Responsibilities
– Trafficcharacteristicsmaydiffer
o Bit rates
o Timeliness constraints o Reliability requirements
– Addressing
o Unicast / multicast / geocast
o Host / content / capability based
6
2
LM CCN Section 4.1: Mobile Ad-hoc Networks
MANETs (Cont.)
o Mobility is a major source of variation – Pattern
o People in airport lounges o Vehicles
o Sensors on assets
– Characteristics
o Speed of movement o Predictability
– Direction
– Pattern
o Uniformity amongst nodes
7
MANETs (Cont.)
o A good protocol for use with MANETs must account for: – Limited transmission range
– Broadcast nature of medium
– Packet loss / transmission errors
– Mobility induced issues – Power constraints
– Security
o No single protocol addresses all issues
o Performance metrics often do not scale well with mobility
8
Unicast Routing in MANETs
o What’s special about MANET routing? – Host mobility (particularly at speed) – Unusual performance criteria
o Route stability
o Energy consumption
o Unicast MANET routing protocol classes
– Proactive protocols
o Traditional link-state and distance-vector protocols etc.
– Reactive protocols
o Maintain routes only if needed
– Hybrid protocols
9
3
LM CCN Section 4.1: Mobile Ad-hoc Networks
Unicast Routing in MANETs (Cont.)
o MANETroutingprotocoltrade-offs – Delaysfromroutediscovery
o Proactive approaches have lower delay to transmission – Routes continuously updated
o Reactive protocols have some delay
– Route for X to Y only discovered upon transmission
attempt
– Overheadofroutemaintenance
o Reactive protocols have lower maintenance overhead – Routes only discovered / updated as needed
o Proactive protocols can result in higher delays – Continuous route update / maintenance
– Optimalchoicedependsontrafficandmobilitypatterns
10
Flooding in MANETs
o Flooding for data delivery
– Sender S broadcasts data packet P
to neighbours
o Packet bound for D
– Each node receiving P forwards to neighbours
– Sequence numbers prevent multiple forwarding
– Packet P reaches D provided D is reachable
o D does not forward (it is the target)
11
Flooding
FNlodoedsinJg acnodmKplebtoeth broadcast P to D.
FZAlsoaonJdainYgdamKreauyrendreheliaidvcdeheranpbaflrecokfmoertesSatocshotodoomnaont yrencoediveesP
NoNBHoAdtrnohoreydeaeCcrnd,eocDtrihdaveedscitsoeroeoiPtvnrsfelayPfsnroroswPemtmaitfhcoir2sohirsnwmnaioebanGilrgedshatPmbhn,oradouyuHrsgc,ohbllduidetesdtoineastion also (all nodes reachable from sender in worst case)
Y
noatP-drt>soaofenoPtietsrnwimsntaiaoiatsrhytldsercineoaodocnsletleiisrsbitaviteohinenagdaPsetiloaiovnlfreSoraefdPytoseDen it despite flooding
E
S BFL
C
AHG
J
D
K
Z
M
N
Node that has I received P
Connected nodes within transmission range
Transmission of P
12
4
LM CCN Section 4.1: Mobile Ad-hoc Networks
Advantages of Flooding for
Data Delivery
o As a data delivery mechanism, flooding is:
– Simple
– May be more efficient than proactive protocols if rate of transmission in network is low
o e.g. small, infrequent transmissions in a topology that changes regularly
– Potential for higher reliability of delivery o Multiple paths used for transmission
13
Disadvantages of Flooding for
Data Delivery
o A a data delivery mechanism, flooding risks: – High traffic overhead
o Packets delivered to many nodes, most of which don’t need them
o Bad for low-power use
– Packets may be lost due to collisions
o Broadcast in 802.11 MAC is unreliable
14
Flooding for Control
o Many protocols use flooding for control packets
– Often limited
– Control packets used for route discovery
o Discovered routes then used for data packets
– Traffic overhead of control packet flooding is amortised over targeted data packet transmissions
15
5
LM CCN Section 4.1: Mobile Ad-hoc Networks
Broadcast Storm Problem
o Imagine node A broadcasts a route query
– Nodes B and C receive it
– Next, B and C forward it onto their neighbours
o Because B and C received at the same time, they retransmit at the same time
– High probability of collision at D o Issue of redundancy
– Any node many receive the route request multiple times
D
BC
A
16
Broadcast Storm Problem (Cont.)
o Possible solutions
– Probabilistic scheme
– Implement a random delay
o “Jittering”
– Implement counter-based scheme
– Implement a distance-based scheme
D
B C
dA
17
Broadcast Storm Problem (Cont.)
o Summary
– Flooding is used in many protocols
o Inc. Dynamic Source Routing
– Problems associated with flooding
o Collisions
o Redundancy
– Collisions can be reduced by jittering
– Redundancy may be reduced by only retransmitting from a portion of the nodes
18
6
LM CCN Section 4.1: Mobile Ad-hoc Networks
Dynamic Source Routing
o Dynamic Source Routing
– When node S wants to route data to node D,
it initiates a route discovery
– S floods the network with RREQ messages
– Each node forwards the RREQ, appending its
identifier
o To find out more review
– Johnson, D.B. and Maltz, D.A. 1996. Dynamic
source routing in ad hoc wireless networks. Mobile Computing, lmielinski, T. and Korth, H. (Eds.), Kluwer, 153-81
19
Dynamic Source Routing (Cont.)
C
AHG
Y
Z BFL
E S
M
J
[S, E, F, J]
RREQ + D
K
N
Node that has I received RREQ
Connected nodes within transmission range
Transmission of RREQ
20
Dynamic Source Routing (Cont.)
o Route Discovery in DSR
– Destination D on receiving first RREQ sends a route reply (RREP)
– RREP is sent on route obtained when RREQ path is reversed
– RREP includes the route from S to D on which RREQ was received
21
7
LM CCN Section 4.1: Mobile Ad-hoc Networks
Dynamic Source Routing (Cont.)
E
Y
RREP +
[S, E, F, J, D]
S BFL
C
AHG
J
D
K
Z
M
N
Node that has I received RREQ
Connected nodes within transmission range
Transmission of RREP
22
Dynamic Source Routing (Cont.)
o RREP can use reverse of RREQ route only if links are bi-directional – RREQ should only be forwarded initially on bi-directional links
o If unidirectional links are allowed, RREP may need a route discovery for S from D
– Unless this is known already
– If RREQ for S is issued, RREP from S to D is piggybacked on
message
o If 802.11 MAC is used, all links must be bi-direction – ACK is used
23
Dynamic Source Routing (Cont.)
o Node S, on receipt of RREP, caches the route
– Data for D is transmitted with entire route in header
o Hence “source routing”
– Intermediate nodes remove their identifier from route
and forward to next node o Optimised route caching
– Intermediate nodes may learn routes from content of RREQ and RREP messages they forward
o Route errors (RERR) work in similar way
24
8
LM CCN Section 4.1: Mobile Ad-hoc Networks
Dynamic Source Routing (Cont.)
E
S BFL
Y
RERR [J, D]
Z
M
N
C
AHG
J
D
K
Node that has I received RREQ
Connected nodes within transmission range
Transmission of RERR
25
Dynamic Source Routing (Cont.)
o Disadvantages of route caching
– Stale caches can adversely effect
performance
– Passage of time and host mobility
lead to routes becoming stale
– Several stale routes may be tried before a good route is found
– Adverse impact on TCP
26
Dynamic Source Routing (Cont.)
o Advantages
– Routes maintained only between communicating nodes
o Reduced route maintenance
– Route caching can be used to reduce discovery overhead
– A single discovery may yield many routes due to intermediate nodes
o Disadvantages
– Packets grow with route
length
– Flood requests may reach all nodes
o Energy
– Must avoid RREQ collisions
o Jittering
– Increased contention if
nodes form RREPs from local caches
– Intermediate nodes may RREP using stale cache
27
9
LM CCN Section 4.1: Mobile Ad-hoc Networks
AODV
o Ad-hoc On-demand Distance Vector (AODV) routing o DSR stores routes in packet headers
– Large packets
– May degrade performance if data is small
o AODV attempts to improve on DSR by maintaining routing
tables at nodes
o Retains the advantage that routes are only maintained between
communicating nodes o To find out more review
– Perkins, C.E. and Royer, E.M. 1999. Ad-hoc On-Demand Distance Vector Routing. Proc. 2nd IEEE Wksp. Mobile Comp. Sys. and Apps., 90-100.
28
AODV (Cont.)
o Route requests (RREQ) forwarded in same way as DSR
o On forwarding a RREQ, node sets up a temporary reverse path towards the source
– AODV assumes bi-directional links o When the destination node receives a
RREQ, it issues a RREP
o RREP travels along the temporary
reverse path set up behind RREQ
29
AODV (Cont.)
FSRBNRloireoeoenorvdvovgwaedldaericsDnsrsrdaegeisrvpcltoienaoatouhrktmtsftheseRpsciuilnRpsersetatEeseatunedQhtpidtsotewuobnadpiertehtinainrgdet raRtcrrodaRundntEteiseinQndmgRupiestRaesEbriolPnenosdraoengneoodfeSs & after a short time reverse paths timeout S
Y
E
Z BFL
C
AHG
J
D
K
M
N
Node that has I received RREQ
Connected nodes within transmission range
Transmission of RREQ
30
10
LM CCN Section 4.1: Mobile Ad-hoc Networks
AODV (Cont.)
o Route replies
– Intermediate nodes may reply with routes, provided they are more recent than the route known to S
o Based on a destination node sequence number
– The likelihood of an intermediate node issuing a RREP is not as high as DSR
o Many paths have < or same destination node sequence number
31
AODV (Cont.)
o Timeouts
– Routing table entries maintaining
reverse paths are purged after timeout interval
o Needs to be sufficient to allow return of RREP
– Forward paths are purged if not used for active_route_timeout interval
o May clear valid, but recently
unused routes
32
AODV (Cont.)
o Link failure reporting
– A neighbour of X is active if a packet was forwarded to it within active_route_timeout
– When a next-hop link is broken all active neighbours are informed
– Link failures are propagated using RERR messages, which also update destination sequence numbers
33
11
LM CCN Section 4.1: Mobile Ad-hoc Networks
AODV (Cont.)
o Routeerrorhandling
– WhennodeXisunabletoforwardpacketP(fromnodeStonode
D) on link (X,Y), it generates a RERR message
– NodeXincrementsthedestinationsequencenumberforDcached
at node X
– TheincrementedsequencenumberNisincludedintheRERR
– WhennodeSreceivestheRERR,itinitiatesanewroutediscovery
for D using destination sequence number at least as large as N o Destinationsequencenumber
– WhennodeDreceivestherouterequestwithdestinationsequence number N, node D will set its sequence number to N, unless it is already larger than N
34
AODV (Cont.)
o Link failure detection
– Hello messages: Neighbouring nodes periodically
exchange short hello message packets to indicate
active neighbour presence
– Absence of hello message is used as an indication of
link failure
– Alternatively, failure to receive several MAC-level
acknowledgement may be used as an indication of link failure
35
AODV (Cont.)
o Optimisations?
– Expanding Ring Search
o Route Requests are initially sent with small Time-to-Live (TTL) field, to limit their propagation
– DSR also includes a similar optimisation
o If no Route Reply is received, then larger TTL tried
36
12
LM CCN Section 4.1: Mobile Ad-hoc Networks
AODV (Cont.)
o Summary of AODV routing
– No need for routes in packet headers
– Nodes maintain table entries only for active routes
– At most one next-hop per destination is maintained at each
node
o DSR may maintain several routes
– Unused routes expire even if topology does not change
37
Summary
o Mobile Ad-hoc Networks – Basics of MANETS
– Routing
o Flooding
oDynamic Source Routing (DSR)
oAd-hoc On-demand Distance Vector (AODV) routing
38
13