Routing Protocols

Issues in Designing Routing Protocols

• Mobility

• Bandwidth Constraint

• Error-Prone Shared Broadcast Radio Channel

• Hidden and Exposed Terminals Problems

• Resource Constraints
 Cont..
• The limited bandwidth availability also imposes a constraint on routing protocols in
maintaining the topological information.

• The wireless links have time-varying characteristics in terms of link capacity and link-
error probability.

• This requires that the ad hoc wireless network routing protocol interacts with the MAC
layer to find alternate routes through better-quality links.

• Route computation and maintenance must involve a minimum number of nodes.

• It must be loop-free and free from stale routes.

Classification of Routing Protocols
The routing protocols (RP) for ad-hoc wireless networks can be broadly classified into four
categories based on:

• Routing information update mechanism

• Use of temporal information for routing

• Routing topology

• Utilization of specific resources

 RP based on Routing information update mechanism
Proactive or table-driven routing protocols: Every node maintains the network topology
information in the form of routing tables by periodically exchanging routing information.

• Whenever a node requires a path to a destination, it runs an appropriate path-finding algorithm

on the topology information it maintains.

Reactive or on-demand routing protocols: These protocols do not maintain the network topology
information.

• They obtain the necessary path when it is required, by using a connection establishment process.

• Hence these protocols do not exchange routing information periodically.

 Cont..
Hybrid routing protocols: Nodes within a certain distance from the node concerned, or within a
particular geographical region, are said to be within the routing zone of the given node.

• For routing within this zone, a table-driven approach is used.

• For nodes that are located beyond this zone, an on-demand approach is used.
 RP based on Use of Temporal Information For Routing
• Use of temporal information (lifetime of the wireless links)

Routing protocols using past temporal information: Use information about the past status of
the links or the status of links at the time of routing to make routing decisions.

• For example, the routing metric based on the availability of wireless links along with a
shortest path-finding method, provides a path that may be efficient and stable at the time of
path-finding.

• The topological changes may immediately break the path, making the path undergo a
resource-wise expensive path reconfiguration process.
 Cont..
Routing protocols that use future temporal information: They use information about the
expected future status of the wireless links to make approximate routing decisions.

• Apart from the lifetime of wireless links, the future status information also includes
information regarding the lifetime of the node (the remaining battery charge and discharge
rate), prediction of location, and prediction of link availability.
RP based Routing Topology
Flat topology routing protocols: Flat topology routing protocols treat all nodes equally,
without any hierarchical structure or clustering.

• All nodes function as peers; no special roles like cluster heads.

• It assumes the presence of a globally unique addressing mechanism for nodes in networks.

Hierarchical topology routing protocols: Hierarchical topology routing organize nodes into
structured layers (hierarchies), improving scalability and routing efficiency for large networks.

• Nodes are grouped into clusters, zones, or trees.

• Certain nodes (e.g., cluster heads or gateways) manage routing within and between groups.

• Reduces overhead and improves efficiency for large networks.

RP based Utilization of Specific Resources
Power Aware Routing: This category of routing protocols aims at minimizing the consumption
of battery power.

• The routing decisions are based on minimizing the power consumption either locally or
globally in the network.

Geographical Information Assisted Routing: Protocols belonging to this category improve the
performance of routing and reduce the control overhead by effectively utilizing the
geographical information available..
 Table-Driven Routing Protocols

• These protocols maintain the global topology information in the form of tables at every node.

• These tables are updated frequently in order to maintain consistent and accurate network
state information.
 Destination Sequenced Distance-Vector (DSDV) Routing Protocol

 Wireless Routing Protocol (WRP)

 Cluster-Head Gateway Switch (CGSR) Routing Protocol

 Source-Tree Adaptive Routing Protocol (STAR)

Destination Sequenced Distance-Vector (DSDV) RP
• Each node maintains a table that contains the shortest distance and the first node on
the shortest path to every other node in the network.

• It incorporates table updates with increasing sequence number tags to prevent loops, to
counter the count-to-infinity problem.

• Routes to all destinations are readily available at every node at all times.

• The tables are exchanged between neighbors at regular intervals to keep an up-to-date
view of the network topology.

• The tables are also forwarded if a node observes a significant change in local topology.

• The table updates are of two types: incremental updates and full dumps.
 Cont..
• An incremental update takes a single network data packet unit (NDPU), while a full dump may
take multiple NDPUs.

• Table updates are initiated by a destination with a new sequence number which is always
greater than the previous one.

• Upon receiving an updated table, a node either updates its tables based on the received
information or holds it for some time to select the best metric received.

• Based on the sequence number of the table update, it may forward or reject the table.

• The number is even for periodic updates and odd for route invalidation.

