MODULE 2 Routing Protocols for
Ad-hoc Networks
SYLLABUS
Overview of routing in ad-hoc networks, Proactive routing protocols:
Destination-Sequence Distance-Vector (DSDV), Optimized Link
State Routing (OLSR). Reactive routing protocols: Ad-hoc On-Demand
Distance Vector (AODV), Dynamic Source Routing (DSR). Hybrid routing
protocols: Zone Routing Protocol (ZRP), Performance evaluation and
comparison of routing protocols.
OVERVIEW OF ROUTING IN
AD-HOC NETWORKS
Ad-hoc networks are characterized by dynamic topologies where nodes
can freely move, making routing a crucial challenge.
Routing protocols in such networks can be classified into different
categories based on their operation:
Proactive Routing Protocols: These protocols maintain fresh lists of
destinations and their routes by periodically distributing routing tables
throughout the network.
Reactive Routing Protocols: These protocols create routes only when
desired by the source node, thus saving bandwidth and power.
Routing is essential for ensuring communication between nodes,
and due to the lack of a fixed infrastructure, ad-hoc networks rely
on distributed routing algorithms.
Major challenges include: Dynamic topology, Limited bandwidth,
Power constraints, Multi-hop routing.
1. Proactive or table-driven protocols:
Every node maintains the network topology information in the
form of routing table.
These tables are updated frequently.
Information is flooded in the entire network.
Ex: i. DSDV – Destination Sequenced Distance Vector Routing
Protocol
ii. OLSR - Optimized Link State Routing Protocol
PROACTIVE ROUTING PROTOCOLS
Proactive routing protocols maintain up-to-date routing information to all
nodes in the network by frequently distributing routing tables.
Some common proactive routing protocols include:
1. Destination-Sequenced Distance-Vector (DSDV)
2. Optimized Link State Routing (OLSR)
DSDV: DESTINATION
SEQUENCED DISTANCE VECTOR
ROUTING PROTOCOL
Enhanced version of distributed Bellam- Ford algorithm.
Each node maintains the shortest distance and the first node on
the shortest path.
Table updates are with increasing sequence number tags to
prevent loops – for faster convergence
Types of table updates – incremental and full dumps.
Incremental – single network data packet unit (NDPU), when no
significant topology changes are observed
Full dump – multiple NDPUs, when significant topology changes
are observed
PROCEDURE
Table update: - destination, with new sequence number > than
previous one
Advantages:
1. Less delay in the route setup process
2. Existing wired network protocols are applicable
3. Up-to-date view of network topology is maintained at all nodes
Disadvantages:
4. Heavy control overhead during high mobility – choke the available
bandwidth.
5. Not scalable
6. To obtain information about a particular destination node, a node has to
wait for a table update message which can lead to stale routing info. at
the nodes
OLSR: OPTIMIZED LINK STATE ROUTING
PROTOCOL
OLSR is a proactive link-state routing protocol, which
uses hello and topology control (TC) messages to discover and then
disseminate link state information throughout the mobile ad hoc
network.
Improvement over LSR.
Individual nodes use this topology information to compute next hop
destinations for all nodes in the network using shortest hop forwarding paths.
FLOW DIAGRAM OF OLSR
BASIC CONCEPTS
PHASE 1 – NEIGHBOUR
DISCOVERY
A HELLO MESSAGE IS
EXCHANGED PERIODICALLY
Using Hello messages the OLSR protocol at each node discovers 2-hop
neighbor information and performs a distributed election of a set of
multipoint relays (MPRs).
Nodes select MPRs such that there exists a path to each of its 2-hop
neighbors via a node selected as an MPR.
These MPR nodes then source and forward TC messages that contain
the MPR selectors.
This functioning of MPRs makes OLSR unique from other link state
routing protocols in a few different ways:
The forwarding path for TC messages is not shared among all nodes but varies
depending on the source, only a subset of nodes source link state information
Not all links of a node are advertised but only those that represent MPR selections.
Multipoint relays
Multipoint relays (MPRs) relay messages between nodes.
They also have the main role in routing and selecting the proper route
from any source to any desired destination node.
MPRs advertise link-state information for their MPR selectors (a node
selected as a MPR) periodically in their control messages.
MPRs are also used to form a route from a given node to any destination
in route calculation.
Each node periodically broadcasts a Hello message for the link sensing,
neighbor detection and MPR selection processes.
OLSR makes use of "Hello" messages to find its one hop neighbors and
its two hop neighbors through their responses.
The sender can then select its multipoint relays (MPR) based on the one
hop node that offers the best routes to the two hop nodes.
Each node has also an MPR selector set, which enumerates nodes that
have selected it as an MPR node.
OLSR uses topology control (TC) messages along with MPR forwarding to
disseminate neighbor information throughout the network.
Host and network association (HNA) messages are used by OLSR to
disseminate network route advertisements in the same way TC messages
advertise host routes.
HELLO
TOPOLOGY CONTROL (TC)
REACTIVE ROUTING PROTOCOLS:
AODV, DSR
On-Demand Routing protocols
Only when a path is required by a node to communicate with
destination – execute the path finding process and exchange the
information.
EX:
Ad Hoc On-Demand Distance Vector Routing Process – AODV
Dynamic Source Routing Protocol – DSR
AODV: AD-HOC ON-DEMAND
VECTOR ROUTING
PROTOCOL
A route is established only when it is required by a source node
for transmitting data packets.
It employs destination sequence numbers to identify the most
recent path
DSR- data packet carries the complete path to be traversed
AODV- the source node & intermediate nodes store the next hop
information corresponding to each flow
A node updates its path information only if the DestSeqNum of the
current packet received is greater than the last DestSeqNum stored
at the node.
Advantages:
1. Connection setup delay is less
Disadvantages:
1. Incossistent routes if sequence number is very old.
2. Multiple route reply packets for single route request.
3. More bandwidth consumption due to periodic beaconing.
DSR
It is beacon less – hence does not require periodic hello packet
transmission
Route request packet is sent, the destination node responds with a
route reply packet back to the source, which carries the route
traversed by the route request packet received
EXAMPLE
1. Consider a source node that does not have a route to destination
2. When it has data packets to be sent to that destination, it initiates
a routerequest packet.
3. This Routerequest is flooded throughout the network
4. Each node upon receiving a routerequest packet, rebroadcasts it if
it is not the destination node, provided the packet’s Time to Live (TTL)
counter has not exceeded and is not a duplicate routerequest.
5. Each routerequest carries a sequence number generated by the
source node and the path it has traversed.
6. All nodes except the destination node take part in forwarding the
routerequest packet.
7. The destination node, after receiving the routerequest packet,
replies to the source node through the reverse path the route
request packet has traversed.
Key feature:
It uses a route cache that stores all possible information
ROUTE ESTABLISHMENT IN
DSR
Advantages:
1. Eliminates the need to periodically flood the network with table update
messages.
2. There is no need to find routes to all other nodes.
3. Reduced control overhead
Disadvantages:
1. Not possible to locally repair a broken link
2. Connection set up delay is higher than in table – driven protocols.
3. Performance is affected with increased node mobility
4. Routing overhead ( directly proportional to the path length)
HYBRID ROUTING PROTOCOLS ZRP
HYBRID ROUTING PROTOCOLS
Zone Routing Protocol (ZRP): combines best features of proactive
and reactive routing protocols.
Uses proactive routing scheme within a limited zone in a r- hop
neighbourhood of every node
Uses a reactive routing scheme for nodes beyond this zone.
An INTRA-ZONE ROUTING PROTOCOL (IARP) – for proactive
An INTER-ZONE ROUTING PROTOCOL (IERP) – for reactive
Routing zone diameter selected that optimized the routing
ZRP
Zone Radius = ?
Advantages:
1. Reduced control overhead
Disadvantage:
1. Redundant routerequests might be forwarded.
PERFORMANCE EVALUATION AND COMPARISON OF ROUTING PROTOCOLS
The performance of routing protocols depends on the network conditions, such as
the number of nodes, traffic density, and mobility rate:
•DSDV- Performs best in networks with fewer, denser nodes. However, its
performance declines with more nodes due to increased traffic. DSDV performs
poorly at high movement speeds and with a large number of nodes.
•OLSR- Performs best in networks with fewer, denser nodes. OLSR has the highest
throughput performance at 20 nodes, but its performance decreases at higher node
counts.
•AODV- Performs well in networks with a larger number of nodes. AODV has the best
throughput and packet loss value compared to DSDV and AOMDV.
•DSR- Performs well in networks with low mobility and low traffic density. DSR
performs well in terms of packet delivery ratio when there are fewer nodes. However,
its performance declines with more nodes. DSR has a relatively lower routing
overload compared to other protocols.
The performance of routing protocols can be evaluated using metrics like average jitter,
throughput, packet delivery ratio, and average end to end delay. Here's some information
about proactive, reactive, and hybrid routing protocols:
• Proactive routing protocols: These protocols are also known as destination-based
protocols, and they help maintain routing tables. They're best for networks with low node
mobility or where nodes transmit data frequently. Proactive protocols guarantee route
availability, but they can suffer from scalability and overhead.
• Reactive routing protocols: These protocols are also known as table-driven protocols,
and they use route discovery and maintenance mechanisms. Unlike proactive protocols,
each node doesn't store the current route of the entire network.
• Hybrid routing protocols: These protocols are a combination of proactive and reactive
protocols.
END OF MODULE 2
