Routing in MANETs — Complete Study Notes | UNIT-I

ROUTING IN MANETs
Complete 10-Mark Answer Notes
UNIT-I | Ad Hoc Networks & MANETs

Topics Covered
• Criteria for Classification of Routing Algorithms
• Taxonomy of MANET Routing Algorithms
• Proactive Routing — DSDV
• Reactive Routing — DSR
• Reactive Routing — AODV
• Hybrid Routing — ZRP
• Position-Based Routing — Location Services (DREAM & Quorum)
• Forwarding Strategies — Greedy, Directional Flooding, DREAM, LAR

Ad Hoc Networks & MANETs | Page 1 of 12

Routing in MANETs — Complete Study Notes | UNIT-I

1. Criteria for Classification of Routing Algorithms

Routing in MANETs is the process of finding a path between a source and destination node in a
dynamic, infrastructure-less network. Since the topology changes frequently, routing algorithms are
classified based on several criteria.

Classification Criteria
1. Route Discovery Strategy
• Proactive (Table-driven): Routes are maintained continuously even before they are needed.
Every node keeps an up-to-date routing table.
• Reactive (On-demand): Routes are discovered only when needed, significantly reducing
overhead.
• Hybrid: Combines both proactive and reactive strategies for balanced performance.

2. Use of Topology Information

• Topology-based: Routing decisions made based on network topology (link-state or distance-
vector).
• Position-based (Geographic): Routing uses geographic coordinates of nodes via GPS.

3. Route Structure
• Flat Routing: All nodes play equal roles in the network.
• Hierarchical Routing: Nodes are organized in clusters or levels.

4. Use of Temporal Information

• Some protocols use time-based metrics to predict link availability and adapt to mobility.

5. Resource Awareness
• QoS-based routing considers bandwidth, delay, and energy constraints for optimal path
selection.

6. Single path vs. Multipath

• Some protocols discover multiple paths for reliability and load balancing.

Conclusion: These criteria help in choosing the right routing protocol based on network size, mobility,
traffic pattern, and energy constraints.

2. Taxonomy of MANET Routing Algorithms

The taxonomy provides a systematic classification of all MANET routing protocols into meaningful
categories based on their fundamental approach to route discovery and maintenance.

Classification Tree
MANET Routing Algorithms

Ad Hoc Networks & MANETs | Page 2 of 12

Routing in MANETs — Complete Study Notes | UNIT-I
├── Topology-Based
│ ├── Proactive → DSDV
│ ├── Reactive → DSR, AODV
│ └── Hybrid → ZRP
└── Position-Based (Geographic)
├── Location Services → DREAM, Quorum-based
└── Forwarding Strategies
├── Greedy Packet Forwarding
└── Restricted Directional Flooding → DREAM, LAR

Topology-Based Routing
• Nodes maintain routing tables based on network topology.
• Proactive protocols update tables periodically.
• Reactive protocols find routes on demand only when required.
• Hybrid protocols divide the network into zones for efficiency.

Position-Based Routing
• Nodes use physical location (GPS coordinates) to make forwarding decisions.
• Requires a Location Service to find the current position of destination nodes.
• Forwarding is done without maintaining full routing tables, improving scalability.

Comparison Table
Feature Topology-Based Position-Based
Control Overhead High Low
Route Setup Delay Low (proactive) / High No setup needed
(reactive)
Scalability Limited High
GPS Required No Yes
Loop Prevention Sequence numbers / Source Not applicable
routing

Conclusion: The taxonomy helps in understanding which routing protocol is best suited for a particular
MANET scenario based on scale, mobility, and infrastructure.

3. Proactive Routing — DSDV (Destination Sequenced Distance

Vector)
DSDV is a table-driven proactive routing protocol based on the Bellman-Ford algorithm. Every node
maintains a routing table with routes to all other nodes in the network at all times.

Ad Hoc Networks & MANETs | Page 3 of 12

Routing in MANETs — Complete Study Notes | UNIT-I

Key Features
• Each routing table entry contains: Destination, Next Hop, Number of Hops, Sequence Number.
• Sequence Number (assigned by the destination): Prevents routing loops and ensures
freshness of routes.
• Higher sequence number = more recent route = preferred route.

Working of DSDV
• Step 1: Every node periodically broadcasts its routing table to its neighbors.
• Step 2: When a node receives an update, it compares sequence numbers — higher sequence
number = more recent route (preferred).
• Step 3: Same sequence number but fewer hops = better route (preferred).

