This answer is restricted. Please login to view the answer of this question.

Login NowLink state routing is a technique in which each router shares the knowledge of its neighborhood with every other router in the internetwork.

**1. Reliable Flooding**

**Initial state:**Each node knows the cost of its neighbors.**Final state:**Each node knows the entire graph.

**2. Route Calculation**

Each node uses Dijkstra’s algorithm on the graph to calculate the optimal routes to all nodes.

- The Link state routing algorithm is also known as Dijkstra’s algorithm which is used to find the shortest path from one node to every other node in the network.
- The Dijkstra’s algorithm is an iterative, and it has the property that after k
^{th}iteration of the algorithm, the least cost paths are well known for k destination nodes.

Let’s understand through an example:

*Notaions:*

**D(v):**It defines the cost of the path from source code to destination v that has the least cost currently.**P(v):**It defines the previous node (neighbor of v) along with current least cost path from source to v.**N:**It is the total number of nodes available in the network.

In the above example, Source Vertex is A

**Step 1:**

The first step is an initialization step. The currently known least cost path from A to its directly attached neighbors, B, C, D are 2,5,1 respectively. The cost from A to B is set to 2, from A to D is set to 1 and from A to C is set to 5. The cost from A to E and F are set to infinity as they are not directly linked to A.

Step | N | D(B),P(B) | D(C),P(C) | D(D),P(D) | D(E),P(E) | D(F),P(F) |
---|---|---|---|---|---|---|

1 | A | 2, A | 5, A | 1,A | ∞ | ∞ |

**Step 2:**

In the above table, we observe that vertex D contains the least cost path in step 1. Therefore, it is added in N. Now, we need to determine a least-cost path through D vertex.

Step | N | D(B), P(B) | D(C),P(C) | D(D),P(D) | D(E),P(E) | D(F),P(F) |
---|---|---|---|---|---|---|

1 | A | 2, A | 5, A | 1, A | ∞ | ∞ |

2 | AD | 2, A | 4, D | 2,D | ∞ |

**Step 3:**

In the above table, we observe that both E and B have the least cost path in step 2. Let’s consider the E vertex. Now, we determine the least cost path of remaining vertices through E.

Step | N | D(B),P(B) | D(C),P(C) | D(D),P(D) | D(E),P(E) | D(F),P(F) |
---|---|---|---|---|---|---|

1 | A | 2,A | 5,A | 1,A | ∞ | ∞ |

2 | AD | 2,A | 4,D | 2,D | ∞ | |

3 | ADE | 2,A | 3,E | 4,E |

**Step 4:**

In the above table, we observe that B vertex has the least cost path in step 3. Therefore, it is added in N. Now, we determine the least cost path of remaining vertices through B.

Step | N | D(B),P(B) | D(C),P(C) | D(D),P(D) | D(E),P(E) | D(F),P(F) |
---|---|---|---|---|---|---|

1 | A | 2,A | 5,A | 1,A | ∞ | ∞ |

2 | AD | 2,A | 4,D | 2,D | ∞ | |

3 | ADE | 2,A | 3,E | 4,E | ||

4 | ADEB | 3,E | 4,E |

**Step 5:**

In the above table, we observe that C vertex has the least cost path in step 4. Therefore, it is added in N. Now, we determine the least cost path of remaining vertices through C.

Step | N | D(B),P(B) | D(C),P(C) | D(D),P(D) | D(E),P(E) | D(F),P(F) |
---|---|---|---|---|---|---|

1 | A | 2,A | 5,A | 1,A | ∞ | ∞ |

2 | AD | 2,A | 4,D | 2,D | ∞ | |

3 | ADE | 2,A | 3,E | 4,E | ||

4 | ADEB | 3,E | 4,E | |||

5 | ADEBC | 4,E |

The final table is

Step | N | D(B),P(B) | D(C),P(C) | D(D),P(D) | D(E),P(E) | D(F),P(F) |
---|---|---|---|---|---|---|

1 | A | 2,A | 5,A | 1,A | ∞ | ∞ |

2 | AD | 2,A | 4,D | 2,D | ∞ | |

3 | ADE | 2,A | 3,E | 4,E | ||

4 | ADEB | 3,E | 4,E | |||

5 | ADEBC | 4,E | ||||

6 | ADEBCF |

If you found any type of error on the answer then please mention on the comment or report an answer or submit your new answer.

Click here to submit your answer.

HAMROCSIT.COM

## Discussion