Transcript adhoc_routing-1 - LINK@KoreaTech

Adhoc Networks Routing Tutorial
- Part I Internet Computing Laboratory @ KUT
(http://icl.kut.ac.kr)
Youn-Hee Han
It is licensed under a Creative Commons Attribution 2.5 License
Adhoc Routing Protocol 101
2
Computer Network
Layer 2 Routing (1)
The source determines that the destination interface is
in the same IP subnet

This necessarily implies that the source and destination are
directly connected by a Layer 2 network
ARP allows the source to determine the Layer 2 (MAC)
address of the destination
The source encapsulates the IP datagram in a Layer 2
frame, addresses the frame appropriately, and transmits
the frame
Layer 2 “interworking units” (e.g., Ethernet bridges,
802.11 APs) may need to perform some forwarding or
routing functions
3
Computer Network
Layer 2 Routing (2)
10.0.1.4
255.255.255.0
10.0.1.X
ARP Request
for 10.0.1.9
Dest IP = 10.0.1.9
(Dest Net = 10.0.1.X)
ARP
Reply
IP
MAC
10.0.1.9
Dest
…
AP
Src
…
Local IP:
Subnet Mask:
Local Network:
Local IP: 10.0.1.9
Dest
4
Computer Network
Layer 2 Routing (3)
Local IP:
Subnet Mask:
Local Network:
10.0.1.4
255.255.255.0
10.0.1.X
S
Dest IP = 10.0.1.9
(Dest Net = 10.0.1.X)
IP Dest = 10.0.1.9
DA = D
BSSID = AP
AP
IP Dest = 10.0.1.9
Dest = D
D
5
Computer Network
Need for Layer 3 Routing
Of course, nodes may not be connected via Layer 2


Nodes that are in a different IP subnet, i.e., the destination IP
network is different than the local IP network
Nodes that are out of radio range in an ad hoc wireless network
Layer 3, or IP, routing is needed in this case
10.0.3.6
10.0.1.1
10.0.1.3
6
10.0.3.3
10.4.6.9
10.4.6.1
Computer Network
Routing
Routing consists of two fundamental steps


Forwarding packets to the next hop (from an input interface to
an output interface in a traditional wired network)
Determining how to forward packets (building a routing table or
specifying a route)
Forwarding packets is easy, but knowing where to
forward packets (especially efficiently) is hard





7
Reach the destination
Minimize the number of hops (path length)
Minimize delay
Minimize packet loss
Minimize cost
Computer Network
Routing Decision Point
Source routing


Sender determines a route and specifies it in the packet header
Supported in IP, although not the typical routing scheme
Hop-by-hop (datagram) routing


A routing decision is made at each forwarding point (at each
router)
Standard routing scheme for IP
Virtual circuit routing


8
Determine and configure a path prior to sending first packet
Used in ATM (and analogous to voice telephone system)
Computer Network
Routing Table
A routing table contains information to determine how
to forward packets



Source routing: Routing table is used to determine route to the
destination to be specified in the packet
Hop-by-hop routing: Routing table is used to determine the
next hop for a given destination
Virtual circuit routing: Routing table used to determine path to
configure through the network
A distributed algorithm is required to build the routing
table


9
Distance vector algorithms
Link state algorithms
Computer Network
Distance Vector Algorithms (1)
“Distance” of each link in the network is a metric that is
to be minimized


Each link may have “distance” 1 to minimize hop count
Algorithm attempts to minimize distance
The routing table at each node…


Specifies the next hop for each destination
Specifies the distance to that destination
Neighbors can exchange routing table information to
find a route (or a better route) to a destination
10
Computer Network
Distance Vector Algorithms (2)
Dest
Next Metric
A
B
2
B
B
1
D
D
1
A
Dest
11
C
D
Next Metric
B
B
1
C
B
2
D
B
3
Dest
B
Dest
Next Metric
A
A
1
C
C
1
D
C
2
Next Metric
A
C
3
B
C
2
C
C
1
Computer Network
Distance Vector Algorithms (3)
Node A will learn of Node
C’s shorter path to Node
D and update its routing
table
Dest
Next
Metric
A
A
1
B
B
1
D
D
1
A
12
Dest
Next
Metric
B
B
1
C
C
1
D
C
2
C
D
B
Computer Network
Link-State Algorithms (1)
Each node shares its link information so that all nodes
can build a map of the full network topology


Each node periodically floods status of its links
Each node re-broadcasts link state information received from its
neighbour
Link information is updated when a link changes state
(goes up or down)

Link state determined by sending small “hello” packets to
neighbors
Given full topology information, a node can determine
the next best hop or a route from the source
13
Computer Network
Link-State Algorithms (2)
Link
A-B
B-C
A
Link
A-B
Link
A-B
B-C
B-C
C-D
C-D
C
D
C-D
B
Link
A-B
B-C
Assuming the topology is
stable for a sufficiently long
period, all nodes will have the
same topology information
C-D
14
Computer Network
Link-State Algorithms (3)
Link
A-B
A-C
Link
A-C
A-B
A-C
A
B-C
C-D
C
A-B
D
B-C
A-C
B-C
C-D
A-C
Link
A-B
A-C
B-C
C-D
15
Link
A-C
C-D
B
Nodes A and C propagate the
existence of link A-C to their
neighbors and, eventually, to
the entire network
Computer Network
MANETs
A mobile ad hoc network (MANET) is characterized by…



Multi-hop routing so that nodes not directly connected at Layer
2 can communicate through Layer 3 routing
Wireless links
Mobile nodes
Logical
Topology
S
S
D
16
D
Computer Network
MANET vs. Traditional Routing (1)
Every node is potentially a router in a MANET, while
most nodes in traditional wired networks do not route
packets

Nodes transmit and receive their own packets and, also,
forward packets for other nodes
Topologies are dynamic in MANETs due to mobile
nodes, but are relatively static in traditional networks
Routing in MANETs must consider both Layer 3 and
Layer 2 information, while traditional protocols rely on
Layer 3 information only

17
Link layer information can indicate connectivity and interference
Computer Network
MANET vs. Traditional Routing (2)
MANET topologies tend to have many more redundant
links than traditional networks
A MANET “router” typically has a single interface, while
a traditional router has an interface for each network to
which it connects

Routed packet sent forward when transmitted, but also sent to
previous transmitter
Channel properties, including capacity and error rates,
are relatively static in traditional networks, but may vary
in MANETs
18
Computer Network
MANET vs. Traditional Routing (3)
Interference is an issue in MANETs, but not in traditional
networks

For example, a forwarded packet from B-to-C competes with
new packets sent from A-to-B
Channels can be asymmetric with some Layer 2
technologies

Note that the IEEE 802.11 MAC assumes symmetric channels
Power efficiency is an issue in MANETs, while it is
normally not an issue in traditional networks
MANETs may have gateways to fixed network, but are
typically “stub networks,” while traditional networks can
be stub networks or transit networks
19
Computer Network
MANET vs. Traditional Routing (4)
There is limited physical security in a MANET compared
to a traditional network

Increased possibility of eavesdropping, spoofing, and denial-ofsecurity attacks
Traditional routing protocols for wired networks do not
work well in most MANETs


20
MANETs are too dynamic
Wireless links present problems of interference, limited capacity,
etc.
Computer Network
MANET Routing
Nodes must determine how to forward packets


Source routing: Routing decision is made at the sender
Hop-by-hop routing: Routing decision is made at each
intermediate node
Difficult to achieve good performance




21
Routes change over time due to node mobility
Best to avoid long delays when first sending packets
Best to reduce overhead of route discovery and maintenance
Want to involve as many nodes as possible – to find better
paths and reduce likelihood of partitions
Computer Network
MANET Routing Approaches
Decision time


Proactive or table-driven – maintain routing tables
Reactive or on-demand – determine routing on an as-needed
basis
Network structure

Hierarchical – impose a hierarchy on a collection of nodes and
reflect this hierarchy in the routing algorithm
 May use a proactive protocol for routing within a cluster or zone
 May use a reactive protocol for routing between distinguished
“cluster heads”

22
Non-hierarchical – make decisions among all nodes
Computer Network
Types of MANET Routing
Unicast-Routing Protocol for MANET
Table-Driven/
Proactive
DistanceVector
LinkState
DSDV
OLSR
TBRPF
FSR
STAR
23
Hybrid
On-Demanddriven/Reactive
Clusterbased/
Hierarchical
ZRP
DSR
AODV
TORA
LANMAR
CEDAR
MANET: Mobile Ad hoc Network
(IETF working group)
Computer Network
Common Features
MANET routing protocols must…



Discover a path from source to destination
Maintain that path (e.g., if an intermediate node moves and
breaks the path)
Define mechanisms to exchange routing information
Proactive protocols



Find paths, in advance, for all source-pair destinations
Periodically exchange routing information to maintain paths
(-) Larger signalling traffic and power consumption.
Reactive protocols



24
Discover a path when a packet needs to be transmitted and no
known path exists
Attempt to alter the path when a routing failure occurs
(-) A long delay for application when no route to the
destination available
Computer Network
Basic Classifications
Proactive protocols


Maintaining route map of all nodes
Example protocols: DSDV[1], OLSR[2], FSR[3]
Reactive protocols


Adapting to the traffic pattern on a demand or need basis
Example protocols: DSR[4], AODV[5], TORA[6]
Hybrid protocols


25
Proactive for nearby nodes while reactive for distant nodes
Example protocols: ZRP[7]
Computer Network
Basic Classifications
[1] C. E. Perkins, P. Bhagwat, “Highly Dynamic Destination-Sequenced Distance
Vector (DSDV) for Mobile Computers”, Proc. of the SIGCOMM 1994 Conference on
Communications Architectures, Protocols and Applications, Aug 1994, pp 234-244.
[2] T. Clausen, P. Jacquet “Optimized Link State Routing Protocol”, RFC 3626
[3] M. Gerla, G. Pei, X. Hong, Ts. Chen “Fisheye State Routing Protocol (FSR) for Ad
Hoc Networks”, Internet Draft, draft-ietf-manet-fsr-00.txt, work in progress, June
2001.
[4] David B. Johnson, David A. Maltz, Yih-Chun Hu, “The Dynamic Source Routing
Protocol for Mobile Ad Hoc Networks (DSR)”, <draft-ietf-manet-dsr-10.txt>
[5] C. Perkins, E. Belding-Royer, S. Das, “Ad hoc On-Demand Distance Vector (AODV)
Routing”, RFC 3561
[6] V. Park and S. Corson, “Temporally-Ordered Routing Algorithm (TORA) Version 1
Functional Specification,” IETF I-D draft-ietf-manet-tora-spec-04.txt
[7] Nicklas Beijar, “Zone Routing Protocol (ZRP)”
26
Computer Network
Quantitative Metrics
End-to-end data throughput and delay
Route Acquisition Time (on-demand routing)
Percentage Out-of-Order Delivery
Efficiency

Control Overhead
Power consumption and network lifetime
27
Computer Network
Proactive Routing Protocols
28
Computer Network
Proactive Approach - Principle
Routing Table

29
Each terminal has its own routing table
Destination
terminal
Next
node
A
A
B
A
C
E
D
D
…
…
Computer Network
Proactive Approach - Principle
Control Packet


Used to make and update the Routing Table
Broadcasted in a limited area
Format of Typical Control Packet
ID of terminal
which create the
packet
30
Timestamp for the
created packet
ID of hop source
terminal
Hop
count
Computer Network
Proactive Approach
Example of Control Packet Exchange
A
1
A 1 B 2
A 1
A
B
A
31
t =1
A
t =2
A 1 C 3
D
C
A
B
B
B
A C
C C
t =3
t =4
Computer Network
Proactive Approach
Routing Table in D
G
B
E
C
To F
Dest
Next
A
A
B
B
C
E
D
-
E
E
F
I
G
E
H
I
I
I
D
A
32
I
F
H
Computer Network
Proactive Approach
Routing Table in I
G
B
E
C
To F
Dest
Next
A
D
B
D
C
C
D
D
E
E
F
H
G
E
H
H
I
-
D
A
33
I
F
H
Computer Network
Proactive Approach
Routing Table in H
G
B
E
C
To F
Dest
Next
A
I
B
I
C
C
D
I
E
I
F
F
G
C
H
-
I
I
D
A
34
I
F
H
Computer Network
Destination-Sequenced Distance Vector
Design goals:



Keep it simple!
Routes are chosen by a metric (hop count, least delay, best signal
strength, etc..)
Avoid the looping problem
 Tag each routing table entry with a Destination sequence number

Allow fast reaction to topology changes
 Make immediate route advertisement on significant changes in routing table

Both periodic and triggered routing updates to maintain table
DSDV is Proactive




35
Each node maintains routing information for all known destinations
Routing information must be updated periodically
Traffic overhead even if there is no change in network topology
Maintains routes which are never used
Computer Network
DSDV - Table entries
Destination
Next
Metric
Seq. Nr
Install Time
A
B
C
D
A
B
B
B
0
1
3
4
A-550
B-102
C-588
D-312
001000
001200
001200
001200
Sequence number originated from destination.


Ensures loop freedom and route freshness
Format = Dest_NNN
Install Time when entry was made

36
used to delete stale entries from table
Computer Network
DSDV -
Transmitting Route Information
Routing information is transmitted by broadcast
Updates are transmitted periodically or immediately when any
significant topology change is available
Rules to set sequence number information
•
•
On each advertisement increase own destination sequence number
(use only even numbers)
If a node is no more reachable (timeout) increase sequence number of
this node by 1 (odd sequence number) and set metric = .
Full dump: all information from the transmitting node
Incremental dump: all information that has changed since the last
full dump
37
Computer Network
DSDV -
Route Selection
Update information is compared to own routing table


1. Select route with higher destination sequence number (This ensure
to use always newest information from destination)
2. Select the route with better metric when sequence numbers are
equal.
Tables
A
38
B
C
Dest.
Next
Metric
Seq
Dest.
Next
Metric
Seq
Dest.
Next
Metric
Seq.
A
A
0
A-550
A
A
1
A-550
A
B
1
A-550
B
B
1
B-100
B
B
0
B-100
B
B
2
B-100
C
B
2
C-586
C
C
1
C-588
C
C
0
C-588
Computer Network
DSDV -
Route Advertisement
B increases Seq.Nr from 100 to 102
B broadcasts routing information to Neighbors A
and C including the destination sequence numbers
(A, 1, A-550)
(B, 0, B-102)
(C, 1, C-588)
A
39
(A, 1, A-550)
(B, 0, B-102)
(C, 1, C-588)
B
C
Dest.
Next
Metric
Seq
Dest.
Next
Metric
Seq
Dest.
Next
Metric
Seq.
A
A
0
A-550
A
A
1
A-550
A
B
2
A-550
B
B
1
B-100
B
B
0
B-102
B
B
1
B-100
C
B
2
C-588
C
C
1
C-588
C
C
0
C-588
Dest.
Next
Metric
Seq
Dest.
Next
Metric
Seq
Dest.
Next
Metric
Seq.
A
A
0
A-550
A
A
1
A-550
A
B
2
A-550
B
B
1
B-102
B
B
0
B-102
B
B
1
B-102
C
B
2
C-588
C
C
1
C-588
C
C
0
C-588
Computer Network
DSDV -
New Node
1. D broadcast for first time
Send Sequence number D-000
(D, 0, D-000)
A
B
C
D
Dest.
Next
Metric
Seq.
Dest.
Next
Metric
Seq.
Dest.
Next
Metric
Seq.
A
A
0
A-550
A
A
1
A-550
A
B
2
A-550
B
B
1
B-104
B
B
0
B-104
B
B
1
B-104
C
B
2
C-590
C
C
1
C-590
C
C
0
C-590
2. Insert entry for D with
sequence number D-000
A
40
B
C
D
Dest.
Next
Metric
Seq.
Dest.
Next
Metric
Seq.
Dest.
Next
Metric
Seq.
A
A
0
A-550
A
A
1
A-550
A
B
2
A-550
B
B
1
B-104
B
B
0
B-104
B
B
1
B-104
C
B
2
C-590
C
C
1
C-590
C
C
0
C-590
D
D
1
D-000
Computer Network
DSDV -
New Node
3. C increases its sequence number to
C-592 then
Immediately broadcasts!
its new table.
(A, 2, A-550)
(B, 1, B-102)
(C, 0, C-592)
(D, 1, D-000)
A
41
B
(A, 2, A-550)
(B, 1, B-102)
(C, 0, C-592)
(D, 1, D-000)
C
D
Dest.
Next
Metric
Seq.
Dest.
Next
Metric
Seq.
Dest.
Next
Metric
Seq.
A
A
0
A-550
A
A
1
A-550
A
B
2
A-550
B
B
1
B-104
B
B
0
B-102
B
B
1
B-102
C
B
2
C-590
C
C
1
C-590
C
C
0
C-592
D
D
1
D-000
Computer Network
DSDV 4. B gets this new information
and updates its table…….
A
D gets routing table from C
and create its own table.
B
C
D
Seq.
3
2
1
0
A-550
B-102
C-592
D-000
Dest. Next Metric
Dest.
Next
Metric
Seq.
Dest.
Next
Metric
Seq.
Dest.
Next
Metric
Seq.
A
A
0
A-550
A
A
1
A-550
A
B
2
A-550
B
B
1
B-104
B
B
0
B-102
B
B
1
B-102
C
B
2
C-590
C
C
1
C-592
C
C
0
C-592
D
C
2
D-000
D
D
1
D-000
42
New Node
A
B
C
D
C
C
C
D
Computer Network
DSDV -
2. B does its broadcast
-> no effect on C (C knows that B
1. Node C detects broken Link:
 Increase Seq. Nr. by 1
has stale information because C has
higher seq. number for destination D)
(no reachable -> odd number)
->
no loop!
(D, 2, D-100)
A
(D, 2, D-100)
B
Dest.
Next
Metric
…
…
…
D
B
3
Dest.
Next
…
D
Seq.
Next
Metric
…
…
…
D
C
2
Metric
Dest.c
Next
…
…
…
B
3
D
D-100
D
C
Dest.c
(D, 2)
43
no loops, no count to infinity
Dest.
Next
Metric
…
…
…
D
D

Metric
Dest.
Next
Metric
…
…
…
…
…
C
2
D
D

Dest.
Next
Metric
…
…
…
D
B
3
(D, 2)
Seq.
D-100
Seq.
D-101
Loop made without
sequence number
Computer Network
DSDV -
Immediate Advertisement
4. Immediate propagation
B to A:
3. Immediate propagation
C to B:
(update information has higher
Seq. Nr.  replace table entry)
(update information has higher
Seq. Nr.  replace table entry)
(D, , D-101)
A
44
(D, , D-101)
B
D
C
Dest.
Next
Metric
Seq.
Dest.c
Next
Metric
Seq.
Dest.
Next
Metric
Seq.
…
…
…
...
…
…
…
...
…
…
…
D
B
4
3
D-100
D
C
3
2
D-100
D
B
D
1
D-100
D
B

D-101
D
C

D-101
D
D

D-101
Computer Network
DSDV -
Limitation
DSDV generally requires a full dump update periodically
 DSDV is not efficient in route updating
DSDV limits the number of nodes that can join the network
Topology changes are slowly propagated

Whenever topology of a network changes, DSDV is unstable until
update packets propagate through the network
Table exchange eats bandwidth


DSDV is effective for creating ad-hoc networks for small populations of
mobile nodes
DSDV is a fairly brute force approach, because connectivity information
needs periodical update througout the whole network
DSDV can no longer find a route reliably when there is high
mobility
45
Computer Network
DSDV –
A
46
B
A
A
0
10
B
B
1
20
C
B
2
30
D
B
3
40
A
B
2
10
B
B
1
20
C
C
0
30
D
D
1
40
C
one more example
A
A
1
10
B
B
0
20
C
C
1
30
D
C
2
40
A
C
3
10
B
C
2
20
C
C
1
30
D
D
0
40
D
Computer Network
DSDV –
A
B
A
A
0
12
B
B
1
20
C
B
2
30
D
B
3
40
A & C perform a
broadcast
47
A
B
2
10
B
B
1
20
C
C
0
32
D
D
1
40
C
one more example
A
A
1
12
B
B
0
20
C
C
1
32
D
C
2
40
A
C
3
10
B
C
2
20
C
C
1
32
D
D
0
40
D
Computer Network
DSDV –
one more example
B detects A’s
movement
Odd numbers
for all destinations
A
A
A
0
13
B
-
∞
21
C
-
∞
31
D
-
∞
41
A move out of
range of all other
nodes
48
B
A
B
2
10
B
B
1
20
C
C
0
32
D
D
1
40
C
Odd number
A
-
∞ 13
B
B
0
20
C
C
1
32
D
C
2
40
A
C
3
10
B
C
2
20
C
C
1
32
D
D
0
40
D
Computer Network
DSDV –
A
B
A
A
0
13
B
-
∞
21
C
-
∞
31
D
-
∞
41
B broadcasts its
modified route
table
49
A
-
∞ 13
B
B
1
22
C
C
0
32
D
D
1
40
C
one more example
A
-
∞ 13
B
B
0
22
C
C
1
32
D
C
2
40
A
C
3
10
B
C
2
20
C
C
1
32
D
D
0
40
D
Computer Network
DSDV –
A
B
A
A
0
12
B
-
∞
21
C
-
∞
31
D
-
∞
41
C broadcasts its
modified route
table
As a result
contents of all
tables are same
exception for A
50
A
-
∞ 13
B
B
1
22
C
C
0
34
D
D
1
40
C
one more example
A
-
∞ 13
B
B
0
22
C
C
1
34
D
C
2
40
A
-
∞ 13
B
C
2
22
C
C
1
34
D
D
0
40
D
Computer Network
DSDV –
B
one more example
A
-
∞ 13
B
B
0
22
C
C
1
34
D
C
2
40
A
A
0
13
A
A
1
13
A
-
∞ 13
B
-
∞
21
B
B
1
22
B
C
2
22
C
-
∞
31
C
C
0
34
C
C
1
34
D
-
∞
41
D
D
1
40
D
D
0
40
A
C
D
A moves in range of C
51
Computer Network
DSDV –
B
one more example
A
C
2
14
B
B
0
22
C
C
1
36
D
C
2
40
A
A
0
14
A
A
1
14
A
C
2
14
B
C
2
22
B
B
1
22
B
C
2
22
C
C
1
36
C
C
0
36
C
C
1
36
D
C
2
40
D
D
1
40
D
D
0
40
A
C
D
C broadcasts routing table
52
Computer Network
OLSR
Optimized Link State Routing (OLSR) protocol

On track to become an IETF Experimental RFC
References


53
C. Adjih, et al., “Optimized Link State Routing Protocol,” IETF
RFC 3626, Oct., 2003.
P. Jacquet, P. Muhlethaler, T. Clausen, A. Laouiti, A. Qayyum,
and L. Viennot, “Optimized Link State Routing Protocol for Ad
Hoc Networks,” Proceedings IEEE INMIC, 2001, pp. 62-68.
Computer Network
OLSR Concepts (1)
Proactive (table-driven) routing protocol

A route is available immediately when needed
Based on the link-state algorithm

Traditionally, all nodes flood neighbor information in a link-state
protocol, but not in OLSR
Selective Flooding


Reduces flooding by using only multipoint relay nodes to send
information in the network
Reduces number of control packets by reducing duplicate
transmissions
Selective Advertisement


54
Nodes advertise information only about links with neighbors in
its multipoint relay selector set
Reduces size of control packets
Computer Network
OLSR Concepts (2)
Does not require reliable transfer, since updates are
sent periodically
Does not need in-order delivery, since sequence
numbers are used to prevent out-of-date information
from being misinterpreted
Uses hop-by-hop routing

55
Routes are based on dynamic table entries maintained at
intermediate nodes
Computer Network
Overview
OLSROLSR
Concepts
(3)
In LSR
 protocol a lot of control messages unnecessary duplicated
In OLSR
 only MPR retransmit control messages:
 Reduce size of control message;
 Minimize flooding
Other advantages (the same as for LSR):






56
As stable as LSR protocol;
Proactive protocol(routes already known);
Does not depend upon any central entity;
Tolerates loss of control messages;
Supports nodes mobility.
Good for dense network
Computer Network
Optimized Link state
OLSRrouting
Concepts(OLSR)
(4)
24 retransmissions nodes to
diffuse a message up to 3
hops
Retransmission node
57
11 retransmission nodes to
diffuse a message up to 3
hops
Retransmission node
Computer Network
Multipoint Relays
Each node N in the network selects a set of neighbor
nodes as multipoint relays, MPR(N), that retransmit
control packets from N

Neighbors not in MPR(N) process control packets from N, but
they do not forward the packets
MPR(N) is selected such that all two-hop neighbors of N
are covered by (one-hop neighbors) of MPR(N)
4
6
1
3
2
58
5
One optimal set for Node 4:
MPR(4) = { 3, 6 }
7
Is there another
optimal MPR(4)?
Computer Network
Multipoint Relay Selector Set
The multipoint relay selector set for Node N, MS(N), is
the set of nodes that choose Node N as their multipoint
relay

Only links N-M, for all N such that MMS(N) will be advertised
in control messages
4
6
1
3
5
MS(3) = {…, 4, …}
MS(6) = {…, 4, …}
7
2
(Assuming bidirectional links)
59
Computer Network
HELLO Messages (1)
Each node uses HELLO messages to determine its MPR
set
All nodes periodically broadcast HELLO messages to
their one-hop neighbors (bidirectional links)
HELLO messages are not forwarded
HELLO: NBR(4) = {1,3,5,6}
4
6
1
3
5
7
2
60
Computer Network
HELLO Messages (2)
Using the neighbor list in received HELLO messages,
nodes can learn topology up to their two-hop
neighborhood and an optimal (or near-optimal) MPR set
A sequence number is associated with this MPR set

Sequence number is incremented each time a new set is
Two-hop neighbors
calculated
One-hop neighbors: {1,3,5,6}
At Node 4:
NBR(1) = {2}
NBR(3) = {2,5}
NBR(5) = {3,6}
NBR(6) = {5,7}
4
Access though
2
1 or 3
7
6
6
1
MPR(4) = {3,6}
NBR
3
5
7
2
61
Computer Network
HELLO Messages (3)
Subsequent HELLO messages also indicate neighbors
that are in the node’s MPR set

So, each MPR node knows its Multipoint Relay Selector Set, MS.
MPR set is recalculated when a change in the
one-hop or two-hop neighborhood is detected
HELLO: NBR(4) = {1,3,5,6}, MPR(4) = {3,6}
4
6
1
3
2
62
5
MS(6) = {…, 4,…}
7
MS(3) = {…, 4,…}
Computer Network
TC Messages
Nodes send topology information in Topology Control
(TC) messages


List of neighbors (link information)
Sequence number (to prevent use of stale information)
A node generates TC messages only for those neighbors
in its MS set


Only MPR nodes generate TC messages
Not all links are advertised
A nodes processes all received TC messages, but only
forwards TC messages if the sender is in its MS set

63
Only MPR nodes propagate TC messages
Computer Network
OLSR Example (1)
4
6
1
3
7
5
2
MPR(1)
MPR(2)
MPR(3)
MPR(4)
MPR(5)
MPR(6)
MPR(7)
64
={4}
={3}
={4}
= { 3, 6 }
= { 3, 4, 6 }
={4}
={6}
MS(1)
MS(2)
MS(3)
MS(4)
MS(5)
MS(6)
MS(7)
=
=
=
=
=
=
=
{}
{}
{ 2, 4, 5 }
{ 1, 3, 5, 6 }
{}
{ 4, 5, 7 }
{}
Computer Network
OLSR Example (2)
4
6
1
3
2
5
7
TC(3) = <2,4,5>
Node 3 generates a TC message advertising nodes in
MS(3) = {2, 4, 5}
Node 4 forwards Node 3’s TC message since
Node 3  MS(4) = {1, 3, 5, 6}
Node 6 forwards TC(3) since Node 4  MS(6)
65
Computer Network
OLSR Example (3)
TC(4) = <1,3,5,6>
4
6
1
3
5
7
2
Node 4 generates a TC message advertising nodes in
MS(4) = {1, 3, 5, 6}
Nodes 3 and 6 forward TC(4) since Node 4  MS(3) and
Node 4  MS(6)
66
Computer Network
OLSR Example (4)
4
6
1
3
5
TC(6) = <4,5,7>
7
2
Node 6 generates a TC message advertising nodes in
MS(6) = {4, 5, 7}
Node 4 forwards TC(6) from Node 6
Node 3 forwards TC(6) from Node 4
After Nodes 3, 4, and 6 have generated TC messages, all
nodes have link-state information to route to any node
67
Computer Network
OLSR Example (5)
TC(4) = <1,3,5,6>
TC(6) = <4,5,7>
4
6
1
3
2
68
5
7
TC(3) = <2,4,5>
Dest
Next
Hops
1
4
2
2
2
1
4
4
1
5
5
1
6
4 or 5
2
7
4 or 5
3
Given TC information, each node
forms a topology table
A routing table is calculated from
the topology table
Note that Link 1-2 is not visible
except to Nodes 2
Computer Network
Structure
of
an
OLSR
Network
OLSR mimics Internet routing
MPRs form routing backbone
and Other nodes act as “hosts”
69
Computer Network
Structure
of
an
OLSR
Network
OLSR mimics Internet routing
MPRs form routing backbone
and Other nodes act as “hosts”
As devices move
70
Computer Network
Structure
of
an
OLSR
Network
OLSR mimics Internet routing
MPRs form routing backbone
and Other nodes act as “hosts”
As devices move
Topological relationships change
Routes change
Backbone shape and
composition changes
71
Computer Network
OLSR Conclusions
Advantages




Route immediately available
Reactivity to topological changes can be adjusted by
setting the time interval for HELLO messages
Minimize flooding by using MPR
Disadvantages




72
Bigger overhead
Need more power (CPU Cycle)
Not all algorithms publically documented
Needs more operational experience to debug
Computer Network