G.H.
Raisoni collage of Engineering and
Management
TAE-2
PPT presentatio
Topic : Link State routine
Presentate by:. Guided by: Sarita Patil
Pritam karad (TCOA34)
Vaidehi Kawal (TCOA35)
Dhiraj Kolhe(TCOA36)
Introduction:
• The basic concept of link-state routing is that every node
constructs a map of the connectivity to the network, in the
form of a graph, showing which nodes are connected to
which other nodes.
• While distance vector routers use a distributed algorithm to
compute their routing tables, link-state routing uses link-
state routers to exchange messages that allow each router to
learn the entire network topology.
Link State Routing:
• Link state routing is the second family of routing protocols.
• Based on this learned topology, each router is then able to
compute its routing table by using a shortest path
computation.
• Each node then independently calculates the next best
logical path from it to every possible destination in the
network.
Features of link State protocols:
• Link state packet – A small packet that contains routing
information.
• Link state database – A collection information gathered
from link state packet.
• Shortest path first algorithm (Dijkstra algorithm) – A
calculation performed on the database results into shortest path.
• Routing table – A list of known paths and interfaces.
The three keys to understand the Link State Routing
algorithm:
• Knowledge about the neighborhood: Instead of sending its routing table,
a router sends the information about its neighborhood only. A router
broadcast its identities and cost of the directly attached links to other
routers.
• Flooding: Each router sends the information to every other router on the
internetwork except its neighbors. This process is known as Flooding.
Every router that receives the packet sends the copies to all its neighbors.
Finally, each and every router receives a copy of the same information.
• Information sharing: A router sends the information to every other
router only when the change occurs in the information.
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.
Calculation of shortest path –
• Step-1: The node is taken and chosen as a root node of the tree, this
creates the tree with a single node, and now set the total cost of each
node to some value based on the information in Link State Database
• Step-2: Now the node selects one node, among all the nodes not in the
tree like structure, which is nearest to the root, and adds this to the
[Link] shape of the tree gets changed .
• Step-3: After this node is added to the tree, the cost of all the nodes not in
the tree needs to be updated because the paths may have been changed.
• Step-4: The node repeats the Step 2. and Step 3. until all the nodes are
added in the tree.
Let's describe some notations:
• c( i , j): Link cost from node i to node j. If i and j nodes are not directly
linked, then c(i , j) = ∞.
• 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.
Algorithm:
Initialization N = {A} // A is a root node.
for all nodes v if v
adjacent to A
then D(v) = c(A,v)
else D(v) = infinity loop
find w not in N such that D(w) is a minimum.
Add w to N
Update D(v) for all v adjacent to w and not in N: D(v) = min(D(v) , D(w) +
c(w,v)) Until all nodes in N
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.
a) Calculating shortest path from A to B
1. v = B, w = D
2. D(B) = min( D(B) , D(D) + c(D,B) )
3. = min( 2, 1+2)>
4. = min( 2, 3)
The minimum value is 2. Therefore, the currently shortest path from A to B is 2.
b) Calculating shortest path from A to C
1. v = C, w = D
2. D(B) = min( D(C) , D(D) + c(D,C) )
3. = min( 5, 1+3)
4. = min( 5, 4)
The minimum value is 4. Therefore, the currently shortest path from A to C is
4.</p>
c) Calculating shortest path from A to E
1. v = E, w = D
2. D(B) = min( D(E) , D(D) + c(D,E) )
3. = min( ∞, 1+1)
4. = min(∞, 2)
The minimum value is 2. Therefore, the currently shortest path from A to E is 2.
Note: The vertex D has no direct link to vertex E. Therefore, the value of D(F) is
infinity.
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.
• a) Calculating the shortest path from A to B.
• v = B, w = E
• D(B) = min( D(B) , D(E) + c(E,B) )
• = min( 2 , 2+ ∞ )
• = min( 2, ∞)
• The minimum value is 2. Therefore, the currently shortest path from A to B is
2.
• b) Calculating the shortest path from A to C.
• v = C, w = E
• D(B) = min( D(C) , D(E) + c(E,C) )
• = min( 4 , 2+1 )
• = min( 4,3)
• The minimum value is 3. Therefore, the currently shortest path from A to C is 3.
• c) Calculating the shortest path from A to F.
• v = F, w = E
• D(B) = min( D(F) , D(E) + c(E,F) )
• = min( ∞ , 2+2 )
• = min(∞ ,4)
• The minimum value is 4. Therefore, the currently shortest path from A to F is 4.
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.
a) Calculating the shortest path from A to C.
1. v = C, w = B
2. D(B) = min( D(C) , D(B) + c(B,C) )
3. = min( 3 , 2+3 )
4. = min( 3,5)
5. The minimum value is 3. Therefore, the currently shortest path from A to C
is 3.
b) Calculating the shortest path from A to F.
1. v = F, w = B
2. D(B) = min( D(F) , D(B) + c(B,F) )
3. = min( 4, ∞)
4. = min(4, ∞)
5. The minimum value is 4. Therefore, the currently shortest path from A to F
is 4.
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.
a) Calculating the shortest path from A to F.
1. v = F, w = C
2. D(B) = min( D(F) , D(C) + c(C,F) )
3. = min( 4, 3+5)
4. = min(4,8)
5. The minimum value is 4. Therefore, the currently shortest path from
A to F is 4.
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
Final table:
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
Disadvantage:
Heavy traffic is created in Line state routing due to Flooding.
Flooding can cause an infinite looping, this problem can be
solved by using Time-to-leave field