• When broadcasting routing tables, nodes update their neighbors with the latest sequence
numbers.
Cont..
Cont..
 Wireless Routing Protocol
• Similar to DSDV routing protocol, but avoids count-to-infinity problem.

• It employs a unique method of maintaining information regarding the shortest distance to

every destination node in the network and the penultimate (predecessor) hop node on the
path to every destination node.

• It uses a set of tables to maintain more accurate information:

 Distance table

 Routing table (RT)

 Link cost table (LCT)

 Message retransmission list (MRL)

 Cluster-Head Gateway Switch (CGSR) RP
• It uses a hierarchical network topology, unlike other table-driven routing method that employ flat
topologies.

• CGSR organizes nodes into clusters, with coordination among the members of each cluster entrusted to a
special node named cluster-head.

• This cluster head is elected dynamically by employing a least cluster change (LCC) algorithm.

• Clustering provides a mechanism to allocate bandwidth, which is a limited resource, among different
clusters, thereby improving reuse.

• All member nodes of a cluster can be reached by the cluster-head within a single hop, thereby enabling the
cluster-head to provide improved coordination among nodes that fall under its cluster.

• CGSR assumes that all communication passes through the cluster-head.

 Cont..
• Communication between two clusters takes place through the common member nodes that are
members of both the clusters.

• These nodes which are members of more than one cluster are called gateways.

• Gateway is expected to be able to listen to multiple spreading codes (CDMA) that are currently in
operation in the clusters in which the node exists as a member.

• The routing protocol used in CGSR is an extension of DSDV.

• Each node maintains a cluster member table that has mapping from each node to its respective
cluster-head.

• Each node broadcasts its cluster member table periodically and updates.
 Cont..

• In addition, each node also maintains a routing table that determines the next hop to reach the
destination cluster.

• On receiving a packet, a node finds the nearest cluster-head along the route to the destination
according to the cluster member table and the routing table.
Cont..
 On-Demand Routing Protocols

Unlike the table-driven routing protocols, on-demand routing protocols execute the path-
finding process and exchange routing information only when a path is required by a node
to communicate with a destination.

• Dynamic Source Routing Protocol (DSRP)

• Ad Hoc On-Demand Distance-Vector Routing Protocol (AODV)

• Temporally Ordered Routing Algorithm (TORA)

• Location-Aided Routing (LAR)

 Dynamic Source Routing Protocol (DSRP)

• It is an on-demand protocol designed to restrict the bandwidth consumed by control packets by

eliminating the periodic table-update messages required in the table-driven approach.

• It does not require periodic hello packet (beacon) transmissions, which are used by a node to inform its
neighbors of its presence.

• The basic approach of this protocol (and all other on-demand RPs) during the route construction phase
is to establish a route by flooding RouteRequest packets in the network.

• The destination node, on receiving a RouteRequest packet, responds by sending a RouteReply packet
back to the source, which carries the route travelled by the RouteRequest packet received.
 Cont..
• Each node, upon receiving a RouteRequest packet, rebroadcasts the packet to its
neighbors if it has not forwarded already or if the node is not the destination node,
provided the packet’s time to live (TTL) counter has not exceeded.

• Each RouteRequest carries a sequence number generated by the source node and the
path it has travelled.

• The packet is forwarded only if it is not a duplicate RouteRequest.

• The sequence number on the packet is used to prevent loop formations and to avoid
multiple transmissions of the same RouteRequest by an intermediate node that receives
it through multiple paths.
 Cont..
• A destination node, after receiving the RouteRequest packet, replies to the source node
through the reverse path the RouteRequest packet had navigated.

• The source node selects the latest and best

route, and uses that for sending data packets.
• Each data packet carries the complete path to
its destination.
 Cont..
• When an intermediate node in the path moves
away, a RouteError message is generated from the
node adjacent to the broken link to inform the
source node.

• The source node reinitiates the route

establishment procedure.

• The cached entries at the intermediate nodes and

the source node are removed when a RouteError
packet is received.
 Ad Hoc On-Demand Distance-Vector (AODV) RP
• The major difference between AODV and DSR stems out from the fact that DSR uses source
routing in which a data packet carries the complete path to be traversed.

• In AODV, the source node and the intermediate nodes store the next-hop information
corresponding to each flow for data packet transmission.

• The major difference between AODV and other on-demand RPs is that it uses a destination
sequence number (DestSeqNum) to determine an up-to-date path to the destination.

• 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.
 Cont..
• A RouteRequest carries the following details:
• the source identifier (SrcID)

• the destination identifier (DestID)

• the source sequence number (SrcSeqNum)

• the destination sequence numer (DestSeqNum)

• the broadcast identifier (BcastID),

• the time to live (TTL)

• DestSeqNum indicates the freshness of the route that is accepted by the source.

