Explain link state routing with example.

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

Login Now

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

Link State Routing has two phases:

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 kth 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.

Link State Routing

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.
Leave your Answer:

Click here to submit your answer.

Discussion
0 Comments
  Loading . . .