Types of Updates
• Full Dump: Complete routing table is sent. Used rarely (when major changes occur).
• Incremental Update: Only changed entries are sent. Used frequently to reduce overhead.

Routing Table Example

Destination Next Hop Hops Sequence No.
Node B Node B 1 302
Node C Node B 2 210
Node D Node C 3 148

Advantages
• Routes are immediately available when needed — no discovery delay.
• Loop-free routing guaranteed due to sequence numbers.
• Simple and easy to implement.

Disadvantages
• High control overhead due to periodic broadcasts regardless of traffic.
• Not scalable for large networks with many nodes.
• Wastes bandwidth maintaining routes that may never be used.

Conclusion: DSDV is suitable for small, stable MANETs where routes are frequently used and delay is
critical.

Ad Hoc Networks & MANETs | Page 4 of 12

Routing in MANETs — Complete Study Notes | UNIT-I

4. Reactive Routing — DSR (Dynamic Source Routing)

DSR is an on-demand reactive routing protocol where the complete route from source to destination is
embedded in the packet header itself (source routing). Routes are only discovered when needed.

Phase 1: Route Discovery

• Step 1: Source broadcasts a Route Request (RREQ) packet containing source address,
destination address, and a unique request ID.
• Step 2: Intermediate nodes append their own address to the RREQ and forward it.
• Step 3: When the RREQ reaches the destination (or a node with a cached route), a Route
Reply (RREP) is sent back with the full discovered path.

Example
RREQ: A → [A,B] → [A,B,C] → D
RREP: D sends back path [A → B → C → D] to A
Data packets now carry route: [A, B, C, D] in header

Phase 2: Route Maintenance

• If a link breaks, the node detecting it sends a Route Error (RERR) back to the source.
• Source can use an alternate cached route or initiate a new route discovery.

Route Caching
• Nodes overhear packets and cache routes for future use, reducing discovery overhead.
• Any node can answer a RREQ if it has a valid cached route to the destination.

Advantages
• No periodic updates — routes found only when needed, saving bandwidth.
• Route caching reduces latency for frequently accessed destinations.
• Supports asymmetric links.
• Multiple routes can be cached for the same destination.

Disadvantages
• Packet headers grow large in big networks as the full route is stored in header.
• Stale cache entries cause problems in high-mobility networks.
• Route discovery overhead in large, sparse networks can be significant.

Conclusion: DSR is suitable for moderate-mobility MANETs with low-to-medium traffic load where route
caching benefits are maximized.

Ad Hoc Networks & MANETs | Page 5 of 12

Routing in MANETs — Complete Study Notes | UNIT-I

5. Reactive Routing — AODV (Ad Hoc On-Demand Distance

Vector)
AODV combines the on-demand route discovery of DSR with the hop-by-hop routing of DSDV. Unlike
DSR, the full route is NOT stored in the packet. Instead, each intermediate node maintains routing table
entries.

RREQ Packet Fields

Field Description
Source IP Address of the originating node
Source Seq No. Sequence number of source (prevents loops)
Destination IP Address of desired destination
Dest Seq No. Last known sequence number of destination
Broadcast ID Unique ID to identify duplicate RREQs
Hop Count Number of hops traversed so far

Phase 1: Route Discovery

• Step 1: Source broadcasts RREQ if no valid route exists in routing table.
• Step 2: Intermediate nodes set up a reverse route to the source and forward RREQ.
• Step 3: Destination (or intermediate node with fresh enough route) sends RREP back along the
reverse path.
• Step 4: Forward routes are established in each node's routing table as RREP travels back to
source.

Phase 2: Route Maintenance

• Each routing table entry has a lifetime timer — expires if unused.
• If a link breaks, a RERR message is propagated to notify all affected upstream nodes.
• Sequence numbers ensure loop-free and fresh routes at all times.

Sequence Number Rule

• Higher destination sequence number → more recent route (always preferred).
• Same sequence number + fewer hops → preferred (shorter path).

AODV vs DSR Comparison

Feature AODV DSR
Route stored in packet No Yes (in header)

Ad Hoc Networks & MANETs | Page 6 of 12

Routing in MANETs — Complete Study Notes | UNIT-I

Routing table Yes (per node) No (route cache)

Loop prevention Sequence numbers Source routing
Route maintenance RERR messages Route Error + Cache
Scalability Better Moderate
Mobility handling Good Moderate (stale cache)

