Each node knows the distance (cost) to each
of its directly connected neighbors. Hosts that are not directly connected or
if link is down, is assigned infinite cost.
Each
node constructs a vector containing (Destination, Cost, Next
Hop) to all other nodes and distributes to its neighbors.
Each
node computes a vector (table) of minimum distance (cost) to every other
node using the information from its neighbors.
Thus
the table at each node guides a packet to the desired node by showing the Next
Hop.
Initial State
For the given network, each node sets a distance of 1
(hops) to its immediate neighbors. The distance for non-neighbors is marked as unreachable
with value (infinity).
The initial routing table stored at A is
|
Destination
|
Cost
|
Next Hop
|
|
B
|
1
|
B
|
|
C
|
1
|
C
|
|
D
|
|
—
|
|
E
|
1
|
E
|
|
F
|
1
|
F
|
|
G
|
|
|
Sharing &
Updation
Each node shares its cost list (distance) to
all of its directly connected neighbors. Node A receives distance
vectors from B, C, E and F.
o For example the
tables received by
A from C and F are:
|
Destination
|
Cost
|
Next Hop
|
|
A
|
1
|
A
|
|
B
|
1
|
B
|
|
D
|
1
|
D
|
|
E
|
|
|
|
F
|
|
|
|
G
|
|
|
|
Destination
|
Cost
|
Next Hop
|
|
A
|
1
|
A
|
|
B
|
|
|
|
C
|
|
|
|
D
|
|
|
|
E
|
|
|
|
G
|
1
|
G
|
Now node A can use information from its
neighbors to reach other unreachable nodes. For example, node F
tells node A that it can reach node G at a cost of 1.
Each node updates its
routing table by comparing with its neighbor tables as follows
o
For each destination Total
Cost
is computed as:
Total Cost = Cost(Node, Neighbor)
+ Cost(Neighbor, Destination).
o
If Total Cost
< NodeCost(Destination) then
NodeCost(Destination) = Total
Cost and Next
Hop(Destination) = Neighbor
For example, A compares its table
with C's table
o
Total Cost for B = Cost(A,
B) + Cost(B, C) = 2 Since 2 > 1, there is no
change
o
Total Cost for D = Cost
(A, C) + Cost(C, D) = 1
+ 1 = 2.
Since 2 < , entry for
destination D in A's table is changed to (D, 2, C) o Similarly
other entries are checked and there is no change.
In a similar manner, A updates its routing
table using information from B, E and F. The final routing
table at A is
|
Destination
|
Cost
|
Next Hop
|
|
B
|
1
|
B
|
|
C
|
1
|
C
|
|
D
|
2
|
C
|
|
E
|
1
|
E
|
|
F
|
1
|
F
|
|
G
|
2
|
F
|
Each
node builds complete routing table after few exchanges with its neighbors.
The
process of obtaining complete routing information to all nodes is called convergence.
The sharing & updation process take place periodically and in case
of triggered update. Periodic updation is normally done every 30
seconds.
Triggered Update
A
node can test link status by using hello (control) packets.
Alternatively
a link or node failure is presumed, if it does not receive periodic updates
from its neighbor for a while.
This
forces the node to update its neighbors, neighbors update their
neighbors and so on. Assume that F detects that its link to G has
failed.
o F sets
its new distance to G as
and shares its table with A. o Node A updates
its distance to G as .
o Node A also
receives periodic update from C with
distance to G as 2. o Node A updates
its distance to G as
3 through C.
Loop Instability
Suppose
link from node A to E goes down.
A
advertises
a distance of in nity to E, meanwhile B and C advertise
a distance of 2 to E. o B using
information from
C, concludes that E can be reached
in 3 hops through
C. o B advertises this
to A, and A in turn updates C with a distance
of 4 hops to E.
o Now
node
C advertises
with a distance of 5 to E and
so on.
Thus the nodes update each other until cost to E
reaches a large number, say infinity. Thus convergence does not occur.
This problem is known as loop instability.
Solutions
Infinity is
redefined to a small number. Most implementations define 16
as
infinity. o Distance between any two nodes
should not exceed 15 hops.
o Thus
distance vector routing cannot be used in
large networks.
When a node updates its neighbors, it does not send
those routes it learned from each neighbor back to that neighbor. This is known
as split horizon.
o
For example, if B has the route
(E, 2, A) in its table, then it does not include the route (E, 2) in its update
to A.
o
Continued absence of route update
for a destination leads to deletion of its entry. In split horizon with
poison reverse, Node B can still advertise the value of (E, 2) to A,
but
with a warning message.
o
This approach delays the
convergence process and does not work well for large number of nodes.
