Transcript Optimized Link State Routing Protocol for Ad Hoc Networks

Ad Hoc Networks
Cholatip Yawut
Faculty of Information Technology
King Mongkut's University of Technology North Bangkok
1
IEFT MANET Working Group

Goals




standardize an interdomain unicast (IP) routing protocol
define modes of efficient operation
support both static and dynamic topologies
A dozen candidate routing protocols have been propos
ed
2
Routing
??
?
?? ?
??
?
?
?
?
?
?
?
? ?
? ?
?
Ants Searching for Food
?
?
?
?
?
??
??
??
?
from Prof. Yu-Chee Tseng’s slides
3
Routing (Ants’ scenario)
4
Three Main Issues in Ants’ Life

Route Discovery:


Packet Forwarding:


searching for the places with food
delivering foods back home
Route Maintenance:

when foods move to new place
5
Introduction
Routing Protocol for
MANET
Table-Driven/
Proactive
Distance
Vector
DSDV
LinkState
OLSR
TBRPF
FSR
STAR
Hybrid
ZRP
On-Demanddriven/Reactive
DSR
AODV
TORA
Clusterbased/
Hierarchical
LANMAR
CEDAR
MANET: Mobile Ad hoc Network
(IETF working group)
Ref: Optimized Link State Routing Protocol for Ad Hoc Networks
Jacquet, p and park gi won
6
Reactive versus Proactive routing approach

Proactive Routing Protocols




Periodic exchange of control messages
+ immediately provide the required routes when needed
- Larger signalling traffic and power consumption.
Reactive Routing Protocols



Attempts to discover routes only on-demand by flooding
+ Smaller signalling traffic and power consumption.
- A long delay for application when no route to the destination
available
7
Routing Protocols

Proactive (Global/Table Driven)



Reactive (On-demand)



route determination at startup
maintain using periodic update
route determination as needed
route discovery process
Hybrid

combination of proactive and reactive
8
Proactive








Destination-sequenced distance vector (DSDV)
Wireless routing protocol (WRP)
Global state routing (GSR)
Fisheye state routing (FSR)
Source-tree adaptive routing (STAR)
Distance routing algorithm for mobility (DREAM)
Cluster-head gateway switch routing (CGSR)
OLSR (Optimized Link State Routing)
9
Reactive








Associativity-base routing (ABR)
Dynamic source routing (DSR)
Ad hoc on-demand distance vector (AODV)
Temporally ordered routing algorithm (TORA)
Routing on-demand acyclic multi-path (ROAM)
Light-weight mobile routing (LMR)
Signal stability adaptive (SSA)
Cluster-based routing protocol (CBRP)
10
Hybrid





Zone routing protocol (ZRP)
Zone-based hierarchical link state (ZHLS)
Distributed spanning trees (DST)
Distributed dynamic routing (DDR)
Scalable location update routing pro. (SLURP)
11
Flooding


Simplest of all routing protocols
Send all info to everybody
 If data not for you, send to all neighbors

Robust
 destination is guaranteed to receive data

Resource Intensive
 unnecessary traffic
 load increases, network performance drops quickly
12
Routing Examples








Destination Sequenced Distance Vector (DSDV)
Cluster Gateway Switch Routing (CGSR)
Ad hoc On-demand Distance Vector (AODV)
Dynamic Source Routing (DSR)
Zone Routing Protocol (ZRP)
Location-Aided Routing (LAR)
Distance Routing effect Algorithm for mobility (DREAM)
Power-Aware Routing (PAR)
13
Destination Sequenced Distance Vector
(DSDV)



Table-driven
Based on the distributed Bellman-Ford routing algorith
m
Each node maintains a routing table


Routing hops to each destination
Sequence number
14
DSDV

Problem


a lot of control traffic in the network
Solution: two types of route update packets


full dump (All available routing info)
incremental (Only changed info)
15
Cluster Gateway Switch Routing (CGSR)


Table-driven for inter-cluster routing
Uses DSDV for intra-cluster routing
C2
C1
M2
C3
16
Ad hoc On-demand Distance Vector (AODV)



On-demand driven
Nodes that are not on the selected path do not
maintain routing information
Route discovery
 source broadcasts a route request packet (RREQ)
 destination (or intermediate node with “fresh enou
gh” route to destination) replies a route reply pack
et (RREP)
17
AODV
N2
Source N1
N8
N5
N7
N4
N3
RREQ
Destination
N2
N5
N6
Source N1
Destination
N7
N4
N3
N8
N6
RREP
18
AODV

Problem


a node along the route moves
Solution



upstream neighbor notices the move
propagates a link failure notification message to each of its ac
tive upstream neighbors
source receives the message and re-initiate route discovery
19
Dynamic Source Routing (DSR)




On-demand driven
Based on the concept of source routing
Required to maintain route caches
Two major phases


Route discovery (flooding)
Route maintenance

