Month 2000

August 2004

doc.: IEEE 802.11-00/1047r0

Routing Protocols for MANET

Avinash Joshi, Vann Hasty, MeshNetworks Inc.

Michael Bahr, Siemens Corporate Technology

Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

Overview
Introduction
Different Routing Protocols
Reactive Routing Protocols
Proactive Routing Protocols
Hybrid Routing Protocols

IETF MANET Group

Other Active work
802.11s and MANET
Conclusion

Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

Introduction
Mobile Ad hoc Network (MANET)
Collection of wireless mobile nodes
Without using a pre-existing infrastructure
Routes between nodes may potentially
contain multiple hops
This presentation
Considers only routing protocols discussed
in IETF MANET working group
Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

Typical Ad hoc Network

G
F
H
A
J

Node

B
D
Submission

Transmission
Range

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

Different Routing Protocols

Proactive Routing Protocols
Reactive Routing Protocols
Hybrid Routing Protocols

Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

Proactive Routing Protocols

Main features:
Maintain routing information on all nodes in the network at all times.
This can be achieved by event driven routing information distribution
and regular distribution of updated routing information.

Advantages:
Lower route setup latency

Disadvantages:
High routing overhead (periodic distribution of routing information)
Stale routing information in highly dynamic topologies.

Protocol examples:
Optimized Link State Routing (OLSR)
Topology Dissemination Based on Reverse Path Forwarding (TBRPF)

Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

Reactive Routing Protocols

Main features:
maintain routing information for the nodes which are needed and
only for the time when they are needed (Also called on-demand
routing protocols.)

Advantages:
Lower routing overhead

Disadvantages:
Larger route set up latency
Route discovery packet flooding

Protocol examples:
Dynamic Source Routing (DSR)
Ad hoc On-demand Distance Vector (AODV)

Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

Hybrid Routing Protocols

Main features:
The routing is proactive for short distances and reactive for long
distances.

Advantages:
Reduces impact of disadvantages of proactive and reactive routing
protocols
No route setup latency for short distance connections
Lower routing overhead due to reactive routing for further away
destinations

Disadvantages:
More complex

Protocol examples:
Zone Routing Protocol (ZRP)
Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

IETF MANET Working Group

Description:
To standardize IP routing protocol functionality suitable
for wireless routing application within both static and
dynamic topoligies
In the past, focused on exploring a broad range of MANET
problems, performance issues, and related candidate
protocols
Promotion of a number of core routing protocol
specifications to EXPERIMENTAL RFC status
http://www.ietf.org/html.charters/manet-charter.html

Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

IETF MANET Working Group

Current Status:
Reached all milestones
3 Experimental RFCs (AODV RFC 3561, OLSR RFC
3626, TBRPF RFC 3684)
DSR submitted as Experimental RFC
Recharter in November
decide on single reactive routing protocol and on single proactive
routing protocol
aspects of security and congestion control in the designed routing
protocol/protocols.

OSPF-MANET in OSPF working group

Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

Example of a Proactive Routing

Protocol
Optimized Link State Routing (OLSR)
Experimental RFC 3626
Authors: Thomas Clausen, Philippe Jacquet,
et al, Project Hipercom, INRIA (France)

Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

OLSR
Optimization of pure link state protocol
Reduced size of control packets (Only links to
multipoint relay selector nodes are advertised)
Minimized flooding (only multipoint relay
(MPR) nodes forward the packets)

Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

MPR Selection

Reference Node
One Hop Neighbors
Two Hop Neighbors
Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

MPR Selection

Selected MPRs

Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

MPR Selection

MPR can reach all

the two hop
neighborhood

Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

MPR Selection

MPR can reach all

the two hop
neighborhood

Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

OLSR Neighbor Sensing

G

Periodic Hello
messages detect the 2hop neighborhood

F
H
A

B
D
Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

Multi Point Relay Selection

MPR nodes are
selected

G
F
H
A
C

J
E

B
D
Submission

Slid

reference node
1-hop neighbors
Multi Point Relays
2-hop neighbors

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

Multi Point Relay Selection

Only Multi Point
Relays (MPRs)
retransmit broadcast
packets from their
MPR selector

G
F
H
A
C

J
E

B
D
Submission

Slid

reference node
1-hop neighbors
Multi Point Relays
2-hop neighbors

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

Topology Info Dissemination

EVERY node MPRbroadcasts its links
between itself and
neighbors that selected
this node as MPR

G
F
H
A
C

J
E

B
D
Submission

Slid

reference node
1-hop neighbors
Multi Point Relays
2-hop neighbors

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

Topology Info Dissemination

EVERY node MPRbroadcasts its links
between itself and
neighbors that selected
this node as MPR

G
F
H
A
C

J
E

B
D
Submission

Slid

reference node
1-hop neighbors
Multi Point Relays
2-hop neighbors

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

Path Computation

iterative shortest path

algorithm using
information from
neighbor table and
topology table

G
F
H
A
C

J
E

B
D
Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

Route Break
compute new MPR set
broadcast TC message

G
F
H
A
C

Link
Break

B
D
Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

Route Break
compute new MPR set
broadcast TC message
compute new path

G
F
H
A
C

Link
Break

B
D
Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

