Routing in Mobile Ad-Hoc Network

Dr. Shariq Mahmood Khan

shariq@[Link]

Department of Computer Science & IT, NED University of Engineering & Technology, Karachi
Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 1
What is a Mobile Ad Hoc Network (MANET)?
• Collection of mobile nodes
• Located in such a manner that the interconnections between nodes are capable of
changing on continuous basis
• Self-forming, self-maintained and self-healing
• Nodes change location and configure itself

Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 2
A scenario for a Mobile Wireless Ad Hoc Network (MANET)

Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 3
Routing Protocols
Reactive protocols
- Determine route if and when needed
- Source initiates route discovery
- Example: AODV (Ad hoc On-Demand Distance Vector)

Proactive protocols
- Traditional distributed shortest-path protocols
- Maintain routes between every host pair at all times
- Based on periodic updates; High routing overhead
- Example: DSDV (destination sequenced distance vector)

Hybrid protocols
- Adaptive; Combination of proactive and reactive
- Example : ZRP (zone routing protocol)

Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 4
Ad hoc routing protocols

AD-HOC MOBILE ROUTING

PROTOCOLS

TABLE DRIVEN/ ON-DEMAND-DRIVEN

PROACTIVE REACTIVE

DSDV HYBRID DSR

OLSR AODV

ZRP

Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 5
Protocol Trade-offs
Proactive protocols
- Always maintain routes
- Little or no delay for route determination
- Consume bandwidth to keep routes up-to-date
- Maintain routes which may never be used

Reactive protocols
- Lower overhead since routes are determined on demand
- Significant delay in route determination
- Employ flooding (global search)
- Control traffic may be bursty

Which approach achieves a better trade-off depends on the traffic and mobility patterns

Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 6
MANET Reactive protocol
• AODV (Ad hoc On-Demand Distance Vector )
Uses Distance-Vector routing protocol

Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 7
Distance-Vector routing protocol
What it does:
- Computes best paths to all destinations
- Fully distributed and Updates are performed periodically
- Using as only information the distances from self to all destinations
How it works
- Uses Bellman–Ford algorithm, Ford–Fulkerson algorithm, or DUAL FSM
- Can faces Count to infinity problem
Do not have knowledge of the entire path to a destination. Instead they use two methods:
- Direction in which a packet should be forwarded.
- Distance from its destination

Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 8
AODV Protocol
• The Ad hoc On-Demand Distance Vector protocol is an on-demand

• Dynamic, self-starting, multi-hop routing between mobile nodes

• A route is maintained only when it is used and hence old and expired routes are never
used.

• AODV maintains only one route between a source-destination pair.

• The packet size in AODV is uniform and supports multicasting and unicasting within a
uniform framework.

• Each route has a lifetime after which the route expires if it is not used.

Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 9
AODV Protocol
AODV defines 3 message types:
- Route Requests (RREQs)
- Route Replies (RREPs)
- Route Errors (RERRs)
RREQ messages are used to initiate the route finding process.
RREP messages are used to finalize the routes
RERR messages are used to notify the network of a link breakage in an active route.
Route table information must be kept for all routes even short-lived routes.

Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 10
AODV Routing Table

Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 11
Route Request
• Type 1
• J Join flag : reserved for multicast.
• R Repair flag : reserved for multicast.
• G Gratuitous RREP flag
• D Destination only flag
• U Unknown sequence number
• Reserved Sent as 0
• Hop Count: The number of hops from the Originator IP Address to the node handling the request.

Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 12
Route Reply
• Type 2
• R Repair flag; used for multicast.
• A Acknowledgment required
• Reserved Sent as 0
• Prefix Size: If nonzero, the 5-bit Prefix Size specifies that the indicated next hop may be used for any
nodes with the same routing prefix
• Hop Count : The number of hops from the Originator IP Address to the Destination IP Address.

Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 13
Route Request and Route Reply
Route Request (RREQ) includes the last known sequence number for the destination

An intermediate node may also send a Route Reply (RREP) provided that it knows a more recent path than
the one previously known to sender
Intermediate nodes that forward the RREP, also record the next hop to destination