A route error packet
20
DSR
N1-N2
N1-N2-N5
N2
N8
N5
N1
N1-N3-N4
N1
N7
N4
N1
N1-N3-N4
N1-N3
N3
N1-N3-N4-N7
N1-N3-N4
Route Discovery
N2
N1-N3-N4-N6
N6
N1-N2-N5-N
8
N5
N1-N2-N5-N
N8
8
N1-N2-N5-N
8
N1
N7
N4
N3
Route Reply
N6
21
Modified DSR

Route information determined by the current network
conditions




number of hops
congestion
node energy
Other considerations


fairness
number of route requests
22
Zone Routing Protocol (ZRP)

Hybrid protocol



On-demand
Proactive
ZRP has three sub-protocols



Intrazone Routing Protocol (IARP)
Interzone Routing Protocol (IERP)
Bordercast Resolution Protocol (BRP)
23
Zone Routing Protocol (ZRP)
Zone of Node Y
Border Node
Zone Radius = r Hops
Border Node
Zone of Node Z
Node Z
Node X
Zone of Node X
Bordercasting
24
Location-Aided Routing (LAR)

Location information via GPS

Shortcoming (maybe not anymore 2005)

GPS availability is not yet worldwide

Position information come with deviation
25
Location-Aided Routing (LAR)




Each node knows its location in every moment
Using location information for route discovery
Routing is done using the last known location + an assu
mption
Route discovery is initiated when:


S doesn’t know a route to D
Previous route from S to D is broken
26
LAR - Definitions

Expected Zone




S knows the location L of D in t0
Current time t1
The location of D in t1 is the expected zone
Request Zone


Flood with a modification
Node S defines a request zone for the route request
27
LAR
Expected Zone (Xd+R, Yd+R)
Request Zone
Destination (Xd,Yd)
R
source(Xs,Ys)
28
Distance Routing effect Algorithm for
mobility (DREAM)


Position-based
Each node


maintains a position database
regularly floods packets to update the position


Temporal resolution
Spatial resolution
29
Restricted Directional Flooding

Distance Routing effect Algorithm for mobility
(DREAM)
 Sender will forward the packet to all one-hop neigh
bors that lie in the direction of destination
 Expected region is a circle around the position of d
estination as it is known to source
 The radius r of the expected region is set to (t1-t0)*
Vmax, where t1 is the current time, t0 is the timest
amp of the position information source has about d
estination, and Vmax is the maximum speed that a
node may travel in the ad hoc network
 The direction toward destination is defined by the l
ine between source and destination and the angle 
30
From ECE 5970 Class
DREAM
31
Power-Aware Routing (PAR)
N1
+
N2
–
SRC
+
–
DES
T
+
+
–
–
N3
+
–
N4
+
–
32
OLSR - Overview

OLSR



Inherits Stability of Link-state protocol
Selective Flooding
only MPR retransmit control messages:


Minimize flooding
Suitable for large and dense networks
33
OLSR – Multipoint relays (MPRs)



MPRs = Set of selected neighbor nodes
Minimize the flooding of broadcast packets
Each node selects its MPRs among its on hop neighbors



MPR Selector = a node which has selected node as MPR
The information required to calculate the multipoint relays :



The set covers all the nodes that are two hops away
The set of one-hop neighbors and the two-hop neighbors
Set of MPRs is able to transmit to all two-hop neighbors
Link between node and it’s MPR is bidirectional.
34
OLSR – Multipoint relays (cont.)

To obtain the information about one-hop neighbors :


To obtain the information about two-hop neighbors :


Use HELLO message (received by all one-hop neighbors)
Each node attaches the list of its own neighbors
Once a node has its one and two-hop neighbor sets :

Can select a MPRs which covers all its two-hop neighbors
35
OLSR – Multipoint relays (cont.)
MPR(Retransmission
node)
4 retransmission to diffuse a
message up to 2 hops
Figure 1. Diffusion of a broadcast message using multipoint relays
36
OLSR – Multipoint relays (cont.)
Node
B
1 Hop Neighbors
2 Hop Neighbors
A,C,F,G
D,E
MPR(s)
C
E
D
F
A
C
G
B
Figure 2. Network example for MPR selection
37
OLSR – Multipoint relays (cont.)
E
F
H
MS(A) = {B,H,I}
D
C
B
MS(C) = {B,D,E}
A
I
MPR(B) = {A,C}
G
Figure 3. MPR과 MPR Selector Set
38
Protocol functioning – Neighbor sensing

Each node periodically broadcasts its HELLO messages:



Containing the information about its neighbors and their link
status
Hello messages are received by all one-hop neighbors
HELLO message contains:


List of addresses of the neighbors to which there exists a valid
bi-directional link
List of addresses of the neighbors which are heard by node( a
HELLO has been received )

But link is not yet validated as bi-directional
39
Protocol functioning – Neighbor sensing (cont.)
Message type
Vtime
Message size
Originator Address
Time To Live
Hop count
Message Sequence Number
Reserved
Link code
Htime
Reserved
Willingness
Link message size
Neighbor Interface Address
Neighbor interface Address
…
Reserved
Link code
Htime
Reserved
Willingness
Link message size
Neighbor interface address
Neighbor interface address
…
Link type
Neighbor type
Table 1. Hello Message Format in OLSR
40
Protocol functioning – Neighbor sensing (cont.)