• When an intermediate node receives a RouteRequest, it either forwards it or prepares a RouteReply if

it has a valid route to the destination.
 Cont..
• The validity of a route at the intermediate node is determined by comparing the sequence number at
the intermediate node with the destination sequence number in the RouteRequest packet.

• If a RouteRequest is received multiple times, the duplicate copies are discarded.

• All intermediate nodes having valid routes to the destination, or the destination node itself, are allowed
to send RouteReply packets to the source.

• Every intermediate node, while forwarding a RouteRequest, enters the previous node address and its
BcastID.

• When a node receives a RouteReply packet, information about the previous node from which the
packet was received is also stored in order to forward the data packet to this next node as the next hop
toward the destination.
Cont..
 Temporally Ordered Routing Algorithm (TORA)
• It uses a link reversal algorithm and provides loop-free multipath routes to a destination node.

• In TORA, each node maintains its one-hop local topology information and also has the capability
to detect partitions.

• TORA has the unique property of limiting the control packets to a small region during the
reconfiguration process initiated by a path break.

• TORA uses a distance metric which is nothing but the length of the path, or the height from the
destination H(N).

• TORA has three main functions: establishing, maintaining, and erasing routes.
 Cont..
• The route establishment function is performed only when a node requires a path to a
destination but does not have any directed link.

• This process establishes a destination-oriented directed acyclic graph (DAG) using a

Query/Update mechanism.

• Query packet is originated by the source node with the destination address included in it.

• This Query packet is forwarded by intermediate nodes and reaches the destination node, or any
other node which has a route to the destination.

• The node that terminates the Query packet replies with an Update packet containing its
distance from the destination (it is zero at the destination node).

• Each node that receives the Update packet sets its distance to a value higher than the
distance of the sender of the Update packet.
 Cont..
• Once a path to the destination is obtained, it is considered to exist as long as the path is
available, irrespective of the path length changes due to the reconfigurations that may
take place during the course of the data transfer session.
 Cont..
• When an intermediate node (say, node 5) discovers that the route to the destination node is invalid, it
changes its distance value to a higher value than its neighbors and originates an Update packet.

• The neighboring node 4 that receives the Update packet reverses the link between 1 and 4 and forwards
the Update packet.

• This is done to update the DAG corresponding to destination node 7.

• If the source node has no other neighbor that has a path to the destination, it initiates a fresh Query.
 Zone Routing Protocol (Hybrid RP)
• Zone routing protocol (ZRP) is a hybrid routing protocol which effectively combines the best
features of both proactive and reactive routing protocols.

• Key Concept: A proactive routing scheme within a limited zone in the r-hop neighborhood of
every node, and use a reactive routing scheme for nodes beyond this zone.

• An intra-zone routing protocol (IARP) is used in the zone where a particular node employs
proactive routing.

• The reactive routing protocol used beyond this zone is referred to as inter-zone routing
protocol (IERP).

• The routing zone of a given node is a subset of the network, within which all nodes are
reachable within less than or equal to zone radius hops.
 Cont..
• With zone radius = 2, the nodes 7, 4, 12, and 13 are
interior nodes, whereas nodes 2, 3, 5, 9, 10, 13, and
15 are peripheral nodes (nodes with the shortest
distance equal to the zone radius).

• Each node maintains the information about routes to

all nodes within its routing zone by exchanging
periodic route update packets (part of IARP).

• Larger the routing zone, the higher the update

control traffic.
 Cont...
• IERP effectively uses the information available at every node’s routing zone.

• When a node s has packets to be sent to a destination node d, it checks whether node d is
within its zone.

• If the destination belongs to its own zone, then it delivers the packet directly.

• Otherwise, node s bordercasts (uses unicast routing to deliver packets directly to the border
nodes) the RouteRequest to its peripheral nodes.

• If any peripheral node finds node d to be located within its routing zone, it sends a RouteReply
back to node s indicating the path; otherwise, the node re-bordercasts the RouteRequest
packet to the peripheral nodes.
 Cont...
• Nodes 10 and 14 find the information about node 16 to be
available in their intra-zone routing tables, and hence they
originate RouteReply packets back to node 8.

• During RouteRequest propagation, every node that forwards

the RouteRequest appends its address to it.

• This information is used for delivering the RouteReply packet

back to the source.

• The path-finding process may result in multiple RouteReply

packets reaching the source, in which case the source node
can choose the best path among them.

When a broken link in the path is detected, the node performs a local path reconfiguration in which the broken link is
bypassed by means of a short alternate path connecting the ends of the broken link.
 Optimized Link State Routing (Flooding Mechanism)
• The optimized link state routing (OLSR) protocol is a proactive routing protocol that employs
an efficient link state packet forwarding mechanism called multipoint relaying.

