Routing protocols

Routing protocols – In Mobile Ad hoc Network (MANET), nodes do not know the topology of their network, instead, they have to discover it every time whenever they need communication.

The rules are that a new node whenever enters into an ad-hoc network must announce its arrival and presence and should also listen to similar announcement broadcasts made by other mobile nodes.

Various routing protocols are used to discover the path to communicate from source to destination –

These routing protocols are-

Pro-active routing protocols and
Reactive routing protocols

These protocols are discussed below-

Pro-active routing protocols

Pro-active routing protocols are also known as table-driven routing protocols.

In table-driven routing protocols, each mobile node maintains a separate routing table that contains the information of the routes to all the possible destination mobile nodes.

Since the topology in the mobile ad-hoc network is dynamic, these routing tables are updated periodically as and when the network topology changes.

It has a limitation that it doesn’t work well for the large networks because the entries in the routing table become too huge since they need to maintain the route information to all possible nodes.

A detailed description of table-driven routing protocols are as below-

Destination Sequenced Distance Vector Routing Protocol (DSDV)

It is a pro-active/table-driven routing protocol.
It actually extends the distance vector routing protocol of the wired networks.
It is based on the Bellman-ford routing algorithm.
The distance vector routing protocol was not suited for mobile ad-hoc networks due to the count-to-infinity problem.

(Counting to infinity is just another name for a routing loop. In distance vector routing, routing loops usually occur when an interface goes down. It can also occur when two routers send updates to each other at the same time.)

Hence, as a solution Destination Sequenced Distance Vector Routing Protocol (DSDV) came into the existence.

Some important features of DSDV are as follows-

Destination Sequenced Distance Vector (DSDV) is a hop-by-hop vector routing protocol requiring each node to periodically broadcast routing updates.
This is a table-driven algorithm based on the Bellman-Ford routing mechanism.
Each node in the network maintains a routing table that has entries for each of the destinations in the network and the number of hops required to reach each of them.
Each entry has a sequence number associated with it that helps in identifying old entries.
This mechanism allows the protocol to avoid the formation of routing loops.
Each node periodically sends updates.
New route broadcasts contain the address of the destination, the number of hops to reach the destination, the sequence number of the information received regarding the destination, as well as a new sequence number unique to the broadcast.
The route labeled with the most recent sequence number is always used.
When the neighbors of the transmitting node receive this update, they recognize that they are one hop away from the source node and include this information in their distance vectors.
Every node stores the “next routing hop” for every reachable destination in their routing table.
The route used is the one with the highest sequence number i.e. the most recent one.
When a neighbor B of A finds out that A is no longer reachable, it advertises the route to A with an infinite metric and a sequence number one greater than the latest sequence number for the route forcing any nodes with B on the path to A, to reset their routing tables.

Example

Consider the network in the following figure shows the movement of node N1. Table 1 is the routing table at node N4 before node N1 moves.

Table 2 is the routing table updated for node N4 after node N1 moved.

Routing table updates in DSDV are distributed by two different types of update packets:

Global State Routing (GSR)

Global state routing is a pro-active/table-driven routing protocol.

Global state routing is the extension of the link-state routing protocol which is the protocol of wired networks.
It is based on Dijkstra’s routing algorithm.
Link state routing protocol was not suited for mobile ad-hoc networks because, in it, each node floods the link-state routing information directly into the whole network i.e.Global flooding which may lead to the congestion of control packets in the network.Hence, as a solution, Global State Routing Routing Protocol (GSR) came into existence.

Global State Routing is based on the concepts of link-state routing.
In Link State Routing(LSR), one of the node floods out a single routing table information to its neighbors and those neighbors floods out that table to further nodes.
This process continues until the routing table is received by all the nodes throughout the network.
But in case of Global State Routing, the routing table of a particular node is broadcast-ed to its immediate neighbors only.
Then initial tables of those neighboring nodes are updated.
These updated tables are further broadcasted one by one and this process remains continue until all the nodes broadcasts their tables to each node in the network.

Global State Routing Protocol Working

GSR broadcasts the routing tables to its immediate neighbors rather than flooding it to all the nodes as Link State Routing protocol does.
Consider a network of 4 nodes having a distance of “1” on each of its edges.
Below mentioned steps will let you know how GSR works and how its routing tables are updated.

Advantages: Global State Routing Protocol

Higher accuracy of GSR in generating optimal path as compared to Link State Routing (LSR).
Broadcasting reduces error rate as compare to flooding used in LSR.

Disadvantages: Global State Routing Protocol

