OSPF Routing Protocol (Use Cases)

OSPF is a Link State protocol that’s considered maybe the most famous protocol among the Interior Gateway Protocol (IGP) family, developed in the mid-1980s by the OSPF working group of the IETF(The Internet Engineering Task Force is the leading Internet standards body. It develops open standards through open processes with one goal in mind: to make the Internet work better.)

When configured, OSPF will listen to neighbors and gather all link state data available to build a topology map of all available paths in its network and then save the information in its topology?database, also known as its Link-State Database (LSDB). Using the information from its topology database. From the information gathered, it will calculate the best shortest path to each reachable subnet/network using an algorithm called Shortest Path First (SFP) that was developed by the computer scientist Edsger W. Dijkstra in 1956. OSPF will then construct three tables to store the following information:

• Neighbor Table: Contains all discovered OSPF neighbors?with whom routing information will be interchanged
• Topology Table: Contains the entire road map of the network with all available OSPF routers and calculated best and alternative paths.
• Routing Table: Contain the current working best paths that will be used to forward data traffic between neighbors.

Shortest Path First Algorithm

OSPF uses a shortest-path first algorithm in order to build and calculate the shortest path to all known destinations. The shortest path is calculated with the use of the Dijkstra algorithm. The algorithm by itself is quite complicated. This is a very high level, simplified way of looking at the various steps of the algorithm:

1. Upon initialization or due to any change in routing information, a router generates a link-state advertisement. This advertisement represents the collection of all link-states on that router.
2. All routers exchange link-states by means of flooding. Each router that receives a link-state update should store a copy in its link-state database and then propagate the update to other routers.
3. After the database of each router is completed, the router calculates a Shortest Path Tree to all destinations. The router uses the Dijkstra algorithm in order to calculate the shortest path tree. The destinations, the associated cost, and the next hop to reach those destinations form the IP routing table.
4. In case no changes in the OSPF network occur, such as the cost of a link or a network being added or deleted, OSPF should be very quiet. Any changes that occur are communicated through link-state packets, and the Dijkstra algorithm is recalculated in order to find the shortest path.

The algorithm places each router at the root of a tree and calculates the shortest path to each destination based on the cumulative cost required to reach that destination. Each router will have its own view of the topology even though all the routers will build a shortest-path tree using the same link-state database. The following sections indicate what is involved in building a shortest-path tree.

OSPF Cost

The cost (also called metric) of an interface in OSPF is an indication of the overhead required to send packets across a certain interface. The cost of an interface is inversely proportional to the bandwidth of that interface. A higher bandwidth indicates a lower cost. There is more overhead (higher cost) and time delays involved in crossing a 56k serial line than crossing a 10M ethernet line. The formula used to calculate the cost is:

• cost= 10000 0000/bandwith in bps

For example, it will cost 10 EXP8/10 EXP7 = 10 to cross a 10M Ethernet line and will cost 10 EXP8/1544000 = 64 to cross a T1 line.

By default, the cost of an interface is calculated based on the bandwidth; you can force the cost of an interface with the ip ospf cost <value> interface sub configuration mode command.

OSPF Areas

OSPF offers a very distinguishable feature named: Routing Areas. It means dividing routers inside a single autonomous system running OSPF, into areas where each area consists of a group of connected routers.

The idea of dividing the OSPF network into areas is to simplify administration and optimize available resources. Resource optimization is especially important for large enterprise networks with a plethora of networks and links.?Having many routers exchange the link-state database could flood the network and reduce its efficiency – this was the need that led to the creation of concept Areas.

Areas are a logical collection of routers that carry the same Area ID or number inside of an OSPF network, the OSPF network itself can contain multiple areas, the first and main Area is called the backbone area “Area 0”, all other areas must connect to Area 0 as shown in the diagram below:

All routers within the same area have the same topology table -Link State Database- but a different routing table as OSPF calculates different best paths for each router depending on its location within the network topology while they will all share the same Link State topology.

The goal of having an Area is to localize the network as follow:

• The Area boundaries will give the opportunity of using summarization, as it’s not possible to summarize network prefixes in normal link-state protocols because routers are supposed to have the same map topology of the entire network coincide in all neighbors.
• Area boundaries will also help to prevent fault containment by suppressing updates that take place when a change occurs in the network causing a flood of updates between routers. This also happens to be a weakness of link-state protocols: When connecting large-sized networks it is very difficult to avoid link-state database floods.

Basics of 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.

• 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.

Algorithm implementation:-

1. The very first step is to mark all nodes as unvisited,
2. Mark the picked starting node with a current distance of 0 and the rest nodes with infinity,?
3. Now, fix the starting node as the current node,
4. For the current node, analyze all of its unvisited neighbors and measure their distances by adding the current distance of the current node to the weight of the edge that connects the neighbor node and current node,
5. Compare the recently measured distance with the current distance assigned to the neighboring node and make it the new current distance of the neighboring node,
6. After that, consider all of the unvisited neighbors of the current node, mark the current node as visited,
7. If the destination node has been marked visited then stop, an algorithm has ended, and
8. Else, choose the unvisited node that is marked with the least distance, fix it as the new current node, and repeat the process again from step 4.?

Dijkstra’s Algorithm has several real-world use cases, some of which are as follows:

1. Digital Mapping Services in Google Maps: Many times we have tried to find the distance in G-Maps, from one city to another, or from your location to the nearest desired location. There encounters the Shortest Path Algorithm, as there are various routes/paths connecting them but it has to show the minimum distance, so Dijkstra’s Algorithm is used to find the minimum distance between two locations along the path. Consider India as a graph and represent a city/place with a vertex and the route between two cities/places as an edge, then by using this algorithm, the shortest routes between any two cities/places or from one city/place to another city/place can be calculated.
2. Social Networking Applications: In many applications, you might have seen the app suggests the list of friends that a particular user may know. How do you think many social media companies implement this feature efficiently, especially when the system has over a billion users. The standard Dijkstra algorithm can be applied using the shortest path between users measured through handshakes or connections among them. When the social networking graph is very small, it uses standard Dijkstra’s algorithm along with some other features to find the shortest paths, and however, when the graph is becoming bigger and bigger, the standard algorithm takes a few several seconds to count and alternate advanced algorithms are used.
3. Telephone Network: As we know, in a telephone network, each line has a bandwidth, ‘b’. The bandwidth of the transmission line is the highest frequency that the line can support. Generally, if the frequency of the signal is higher in a certain line, the signal is reduced by that line. Bandwidth represents the amount of information that can be transmitted by the line. If we imagine a city to be a graph, the vertices represent the switching stations, and the edges represent the transmission lines and the weight of the edges represents ‘b’. So as you can see it can fall into the category of shortest distance problem, for which the Dijkstra is can be used.

Thanks for Reading !! ??????

Keep Learning !! Keep Sharing !! ??