OSPF — The Dijkstra Algorithm
The OSPF means Open Shortest Path First. It is widely used and supported routing protocol. This protocol is used within a network, hence a Interior Gateway Protocol. It is based on link state routing algorithm in which each router contains the information of every domain and based on this information it defines the shortest path. The OSPF learns about every router and subnet within entire network.
The way through which OSPF learns about other routers is by sending Link State Advertisement or LSA. These LSA contains information about subnets, routers and some of the network information. Once all the LSA’s are transferred within network, OSPF put’s these in a database called as LSDB i.e Link State Database. The main goal here is to have each router with same information in their LSDB’s.
Let’s understand in breif. So, there are mainly 3 steps to achieve this.
- Becoming OSPF neighbours: Two routers running OSPF on the same link agree to form a neighbour relationship. We can consider routers as a node and becoming neighbours means becoming a adjacent node.
- Exchange Database information: After becoming neighbours, routers will exchange or swap their LSDB information with each other.
- Choosing the best routes: Finally, each router chooses the best routes to add to it’s routing table based on the learned LSDB information.
First & foremost thing before becoming a neighbour or relationship is formed is that each router have to choose a Router ID (RID). Router ID is a number which can be used to identify unique routers in a network. It’s kind of OSPF name. It is in format of IPv4 address, but we can set it to our wish using manually or let the router decides itself.
While selecting RID, it first check if we have set it manually. If we have not set it manually then router will choose the highest up status loopback IP address. If this is not present then it would choose the highest up non-loopback IP address.
Once,we routers have RID, they will communicate with their potential neighbours by sending a Hello message. This message contains important information consisting of the unique RID and known neighbours.
Once router2 receives this message, it follows some checks. These are requirements match check:
- Area ID: Area ID needs to be same as it is helpful in scaling OSPF
- Subnet: The connecting links between two routers must be in same network.
- Hello & Dead Interval : The hello and dead timer should be the same. The default hello timer is 10sec for P2P and broadcast nertwork.
- Authentication : If using authentication, it should match.
- Stub area flag
- Unique router ID
Once, all the checks is made and all is good then router 2 will be in INIT state. Now, router2 will send it’s own hello message.
This message also contains router1 RID as a known neighbour. So, when router1 recieves this message, it see’s as it’s known neighbour. This allow router1 to come in 2-way state. Now, Router1 sends another message listing router2 as its known neighbour. Then router2 will also be in 2-way state.
Before sending database information, it chooses Designated Router (DR) and Backup Designated Router (BDR). DR and BDR’s are not elected on Point to Point connections. DR and BDR election are done on the basis of highest OSPF priority. Bydefault, it is set to 1, but we can change. So, router will become full neighbour only with DR’s and BDR’s. Other will remain in 2-way state.
Once, the database exchange process start’s both the routers come into Exstart state. At this point router select’s the Slave and Master, this is based on Router ID. The Master controls the sequence number and start the exchange process. Now, it comes into Exchange state and both routers send’s their list of LSA’s which is called Database Description (DBD). Then it’s come into Loading state and it looks at the DBD and send’s request for the information it does’nt have in order to prevent loops. This request is called Link State Request (LSR). Then the other router will send it’s information/update by Link State Update (LSU). Finally, router1 will send the Link State Acknowledgement (LSAck) to tell that it has received the information. Once, all the information is exchanged both the routers enter into the Full neighbour state.
Adding Best Route to Routing Table
The way through which OSPF chooses best route is by a metrics called cost. OSPF cost is the value to given to a link based on the bandwidth of that interface.
Cost = Reference Bandwidth / Interface Bandwidth
Reference value is set to the router itself, bydefault it is 100,000 Kbps
Cost assigned per Interface is listed below.
Let’s understand by taking a simple example.
Each router acts a independent Node and the edge’s consists of the n/w bandwidth according to which we can give the weights as we discussed above.
Now, let say our source is R1 and destination is R3. So, now we have 3 different routes.
R1 → R4 →R3 → : This route has 1544Kbps bandwidth so has cost=64. Also, for R4 to R3 cost will be 64. Lastly, it has 10Mbps bandwidth so cost=10.
So, total cost = 64+64+10 = 138
Similarly, R1 →R2 →R3 →: cost=10+10+10=30 and for
R1 → R5 →R3 →: cost=1+1+10=12
Hence it chooses the route with minimum cost which is R1 →R5 →R3.
We maintain two sets, one set contains routers included in shortest path tree, other set includes routers not yet included in shortest path tree. At every step of the algorithm, we find a router which is in the other set (set of not yet included) and has a minimum distance from the source i.e router R1.
Update cost value of all adjacent routers of u(Source). To update the distance values, iterate through all adjacent routers. For every adjacent router v, if sum of cost value of u (from source) and weight of edge u →v, is less than the cost value of v, then update the cost value of v. This way we can get the total cost of route and find out the best or shortest path.
Hope you find it informative!
Thank you for reading 😃
