distance vector routing

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.