Transcript Optimized Link State Protocol

Optimized Link State
Protocol
Version 2
Assaf Israel, Eli Nazarov, Asi Bross
OLSRv2 - Overview
Applicability
mobile ad-hoc networks (MANET)
dynamic topology
100%> reliable environment (WiFi, WiMax)
nodes can be gateways to other networks
Characteristics
Table driven
proactive protocol
Build on top of MANET NHDP
Terminology
node
1-hop neighbor set
2-hop neighbor set
bidirectional link
interface
Mobile Ad-hoc Networks
Neighborhood Discovery Protocol
A solid base for the OLSRv2 protocol.
Objective - maintain 1-hop & 2-hop neighbors link
state tables
Pros
Simplicity - only one type of messages
Generic - does not limit to type of connectivity technology
Cons
Effects bandwidth as messages are routinely transmitted
Mobile Ad-hoc Networks
Neighborhood Discovery Protocol (cont.)
Local Information Base - per node
Active interface - IP tuples set
Removed interface - IP tuples set
Interface
IP
eth0
192.168.2.20
eth1
192.168.4.67
Interface Information Base - per interface
Link Set
Current & Recently lost 1-hop neighbors to this interface
Link Set - eth0
Connection quality
Target Interface
Validation time
Quality
V-Time
192.168.2.34 eth0
13609 ms
10.148.3.20 - eth2
15338 ms
128.3.41.98 - eth1
Lost
-
Mobile Ad-hoc Networks
Neighborhood Discovery Protocol (cont..)
Interface Information Base (Cont.)
2-Hop Set
Each entry consist of 2-hop address & all of the addresses of the
corresponding symmetric 1-hop neighbor
Each tuple records an address of recently lost 1-hop neighbor
2-Hop Set - eth0
2-hop IP
Reachable via
128.3.4.120
[ 192.168.2.34 , 10.148.3.20
]
128.3.4.120
[ 10.148.5.1 ]
133.5.5.90
[ 192.168.2.34 , 10.148.3.20
]
Mobile Ad-hoc Networks
Neighborhood Discovery Protocol (cont.)
Neighbor Information Base
Neighbor Set - Neighbor tuples
List all IP’s of a single 1-hop neighbor
Lost Neighbor Set - Lost Neighbor tuples
Neighbor Set
Local Interface
Target Interface set
eth0
[ 192.168.2.34 , 10.148.3.20
]
eth0
[ 10.148.5.1 ]
eth1
[ 192.168.2.34 , 10.148.3.20
]
Lost Neighbor Set
Local Interface
Target Interface set
eth0
[ 192.168.2.90 ]
“Hello” message
The only type of message in MANET NHDP
Generated by a node independently on each
MANET interface
Identify the source interface but adds information of
all other local interfaces
May be sent
Proactively - at a regular pre-defined interval
Dynamically - interval may be backed off to to congestion or network
stability
Event driven - e.g new/lost/changed status link
“Hello” message - Objectives
Advertise the router’s interface addresses to it’s 1hop neighbors.
Advertise the router’s knowledge of each of its 1hop neighbors.
“Hello” message - Content
Must contain all of the Local Interface Set IPs
For each interface, and every pre-defined RefreshInterval Must send all relevant information in the
Interface Link Set & Neighbor Information Base.
Validity Time for which the information is
considered valid
periodically should contain the Interval Time for
which messages are sent from the interface.
“Hello” message - Processing
Updates the receiver’s Interface Information Base
If an entry from the message source exists then the valid time is checked
and updated accordingly
If an entry does not exist from the message source, a new one will be
created
If a message contains information that a symmetrical link has been
lost/created between the source and a third node the 2-hop neighbor, the
2-hop Set will be updated accordingly
Updates to the Neighbor Information Base may
occur
Will cause generation of yet another Hello message
Hello message are not forwarded
MANET Neighborhood Discovery
Protocol
Optional extensions
Link quality
Jitter
OSLRv2 - Multi Point Relays
Multipoint Relays (MPR)- Set of 1-hop neighbors
which broadcast node’s packets.
MPR must have bi-directional like with the node avoid uni-directional link problems.
The union of all neighbors of MPRs give the group
of 2-hop neighbors of the node.
Multi Point Relays (Cont.)
•
OLSRv2 uses MPR’s to calculate routes to all
known nodes.
•
Route is a sequence of hops through MPRs.
•
Last MPR is the target node or the target is a 1-hop
neighbor of the last MPR.
•
MPR Selector is a neighbor that selected this node
as a MPR.
Signaling
Extends NHDP “Hello” messages to include the
selected MPRs set of the source node.
For each 1-hop neighbor with symmetric link that is selected as MPR for
this router.
TC messages
Includes a Set of all 1-hop neighbors that selected the sending node as an
MPR.
Advertised Neighbor Set.
Attached Network Set.
Message Processing &
Forwarding
TC messages may be processed and/or forwarded
Hello messages are available to OLSRv2 after
NHDP process - Never forwarded.
OSLRv2 - Databases
All MANET NHDP Tables - with extensions
e.g flags to indicate MPR and MPR selector in Neighbor set.
Topology Information Base
Processing & Forwarding Information Base
Topology Information Base
Advertised Neighbor Set
Includes addresses of neighbors that selected this node as MPR.
Symmetric 1-hop neighbors that are advertised through TC massages.
Derived from Neighbor Set.
Advertised Remote Router Set
Remote addresses of routers that transmits TC massages.
Contains all of their addresses.
Advertised Remote Router Set
Source IP
IP List
Sequence No’
Time
192.168.2.34
[ 192.168.2.34 ,
10.148.3.20 ]
1234
14228 ms
Topology Information Base (Cont.)
Topology Set
Topology information about the network.
Topology Set Table
Destination IP
Last hop
Sequence No’
Time
128.3.4.120
192.168.2.34
1234
14228 ms
Routing Set
Records a path to each destination.
Routing Set Table
Destination IP
Next hop
Hops No’
Local Int’
128.3.4.120
192.168.1.5
10
eth0
Topology Information Base (Cont.)
Attached Network Set
Records Information about networks attached to other routers or can be
reached via those router.
Attached network Set
Net IP
Router IP
Hops No’
Sequence No’
Time
192.168.1.
5
10
1234
14228 ms
255.255.255.19 192.168.2.
2
34
3
1002
15542 ms
Net Mask
192.168.1.0 255.255.255.0
192.168.2.0
Processing & Forwarding Information
Base
Used to ensure that each massage is processed
and forwarded once, at most, per OLSRv2 interface
Before processing/forwarding a massage, we must
first check that it wasn't processed/forwarded yet.
This is done using the information stored in
Processing & Forwarding Information Base.
Processing & Forwarding Information
Base
Received Set - per interface
Signatures of messages received on this interface.
Processed Set
Signatures of messages processed by the router.
Forwarded Set
Signatures of messages forwarded by the router.
Relay Set - per interface
Symmetric 1-hop neighbors which messages should be forwarded when
received on that interface.
“Hello” message process by OLSRv2
Updates its Neighbor Information Base if it
was chosen as a MPR for the originator
router (MPR Selector)
In case of topology change the set of MPRs
is recalculated.
TC messages processing
When TC message received:
Topology Set is updated.
Advertised Remote Router Set is updated.
Attached Network Set is updated.
The Dijkstra algorithm can be used to construct the
Routing Set
Packet routing
When a packet needs to get from A to B it is sent
to the next MPR as described in the Routing Set.
Each MPR will forward the packet to the next MPR
in the route.
MPR
MPR
Source
Target
MPR
MPR
MPR