How OSPF works

What is OSPF?

Open Shortest Path First (OSPF) is an Interior Gateway Protocol used to distribute routing information within an Autonomous System (AS). Or, in layman terms, it is a dynamic routing protocol used to distribute routes within internal networks.

So... what the hell are those other things? Well, for starters, an Autonomous System refers to a collection of independent networks that are controlled by a single entity, such as an ISP. Interior Gateway Protocols (IGPs) are used to route traffic within each network of an AS, such as a company's LAN.

There are three types of IGPs, including

• Distance-vector routing protocols
• Link-state routing protocols
• Hybrid routing protocols

A distance-vector (DVR) routing protocol calculates the best route based on distance. Distance is usually measured in hops, though the metric could be measured in delay, packets lost, or something similar. If the distance metric is a hop, then each time a packet passes through a router, a hop is considered to have traversed. The route with the least number of hops to a given network is concluded to be the best route to that network. Some examples of distance-vector routing protocols include:

• Routing Information Protocol (RIP)
• Interior Gateway Routing Protocol (IGRP)

A link-state routing protocol, also called shortest-path-first protocols, have a complete picture of the network topology. Hence, they have a greater idea about the whole network than any distance vector protocol. Three separate tables are created on each link state routing enabled routing. One table is used to hold details about directly connected neighbors, another is used to hold the topology of the entire internetwork, and the last one is used to hold the actual routing table. Link state protocols send information about directly connected links to all the routers in the network. Some include:

• OSPF
• IS-IS (Intermediate System to Intermediate System)

There also exists hybrid routing protocols in the sense that they used aspects of both distance vctor and link state protocols. 

• EIGRP (Enhanced Interior Gateway Routing Protocol) is one example of a hybrid routing protocol.

So... what exactly is OSPF, then? And what's with all this preamble? Well, it's important to understand the distinction between IGPs and EGP (exterior gateway protocols--routes things over the Internet, basically), the concept of autonomous systems, and the difference between distance-vector and link-state protocols, because OSPF was made due to the need for a high functionality non-proprietary IGP for the TCP/IP protocol family. Now that you know these things, I can move forward.

OSPF was made to used link-state technology due to the limitations of distance-vector-based routing. The most common distance-vector protocol used back in the day was RIP (routing information protocol). Its limits included:

• 15 hop limit
• No support for Variable Length Subnet Masks (VLSM). Basically, it doesn't recognize subnets at all, resulting in large broadcast domains. Divides routes into "classes". Class, A, B, C, etc.
• Slow route convergence, spanning potentially minutes
• Hold-down and garbage collection and information time-outs for not recently received information is inappropriate for large networks, and can cause routing inconsistencies
• No concept of network delays and link costs, since routes are decided on hop counts. 
• Networks are flat networks, and there is no concept of boundaries. With the intro of classless routing and intelligent use of aggregation and summarization, RIP networks have fallen behind.

Enhancements were made to RIP via RIPv2, which addressed issues with lack of VLSM support, authentication, and multicast routing updates, but it wasn't enough. OSPF, on the other hand, fixes most of the issues presented:

• No hop count limit
• VLSM support, and is used with IP address allocation
• OSPF uses multicast to send link-state updates. This ensures resource consumption on routes that do not listen to OSPF packets. Updates are only sent in case routing changes occur instead of periodically, ensuring efficient bandwidth usage
• Better convergence times, since routing changes are propagated instantly and not periodically
• Allows for better load balancing
• Allows for logical definition of networks where routers are divided into areas. This limits the explosion of link state updates over the whole network. Also provides a mechanism to aggregate routes and decrease the unnecessary propagation of subnet information
• Allows for routing authentication through different methods of password authentication
• Allows for the transfer and tagging of external routes injected into an Autonomous System. Helps keep track of external routes injected by exterior protocols such as BGP.

In essence, OSPF is more efficient, complex, and secure due to it using a link-state algorithm to calculate its routes instantly. It's the most commonly used dynamic routing protocol for internal networks, and is still used today in many network topologies. But due to its changes and improvements, configuration is more complex alongside troubleshooting, and there is more CPU overhead. 

How does OSPF work?

As stated previously, OSPF uses a link-state algorithm known as the Shortest Path First Algorithm. It is used to build and calculate the shortest path to all destinations. The shortest path is calculated with the Dijkstra algorithm.

The algorithm itself is complicated. This is a high level look at the various steps in 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 through floods. Each router that receives a link-state update must 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, destinations, associated cost, and next hop to reach those destinations form the IP routing table.
4. In case changes in the OSPF network do not occur, such as cost of a link or a network which is added or deleted, OSPF remains very quiet. Changes are communicated through link-state packets, and the Dijkstra algorithm is recalculated 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 has its own view of the topology even though all the routers build a shortest path tree which uses the same link-state database. These sections indicate what is involved in the creation of a shortest path tree.