Large bandwidth consumption.
Higher operational cost.
Large Message size resulting in more time consumption.

Reactive routing protocols

These are also known as an on-demand routing protocols.

In this routing, the route is discovered only when it is required.

The process of route discovery occurs by flooding the route request packets throughout the mobile network.

It consists of two major phases namely, route discovery and route maintenance.

Dynamic Source Routing protocol (DSR)

It is a reactive and on-demand routing protocol.

In this type of routing, the route is discovered only when it is needed.

The process of route discovery occurs by flooding the route request packets throughout the mobile network.

It consists of two phases:

Route Discovery:
This phase determines the most optimal path for the transmission of data packets between the source and the destination mobile nodes.

Route Maintenance:
This phase performs the maintenance work of the route as the topology in the mobile ad-hoc network is dynamic in nature and hence, there are many cases of link breakage resulting in the network failure between the mobile nodes.

Working of Dynamic Source Routing

When the source node wants to send a packet to a destination, it looks up its route cache to determine if it already contains a route to the destination.
If it finds , then it uses this route to send the packet.
But if the node does not have such a route, then it initiates the route discovery process by broadcasting a route request packet.
The route request packet contains the address of the source and the destination, and a unique identification number.
Each intermediate node checks whether it knows of a route to the destination.
If it does not, it appends its address to the route record of the packet and forwards the packet to its neighbors.
To limit the number of route requests propagated, a node processes the route request packet only if it has not already seen the packet and its address is not present in the route record of the packet.
A route reply is generated when either the destination or an intermediate node with current information about the destination receives the route request packet.

As the route request packet propagates through the network, the route record is formed as shown in figure a.
If the route reply is generated by the destination then it places the route record from route request packet into the route reply packet.
On the other hand, if the node generating the route reply is an intermediate node then it appends its cached route to the destination to the route record of the route request packet and puts that into the route reply packet.
Figure b shows the route reply packet being sent by the destination.
To send the route reply packet, the responding node must have a route to the source.If it has a route to the source in its route cache, it can use that route.
The reverse route record can be used if symmetric links are supported.
In case symmetric links are not supported, the node can initiate route discovery to source and piggyback the route reply on this new route request.

DSRP uses two types of packets for route maintenance:-

Route Error packet and
Acknowledgements.

When a node encounters a fatal transmission problem at its data link layer, it generates a Route Error packet.

When a node receives a route error packet, it removes the hop in error from its route cache.

Acknowledgment packets are used to verify the correct operation of the route links.

This also includes passive acknowledgments in which a node hears the next-hop forwarding the packet along the route.

Ad-Hoc On-Demand Vector Routing protocol (AODV)

It is a reactive/on-demand routing protocol.
It is an extension of dynamic source routing protocol (DSR) and it helps to remove the disadvantage of dynamic source routing protocol.
To find a path to the destination, the source broadcasts a route request packet.
The neighbors in turn broadcast the packet to their neighbors till it reaches an intermediate node that has recent route information about the destination or till it reaches the destination (Figure 4a).
A node discards a route request packet that it has already seen.
The route request packet uses sequence numbers to ensure that the routes are loop-free and to make sure that if the intermediate nodes reply to route requests, they reply with the latest information only.
When a node forwards a route request packet to its neighbors, it also records in its tables the node from which the first copy of the request came.
This information is used to construct the reverse path for the route reply packet.
AODV uses only symmetric links because the route reply packet follows the reverse path of route request packet.
As the route reply packet traverses back to the source (Figure b), the nodes along the path enter the forward route into their tables.

If the source moves then it can reinitiate route discovery to the destination.
If one of the intermediate nodes move then the moved node’s neighbor realizes the link failure and sends a link failure notification to its upstream neighbors and so on till it reaches the source upon which the source can reinitiate route discovery if needed.
In DSR, after route discovery, when the source mobile node sends the data packet to the destination mobile node, it also contains the complete path in its header.
Hence, as the network size increases, the length of the complete path also increases and the data packet’s header size also increases which makes the whole network slow.

Hence, Ad-Hoc On-Demand Vector Routing protocol came as a solution to it.

The main difference lies in the way of storing the path, AODV stores the path in the routing table whereas DSR stores it in the data packet’s heade.

It operates in two phases:

Route discovery and
Route maintenance

Hybrid Routing protocol

It basically combines the advantages of both, reactive and proactive routing protocols.

These protocols are adaptive in nature and adapts according to the zone and position of the source and destination mobile nodes.

