Working of OSPF(Open Short Path First) Routing Protocol using Dijkastra Algorithm
What is Routing Protocols?
Routing protocol is used to gather routing entry information to route anything successfully
across the network. For this Router needs to know following key information:
· The destination of the packet that need to be routed.
· A routing entry for that destination. (This can include unknown default route)
Routing protocol uses a different method to gather information about available networks
and distance, or cost. Routing protocol can be classified into two main categories.
1. Distance vector routing protocols — RIP, IPX, IPX RIP, AppleTalk RTMP, IGRP
2. Link-state routing protocols — OSPF,IPX NLSP, IS-IS
OSPF Protocol
The OSPF stands for Open Shortest Path First. It is a widely used and supported routing protocol. It is an intradomain protocol, which means that it is used within an area or a network. It is an interior gateway protocol that has been designed within a single autonomous system. It is based on a link-state routing algorithm in which each router contains the information of every domain, and based on this information, it determines the shortest path. The goal of routing is to learn routes. The OSPF achieves by learning about every router and subnet within the entire network. Every router contains the same information about the network. The way the router learns this information by sending LSA (Link State Advertisements). These LSAs contain information about every router, subnet, and other networking information. Once the LSAs have been flooded, the OSPF stores the information in a link-state database known as LSDB. The main goal is to have the same information about every router in an LSDBs.
How does OSPF work?
There are three steps that can explain the working of OSPF:
Step 1: The first step is to become OSPF neighbors. The two connecting routers running OSPF on the same link creates a neighbor relationship.
Step 2: The second step is to exchange database information. After becoming the neighbors, the two routers exchange the LSDB information with each other.
Step 3: The third step is to choose the best route. Once the LSDB information has been exchanged with each other, the router chooses the best route to be added to a routing table based on the calculation of SPF.
Types of links in OSPF
A link is basically a connection, so the connection between two routers is known as a link.
There are four types of links in OSPF:
- Point-to-point link: The point-to-point link directly connects the two routers without any host or router in between.
- Transient link: When several routers are attached in a network, they are known as a transient link.
The transient link has two different implementations:
Unrealistic topology: When all the routers are connected to each other, it is known as an unrealistic topology.
Realistic topology: When some designated router exists in a network then it is known as a realistic topology. Here designated router is a router to which all the routers are connected. All the packets sent by the routers will be passed through the designated router. - Stub link: It is a network that is connected to the single router. Data enters to the network through the single router and leaves the network through the same router.
- Virtual link: If the link between the two routers is broken, the administration creates the virtual path between the routers, and that path could be a long one also.
OSPF Packets
There are five different types of packets in OSPF:
1. Hello packet
The Hello packet is used to create a neighborhood relationship and check the neighbor’s reachability. Therefore, the Hello packet is used when the connection between the routers need to be established.
2. Database Description
After establishing a connection, if the neighbor router is communicating with the system first time, it sends the database information about the network topology to the system so that the system can update or modify accordingly.
3. Link state request
The link-state request is sent by the router to obtain the information of a specified route. Suppose there are two routers, i.e., router 1 and router 2, and router 1 wants to know the information about the router 2, so router 1 sends the link state request to the router 2. When router 2 receives the link state request, then it sends the link-state information to router 1.
4. Link state update
The link-state update is used by the router to advertise the state of its links. If any router wants to broadcast the state of its links, it uses the link-state update.
5. Link state acknowledgment
The link-state acknowledgment makes the routing more reliable by forcing each router to send the acknowledgment on each link state update. For example, router A sends the link state update to the router B and router C, then in return, the router B and C sends the link- state acknowledgment to the router A, so that the router A gets to know that both the routers have received the link-state update.
Dijkstra’s Algorithm
Dijkstra’s algorithm is one of the most popular algorithms for solving many single-source shortest path problems having non-negative edge weight in the graphs i.e., it is to find the shortest distance between two vertices on a graph. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.
It is a greedy algorithm that solves the single-source shortest path problem for a directed graph G = (V, E) with nonnegative edge weights, i.e., w (u, v) ≥ 0 for each edge (u, v) ∈ E.
Dijkstra’s Algorithm maintains a set S of vertices whose final shortest — path weights from the source s have already been determined. That’s for all vertices v ∈ S; we have d [v] = δ (s, v). The algorithm repeatedly selects the vertex u ∈ V — S with the minimum shortest — path estimate, insert u into S and relaxes all edges leaving u.
Because it always chooses the “lightest” or “closest” vertex in V — S to insert into set S, it is called as the greedy strategy.
Applications of Dijkstra’s shortest path algorithm
- Digital Mapping Services in Google Maps.
2. Social Networking Applications.
3. Telephone Network.
4. IP routing to find Open shortest Path First.
5. Flighting Agenda.
6. Designate file server.
7. Robotic Path.
Shortest Path Algorithm using Dijkstra algorithm
To calculate the lower cost to a destination OSPF uses Dijkstra algorithm. The algorithm adds up the total cost between source and to the each destination network. If there are multiple path to a destination the lowest cost path is selected. But OSPF keeps up to six equal cost routes in the routing table for load balancing.
Each router will have its own view of the network even though all the routers will build a shortest path tree using the same link-state database.
How to build Shortest Path Tree
In order to built shortest path tree for A in the following diagram, we have to make Router A the root of the tree and calculate the smallest cost for each destination.
* Direction of the arrows in calculating the cost.
For example, the Router B’s interface cost (8) to network 128.213.0.0 is not relevant when calculating the cost to 192.213.11.0 network.
* Cost for from Router A to Destination Network 192.213.11.0
- 10 + 5 = 15 ( Through Router B)
* Cost for from Router A to Destination Network 222.211.10.0
- 10 + 10 = 20 ( Through Router C)
- 10 + 5 + 5 =20 ( Through Router B)
* When equal cost paths exist to the same destination OSPF will keep up to six entries in the routing table.
* After building the shortest path tree, it will build the routing table accordingly.
- For directly connected networks cost is 0 and other networks will be reached according to the calculation of the tree.
ThankYou🙏🙏
