Ad-Hoc wireless networks

Routing protocols for Ad Hoc wireless networks
The properties of the ad-hoc network routing protocol
Simple
Less storage space
Loop free
Short control message (Low overhead)
Less power consumption
Multiple disjoint routes
Fast rerouting mechanism

Routing protocols for Ad Hoc wireless networks
Based on the routing information update mechanism, protocols can be classified into three:
Proactive (table-driven) routing protocols
Reactive (on-demand) routing protocol
Hybrid routing protocols

Routing protocols for Ad Hoc wireless networks

The Basics - Flooding
Simplest of all routing protocols
Send all info to everybody
If data not for you, send to all neighbors
Robust
destination is almost guaranteed to receive data
Resource Intensive
unnecessary traffic
load increases, network performance drops quickly

The Basic- Link State routing
Like the shortest-path computation method
Each node maintains a view of the network topology with a cost for each link
Periodically broadcast link costs to its outgoing links to all other nodes such as flooding

The Basic- Link State routing
E
B
D
G
H
F
A
C
link costs

The Basic- Distance Vector Routing
Known also as Distributed Bellman-Ford or RIP (Routing Information Protocol)
Every node maintains a routing table
all available destinations
the next node to reach to destination
the number of hops to reach the destination
Periodically send table to all neighbors to maintain topology

The Basic- Distance Vector (Tables)
C
1
2
B
A

(A, 1)
(B, 0)
(C, 1)
(A, 1)
(B, 0)
(C, 1)
Distance Vector (Update)
C
1
1
B
A
B broadcasts the new routing information to his neighbors
Routing table
is updated

(D, 0)
(A, 2)
(B, 1)
(C, 0)
(D, 1)
(A, 1)
(B, 0)
(C, 1)
(D, 2)
Distance Vector (New Node)
C
1
1
B
A
D
1
broadcasts to update
tables of C, B, A with new entry for D

Distance Vector (Broken Link)
C
1
1
B
A
D
1

(D, 2)
(D, 2)
Distance Vector (Loops)
C
1
1
B
A
D
1

(D,2)
(D,4)
(D,3)
(D,5)
(D,2)
(D,4)
Distance Vector (Count to Infinity)
C
1
1
B
A
D
1

Distance Vector
DV not suited for ad-hoc networks!
Loops
Count to Infinity
New Solution -> DSDV Protocol

DSDV Protocol
DSDV is Proactive (Table Driven)
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

DSDV Protocol
Keep the simplicity of Distance Vector
Guarantee Loop Freeness
New Table Entry for Destination Sequence Number
Allow fast reaction to topology changes
Make immediate route advertisement on significant changes in routing table

DSDV (Table Entries)
Sequence number originated from destination. Ensures
loop freeness.
Install Time when entry was made (used to delete stale entries from table)
Stable Data Pointer to a table holding information on how stable a route is. Used to damp fluctuations in network.

DSDV (Route Advertisements)
Advertise to each neighbor own routing information
Destination Address
Metric = Number of Hops to Destination
Destination Sequence Number
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 = ∞

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.

DSDV (Tables)
C
B
A
1
2

(A, 1, A-500)
(B, 0, B-102)
(C, 1, C-588)
(A, 1, A-500)
(B, 0, B-102)
(C, 1, C-588)
DSDV (Route Advertisement)
C
B
A
B increases Seq.Nr from 100 -> 102
B broadcasts routing information
to Neighbors A, C including destination sequence numbers
1
1

DSDV (Respond to Topology Changes)
Immediate advertisements
Information on new Routes, broken Links, metric change is immediately propagated to neighbors.
Full/Incremental Update:
Full Update: Send all routing information from own table.
Incremental Update: Send only entries that has changed. (Make it fit into one single packet)

(D, 0, D-000)
DSDV (New Node)
C
B
A
D
1. D broadcast for first time
Send Sequence number D-000
2. Insert entry for D with sequence number D-000
Then immediately broadcast own table

(A, 2, A-550)
(B, 1, B-102)
(C, 0, C-592)
(D, 1, D-000)
(A, 2, A-550)
(B, 1, B-102)
(C, 0, C-592)
(D, 1, D-000)
DSDV (New Node cont.)
C
B
A
D
………
………
3. C increases its sequence number to C-592 then broadcasts its new table.
4. B gets this new information and updates its table…….

(D, 2, D-100)
(D, 2, D-100)
DSDV (no loops, no count to infinity)
C
B
A
D
1. Node C detects broken Link:
-> Increase Seq. Nr. by 1
(only case where not the destination sets the sequence number -> odd number)
2. B does its broadcast
-> no affect on C (C knows that B has stale information because C has higher seq. number for destination D)
-> no loop -> no count to infinity

(D, ∞, D-101)
(D, ∞, D-101)
DSDV (Immediate Advertisement)
C
B
A
D
1. Node C detects broken Link:
-> Increase Seq. Nr. by 1
(only case where not the destination sets the sequence number -> odd number)
3. Immediate propagation
B to A:
(update information has higher Seq. Nr. -> replace table entry)
2. Immediate propagation
C to B:
(update information has higher Seq. Nr. -> replace table entry)

Link State Routing
Each node periodically floods status of its links
Each node re-broadcasts link state
information received from its neighbour
Each node keeps track of link state
information received from other nodes
Each node uses above information to
determine next hope to each destination
24 retransmissions to diffuse a message up to 3 hops

Optimized Link state routing (OLSR)

Optimized Link state routing (OLSR)

Qamar A Tarar
OLSR Protocol
Description of OLSR
* MPR (Multipoint relays)
* MPR selector
* Symmetric 1-hop neighbours
* Symmetric strict 2-hop neighbours

Selecting Multipoint relays