OSPF (Open Short Path First) Routing Protocol Implemented using Dijkstra Algorithm …
Hello Everyone … !!
So, again I come with new concept and that is OSPF Protocol implementing Dijkstra’s Algorithm. OSPF is link state. That means it runs Dijkstra’s Shortest Path First (SPF) Algorithm, that is something that is common to all link state routing protocols which makes topology detail regarding network outside their area…
So firstly I would like to tell you about the OSPF ROUTING PROTOCOL and DIJKASTRA ALGORITHM.
ROUTING PROTOCOL :
When data move across multiple network, IP routing helps to determine the path of data by setting some protocols to reach the source destination. Ultimately data travels at the physical level through routers IP routing protocols enable routers to setup a forwarding table that correlates final destination with next hop addresses. Let me take you through the internal Routing Mechanism and key terms.
The IP network is classified into two categories:
a) Interior Gateway Protocol
b)Exterior Gateway Protocol
- IP routing sending data packets from one network to another through routers. It is routers that examine destination IP address, determine next hop address to address a packet.
- Remote router IP address of router used to reach that network outgoing interface. Populating routing table directly connected to subnets, static routing, default, dynamic routing.
- Directly Connected Interface routes local to router (One or More) network subnets easily recognizable traffic directed to these network can be forwarded without any help from routing protocols.
- Static Routing : Routes to destination manually entered by network administrators in router’s route table, don’t adjust to changes in the network.
- Default Gateway : The router that hosts use to communicate with other hosts — remote networks.
- Default Routing : Network having only one output interface, all the data going through a single exit. Instead of having many static routers connecting to remote networks, single output interface is configured to match all routes.
- Dynamic Routing : Optimal data routing, enables routes to select paths according to real-time logical network changes. Routing protocol responsible for the creation, maintenance, update of a dynamic routing table. While in static routing all routing job have done manually by network administrator.
OSPF ROUTING PROTOCOL :
Open Shortest Path First (OSPF) is a routing protocol for Internet Protocol (IP) networks. It uses a link state routing (LSR) algorithm and falls into the group of interior gateway protocols (IGPs), operating within a single autonomous system (AS). It is defined as OSPF Version 2 in RFC 2328 (1998) for IPv4. The updates for IPv6 are specified as OSPF Version 3 in RFC 5340 (2008).OSPF supports the Classless Inter-Domain Routing (CIDR) addressing model.
OSPF is a widely used IGP in large enterprise networks. IS-IS, another LSR-based protocol, is more common in large service provider networks.
Note :
- Autonomous System could be defined as the set of internet routable IP prefixes belonging to a network or a collection of networks managed by a single entity or organizations.
- Link State routing is the concept within which every node constructs a map of the connectivity to the network in the form of graph.
The most widely used routing protocols is OSPF and is suitable for large network. OSPF is a Link State protocol based on cost under a single routing solution that maintains information of all nodes on the network. Since each nodes holds the entire network structure information, each nodes can independently calculate the path to reach the destination by adopting shortest path algorithm namely Dijkstra’s algorithm.
DIJKSTRA’S ALGORITHM :
Dijkstra’s Algorithm is used to find the shortest path between a node/vertex (source node) to any (or every) other nodes/vertices (destination nodes) in a graph. A graph is basically an interconnection of nodes connected by edges. This algorithm is sometimes referred to as Single source shortest Path Algorithm due to its nature of implementation.
With Dijkstra’s Algorithm, you can find the shortest path between nodes in a graph. Particularly, you can find the shortest path from a node (called the “source node”) to all other nodes in the graph, producing a shortest-path tree.
Main logic of this algorithm is based on the following formula:-
dist[r]=min(dist[r], dist[q]+cost[q][r])- It states that distance vertex r, which is adjacent to vertex q, would be updated only if the value of
dist[q]+cost[q][r]is less thandist[r]. - dist is a 1-D array which keeps track of the shortest distance at every step from source vertex to all other vertices.
- cost is a 2-D array that represents the cost adjacency matrix for the graph
Basics of Dijkstra’s Algorithm :
- 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.
Requirements :
Dijkstra’s Algorithm can only work with graphs that have positive weights. This is because, during the process, the weights of the edges have to be added to find the shortest path.
If there is a negative weight in the graph, then the algorithm will not work properly. Once a node has been marked as “visited”, the current path to that node is marked as the shortest path to reach that node. And negative weights can alter this if the total weight can be decremented after this step has occurred.
Complexity :
- Time complexity: Θ(E+V log V) (V for vertices & E for edges)
- Space complexity: Θ(V)
- Time complexity(If priority queue is not used): Θ(E+V²)
DIJKSTRA’S BEHIND THE OSPF :
OSPF is a routing protocol. Two routers speaking OSPF to each other exchange information about the routes they know about and the cost for them to get there.
When many OSPF routers are part of the same network, information about all of the routes in a network are learned by all of the OSPF routers within that network — technically called an area. (We’ll talk more about area as we go on).
Each OSPF router passes along information about the routes and costs they’ve heard about to all of their adjacent OSPF routers, called neighbors.
OSPF routers rely on cost to compute the shortest path through the network between themselves and a remote router or network destination. The shortest path computation is done using Djikstra’s algorithm. This algorithm isn’t unique to OSPF. Rather, it’s a mathematical algorithm that happens to have an obvious application to networking.
Consider a simple example of five routers connected as shown in the diagram below. Assuming all links have the same cost, what’s the fastest way for R3 to connect to R5? Through R4 — R4 is the lowest cost path. (R3’s path to R5 via R1, for example, adds another link and therefore additional cost.)
OSPF Interfaces :
Another important idea in OSPF is that interfaces used to exchange information with OSPF neighbors have different types. There are too many types to discuss here but you should be aware of two important ones.
- An OSPF broadcast interface is connected to a shared network, like Ethernet.
- An OSPF point-to-point interface is connected to a link where there can only be a single OSPF router on either end, such as a WAN link or a purpose-built Ethernet link.
The reason for the various interface types is to make sure that all routers know about all routes from all other routers.
On point-to-point links, there’s no mystery — the two routers know they’re the only OSPF routers on the link and so they exchange routes with each other.
On broadcast links, there’s a potential for many different OSPF routers to be on the network segment. To minimize the number of neighbor relationships that form on broadcast links, OSPF elects a designated router (as well as a backup) whose job it is to neighbor with all other OSPF routers on the segment and share everyone’s routes with everyone else.
OSPF Areas :
Areas in OSPF are collections of routers grouped together. With the exception of area border routers, OSPF routers in one area don’t neighbor with routers in other areas. Among other reasons, areas were once used to scale large OSPF networks.
Back when router CPUs were less powerful than they are today, a general rule of thumb was to keep an OSPF area to no more than 50 routers. That would keep the number of OSPF shortest path computations and database updates to a manageable amount as interfaces went up and down, routes were learned and withdrawn, and so on.
In modern networks, it’s not unheard of to scale to a thousand routers or more in a single area — router CPUs have come a long way.
Today, although scale is not much of a reason for implementing multiple areas, OSPF areas are still useful as administrative boundaries in a network. For example:
- Route summarization & aggregation (replacing several small routes with one larger route that covers them) can only happen at OSPF area boundaries.
- Not all routers need to know about every other route available in a network. Using OSPF areas, it’s possible to inject a default route representing all routes outside of the local area.
If you’re thinking you should be able to summarize or filter routes between OSPF routers within an area, the problem is that for the shortest path first (SPF) calculation to work, all routers in an area need to have an identical “picture” of the network. Therefore, it’s impossible to hide routes between OSPF routers in an area.
(A type of OSPF filtering you might be familiar with is actually a filter between the OSPF routing information base (RIB) and the router’s forwarding information base (FIB). The local OSPF process still passes information about the filtered route along to other OSPF neighbors.)
The most important area in OSPF is the backbone area, also known as area 0. The backbone area is the area that all OSPF areas must traverse to get to other OSPF areas.
For instance, let’s say we have area 0, area 1, and area 2. Area 1 traffic must traverse area 0 to get to area 2, and vice versa. Even if there was a router with one interface in area 1, and another interface in area 2, area 1 and 2 traffic could not traverse this router directly. The reason for this is loop prevention.
While OSPF routers within an area know everything there is to know about the network topology, topology information is hidden at area borders. For more detail about why the backbone area and related traversal rule exists.
A simple two-router OSPF network :
Here’s an example of a network configuration that creates a very simple OSPF network between two Cisco routers. The routers are placed in area 0 and an OSPF point-to-point link is configured between them. R1 will announce the 1.1.1.1/32 route and R2 will announce 2.2.2.2/32. Let’s walk through it.
Thank You so much for reading…… I hope you get something in it .
If you want to connect me , below is my LinkedIn Profile Link …
Take Care , Be Safe .. :)