Example of a Reactive
Routing Protocol
Ad hoc On-Demand Distance Vector
(AODV)
Experimental RFC 3561
Authors: Charles Perkins, Elizabeth
Belding-Royer, Samir Das

Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

AODV
Main Functions
Route Discovery
Route Maintenance
Uses Destination Sequence Number to
avoid loops and Counting to Infinity
problem

Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

AODV: Route Discovery

G
F
H
A
C

J
E

B
D
Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

AODV: Route Discovery

G

A Source

J - Destination

H
A
C

J
E

B
D
Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

AODV: Route Discovery

G

A Broadcast a route
request (RREQ) packet
with Initial TTL =1

F
H
A
C

J
E

Broadcast RREQ

B
D
Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

AODV: Route Discovery

G

Nodes receiving the RREQ

sets up Reverse Routes to
the source

F
H
A
C

J
E

Broadcast RREQ

Reverse Route
D

Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

AODV: Route Discovery

G

A times out and rebroadcast

a Route Request (RREQ)
packet with TTL = 2

F
H
A
C

J
E

Broadcast RREQ

Reverse Route
D

Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

AODV: Route Discovery

G

Other Nodes Rebroadcasts

the Route Request (RREQ)
packet

F
H
A
C

J
E

B
D
Submission

Slid

Note: Nodes B, C and F

receives RREQ
Multiple times but
forward it only once

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

AODV: Route Discovery

G

A times out and re-broadcast

a Route Request (RREQ)
packet with TTL = 4

F
H
A
C

J
E

Broadcast RREQ

Reverse Route
D

Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

AODV: Route Discovery

G

Route Request Eventually

Reaches the Destination J

F
H
A
C

J
E

Broadcast RREQ

Reverse Route
D

Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

AODV: Route Discovery

G

Destination send route

Reply (RREP) back to
source using the revers
route

F
H
A

RREP
C

B
D
Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

AODV: Route Discovery

G

Node Receiving the RREP

sets up a Forward Path to
the Destination

F
H
A
C

J
E

Route Reply

Forward Path
D

Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

AODV: Route Discovery

G

Node Receiving the RREP

sets up a Forward Path to
the Destination

F
H
A
C

J
E

Route Reply

Forward Path
D

Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

AODV: Route Discovery

G

Node Receiving the RREP

sets up a Forward Path to
the Destination

F
H
A
C

J
E

A now has
a route to J

B
D
Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

AODV: Route Discovery

G

A can now use

the forward
route created

F
H
A
C

J
E

B
D
Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

AODV: Route Discovery

G
F
H
A
C

J
E

B
D
Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

AODV: Route Discovery

G

B Source

J - Destination

H
A
C

J
E

B
D
Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

AODV: Route Discovery

G

B Broadcast a route
request (RREQ) packet

F
H
A
C

J
E

B
D
Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

AODV: Route Discovery

G

A and C replies

F
H
A

RREP

C
B

RREP
D

Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

AODV: Route Discovery

G

B picks the
minimum hop
route (which is
through C)

F
H
A
C

J
E

B
D
Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

AODV: Route Error

G

A Source

J - Destination

H
A
C

J
E

B
D
Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

AODV: Route Break

G

Data is flowing
between A and
J

F
H
A
C

J
E

B
D
Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

AODV: Route Error

G

Link between E
and J breaks
due to

F
H
A

RF reasons, or
C

Link
Break

movement

B
D
Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

AODV: Route Error

G
F
H
A
C

Link
Break

All nodes
maintain a
precursor list of
nodes who
might use a link

B
D
Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

AODV: Route Error

G

Route Error
message is
sent to the
source

F
H
A
C

Link
Break

B
D
Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

AODV: Route Error

G
F
H
A
C

Link
Break

Route to J is
removed and
Route
Discovery is
reinitiated

B
D
Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

IRTF RRG Ad hoc Network Systems

Research Subgroup
Study of Ad hoc Network Systems (ANS)
Inter-layer Protocol Interaction, Quality of
Service Routing, Routing Scalability,
Network Auto-Configuration,
Interoperation with a wired infrastructure
Currently not very active
http://www.flarion.com/ans-research/
Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

Difference between IEEE 802.11s

and IETF MANET
IETF MANET

802.11s

Layer3
Distributed Architecture
Hop Based Metrics
No QoS
No Security Standard
No Multicast Standard
Mobility?
Up to Large Scale

Submission

Slid

Layer 2
Presence of Gateways
LQ/Hop Based Metrics
QoS
Security
Multicast
Mobility?
Reduced Scale

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

Current Research
Link Quality (MIT)
Integration of MANETs into existing
Internet (several Internet drafts, EU project
Daidalos)
Security
Energy-awareness

Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

Conclusion
Many general insights into routing/path
finding
Many concepts available, each with its
advantages and disadvantages
Concepts and experiences from MANETs
can be used for TGs

Submission

Slid

Avinash Joshi, Vann

Month 2000
August 2004

doc.: IEEE 802.11-00/1047r0

References
Ad Hoc Networking by Charles E. Perkins
http://moment.cs.ucsb.edu/AODV/aodv.html
http://hipercom.inria.fr/olsr/
http://w3.antd.nist.gov/wctg/manet/manet_bibliog.html
Google

Submission

Slid

Avinash Joshi, Vann