OSPF Using Dijkstra's Algorithm

Open Shortest Path First (OSPF)

It's a routing protocol used in routers to find the shortest path between routers. It's based on Dijkstra's Algorothm.

OSPF supports variable length subnet masks (VLSM) and route summarization.

It uses link state routing (LSR).

OSPF routers maintain a map of internetwork called Link State Database.

Here each router maintains the information of all other domains, routers, subnets within the entire network and based on this information, they determine the shortest path using dijkstra's algo.

The routers gets this information through LSA.

LSA - Link State Advertisements. They contains information about routers. An LSA is a router's way of communicating information in OSPF. There are different types of LSAs. We'll learn about them later in this blog

Once this LSA have been flooded, OSPF stores information in Link State Database called LSDB.

A large OSPF domain is broken into seperate areas to restrict the propagation of routes and reduces the amount of resources required by each router to maintain it's LSDB. Each area is connected to a central backbone called area 0.

After having same copy of LSDB in each routers, the routers then creates a Sortest Path First (SPF) Tree using Dijkstra's algorithm on LSDB and routing table can be derived from the SPF tree which contains the best route to each router. This routing table contains all the destinations the routing protocol knows about, associated with a next Hop ip address and ongoing Interface.

The protocol recreates routes when network topology changes using the Dijkstra's algorithm and minimises the routing protocol traffic that it generates.

How this Shortest Path First (SPF) Tree created using Dijkstra's algo?

For this, let's first learn about OSPF Area, LSA Type and Router Type.

OSPF Area :

OSPF divides networks into sub-domains called areas. An area is a logical collection of OSPF networks, routers, and links that have the same area identification. A router within an area only has to maintain a topological database for its assigned area, which reduces its database size. Rather than knowing an entire network's topology, it only needs to know its own, which makes the routers within the area run much more efficiently.

So, the main benefit of creating areas is a reduction in the number of routes to propagate — by filtering and summarizing routes.

• Backbone area (area 0)
• Standard area
• Stub area
• Totally stubby area
• Not-so-stubby area (NSSA)

OSPF Router Type :

Internal Router: It maintains a current and accurate database of subnets within the area. Forwards data to other networks using the shortest path.

Backbone Router: Has an interface connected to the backbone (Area 0).

Area Border Router (ABR): Has interfaces in multiple areas with at least one interface in area 0. Connects other areas to the backbone and maintains routing information for each connected area. (Responsible for exchanging routes between two areas.)

Autonomous System Boundary Router (ASBR): Router located between OSPF autonomous system and a non-OSPF network.

It's Used to redistribute routing information between networks

OSPF LSA Type :

Each router in an AS (Autonomous System) generates one or more type of LSA, depending on router type and multiple LSA form an LSDB.

• LSA Type 1: Router LSA

• LSA Type 2: Network LSA

• LSA Type 3: Summary LSA

• LSA Type 4: Summary ASBR LSA

• LSA Type 5: Autonomous system external LSA

• LSA Type 7: Not-so-stubby area LSA

 
ROUTER-LSA (TYPE 1)
A router-LSA describes the link status and cost of a router.
Router-LSAs are generated by a router and advertised within the area to which the router belongs.

NETWORK-LSA (TYPE 2)
A network-LSA describes the link status of all routers on the local network segment. Network-LSAs are generated by a DR on a broadcast or non-broadcast multiple access (NBMA) network and advertised within the area to which the DR belongs.

NETWORK-SUMMARY-LSA (TYPE 3)
A network-summary-LSA is advertised by an ABR and it describes routes on a network segment in an area. The routes are advertised to other areas. (Since boarder router is responsible for exchanging routes between two areas, so it's generated by ABR)
We exchange advertisement between different areas in the form of LSA3

ASBR-SUMMARY-LSA (Type 4)
An ASBR-summary-LSA describes routes to the ASBR in an area. It's used to advertise the ASBR to other areas. The routes are advertised to all areas except the area to which the ASBR belongs. It is also generated by an ABR (Because ABR tells all the internal routers that who is ASBR).

AS-EXTERNAL-LSA (TYPE 5)
An AS-external-LSA describes AS external routes. AS-external-LSAs are generated by an ASBR. Among the five types of LSAs, only AS-external-LSAs can be advertised to all areas except stub areas and not-so-stubby areas (NSSAs).

NSSA-LSA (TYPE 7)

An NSSA-LSA describes AS external routes. It is originated by an ASBR and only flooded in NSSAs (Not So Stubby Areas).

Lsa1 and Lsa2 both sends advertisement within same area and are never flooded outside of an area. All the routers exchange routes in the form of Lsa1 and Lsa2.

Now, Dijkstra's algorithm is a step-by-step process we can use to find the shortest path between two vertices in a weighted graph. This algorithm enables us to find shortest distances and minimum costs, making it a valuable tool. It only works with graphs having Positive weights.

In order to find the shortest path, Dijkstra’s algorithm mainly allocates a “cost” value taken to reach the destination vertex from the source vertex. The “cost” can be mapped to disance, money or time taken to reach from source to a destination.

How it works?

• Dijkstra's Algorithm basically starts at the node that you choose (the source node) and it analyzes the graph to find the shortest path between that node and all the other nodes in the graph.
• The algorithm keeps track of the currently known shortest distance from each node to the source node and it updates these values if it finds a shorter path.
• Once the algorithm has found the shortest path between the source node and another node, that node is marked as "visited" and added to the path.
• The process continues until all the nodes in the graph have been added to the path. This way, we have a path that connects the source node to all other nodes following the shortest path possible to reach each node.

Hope you like this..