One of the most popular hybrid routing protocol is Zone Routing Protocol (ZRP).

The whole network is divided into different zones and then the position of source and destination mobile node is observed.

If the source and destination mobile nodes are present in the same zone, then proactive routing is used for the transmission of the data packets between them.

And if the source and destination mobile nodes are present in different zones, then reactive routing is used for the transmission of the data packets between them.

Hybrid Protocol – Zone Routing Protocols

Hybrid protocols attempt to take advantage of the best of reactive and proactive schemes.

The basic idea behind such protocols is to initiate route discovery on demand but at a limited search cost.

One of the popular hybrid protocols is zone routing protocol (ZRP).

The zone routing protocol (ZRP)

The zone routing protocol is a hybrid of reactive and proactive protocols. It combines the advantage of both reactive and proactive schemes.
ZRP was invented by Zygmunt Haas of Cornell University.
Zone routing protocol is a loop-free routes to the destination.
ZRP divides the network into zones of variable size; the size of the zone determines radius of length.

The neighborhood of the local node is called a routing zone.
Specifically, a routing zone of the node is defined as the set of nodes whose minimum distance in hops from the node is no greater than the zone radius.
A node maintains routes to all the destinations proactively in the routing zone. It also maintains its zone radius, and the overlap from the neighboring routing zones.
To create a routing zone, the node must identify all its neighbors first which are one hop away and can be reached directly.
The Process of neighbor discovery is governed by the NDP (Neighbor Discovery Protocol), a MAC level scheme.
ZRP maintains the routing zones through a proactive component called the intra-zone routing protocol (IARP) and is implemented as a modified distance vector scheme.
Thus IARP is responsible for maintaining routes within the routing zone.
Another protocol called the inter-zone routing protocol (IERP) which is responsible for maintaining and discovering the routes to nodes beyond the routing zone.
This type of process uses a query-response mechanism on-demand basis. IERP is more efficient than standard flooding schemes.
When a source node send data to a destination which is not in the routing zone, the source initiates a route query packet.
The latter identified by the tuple <source node ID, request number>. This request is then broadcasted to all the nodes in the source nodes periphery.
When a node receives this query, it adds its own identification number (ID) to the query. Thus the sequence of recorded nodes presents a route from the current routing zone. Otherwise, if the destination is in the current routing zone of the node, a route reply is sent back to the source along the reverse from the accumulated record.
A big advantage of this scheme is that a single route request can result in multiple replies of route.

The source can determine the quality of these multiple routes based on such parameter as hop count or traffic and choose the best route to be used.

Temporary ordered routing algorithm (TORA)

TORA (Temporally Ordered Routing Algorithm) is a source initiated on-demand routing protocol.
It was invented by Vincent Park and M. Scott Corson from university of Maryland in 1997 for wireless ad hoc network.
TORA is a highly adaptive, efficient, loop-free and scalable routing protocol based on link reversal algorithm.
The main objective of TORA is to limit message propagation in the highly dynamic mobile computing environment. It means, it is designed to reduce communication overhead by adapting local topological changes in ad hoc network.
Another main feature of TORA routing protocol is the localization of control packets to a small region (set of nodes) near the occurrence of a topological changes due to route break. Hence, each node of the network required to contain its local routing and topology information about adjacent nodes.
TORA supports multiple routes to transmit data packet between source and destination nodes of mobile ad hoc network. In short, TORA exhibits multipath routing capability.
The TORA’s operation can be compared to that of water flowing downhill toward a sink node through a grid of tubes that model the routes in the real-world network.

The tube junctions represent the nodes, the tube themselves represent the route links between the nodes, the tube’s water represents the packets flowing between nodes through the route links toward the destination, as shown in the figure:

Considering the data flow to be downhill, each node has a height with respect to the destination node. The analogy also makes it easy to correct routes in case of link failure or error.
One of the biggest advantages of TORA is that it can operate smoothly in a highly dynamic mobile environment. It provides multiple paths for any source-destination pair. For this purpose, each node must maintain routing information about their one-hop neighbors.
TORA works in three main phases:
- Route creation: Route creation from source to destination.
- Route maintenance: Maintenance of the route.
- Route erasure: Erasing of the route when the route is no longer valid.
TORA attempts to build a separate directed acyclic graph (DAG) by each node to every destination. When a route to a particular destination is required, the source node broadcasts a QUERY packet containing the address of the destination. The route query propagates via the network till it reaches either the destination or an intermediate node containing the route to the destination.

Routing protocols – Mobile Ad hoc Networking