A routing table entry maintaining a reverse path is purged after a timeout interval
A routing table entry maintaining a forward path is purged if not used for a active_route_timeout interval

Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 14
Maintaining Sequence Numbers
Keep AODV loop-free and avoiding the “counting to infinity” problem.
Nodes originating RREQ messages must increment their own sequence number before transmitting the
RREQ.
Before a destination node originates a RREP in response to a RREQ, it MUST update its own sequence
number
Forwarding nodes update their stored sequence number when forwarding RREP when:
- The sequence number in the routing table is invalid
- The sequence number in the RREP message is greater than the stored number
- The sequence numbers are identical, but the route is marked as inactive
- The sequence numbers are the same, but the hop count is smaller for the RREP message.

Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 15
AODV Operation
Route Requests (RREQ) are broadcasted it to its neighbors with initial TTL of 1.

When a node re-broadcasts a Route Request, it sets up a reverse path pointing towards
the source
- AODV assumes symmetric (bi-directional) links

When the intended destination receives a Route Request, it replies by sending a Route
Reply (RREP)

Route Reply travels along the reverse path set-up when Route Request is forwarded

Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 16
Route Requests in AODV
Y

Z
S E
F
B
C M L
J
A G
H D
K
I N

Represents a node that has received RREQ for D from S

Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 17
Route Requests in AODV
Y
Broadcast transmission

Z
S E
F
B
C M L
J
A G
H D
K
I N

Represents transmission of RREQ

Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 18
Route Requests in AODV
Y

Z
S E
F
B
C M L
J
A G
H D
K
I N

Represents links on Reverse Path

Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 19
Reverse Path Setup in AODV
Y

Z
S E
F
B
C M L
J
A G
H D
K
I N

• Node C receives RREQ from G and H, but does not forward

it again, because node C has already forwarded RREQ once

Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 20
Reverse Path Setup in AODV
Y

Z
S E
F
B
C M L
J
A G
H D
K
I N

Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 21
Reverse Path Setup in AODV
Y

Z
S E
F
B
C M L
J
A G
H D
K
I N

• Node D does not forward RREQ, because node D

is the intended target of the RREQ
Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 22
Forward Path Setup in AODV
Y

Z
S E
F
B
C M L
J
A G
H D
K
I N

Forward links are setup when RREP travels along

the reverse path

Represents a link on the forward path

Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 23
Link Failure
A neighbor of node X is considered active for a routing table entry if the neighbor sent a packet within
active_route_timeout interval which was forwarded using that entry

Neighboring nodes periodically exchange hello message

When the next hop link in a routing table entry breaks, all active neighbors are informed

Link failures are propagated by means of Route Error (RERR) messages, which also update destination
sequence numbers

Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 24
Route Error
When node X is unable to forward packet P (from node S to node D) on link (X,Y), it generates a RERR
message

Node X increments the destination sequence number for D cached at node X

The incremented sequence number N is included in the RERR

When node S receives the RERR, it initiates a new route discovery for D using destination sequence
number at least as large as N

When node D receives the route request with destination sequence number N, node D will set its sequence
number to N, unless it is already larger than N

Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 25
Performance of AODV
AODV does not retransmit data packets that are lost and hence does not guarantee packet delivery.

The packet delivery percentage drops with increased mobility.

Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 26
Control Overheads
The overhead packets in AODV are due to RREQ, RREP and RERR messages.

AODV needs much less number of overhead packets compared to DSDV.

The number of overhead packets increases with increased mobility, since this gives rise to frequent link
breaks and route discovery.

Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 27
AODV: Summary
Routes need not be included in packet headers

Nodes maintain routing tables containing entries only for routes that are in active use

At most one next-hop per destination maintained at each node

- DSR may maintain several routes for a single destination

Sequence numbers are used to avoid old/broken routes

Sequence numbers prevent formation of routing loops

Unused routes expire even if topology does not change

Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 28
Proactive Routing : DSDV
• Proactive, table-driven protocol
• All nodes maintain a Route Table Entry for every
other destination in the network
• Route Table Entry – contains next hop for a
destination, number of hops to reach the
destination, a sequence number
• Nodes broadcast routing updates
• Sequence Number – helps removing stale routes,
and avoids loops

Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 29
Hybrid Routing : Zone Routing Protocol (ZRP)

Zone for S B
E
A

C
S
Zone for D D
F
G

H
Zone for F

Dr. Shariq Mahmood Khan – Department of Computer Science & IT , NED UET Karachi. 30