HELLO messages :





Serves Link sensing
Permit each node to learn the knowledge of its neighbors up
to two-hops (neighbor detection)
On the basis of this information, each node performs the
selection of its multipoint relays (MPR selection signaling)
Indicate selected multipoint relays
On the reception of HELLO message:

Each node constructs its MPR Selector table
41
Protocol functioning – Neighbor sensing ( cont.)

In the neighbor table:


Each node records the information about its on hop neighbor
and a list of two hop neighbors
Entry in the neighbor table has an holding time


Upon expiry of holding time, removed
Contains a sequence number value which specifies the most
recent MPR set

Every time updates its MPR set, this sequence number is
incremented
42
Protocol functioning – Neighbor sensing

Example of neighbor table
One-hop neighbors
Neighbor’s id
State of Link
Two-hop neighbors
Neighbor’s id
Access though
B
Bidirectional
E
C
G
Unidirectional
D
C
C
MPR
…
…
…
…
Table 2. Example of neighbor table
43
Protocol functioning – Multipoint relay selection



Each node selects own set of multipoint relays
Multipoint relays are declared in the transmitted
HELLO messages
Multipoint relay set is re-calculated when:




A change in the neighborhood( neighbor is failed or add new
neighbor )
A change in the two-hop neighbor set
Each node also construct its MPR Selector table with
information obtained from the HELLO message
A node updates its MPR Selector set with information
in the received HELLO messages
44
Protocol functioning – MPR information declaration

TC – Topology control message:




In order to build intra-forwarding database
Only MPR nodes forward periodically to declare its MPR
Selector set
Message might not be sent if there are no updates
Contains:



MPR Selector
Sequence number
Each node maintains a Topology Table based on TC
messages

Routing Tables are calculated based on Topology tables
45
Protocol functioning – MPR information declaration (cont.)
Destination address
MPR Selector in
the received TC
message
Destination’s MPR
MPR Selector
sequence
number
Holding time
Last-hop node to the
destination.
Originator of TC
message
Table 3. Topology table
46
Protocol functioning – MPR information declaration (cont.)
E
F
Send TC message
D
C
B
MS(C) = {B,D,E}
MPR(B) = {A,C}
{B,D,E} build the
topology table
G
Figure 4. TC message and Topology table
47
Protocol functioning – MPR information declaration (cont.)

Upon receipt of TC message:

If there exist some entry to the same destination with higher
Sequence Number, the TC message is ignored

If there exist some entry to the same destination with lower
Sequence Number, the topology entry is removed and the
new one is recorded

If the entry is the same as in TC message, the holding time of
this entry is refreshed

If there are no corresponding entry – the new entry is
recorded
48
Protocol functioning – MPR information declaration (cont.)
Dest’
address
Dest’ MPR
MPR
Selector
sequence
X
M
1
Y
M
1
Z
M
1
..
..
..
S
P
M
S’ Topology table
X
TC’
originator
MPR selector
MPR selector
sequence
M
X
2
M
Y
2
M
Z
2
M
R
2
TC message ( M send to S)
Z
Y
B
A
D
R
Send TC message
Figure 5. Topology table update
49
Protocol functioning – Routing table calculation




Each node maintains a routing table to all known
destinations in the network
After each node TC message receives, store connected pairs of
form ( last-hop, node)
Routing table is based on the information contained in the
neighbor table and the topology table
Routing table:




Destination address
Next Hop address
Distance
Routing Table is recalculated after every change in neighbor
table or in topology table
50
Protocol functioning – Routing table calculation (cont.)
Source
Destination
Figure 5. Building a route from topology table
51
conclusion


OLSR protocol is proactive or table driven in nature
Advantages



Route immediately available
Minimize flooding by using MPR
OLSR protocol is suitable for large and dense networks
52
Current routing protocols

Many do not consider energy conservation




lead to partitions
shorten network life
fairness to intermediate nodes not incorporated
fail to work well in both sparse and dense networks
53
Interesting Research Topics


Energy Awareness Routing
Multipath Routing


more paths used to send information, more reliable the trans
mission
Clustering (Hierarchical Routing)

dynamic management of subnetworks
54
More Research Topics

Topology Control


Internetworking


managing wired and wireless networks
Heterogeneous Networks


adjustment of transmission power to simplify routing
Different devices on the network have different capabilities
Content Aware Networks

Location of services within the network (Printers)
55
References




Ad Hoc Mobile Wireless Networks – Protocols and Syste
m, C-K Toh, Prentice Hall, 2002, ISBN: 0-13-007817-4
“Introduction to Ad Hoc Networking”, Prof. Yu-Chee Ts
eng
“Optimized Link State Routing Protocol
for Ad Hoc Networks, Jacquet”, p and park gi won
“Ad Hoc Network”, Wireless LANs, June – September
2009, Asso. Prof. Anan Phonphoem, Ph.D.
56