Destination Sequenced Distance Vector (DSDV): Algorithm, Illustration, Advantages, Disadvantages

DESTINATION SEQUENCED DISTANCE VECTOR (DSDV)

DSDV was one of the first proactive routing protocols available for Ad Hoc networks. It was developed by C. Perkins in 1994, 5 years before the informational RFC of the MANET group. It has not been standardised by any regulation authorities but is still a reference.

Algorithm

DSDV is based on the Bellman-Ford algorithm.

With DSDV, each routing table will contain all available destinations, with the associated next hop, the associated metric (numbers of hops), and a sequence number originated by the destination node.

Tables are updated in the topology per exchange between nodes.

Each node will broadcast to its neighbors entries in its table. This exchange of entries can be made by dumping the whole routing table, or by performing an incremental update, that means exchanging just recently updated routes.

Nodes who receive this data can then update their tables if they received a better route, or a new one.

Updates are performed on a regular basis, and are instantly scheduled if a new event is detected in the topology.

If there are frequent changes in topology, full table exchange will be preferred whereas in a stable topology, incremental updates will cause less traffic.

The route selection is performed on the metric and sequence number criteria. The sequence number is a time indication sent by the destination node. It allows the table update process, as if two identical routes are known, the one with the best sequence number is kept and used, while the other is destroyed (considered as a stale entry).

Illustration

Let us consider the two following topologies (figure 1 and figure 2). At t=0, the network is organized as shows figure 1. We suppose at this time the network is stable, each node has a correct routing table of all destinations.

Then, we suppose G is moving, and at t+1, the topology is as shown in figure 2.

At this stage, the following events are detected, and actions are taken:

 On node C: Link with G is broken, the route entry is deleted, and updates are sent to node D.

 On node A and F: A new link is detected, the new entry is added to the routing table and updates are sent to neighbors.

On node G: Two new links are detected (to A and F), and one is broken (to C), the routing table is updated and a full dump is sent to neighbors (as the routing table is entirely changed, a full dump equals an incremental update).

Advantages

DSDV was one of the early algorithms available. It is quite suitable for creating ad hoc

networks with small number of nodes. Since no formal specification of this algorithm is present there is no commercial implementation of this algorithm.  

DSDV guarantees for loop free path.

Disadvantages

DSDV requires a regular update of its routing tables, which uses up battery power and a

                            small amount of bandwidth even when the network is idle.  

Whenever the topology of the network changes, a new sequence number is necessary before the network re-converges; thus, DSDV is not suitable for highly dynamic networks.