HOW OSPF ROUTING PROTOCOL IMPLEMENTED USING DIJKASTRA ALGORITHM
After a long time i come up with one more new article a warm welcome of you guys please read this for getting more knowledge related to the protocol and algorithm.
So firstly I would like to tell you about the OSPF ROUTING PROTOCOL and DIJKASTRA ALGORITHM.
WHAT IS OSPF ROTUING 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.
WHAT IS DIJKASTRA ALGORITHM ?
Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later. The algorithm exists in many variants.
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.
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.
DIJKASTRA 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.)
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.
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 126.96.36.199/32 route and R2 will announce 188.8.131.52/32. Let’s walk through it.
………………………………….Thank You ………………………………………