Distination Source Distance Vector Routing :
This protocol is based on classical Bellman-Ford routing algorithm designed for
MANETS. Each node maintains a list of all destinations and number of hops to each
destination. Each entry is marked with a sequence number. It uses full dump or
incremental update to reduce network traffic generated by rout updates. The
broadcast of route updates is delayed by settling time. The only improvement made
here is avoidance of routing loops in a mobile network of routers. With this dsd
improvement, routing information can always be readily available, regardless of
whether the source node requires the information or not. DSDV solve the problem of
routing loops and count to infinity by associating each route entry with a sequence
number indicating its freshness. In DSDV, a sequence number is linked to a
destination node, and usually is originated by that node (the owner). The only case
that a non-owner node updates a sequence number of a route is when it detects a
link break on that route. An owner node always uses even-numbers as sequence
numbers, and a non-owner node always uses odd-numbers. With the addition of
sequence numbers, routes for the same destination are selected based on the
following rules: 1) a route with a newer sequence number is preferred; 2) in the case
that two routes have a same sequence number, the one with a better cost metric is
preferred. [4]
The list which is maintained is called routing table. The routing table contains the
following:
(1) All available destinations’ IP address
(2) Next hop IP address
(3) Number of hops to reach the destination
(4) Sequence number assigned by the destination node
(5) Install time
The sequence number is used to distinguish stale routes from new ones and thus
avoid the formation of loops. The stations periodically transmit their routing tables to 10
their immediate neighbors. A station also transmits its routing table if a significant
change has occurred in its table from the last update sent. So, the update is both
time-driven and event-driven.
As stated above one of “full dump" or an incremental update is used to send routing
table updates for reducing network traffic. A full dump sends the full routing table to
the neighbors and could span many packets whereas in an incremental update only
those entries from the routing table are sent that has a metric change since the last
update and it must fit in a packet. If there is space in the incremental update packet
then those entries may be included whose sequence number has changed. When
the network is relatively stable, incremental updates are sent to avoid extra traffic and
full dump are relatively infrequent. In a fast-changing network, incremental packets
can grow big so full dumps will be more frequent. [4]
Each route update packet, in addition to the routing table information, also contains a
unique sequence number assigned by the transmitter. The route labeled with the
highest (i.e. most recent) sequence number is used. If two routes have the same
sequence number then the route with the best metric (i.e. shortest route) is used.
Based on the past history, the stations estimate the settling time of routes. The
stations delay the transmission of a routing update by settling time so as to eliminate
those updates that would occur if a better route were found very soon.
Each row of the update send is of the following form:
<Destination IP address, Destination sequence number, Hop count>
After receiving an update neighboring nodes utilizes it to compute the routing table
entries.
To damp the routing fluctuations due to unsynchronized nature of periodic updates,
routing updates for a given destination can propagate along different paths at
different rates. To prevent a node from announcing a routing path change for a given
destination while another better update for that destination is still in route, DSDV 11
requires node to wait a settling time before announcing a new route with higher
metric for a destination.
2.2 Resolving failed links in DSDV
No comments:
Post a Comment