• Every node independently constructs and maintains a complete network topology by

exchanging link-state advertisements (LSAs) with its neighbors.

• Optimizations are done in two ways: by reducing the size of the control packets and by
reducing the number of links that are used for forwarding the link state packets.

• The reduction in the size of link state packets is made by declaring only a subset of the links in
the link state updates of the interest.

• This subset of links or neighbors that are designated for link state updates and are assigned
the responsibility of packet forwarding are called multipoint relays.
 Cont..
• The link state update optimization achieves higher efficiency when operating in highly dense
networks.

• In flooding-based approach, the number of message transmissions is approximately equal to

the number of nodes that constitute the network.

• The set consisting of nodes that are multipoint relays is referred to as MPRset.

• Each node (say, P) in the network selects an MPRset that processes and forwards every link
state packet that node P originates.

• The neighbor nodes that do not belong to the MPRset process the link state packets
originated by node P but do not forward them.

• Similarly, each node maintains a subset of neighbors called MPR selectors, which is the set of
neighbors that have selected the node as a multipoint relay.
 Cont..
• A node forwards packets that are received from nodes belonging to its MPRSelector set.

• The members of both MPRset and MPRSelectors keep changing over time.

• The members of the MPRset of a node P are selected such that every node in P’s two-hop
neighborhood has a bidirectional link with the node P.

• Every node periodically broadcasts its MPRSelector set to nodes in its immediate
neighborhood.

• A node periodically sends Hello messages that contain the list of neighbors with which the
node has bidirectional links and the list of neighbors whose transmissions were received in the
recent past but with whom bidirectional links have not yet been confirmed.

• A data structure called neighbor table is used to store the list of neighbors, the two-hop
neighbors, and the status of neighbor nodes.
 Cont..

The neighbour nodes can be in one

of the three possible link status
states, that is, unidirectional,
bidirectional, and multipoint relay.
 Cont..
• To remove the stale entries from the neighbor table, every entry has an associated timeout value, which,
when expired, removes the table entry.

• Similarly a sequence number is attached with the MPRset which gets incremented with every new
MPRset.

• The MPRset need not be optimal, and during initialization of the network it may be same as the neighbor
set.

• The smaller the number of nodes in the MPRset, the higher the efficiency of protocol.

• Every node periodically originates topology control (TC) packets that contain topology information with
which the routing table is updated.

• These TC packets contain the MPRSelector set of every node and are flooded throughout the network
using the multipoint relaying mechanism.
 Fisheye State Routing Protocol (Hierarchical Mechanism)

• The fisheye state routing (FSR) protocol is a generalization of the Global State Routing (GSR) protocol.

• FSR uses the fisheye technique to reduce information required to represent graphical data, to reduce
routing overhead.

• The basic principle behind this technique is the property of a fish’s eye that can capture pixel
information with greater accuracy near its eye’s focal point.

• This accuracy decreases with an increase in the distance from the center of the focal point.

• In FSR, accurate information about nodes in its local topology, and the accuracy of the network
information decreasing with increasing distance.

• FSR maintains the topology of the network at every node, but does not flood the entire network with the
information.
 Cont..

• Instead of flooding, a node exchanges topology information only with its neighbors.

• A sequence numbering scheme is used to identify the recent topology changes.

• This constitutes a hybrid approach comprising of the link-level information exchange of distance
vector protocols (DSDV) and the complete topology information exchange of link state protocols.

• The complete topology information of the network is maintained at every node and the desired
shortest paths are computed as required.

• The topology information exchange takes place periodically rather than being driven by an event.

• FSR defines routing scope, which is the set of nodes that are reachable in a specific number of
hops.
 Cont..

• The routing overhead is significantly

reduced by adopting different
frequencies of updates for nodes
belonging to different scopes.
 Cont..
• The link state information (direct and indirect connections) for the nodes belonging to the
smallest scope is exchanged at the highest frequency.

• The frequency of exchanges decreases with an increase in scope.

• This keeps the immediate neighborhood topology information maintained at a node more
precise compared to the information about nodes farther away from it.

• Thus the message size for a typical topology information update packet is significantly reduced
due to the removal of topology information regarding the far-away nodes.

• The path information for a distant node may be inaccurate as there can be staleness in the
information.

• However, the path information gets more and more accurate as the packet nears its
destination.
 Cont..

• Multi-level scopes employed by FSR

significantly reduces the bandwidth
consumed by link state update packets.
• Hence, FSR is suitable for large and
highly mobile ad hoc wireless networks.
Power Aware Routing Protocols

• Power aware routing metrics

 Minimum energy consumption per packet

 Maximize network connectivity

 Minimum variance in node power levels

 Minimum cost per packet

 Minimize maximum node cost

• Sleep-Based and Duty-Cycle Routing