Highly Dynamic Destination-Sequenced Distance-Vector Routing

DSDV

This routing protocol was developed 1994 by C. Perkins and it is a proactive distance-vector protocol.

What were the design goals of DSDV?

• Keep the simplicity of Distributed Bellman-Ford
• Avoid the looping problem

How do they approach?

• Model each host as a router
• Tag each routing table entry with a sequence number

Here we see a model of such DSDV routing table. Naturally it contains all in the network existing destinations. The Next Hop informs what node is the first node for reaching the destination. The metric a supplement to the costs for routes, is an additional path description. There are even sequence numbers assigned by the destination for sending the next update.

Destination	Next Hop	Hops	Seq. No	Install Time
A	A	0	A-846	001000
B	B	1	B-470	001200
C	B	3	C-920	001500
D	B	4	D-502	001200

Transmitting Route Information

Routing information is transmitted by broadcast on the contrary to distributed Bellman-Ford algorithm. Updates have to be transmitted periodically or immediately when any significant topology change is available. Sequence numbers are assigned by destination, means the destination gives a sort of default even sequence number, and the emitter has to send out the next update with this number. If a broken link is detected, the metric -> ∞ and an updated with an odd sequence number is assigned by the detecting host.
There are two possibilities to update routing table:

• Full dump: all information from the transmitting node (whole routing table).
• Incremental dump: all information that has changed since the last full dump.

Selection of Routes

If new routing information is received, a route with a more recent sequence number is used. If the new route has equal sequence number but better metric, this route is chosen.

How can it be?
Receiving fluctuation routes can be explained with illustration 11.
MH9 broadcasts update information to MH Collection I and II. MH2 receives new routing information earlier than MH6, so transmits the information as update earlier to MH4. MH4 receives the routing information, compares sequence number then MH4’s routing table is updated and an update is send out. Now MH4 receives the same routing information from MH6 but with better metric. Result, MH4 updates its routing table again and sends again an update out.
Imaging this for about 1000 nodes it will obviously occurs much not needed overhead traffic.

Why Dumping Fluctuation?

Causes for Fluctuation:

• Many hosts with irregular updates
• Broadcasts are asynchronous events
• Different propagation speed
• Different transmission intervals.

Solution:
Keep a route settling time table in each node with a time to wait for a route with a better metric before advertising the update message. The settling time is calculated by maintaining a running weighted average over the most recent updates of the routes for each destination.

Stale entries

Stale entries are defined to be entries that have not been updated the last few update periods.
Stale entries are deleted at the same time when routing updates are applied to the routing table for the next time. Any route using that host as a next hop is deleted included the route indicating that host as the actual destination.

Example of DSDV in operation

Destination	Next Hop	Metric	Seq. No
MH4	MH4	0	S406_MH4
MH1	MH2	2	S128_MH1
MH2	MH2	1	S564_MH2
MH3	MH2	2	S710_MH3
MH5	MH6	2	S392_MH5
MH6	MH6	1	S076_MH6
MH7	MH6	2	S128_MH7
MH8	MH6	3	S050_MH8

After MH1 moves in the network from the neighboring of MH2 to MH7 and MH8.

1. We get a triggered update by MH1, broadcasted to MH7 and MH8.
2. On detection of broken link: Immediate incremental update triggered by MH2 with odd sequence number and infinite metric.
3. Updates are propagated through the network.

Destination	Next Hop	Metric	Seq. No
MH4	MH4	0	S516_MH4
MH1	MH6	3	S238_MH1
MH2	MH2	1	S674_MH2
MH3	MH2	2	S820_MH3
MH5	MH6	2	S502_MH5
MH6	MH6	1	S186_MH6
MH7	MH6	2	S238_MH7
MH8	MH6	3	S160_MH8

Example of eliminate looping and count-to-infinity problem

The Distributed Bellman-Ford has the looping and count-to-infinity problem.

Looping hazard if B -> C fails, then:

• the sequence number on B will be odd, and the metric ∞.
• A knows pass by B will not reach C.
• C generate a new even sequence number, then transmit to A, and A transmit to B, and B -> A -> C.

Stability and Scalability

DSDV requires a full dump update periodically, therefore DSDV is not efficient in route updating. DSDV limits the number of nodes that can join the network. Whenever topology of a network changes, DSDV is unstable until update packets propagate through the network.

Conclusions and Current Status

DSDV is effective for creating ad-hoc networks for small populations of mobile nodes.
DSDV is a well-known routing algorithm for ad-hoc network routing. Because of no standard specifications there are no commercial implementations available. Many improved protocols based on DSDV have been developed. Example: AODV: Ad-hoc On-Demand Distance Vector Routing.

References

[Peter2003] All Pictures
[Perkins1994] Original Paper
[Perkins1996]
[Perkins2001a]

"Highly Dynamic Destination-Sequenced Distance-Vector Routing" is mentioned on: Ad Hoc On-Demand Distance Vector Routing Protocol | Ad-Hoc Protocols (Classification) | Ad-Hoc Protocols (History) | Ad-Hoc Workshop Winter 04/05 (Termine) | Cluster-Head Gateway Switch Routing Protocol