Link State Routing in Network Layer
Link state routing is a method in which each router shares its
neighbourhood’s knowledge with every other router in the internetwork. In this
algorithm, each router in the network understands the network topology then
makes a routing table depend on this topology.
Each router will share data about its connection to its neighbour, who will,
consecutively, reproduce the data to its neighbours, etc. This appears just
before all routers have constructed a topology of the network.
In the Link - State Routing Protocol, the router attempts to construct its own
internal map of the network topology. It provides the information about
whether the link to reach the router is active or not.
Every router will create something called Link state packets.
In the first round every node creates link state packets with the help of “Hello
packets”.
Step 1 − Prepare the link state packet at every router.
Step 2 − Every router flood the link state packets to every offer router
At A −
Link state packet B, C, D
Now A can construct the entire graph using the received link protocol.
Like this, every node is able to
construct the graph in its own
memory. Every node has an entire graph. So every router can apply the
Dijkstra algorithm to find the shortest path.
Advantages
The advantages of link-state routing protocol are as follows −
Fast Network Convergence,Topological Map,Hierarchical Design and Event-
driven Updates.
Disadvantages
The disadvantages of link-state routing protocol are as follows
Memory Requirements,Processing Requirements and Bandwidth
Requirements.
Distance Vector Routing (Bellmen- Ford)
Distance Vector Routing Algorithm
Distance vector is the "Dynamic Routing" protocol. Distant vector
protocol also called as Bellman-Ford algorithm or Ford Fulkerson
algorithm used to calculate the shortest path.
A distance-vector protocol calculates the distance and direction of
the vector of the next hop from the information obtained by the
neighboring router. It is necessary to keep track of the topology and
inform neighboring devices if any changes occur in the topology.
Network Information :
Every node in the network should have information about its
neighboring node. Each node in the network is designed to share
information with all the nodes in the network.
Routing Pattern :
In DVR the data shared by the nodes are transmitted only to that node
that is linked directly to one or more nodes in the network.
Data sharing :
The nodes share the information with the neighboring node from time
to time as there is a change in network topology.
The Distance Vector routing algorithm(DVR) shares the
information of the routing table with the other routers in the network
and keeps the information up-to-date to select an optimal path from
source to destination.
The Bellman-Ford algorithm is defined as :
Consider a scenario where all the routers are set and run the distant
vector routing algorithm. Each router in the network will share the
distance information with the neighboring router. All the information is
gathered from the neighbor routers. With each router's information,
an optimal distance is calculated and stored in the routing table. This
way, the process of calculating the optimal path is done using the
distant vector routing protocol.
Example of Distance Vector Routing
Step - 1 :
As we can see in the above diagram of the DVR network, the routers in the
network start sharing their information with the neighboring router in the
network.
Routing table of A :
Step - 2 :
After creating the separate local table this information is shared with the
neighboring node having a direct link.
For Router A :
The router A has a direct connection to neighboring routers B and D.
So based on the vector information of the neighboring router, the value of the
router is updated.
Here the optimal distance is been calculated to reach the specific destination.
First, the distance from A to B is identified, in our case which is 8,
ie ( −> )=8cost(A−>B)=8, and ( −> )=5cost(A−>D)=5
The distance to reach a destination B from router A is :
A= min{(A->B+B->A),(A->D+D->B}= min{8+0,5+infinity} = min{8,infinity}= 8(B)
Since the cost is min from neighbor B so the router chooses the path from B.
It then updates the routing information with entries (8, )(8,B).
To find a cost to reach destination C from router A we will use a similar
approach.
A=min{(A->B+B->C),(A->D+D->C}= min{8+2,5+13} =min{10,8} = 8©
Distance to reach destination D from A
A=min{(A->B+B->D),(A->D+D->D}= min{8+infinity,5+0} =
min{infinity,5} = 5(D)
Consequently, A's new routing table is :
For router B :
Router B receives information from A and C.
The new routing table for B is calculated as :
The cost for vector (B->A)=8
The cost for vector (B->C)=2
Distance to reach destination A from router B :
B=min{(B->A+A->A),(B->C+C->A)}=
min { 8+0 , 2+infinity } = min{8, infinity} = 8(A)
Distance to reach destination C from router B :
B=min{(B->A+A->C),(B->C+C->C)}=
min { 8+infinity , 2+0} = min{infinity, 2} = 2(C)
Distance to reach destination D from router B :
B=min{(B->A+A->D),(B->C+C->D)}=
min { 8+5 , 2+3 } = min{13 , 5 } = 5(C)
For router C :
The router C receives information from B and D.
The new routing table for C is calculated as :
The cost(C->B) = 2
The cost(C->D) = 3
Distance to reach destination A from router C :
B=min{(C->B+B->A),(C->D+D->A),}=
min { 2+8 , 3+5 } = min{10,8} = 8(D)
Distance to reach destination B from router C :
B=min{(C->B+B->B),(C->D+D->B),}=
min { 2+0 , 3+infinity } = 2(B)
Distance to reach destination B from router C :
B=min{(C->B+B->D),(C->D+D->D),}=
min { 2+infinity , 3+0 } = 3(D)
For router D :
The router D receives information from A and C.
The new routing table for D is calculated as :
The cost(D->A) = 5
The cost(D->C) = 3
Distance to reach destination A from router D :
D=min{(D->A+A->A),(D->C+C->A)}= min { 5+0 , 3+infinity } = min{5 + infinity} = 5(A)
Distance to reach destination B from router D :
D=min{(D->A+A->B),(D->C+C->B)}=
min { 5+8 , 3+2, } = min{13,5} = 5(C)
Distance to reach destination C from router D :
D=min{(D->A+A->B),(D->C+C->B)}=
min { 5+infinity , 3+0 } = 3(C)
Step - 3 :
After this, the router again exchanges the distance vector obtained in
step 2 with its neighboring router.
After exchanging the distance vector, the router prepares a new routing table.
For router A :
Similarly we can calculate the minimum distance and can update the table as follows
