Distance Vector Routing Example-
Consider-
There is a network consisting of 4 routers.
The weights are mentioned on the edges.
Weights could be distances or costs or delays.
Step-01:
Each router prepares its routing table using its local knowledge.
Routing table prepared by each router is shown below-
At Router A-
Destination Distance Next Hop
A 0 A
B 2 B
C ∞ –
D 1 D
At Router B-
Destination Distance Next Hop
A 2 A
B 0 B
C 3 C
D 7 D
At Router C-
Destination Distance Next Hop
A ∞ –
B 3 B
C 0 C
D 11 D
At Router D-
Destination Distance Next Hop
A 1 A
B 7 B
C 11 C
D 0 D
Step-02:
Each router exchanges its distance vector obtained in Step-01 with its neighbors.
After exchanging the distance vectors, each router prepares a new routing table.
This is shown below-
At Router A-
Router A receives distance vectors from its neighbors B and D.
Router A prepares a new routing table as-
Cost of reaching destination B from router A = min { 2+0 , 1+7 } = 2 via B.
Cost of reaching destination C from router A = min { 2+3 , 1+11 } = 5 via B.
Cost of reaching destination D from router A = min { 2+7 , 1+0 } = 1 via D.
Explanation For Destination B
Router A can reach the destination router B via its neighbor B or neighbor D.
It chooses the path which gives the minimum cost.
Cost of reaching router B from router A via neighbor B = Cost (A→B) + Cost (B→B)= 2 + 0 =
2
Cost of reaching router B from router A via neighbor D = Cost (A→D) + Cost (D→B) = 1 + 7 =
8
Since the cost is minimum via neighbor B, so router A chooses the path via B.
It creates an entry (2, B) for destination B in its new routing table.
Similarly, we calculate the shortest path distance to each destination router at every router.
Thus, the new routing table at router A is-
Destination Distance Next Hop
A 0 A
B 2 B
C 5 B
D 1 D
At Router B-
Router B receives distance vectors from its neighbors A, C and D.
Router B prepares a new routing table as-
Cost of reaching destination A from router B = min { 2+0 , 3+∞ , 7+1 } = 2 via A.
Cost of reaching destination C from router B = min { 2+∞ , 3+0 , 7+11 } = 3 via C.
Cost of reaching destination D from router B = min { 2+1 , 3+11 , 7+0 } = 3 via A.
Thus, the new routing table at router B is-
Destination Distance Next Hop
A 2 A
B 0 B
C 3 C
D 3 A
At Router C-
Router C receives distance vectors from its neighbors B and D.
Router C prepares a new routing table as-
Cost of reaching destination A from router C = min { 3+2 , 11+1 } = 5 via B.
Cost of reaching destination B from router C = min { 3+0 , 11+7 } = 3 via B.
Cost of reaching destination D from router C = min { 3+7 , 11+0 } = 10 via B.
Thus, the new routing table at router C is-
Destination Distance Next Hop
A 5 B
B 3 B
C 0 C
D 10 B
At Router D-
Router D receives distance vectors from its neighbors A, B and C.
Router D prepares a new routing table as-
Cost of reaching destination A from router D = min { 1+0 , 7+2 , 11+∞ } = 1 via A.
Cost of reaching destination B from router D = min { 1+2 , 7+0 , 11+3 } = 3 via A.
Cost of reaching destination C from router D = min { 1+∞ , 7+3 , 11+0 } = 10 via B.
Thus, the new routing table at router D is-
Destination Distance Next Hop
A 1 A
B 3 A
C 10 B
D 0 D
Step-03:
Each router exchanges its distance vector obtained in Step-02 with its neighboring
routers.
After exchanging the distance vectors, each router prepares a new routing table.
This is shown below-
At Router A-
Router A receives distance vectors from its neighbors B and D.
Router A prepares a new routing table as-
Cost of reaching destination B from router A = min { 2+0 , 1+3 } = 2 via B.
Cost of reaching destination C from router A = min { 2+3 , 1+10 } = 5 via B.
Cost of reaching destination D from router A = min { 2+3 , 1+0 } = 1 via D.
Thus, the new routing table at router A is-
Destination Distance Next Hop
A 0 A
B 2 B
C 5 B
D 1 D
At Router B-
Router B receives distance vectors from its neighbors A, C and D.
Router B prepares a new routing table as-
Cost of reaching destination A from router B = min { 2+0 , 3+5 , 3+1 } = 2 via A.
Cost of reaching destination C from router B = min { 2+5 , 3+0 , 3+10 } = 3 via C.
Cost of reaching destination D from router B = min { 2+1 , 3+10 , 3+0 } = 3 via A.
Thus, the new routing table at router B is-
Destination Distance Next Hop
A 2 A
B 0 B
C 3 C
D 3 A
At Router C-
Router C receives distance vectors from its neighbors B and D.
Router C prepares a new routing table as-
Cost of reaching destination A from router C = min { 3+2 , 10+1 } = 5 via B.
Cost of reaching destination B from router C = min { 3+0 , 10+3 } = 3 via B.
Cost of reaching destination D from router C = min { 3+3 , 10+0 } = 6 via B.
Thus, the new routing table at router C is-
Destination Distance Next Hop
A 5 B
B 3 B
C 0 C
D 6 B
At Router D-
Router D receives distance vectors from its neighbors A, B and C.
Router D prepares a new routing table as-
Cost of reaching destination A from router D = min { 1+0 , 3+2 , 10+5 } = 1 via A.
Cost of reaching destination B from router D = min { 1+2 , 3+0 , 10+3 } = 3 via A.
Cost of reaching destination C from router D = min { 1+5 , 3+3 , 10+0 } = 6 via A.
Thus, the new routing table at router D is-
Destination Distance Next Hop
A 1 A
B 3 A
C 6 A
D 0 D
These will be the final routing tables at each router.
Identifying Unused Links-
After routing tables converge (becomes stable),
Some of the links connecting the routers may never be used.
In the above example, we can identify the unused links as-
We have-
The value of next hop in the final routing table of router A suggests that only edges AB
and AD are used.
The value of next hop in the final routing table of router B suggests that only edges BA
and BC are used.
The value of next hop in the final routing table of router C suggests that only edge CB
is used.
The value of next hop in the final routing table of router D suggests that only edge DA
is used.