Proactive Routing Protocols

Routing implies to the best path selection among all the available possible paths from transmitter to receiver. Protocols are the rules or regulations. In this way, routing protocols are set of rules to select a best path among all the available paths from source to destination. Before going into details of routing in Ad hoc network, let’s discuss basics of link state and distance vector routing protocols.

• Distance Vector Routing

• Link State Routing

Distance Vector Routing Protocol: 

In this routing protocol, each node maintains a metric called distance and the destination address. Let us take an example of three nodes, A,  B and C.

In above figure, let's us focus on the first table maintained by node A. The first column of this table shows the destination addresses/ identifications.

Likewise, the next column shows the next node (hop) to reach that destination and the third column indicates the metric to reach that destination. (Metric in our case is the distance in terms of number of hops). In the same way, the initial routing tables are shown  in the figure above for node B and C.

Let’s say that there is some change at node B, that is the metric between node B to node C has been changed from 2 to 1.  To let others nodes know about this change, node B sends new information to node A and node C.

After some time, a new MH, D enters the Ad hoc network and its routing table is shared with rest of the nodes i.e., A, B and C. The following figure shows the exchange of updated routing table entries among the nodes.

After some successful exchanges of messages, say, due to some problems, node D becomes inactive and as can be seen that only node C can detect this. The rule is that if a node goes down the neighboring node mentions it in their routing table as an unreachable node by setting its value to infinity. Following this rule node C sets the distance to D as infinity as depicted as in following figure. 

However, node B does not have this information and it broadcast its routing table to C telling him that D is still reachable.

In this way, at later stage node C sends the same information back to node B and this situation prevails. After some time, the routing table at A will be as given below.

As can be seen it will go to infinity, in simple words, C will keep sending the information to B that D is reachable through it that is node C. In the same way, B will also do the same; it will be sending information to C that D is reachable by it that is by node B. Ultimately, the distance to node D will reach infinity. 

Due to this loop, count to infinity problem occurs in the network. Count to infinity implies to the distance to a node which actually does not exist in the network. To solve this problem in Ad hoc network, various variations are suggested which are discussed below. Some of the well known protocols are listed below.

• Destination-Sequenced Distance-Vector Protocol

• The Wireless Routing Protocol

• The Topology Broadcast based on Reverse Path Forwarding Protocol

• The Optimized Link State Routing Protocol

• The Source Tree Adaptive Routing Protocol

Destination-Sequenced Distance-Vector Protocol: 

This protocol is based on Distributed Bellman-Ford algorithm. This is also referred as RIP (Routing Information Protocol). In this protocol, every node of Ad hoc network maintains following information in its routing table.

• All available destinations

• The next node to reach to destination

• The number of hops to reach the destination

In DSDV routing protocols, each node in the network maintains a routing table.

Every node periodically sends routing information to its neighboring nodes even when there is no change. Change means there is no failure of any node or  there is no movement of any node.

The routing information exchanged between nodes is shown in the following table.

First column shows the destination address, next column is the next MH to reach the destination, the third column shows the distance to the destination. Fourth column shows the sequence number which indicates the newness of the routing information received from the surrounding nodes. Final column is the install time of routing information into its own table.

Destination	Next	Metric	Seq. Nr	Install Time
A	A	0	A-550	001000
B	B	1	B-102	001200
C	B	3	C-588	001200
D	B	4	D-312	001200

In this protocol, count to infinity problem is solved by using destination sequence number. Every time a node wants to advertise it routing table, it adds 1 to its sequence number and broadcasts its routing table. If a node fails, the adjacent node increase its sequence number and set hop count to that node as infinity and advertises this. 

The Wireless Routing Protocol:

The Wireless Routing Protocol is proactive and table driven protocol. Every node in the network sends an update message and receive acknowledgment message from all other nodes in the network. Nodes maintain shortest path spanning tree depending upon the update message from its neighbor nodes.

An update message has:

• The destination address
• The distance to destination
• Information about node at second-to-last hop (Predecessor)

A null update message is sent every now and then to assure connectivity. In case when a node does not respond for some specific interval of time then a special HELLO message is sent to get the updated information from that node.

These are the four tables stored in every node of Ad hoc network.

• Distance
• Routing
• Link-cost
• Message Retransmission List (MRL) tables

                                     (Each entry in MRL contains the sequence number of the update message)

Each node sends distance and second-to-last hop information to every node in the network. The routing table at each node stores address to destination, distance to destination, predecessor to destination and successor to destination. Successor is the next hop neighbor to the destination.

Let’s take an example for understanding:

In the above example, node A has been taken as a source node where the above routing table is saved. It shows, for instance, destination node E which is reachable with cost 3 and its predecessor node C and successor node is B, depicted as follows.

There are two options to go from A from E.

A→C→D (but the cost will be 11)

A→B→C→D (but the cost will be 3) 

Therefore, option 2 is selected and is shown in the table.

In case a link fails:

The scenario of any link in the network fails can be best understood by following example where link 1 which connects node A to node B fails.

The following sequence of events occurs after link-1 fails.

Node A will be notified about this failure.

Let us take a single destination – for instance Node X fails.

• Node A will change the distance to X as infinity.  Predecessor and Successor will change to “null”.
• This information will be sent to Node C.
• C will update its routing table with new path to A by means of link 2.
• This update is then broadcast to A.
• Node A then computes new routing information via C

The updated routing Table at node A is shown in the following table.

The main difference between DSDV and WRP is that the first uses full dump or incremental packets for route updates and the later uses HELLO messages. In addition, they both use different number of routing tables.

Topology Broadcast based on Reverse Path Forwarding Protocol (TBRPFP)

TBRPFP uses broadcasting topology information to all nodes in the network. Topology information includes link costs and up/down status. Each link-state update is sent on every link of the network though flooding

Flooding refers to forwarding to every node except the one from which received as depicted below.

Spanning Tree:

Spanning tree is a graph of mobile nodes in an Ad hoc network where all nodes are connected with minimum number of paths between them and without any cycle.

Communication cost of broadcasting topology can be reduced if updates are sent along spanning trees. In TBRPFP, messages generated by a given source are broadcast in the reverse direction along the directed spanning tree formed by the shortest paths from all MHs (nodes) to the source.

Each node i selects a next node Pi(v) along the shortest path between i  and destination v.

As in above example, TBRPFP uses spanning tree for forwarding packets, instead of simple flooding because in flooding packet is broadcast to all connected nodes and hence increases the packet traffic. In this way, control traffic is also reduced required for flooding.

The Optimized Link State Routing Protocol:

This is proactive and link state routing protocol which as opposed to flooding uses only selected nodes called multipoint relays to send its message to all nodes in the network.

It also saves bandwidth by reducing the bandwidth of control messages. Every control message has a sequence number; therefore, in order delivery of packets at destination is not needed. Routing of messages is performed in hop by hope mode.

Multi Point Relays (MPR): In flooding every node broadcasts therefore traffic in the network become very heavy. To solve it, only selected nodes are used to forward those packets. These nodes are called multipoint relays. Every node in the network selects its MPR from its neighboring nodes which are one hop away such that they can cover all the nodes which are two hops away.