OSPF (Open Short Path First) Routing Protocol implemented using Dijkstra Algorithm
OSPF is:
Open shortest path first (OSPF) is a link-state routing protocol which is used to find the best path between the source and the destination router using its own shortest path first (SPF) algorithm. A link-state routing protocol is a protocol which uses the concept of triggered updates, i.e., if there is a change observed in the learned routing table then the updates are triggered only, not like the distance-vector routing protocol where the routing table are exchanged at a period of time.
It is:
1>Widely used and supported Protocol
2>Interior Gateway Protocol
3>Link state routing Protocol
The OSPF protocol is a link-state routing protocol, which means that the routers exchange topology information with their nearest neighbors. The topology information is flooded throughout the AS, so that every router within the AS has a complete picture of the topology of the AS. This picture is then used to calculate end-to-end paths through the AS, normally using a variant of the Dijkstra algorithm. Therefore, in a link-state routing protocol, the next hop address to which data is forwarded is determined by choosing the best end-to-end path to the eventual destination.
Dijkstra Algorithm
The Dijkstra Algorithm converts routers, subnets, and links into a tree
In the above example, the layer 3 network consists of LANs, connecting hosts connected via routers.
The building represents LANs, We can imagine the equipment in the building that makes up the LAN
Each LAN is a separate IP subnet
The individual subnets can be regarded as jigsaw that can be clipped together to form a network.
The point where the pieces clip together is called the router
The aim of the algorithm is to find the shortest path to each subnet, so we need to assign a length value to every link
In OSPF, the length of a link is referred to as the cost, the application of the Djikstra Algorithm to OSPF actually finds the least-cost paths.
Link costs are related to link bandwidth, We have actually assigned some arbitrary costs to the link from the routers to the subnets
Turning the network into a tree
Every router can treat the network as a tree, with the router itself as the root.
So, let us build up the tree with R2 as the root
This means we are re-arranging the subnets according to Djikstra's rules.
From the root, branches have added a subnet at a time, starting with the subnets directly connected to R2.
The subnet with the least cost pth is chosen at every step, Sticking to this rule results in a tree of least cost paths.
If a subnet is already connected to the tree,but a less-cost connection point becomes available (R1),move it to the less cost point
The Route R2 to S5 has cost of :1+10+1=12
The ROute R2 to S1 has a cost of :1+10+10+10=31
SO that’s how this Protocol is used!!