Adaptive Distance Vector Routing

ADV

Adaptive Distance Vector Routing Algorithm is a combined proactive and on-demnd type of protocol, called hybrid. The main characteristic is proactive, since routes are maintained all the time. The on-demand character is implemented by two key aspects:

• only routes to active receivers are maintained

• the frequency and size of routing updates to the current network conditions

The term Adaptive indicates that routes change dynamically as function of current state of network.

Distance Vector Routing (DVR) as basis protocol:
Each router maintains a routing table giving the distance from itself to all possible destinations. The routing tables consist of :

• Destination IP address

• Distance to destination

• Next node in the path

Table information is periodically broadcasted to the neighbor routers by each router who update their routing table entries (R. Bellman. Dynamic Programming. Princeton University Press, 1957).

==> Disadvantage: Routing-Loops


Improvement:
ADV starts with a DVR algorithm that uses sequence numbers to avoid long-lived loops. The route update and maintainment strategy of DVR is adoped. However, the routing table update frequency is adjusted to the traffic within the network and adjusted to the nodes mobility. Additionally, only routes to active routers are maintained. In this scenario, a node is an active receiver if it is the receiver of any currently active connection. A so-called receiver-flag in the routing table indicates if the destination is an active receiver.

Connection Construction

At the beginning of a new connection the source floods the network with a init-connection control packet advertising that its destination node is an active receiver. The target destination node upon receiving the init-connection packet responds, if it not an active receiver already by broadcasting network-wide a receiver-alert packet. By this technique, all node will get the information about an active receiver and the routes to it immediately.
In order to terminate the connection, the source floods the network with an end-connection control packet. Then the nodes turn off the corresponding receiver-flag in their routing tables and routes to this node are not advertised in the future updates.

Routing Updates

The following table represents the structure of a routing update entry.

While performing a full update a node includes all the entries of the active receivers. In a partial update, only those entries of active receivers are included which have been updated since the last update. Sequence numbers are used in a similar context as in the DSDV protocol except that every update (full and partial) results in a new higher sequnce number.
The expected response value in each update entry essentially determines the priority with which a neighbor, receiving this update, should respond to the advertised need for a fresh route.

Unlike in other DV-based protocols, a node in ADV does not trigger an update whenever it sees a chance in the metric for a routing entry. Only an advertised need by the neighbor or the need for forwarding nodes to keep the routes fresh can trigger an update.
On the other hand in on-demand protocols, the need for a fresh valid route to an active receiver will immediately result in a route discovery process and the intermadiate nodes rebroadcast the request directly if the route to the receiver is unavailable. Also as the route replies are sent as unicasts, they reach the intended source nodes reliably. In ADV fresh and valid routes can only be obtained from neighbor updates.

Advantages

• better performance compared to AODV and DSR

• The connection-initiation and connection-termination processes that are used once for each connetion, will help in varying the number of active connections open.

Disadvantages

• Obtaining a valid route could take long time in ADV

References

[Bop2001] Original Paper






"Adaptive Distance Vector Routing" is mentioned on: Ad-Hoc Protocols (Classification)