$\textbf{Distance Vector Routing Algorithm:-}$ Distance Vector Routing is a dynamic routing algorithm.
It works in the following steps:
$\textbf{Step 1:}$ Each router prepares its routing table. By their local knowledge each router knows about-
- All the routers present in the network.
- Distance to its neighboring routers.
$\textbf{Step 2:}$
- Each router exchanges its distance vector with its neighboring routers.
- Each router prepares a new routing table using the distance vectors it has obtained from its neighbors.
- This step is repeated for $(n-2)$ times if there are n routers in the network.
- After this, routing tables converge / become stable.
Now, coming to the question.
$\textbf{Step 1:}$ Each router prepares its routing table using its local knowledge.
Routing table prepared by each router is shown below-
$\textbf{At router A:}$
$$\overset{\textbf{Routing Table of A}}{\begin{array}{|c|c|c|}\hline
\textbf{Destination} & \textbf{Distance} & \textbf{Next Hop} \\\hline
\text{A}& 0 & A \\\hline
\text{B}& 4 & B \\\hline
\text{C}& \infty & - \\\hline
\text{D}& 3 & D \\\hline
\end{array}}$$
$\textbf{At router B:}$
$$\overset{\textbf{Routing Table of B}}{\begin{array}{|c|c|c|}\hline
\textbf{Destination} & \textbf{Distance} & \textbf{Next Hop} \\\hline
\text{A}& 4 & A \\\hline
\text{B}& 0 & B \\\hline
\text{C}& 5 & C \\\hline
\text{D}& 9 & D \\\hline
\end{array}}$$
$\textbf{At router C:}$
$$\overset{\textbf{Routing Table of C}}{\begin{array}{|c|c|c|}\hline
\textbf{Destination} & \textbf{Distance} & \textbf{Next Hop} \\\hline
\text{A}& \infty & - \\\hline
\text{B}& 5 & B \\\hline
\text{C}& 0 & C \\\hline
\text{D}& 13 & D \\\hline
\end{array}}$$
$\textbf{At router D:}$
$$\overset{\textbf{Routing Table of D}}{\begin{array}{|c|c|c|}\hline
\textbf{Destination} & \textbf{Distance} & \textbf{Next Hop} \\\hline
\text{A}& 3 & A \\\hline
\text{B}& 9 & B \\\hline
\text{C}& 13 & C \\\hline
\text{D}& 0 & D \\\hline
\end{array}}$$
$\textbf{Step 2:}$
- Each router exchanges its distance vector obtained in Step $1$ with its neighbors.
- After exchanging the distance vectors, each router prepares a new routing table.
This is shown below-
$\textbf{At Router A:}$
- Router $A$ receives distance vectors from its neighbors $B$ and $D.$
- Router $A$ prepares a new routing table as
$$\overset{\textbf{From B}}{\begin{array}{|c|c|c|}\hline
4 \\\hline
0 \\\hline
5 \\\hline
9 \\\hline
\end{array}} \text{Cost}(A \rightarrow B) = 4 \qquad \overset{\textbf{From D}}{\begin{array}{|c|c|c|}\hline
3 \\\hline
9 \\\hline
13 \\\hline
0 \\\hline
\end{array}} \text{Cost}(A \rightarrow D) = 3$$
- Cost of reaching destination $B$ from router $A = \text{min} \{ 4 + 0 , 3 + 9 \} = 4\; \text{via}\; B.$
- Cost of reaching destination $C$ from router $A = \text{min} \{4 + 5 , 3 + 13 \} = 9 \;\text{via}\; B.$
- Cost of reaching destination $D$ from router $A = \text{min} \{ 4 + 9 , 3 + 0 \} = 3\;\text{via}\; D.$
Thus, the new routing table at router $A$ is-
$$\overset{\textbf{Routing Table of A}}{\begin{array}{|c|c|c|}\hline
\textbf{Destination} & \textbf{Distance} & \textbf{Next Hop} \\\hline
\text{A}& 0 & A \\\hline
\text{B}& 4 & B \\\hline
\text{C}& 9 & B \\\hline
\text{D}& 3 & D \\\hline
\end{array}}$$
$\textbf{At Router B:}$
- Router B receives distance vectors from its neighbors $A, C\;\text{and}\; D.$
- Router $B$ prepares a new routing table as-
$$\overset{\textbf{From A}}{\begin{array}{|c|c|c|}\hline
0 \\\hline
4 \\\hline
\infty \\\hline
3 \\\hline
\end{array}} \text{Cost}(B \rightarrow A) = 4 \qquad \overset{\textbf{From C}}{\begin{array}{|c|c|c|}\hline
\infty \\\hline
5 \\\hline
0 \\\hline
13 \\\hline
\end{array}} \text{Cost}(B \rightarrow C) = 5\qquad \overset{\textbf{From D}}{\begin{array}{|c|c|c|}\hline
3 \\\hline
9 \\\hline
13 \\\hline
0 \\\hline
\end{array}} \text{Cost}(B \rightarrow D) = 9$$
- Cost of reaching destination $A$ from router $B = \text{min} \{ 4 + 0 , 5 + \infty , 9 + 3 \} = 4\; \text{via}\; A.$
- Cost of reaching destination $C$ from router $B = \text{min} \{4 + \infty, 5 + 0, 9 + 13 \} = 5 \;\text{via}\; C.$
- Cost of reaching destination $D$ from router $B = \text{min} \{4 + 3 , 5 + 13 , 9 + 0 \} = 7 \;\text{via}\; A.$
Thus, the new routing table at router $B$ is-
$$\overset{\textbf{Routing Table of B}}{\begin{array}{|c|c|c|}\hline
\textbf{Destination} & \textbf{Distance} & \textbf{Next Hop} \\\hline
\text{A}& 4 & A \\\hline
\text{B}& 0 & B \\\hline
\text{C}& 5 & C \\\hline
\text{D}& 7 & A \\\hline
\end{array}}$$
$\textbf{At Router C:}$
- Router $C$ receives distance vectors from its neighbors $B$ and $C$.
- Router $C$ prepares a new routing table as
$$\overset{\textbf{From B}}{\begin{array}{|c|c|c|}\hline
4 \\\hline
0 \\\hline
5 \\\hline
9 \\\hline
\end{array}} \text{Cost}(C \rightarrow B) = 5 \qquad \overset{\textbf{From D}}{\begin{array}{|c|c|c|}\hline
3 \\\hline
9 \\\hline
13 \\\hline
0 \\\hline
\end{array}} \text{Cost}(C \rightarrow D) = 13$$
- Cost of reaching destination $A$ from router $C = \text{min} \{ 5 + 4 , 13 + 3 \} = 9\;\text{via}\; B.$
- Cost of reaching destination $B$ from router $C = \text{min} \{ 5 + 0 , 13 + 9 \} = 5 \;\text{via}\;B.$
- Cost of reaching destination $D$ from router $C = \text{min} \{ 5 + 9 , 13 + 0 \} = 13 \;\text{via}\; D.$
Thus, the new routing table at router $C$ is-
$$\overset{\textbf{Routing Table of C}}{\begin{array}{|c|c|c|}\hline
\textbf{Destination} & \textbf{Distance} & \textbf{Next Hop} \\\hline
\text{A}& 9 & B \\\hline
\text{B}& 5 & B \\\hline
\text{C}& 0 & C \\\hline
\text{D}& 13 & D \\\hline
\end{array}}$$
$\textbf{At Router D:}$
- Router $D$ receives distance vectors from its neighbors $A, B\;\text{and}\; C.$
- Router $D$ prepares a new routing table as-
$$\overset{\textbf{From A}}{\begin{array}{|c|c|c|}\hline
0 \\\hline
4 \\\hline
\infty \\\hline
3 \\\hline
\end{array}} \text{Cost}(D \rightarrow A) = 3 \qquad \overset{\textbf{From B}}{\begin{array}{|c|c|c|}\hline
4 \\\hline
0 \\\hline
5 \\\hline
9 \\\hline
\end{array}} \text{Cost}(D \rightarrow B) = 9 \qquad \overset{\textbf{From C}}{\begin{array}{|c|c|c|}\hline
\infty \\\hline
5 \\\hline
0 \\\hline
13 \\\hline
\end{array}} \text{Cost}(D \rightarrow C) = 13 $$
- Cost of reaching destination $A$ from router $D = \text{min} \{ 3 + 0 , 9 + 4 , 13 + \infty \} = 3 \; \text{via}\; A.$
- Cost of reaching destination $B$ from router $D = \text{min} \{3 + 4 , 9 + 0 , 13 + 5 \} = 7 \;\text{via}\; A.$
- Cost of reaching destination $C$ from router $D = \text{min} \{3 + \infty, 9 + 5 , 13 + 0 \} = 13 \;\text{via}\; C.$
Thus, the new routing table at router $D$ is-
$$\overset{\textbf{Routing Table of D}}{\begin{array}{|c|c|c|}\hline
\textbf{Destination} & \textbf{Distance} & \textbf{Next Hop} \\\hline
\text{A}& 3 & A \\\hline
\text{B}& 7 & A \\\hline
\text{C}& 13 & C \\\hline
\text{D}& 0 & D \\\hline
\end{array}}$$
$\textbf{Step 3:}$
- Each router exchanges its distance vector obtained in Step $2$ with its neighboring routers.
- After exchanging the distance vectors, each router prepares a new routing table.
This is shown below:
$\textbf{At Router A:}$
- Router $A$ receives distance vectors from its neighbors $B$ and $D.$
- Router $A$ prepares a new routing table as
$$\overset{\textbf{From B}}{\begin{array}{|c|c|c|}\hline
4 \\\hline
0 \\\hline
5 \\\hline
7 \\\hline
\end{array}} \text{Cost}(A \rightarrow B) = 4 \qquad \overset{\textbf{From D}}{\begin{array}{|c|c|c|}\hline
3 \\\hline
7 \\\hline
13 \\\hline
0 \\\hline
\end{array}} \text{Cost}(A \rightarrow D) = 3$$
- Cost of reaching destination $B$ from router $A = \text{min} \{ 4 + 0 , 3 + 7 \} = 4\; \text{via}\; B.$
- Cost of reaching destination $C$ from router $A = \text{min} \{4 + 5 , 3 + 13 \} = 9 \;\text{via}\; B.$
- Cost of reaching destination $D$ from router $A = \text{min} \{ 4 + 7 , 3 + 0 \} = 3\;\text{via}\; D.$
Thus, the new routing table at router $A$ is
$$\overset{\textbf{Routing Table of A}}{\begin{array}{|c|c|c|}\hline
\textbf{Destination} & \textbf{Distance} & \textbf{Next Hop} \\\hline
\text{A}& 0 & A \\\hline
\text{B}& 4 & B \\\hline
\text{C}& 9 & B \\\hline
\text{D}& 3 & D \\\hline
\end{array}}$$
$\textbf{At Router B:}$
- Router B receives distance vectors from its neighbors $A, C\;\text{and}\; D.$
- Router $B$ prepares a new routing table as-
$$\overset{\textbf{From A}}{\begin{array}{|c|c|c|}\hline
0 \\\hline
4 \\\hline
9 \\\hline
3 \\\hline
\end{array}} \text{Cost}(B \rightarrow A) = 4 \qquad \overset{\textbf{From C}}{\begin{array}{|c|c|c|}\hline
9 \\\hline
5 \\\hline
0 \\\hline
13 \\\hline
\end{array}} \text{Cost}(B \rightarrow C) = 5\qquad \overset{\textbf{From D}}{\begin{array}{|c|c|c|}\hline
3 \\\hline
7 \\\hline
13 \\\hline
0 \\\hline
\end{array}} \text{Cost}(B \rightarrow D) = 7$$
- Cost of reaching destination $A$ from router $B = \text{min} \{ 4 + 0 , 5 + 9 , 7 + 3 \} = 4\; \text{via}\; A.$
- Cost of reaching destination $C$ from router $B = \text{min} \{4 + 9, 5 + 0, 7 + 13 \} = 5 \;\text{via}\; C.$
- Cost of reaching destination $D$ from router $B = \text{min} \{4 + 3 , 5 + 13 , 7 + 0 \} = 7 \;\text{via}\; A.$
Thus, the new routing table at router $B$ is
$$\overset{\textbf{Routing Table of B}}{\begin{array}{|c|c|c|}\hline
\textbf{Destination} & \textbf{Distance} & \textbf{Next Hop} \\\hline
\text{A}& 4 & A \\\hline
\text{B}& 0 & B \\\hline
\text{C}& 5 & C \\\hline
\text{D}& 7 & A \\\hline
\end{array}}$$
$\textbf{At Router C:}$
- Router $C$ receives distance vectors from its neighbors $B$ and $C$.
- Router $C$ prepares a new routing table as-
$$\overset{\textbf{From B}}{\begin{array}{|c|c|c|}\hline
4 \\\hline
0 \\\hline
5 \\\hline
7 \\\hline
\end{array}} \text{Cost}(C \rightarrow B) = 5 \qquad \overset{\textbf{From D}}{\begin{array}{|c|c|c|}\hline
3 \\\hline
7 \\\hline
13 \\\hline
0 \\\hline
\end{array}} \text{Cost}(C \rightarrow D) = 13$$
- Cost of reaching destination $A$ from router $C = \text{min} \{ 5 + 4 , 13 + 3 \} = 9\;\text{via}\; B.$
- Cost of reaching destination $B$ from router $C = \text{min} \{ 5 + 0 , 13 + 7 \} = 5 \;\text{via}\;B.$
- Cost of reaching destination $D$ from router $C = \text{min} \{ 5 + 7 , 13 + 0 \} = 12 \;\text{via}\; B.$
Thus, the new routing table at router $C$ is-
$$\overset{\textbf{Routing Table of C}}{\begin{array}{|c|c|c|}\hline
\textbf{Destination} & \textbf{Distance} & \textbf{Next Hop} \\\hline
\text{A}& 9 & B \\\hline
\text{B}& 5 & B \\\hline
\text{C}& 0 & C \\\hline
\text{D}& 12 & B \\\hline
\end{array}}$$
$\textbf{At Router D:}$
- Router $D$ receives distance vectors from its neighbors $A, B\;\text{and}\; C.$
- Router $D$ prepares a new routing table as-
$$\overset{\textbf{From A}}{\begin{array}{|c|c|c|}\hline
0 \\\hline
4 \\\hline
9 \\\hline
3 \\\hline
\end{array}} \text{Cost}(D \rightarrow A) = 3 \qquad \overset{\textbf{From B}}{\begin{array}{|c|c|c|}\hline
4 \\\hline
0 \\\hline
5 \\\hline
7 \\\hline
\end{array}} \text{Cost}(D \rightarrow B) = 7 \qquad \overset{\textbf{From C}}{\begin{array}{|c|c|c|}\hline
9 \\\hline
5 \\\hline
0 \\\hline
13 \\\hline
\end{array}} \text{Cost}(D \rightarrow C) = 13 $$
- Cost of reaching destination $A$ from router $D = \text{min} \{ 3 + 0 , 7 + 4 , 13 + 9 \} = 3 \; \text{via}\; A.$
- Cost of reaching destination $B$ from router $D = \text{min} \{3 + 4 , 7 + 0 , 13 + 5 \} = 7 \;\text{via}\; A.$
- Cost of reaching destination $C$ from router $D = \text{min} \{3 + 9, 7 + 5 , 13 + 0 \} = 12 \;\text{via}\; A.$
Thus, the new routing table at router $D$ is
$$\overset{\textbf{Routing Table of D}}{\begin{array}{|c|c|c|}\hline
\textbf{Destination} & \textbf{Distance} & \textbf{Next Hop} \\\hline
\text{A}& 3 & A \\\hline
\text{B}& 7 & A \\\hline
\text{C}& 12 & A \\\hline
\text{D}& 0 & D \\\hline
\end{array}}$$
These will be the final routing tables at each router.
So, the correct answer is $A;B;C.$
$\textbf{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.
Thus, edges $BD$ and $CD$ are never used.
$\textbf{Important Points:-}$
1. In Distance Vector Routing,
- Only distance vectors are exchanged.
- "Next hop" values are not exchanged.
- This is because it results in exchanging the large amount of data which consumes more bandwidth.
2. While preparing a new routing table-
- A router takes into consideration only the distance vectors it has obtained from its neighboring routers.
- It does not take into consideration its old routing table.
3. Some more points regarding distance vector routing algorithm-
- It involves exchanging of distance vectors between the routers.
- Distance vector is nothing but an array of distances.
- The algorithm keeps on repeating periodically and never stops.
- This is to update the shortest path in case any link goes down or topology changes.
- Routing tables are prepared total $(n-1)$ times if there are $n$ routers in the given network.
- This is because shortest path between any $2$ nodes contains at most $n-1$ edges if there are $n$ nodes in the graph.
- Distance Vector Routing suffers from count to infinity problem.
- Distance Vector Routing uses UDP at transport layer.
