Monday, 1 September 2008

Ad-hoc network and Pro-active Routing Protocal Part2 : Destination-Sequenced Distance-Vector Routing (DSDV)

Ad-hoc network and Pro-active Routing Protocal Part1: AWDS and Babel.

Type of protocols
Pro-active Routing (Table-driven)
This protocols maintains fresh lists of destinations and their routes by periodically distributing routing tables throughout the network. The main disadvantages of such algorithms are -

1. Respective amount of data for maintenance.
2. Slow reaction on restructuring and failures.

Examples of proactive algorithms are (con.)-
C).Destination-Sequenced Distance-Vector Routing (DSDV) is a table-driven routing scheme for ad hoc mobile networks based on the Bellman-Ford algorithm. It was developed by C. Perkins and P.Bhagwat in 1994. The main contribution of the algorithm was to solve the Routing Loop problem. Each entry in the routing table contains a sequence number, the sequence numbers are generally even if a link is present; else, an odd number is used. The number is generated by the destination, and the emitter needs to send out the next update with this number. Routing information is distributed between nodes by sending full dumps infrequently and smaller incremental updates more frequently.

For example the routing table of Node A in this network is
Destination Next Hop Number of Hops Sequence Number Install Time
A A 0 A 46 001000
B B 1 B 36 001200
C B 2 B 28 001500

Naturally the table contains description of all possible paths reachable by node A, along with the next hop, number of hops and sequence number.

Selection of Route
If a router receives new information, then it uses the latest sequence number. If the sequence number is the same as the one already in the table, the route with the better metric is used. Stale entries are those entries that have not been updated for a while. Such entries as well as the routes using those nodes as next hops are deleted.

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. Many improved forms of this algorithm have been suggested.

1. 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.
2. 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. (As in all distance-vector protocols, this does not perturb traffic in regions of the network that are not concerned by the topology change.)

While DSDV itself does not appear to be much used today[citation needed], other protocols have used similar techniques. The best-known sequenced distance vector protocol is AODV, which, by virtue of being a reactive protocol, can use simpler sequencing heuristics. Babel is an attempt at making DSDV more robust and more efficient within the framework of proactive protocols.

1.Perkins, Charles E. and Bhagwat, Pravin (1994). "Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers" (pdf). Retrieved on 2006-10-20.
3..Securing the Destination-Sequenced Distance Vector Routing Protocol (S-DSDV)

Additional Research : Securing
1.Securing the Destination-Sequenced Distance Vector Routing Protocol (S-DSDV)
propose : a secure routing protocol based on DSDV, namely S-DSDV, in which, a well-behaved node can successfully detect a malicious routing update with any sequence number fraud (larger or smaller) and any distance fraud (shorter, same, or longer) provided no two nodes are in collusion.
compare : security properties and efficiency of S-DSDV with superSEAD. Our efficiency analysis shows that S-DSDV generates high network overhead, however, which can be reduced by configurable parameters.
believe : the S-DSDV overhead is justified by the enhanced security.

No comments: