Destination-Sequenced Distance Vector Routing (DSDV)
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 modifications made to 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 stale entries. This mechanism allows the protocol to avoid the formation of routing loops. Each node periodically sends updates tagged throughout the network with a monotonically increasing even sequence number to advertise its location. 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.
Consider the network in Figure 1 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:
- Full dump: This type of update packet contains all the routing information available at a node. As a consequence, it may require several Network Protocol Data Units (NPDUs) to be transferred if the routing table is large. Full dump packets are transmitted infrequently if the node only experiences occasional movement.
- Incremental: This type of update packet contains only the information that has changed since the latest full dump was sent out by the node. Hence, incremental packets only consume a fraction of the network resources compared to a full dump.
Figure 1. A network illustrating the movement of node N1