Advantages
• Low overhead — routes found on demand only.
• Scalable compared to proactive protocols.
• Loop-free routing guaranteed via sequence numbers.

Disadvantages
• Route discovery delay before communication begins.
• High overhead in high-mobility networks due to frequent RERR and rediscovery cycles.

Conclusion: AODV is widely used and is best suited for large, dynamic MANETs where traffic patterns
are unpredictable.

6. Hybrid Routing — ZRP (Zone Routing Protocol)

ZRP is a hybrid routing protocol that divides the network into overlapping zones around each node. It
uses proactive routing within zones and reactive routing between zones, combining the best of both
worlds.

Zone Definition
• Zone Radius (ρ): Each node defines a zone of radius ρ hops around itself.
• Nodes within ρ hops = Intrazone nodes (maintained proactively).
• Nodes beyond ρ hops = Interzone nodes (discovered reactively on demand).

Components of ZRP
1. IARP (Intrazone Routing Protocol)
• Proactively maintains routes within the zone.
• Uses link-state or distance-vector updates within the local zone only.
• Ensures all intrazone routes are always available without discovery delay.

2. IERP (Interzone Routing Protocol)

• Reactively discovers routes to destinations outside the zone.
• Uses bordercasting — sending queries to border nodes of the current zone.
• Avoids flooding the entire network with route requests.

Ad Hoc Networks & MANETs | Page 7 of 12

Routing in MANETs — Complete Study Notes | UNIT-I

3. BRP (Bordercast Resolution Protocol)

• Efficiently delivers route queries to border nodes only.
• Prevents duplicate queries and unnecessary network flooding.

Working Example
Node A wants to reach Node Z (outside A's zone):
Step 1: A checks IARP table → Z not found (outside zone)
Step 2: A uses IERP → bordercasts RREQ to border nodes
Step 3: Border nodes forward to their zones until Z is found
Step 4: Route reply sent back to A via reverse path

Zone Radius Trade-off

Zone Radius ρ Behavior Effect
ρ=1 Fully reactive (like AODV) Minimum proactive overhead
ρ = network diameter Fully proactive (like DSDV) Maximum overhead, minimum
delay
Optimal ρ Balanced hybrid Best balance of overhead vs. delay

Advantages
• Reduces route discovery latency compared to pure reactive protocols.
• Reduces routing overhead compared to pure proactive protocols.
• Highly adaptable — zone radius can be tuned per deployment.

Disadvantages
• Complex implementation compared to pure proactive or reactive.
• Choosing the optimal zone radius ρ is difficult and network-dependent.
• Overlapping zones may cause redundant updates.

Conclusion: ZRP is best suited for large MANETs where a balance between routing overhead and
discovery latency is required.

7. Position-Based Routing — Location Services

Position-based routing uses GPS coordinates to forward packets without maintaining routing tables. A
Location Service is required to find the current geographic position of destination nodes before
forwarding can begin.

Ad Hoc Networks & MANETs | Page 8 of 12

Routing in MANETs — Complete Study Notes | UNIT-I

A. DREAM (Distance Routing Effect Algorithm for Mobility)

Core Concept
• Each node periodically broadcasts its location to other nodes in the network.
• The frequency of location update depends on the node's speed — faster movement triggers
more frequent updates.
• Distance Routing Effect: Nodes far away need less frequent updates than nearby nodes,
saving bandwidth.

Working
• Step 1: Node A wants to send to Node Z.
• Step 2: A queries its location table for Z's current position.
• Step 3: A forwards the packet in the direction of Z's known position.
• Step 4: Intermediate nodes forward the packet if Z falls within their forwarding cone (angular
region toward destination).

Key Feature
• Location updates are proactive but adaptive — rate adjusts based on mobility speed.
• Reduces location update overhead significantly for static or slow-moving nodes.

B. Quorum-Based Location Service

Core Concept
• Nodes are organized into a logical grid structure.
• Quorum: A subset of nodes (row + column intersection in grid) that store location information.

Working
Grid Layout:
C1 C2 C3 C4
R1 [ ] [ ] [ ] [ ]
R2 [ ] [ Z ] [ ] [ ] ← Z updates entire Row 2
R3 [ ] [ ] [ ] [ ]
R4 [ ] [ ] [ ] [ ]
↑
A queries Column 2 → finds Z at intersection (R2,C2)

• Update: When Node Z moves, it updates all nodes in its row quorum.
• Query: When Node A wants Z's location, it queries all nodes in its column quorum.
• Since row and column always intersect, at least one quorum node has Z's location —
guaranteed discovery.

Advantages
• Efficient — no single server bottleneck, load is distributed.
• Guaranteed location discovery due to row-column intersection property.

Disadvantages
• Grid structure must be carefully maintained as nodes move.
• Update overhead increases significantly with node mobility.

Ad Hoc Networks & MANETs | Page 9 of 12

Routing in MANETs — Complete Study Notes | UNIT-I

Conclusion: Both DREAM and Quorum-based systems enable efficient position discovery for
geographic routing, each suited to different mobility and scale requirements.

8. Forwarding Strategies — Greedy, Directional Flooding, DREAM

& LAR
Once a node knows the destination's geographic position, it must decide how to forward the packet
toward it. Two primary forwarding strategies are widely used in position-based routing.

A. Greedy Packet Forwarding

Concept
• A node forwards the packet to the neighbor that is closest to the destination geographically.
• Uses geographic distance to make hop-by-hop forwarding decisions without a routing table.

Working
Source S, Destination D at position (x, y)
S finds neighbors: N1, N2, N3
S calculates distance of each neighbor to D
S selects neighbor with minimum distance to D → forwards packet

Problem — Local Maximum (Void)

• Local Maximum: If no neighbor is closer to D than the current node, forwarding gets stuck —
the algorithm fails.
• Solution: Perimeter routing / face routing is used to route around geographic voids in network
coverage.

Advantages
• Simple and computationally lightweight — no routing table required.
• Scales well with network size.
• Near-optimal path length in dense networks.

Disadvantages
• Fails at local maxima (voids) — no neighbor closer than current node.
• Requires GPS at all nodes.

B. Restricted Directional Flooding

Concept
• Instead of broadcasting to ALL neighbors, the packet is forwarded only to nodes within a
directional cone toward the destination.
• Reduces broadcast overhead while maintaining reliability of delivery.

Ad Hoc Networks & MANETs | Page 10 of 12

Routing in MANETs — Complete Study Notes | UNIT-I

DREAM Forwarding Strategy

• Cone Angle: The forwarding cone angle depends on the uncertainty of the destination's
position.
• Large uncertainty → wide cone (more nodes forwarded to).
• Small uncertainty → narrow cone (fewer, more targeted forwarding).

C. LAR (Location Aided Routing)

LAR restricts the route discovery flood to a limited geographic request zone instead of flooding the
entire network, dramatically reducing overhead.

Scheme 1 — Expected Zone

• Based on destination's last known position, speed, and time elapsed since last update, a
circular expected zone is calculated.
• RREQ is forwarded only to nodes inside or adjacent to this expected zone.

Scheme 2 — Request Zone

• A rectangular zone is defined using source and destination coordinates.
• Only nodes within this rectangle forward the RREQ — all others discard it.

S ─────────────────────── D
| Request Zone |
| (only nodes inside |
| forward the RREQ) |
└─────────────────────────┘

Advantages of LAR
• Drastically reduces flooding overhead compared to traditional reactive protocols.
• Faster route discovery in large, sparse networks.
• Easily combined with existing reactive protocols like AODV.

Disadvantages of LAR
• If destination has moved outside the expected zone, discovery fails — falls back to normal
flooding.
• Requires GPS at all participating nodes.
• Accuracy of expected zone depends heavily on location update frequency.

Quick Reference Summary Table

Protocol Type Key Feature Best Use Case

DSDV Proactive Sequence numbers, Small, stable MANETs
periodic updates

Ad Hoc Networks & MANETs | Page 11 of 12

Routing in MANETs — Complete Study Notes | UNIT-I

DSR Reactive Source routing, route cache Moderate mobility, low

in packet traffic
AODV Reactive On-demand, hop-by-hop, Large, dynamic MANETs
seq numbers
ZRP Hybrid Zone-based proactive + Large MANETs needing
reactive balance
DREAM Position-based Mobility-aware location High-mobility networks
updates
Quorum Position-based Grid-based location service Distributed, scalable
systems
Greedy Forwarding Nearest neighbor to Dense, void-free networks
destination
LAR Forwarding Restricted flood using Large networks, known
expected zone mobility

— End of Notes —

Ad Hoc Networks & MANETs | Page 12 of 12