Open Shortest Path First (OSPF)

Introduction: RIP and OSPF as different routing models

The Routing Information Protocol (RIP) exchanges information about known networks and metrics with its neighbors. A router builds its view of the topology from data received through successive neighbors, so a change can propagate slowly. RIP measures paths mainly by hop count and does not distinguish link bandwidth. Larger networks need a protocol that reacts faster and keeps a more complete description of the topology.

OSPF (Open Shortest Path First) uses a different model. Routers in one area flood information about their own interfaces and maintain a consistent topology database from it. Each router independently runs the SPF algorithm to calculate paths with the lowest total cost to known destinations. A consistent database reduces dependence on a single neighbor's view.

In IPv4, OSPF is carried directly in IP protocol 89 rather than in UDP. OSPF is a protocol, which can scale and converge faster than distance-vector protocols when the topology and configuration are suitable. It is an open, non-proprietary . It is used for routing within a single Autonomous System in enterprise and service-provider networks.

The OSPF metric: interface cost and bandwidth

RIP mainly compares routes by hop count. OSPF assigns each interface a metric called cost, then selects a path with the lowest sum of those values.

OSPF cost is a positive numerical value assigned to an interface. A lower cost makes a path preferable, and paths with the same cost can be used as equal-cost paths. The OSPF standard leaves the method of assigning cost to the implementation. Cisco IOS uses a default reference bandwidth of 100 Mbps and derives the interface cost from its bandwidth:

\text{Cost} = \frac{\text{Reference Bandwidth}}{\text{Interface Bandwidth}}

The Reference Bandwidth is configurable. The Interface Bandwidth describes the link rate, for example 10 Mbps for Ethernet, 100 Mbps for Fast Ethernet, and 1000 Mbps for Gigabit Ethernet. A path cost is the sum of the outgoing interface costs along that path. An explicitly configured interface cost can override the calculated value, so the reference setting should be consistent across routers. Implementations also round the resulting value according to their metric rules. The formula is an implementation convention, not a universal OSPF requirement.

Example: Choosing the Faster Path

Consider a packet sent from a network connected to Router A to a network connected to Router D. Assume that the configured reference bandwidth is 1 Gbps (1,000 Mbps).

Path 1 (A -> B -> D): This path uses Gigabit Ethernet links.
- Cost of link A->B: $\frac{1000 \text{ Mbps}}{1000 \text{ Mbps}} = 1$
- Cost of link B->D: $\frac{1000 \text{ Mbps}}{1000 \text{ Mbps}} = 1$
- Total Cost for Path 1 = 2
Path 2 (A -> C -> D): This path uses 10 Mbps Ethernet links.
- Cost of link A->C: $\frac{1000 \text{ Mbps}}{10 \text{ Mbps}} = 100$
- Cost of link C->D: $\frac{1000 \text{ Mbps}}{10 \text{ Mbps}} = 100$
- Total Cost for Path 2 = 200

OSPF selects the path with the lowest total cost, so this example selects Path 1. With this configuration, higher-bandwidth links receive a lower cost than 10 Mbps links. RIP could select another path when the hop count is lower.

OSPF operation: neighbors, LSDB, and SPF

OSPF builds a routing table in three related stages: discovering neighbors, synchronizing link-state information, and calculating routes from the LSDB.

1. Neighbor discovery and adjacency (the Hello protocol)

A router discovers neighbors by sending "Hello" packets through OSPF-enabled interfaces. Receiving packets from the other router and agreeing on parameters such as the area ID, network mask, and timers creates a neighbor relationship. Not every neighbor pair synchronizes a full database; the network type and router role determine whether a full adjacency is formed.

2. Building the map (link-state database exchange)

Once the required adjacency is formed, routers synchronize topology information. Link State Update packets carry . For example, an LSA can describe Router X's connection to Router Y through an interface with cost 10 and to Router Z through an interface with cost 5.

Routers flood LSAs within the scope defined by each LSA type. After synchronization, routers in the same OSPF instance and area should have a consistent Link-State Database (LSDB). Each router then has the topology information required for its area. LSAs carry sequence numbers, age, and a checksum, allowing routers to recognize newer versions and remove expired information.

3. Calculating the best routes (the SPF algorithm)

Using the LSDB, each router independently runs the Shortest Path First (SPF) algorithm, based on Dijkstra's algorithm. It places itself at the root of a tree and uses link costs to calculate paths with the lowest total cost to the destinations.

The SPF calculation produces a shortest-path tree. The router derives loop-free routes from it and installs them in the routing table. A consistent LSDB supports consistent decisions within the area. After a link failure, a new LSA is flooded, routers update their LSDBs, and they rerun the calculation, leading to network .

Scalability through OSPF areas

In a large network with thousands of routers, flooding LSAs and running SPF over a large LSDB increases memory and CPU use. Frequent changes to one link can also generate many updates. OSPF limits this scope by dividing the domain into areas.

OSPF uses a hierarchy based on areas. An area is a logical group of routers and networks with its own topology database. An ABR advertises summarized routes between areas through summary LSAs, while an ASBR describes external routes separately.

The two-level hierarchy

The OSPF domain includes a special Backbone Area (Area 0) and non-backbone areas. Non-backbone areas should connect to Area 0. If the physical backbone is partitioned, a virtual link can provide a logical connection. Area 0 carries inter-area traffic and distributes summarized information.

This structure provides several practical benefits:

Reduced overhead: Area-scoped LSAs are flooded within their own area. A router in Area 11 does not store the detailed topology of Area 10, reducing update traffic and LSDB size.
Faster SPF calculation: A smaller LSDB reduces the number of nodes SPF must examine and can lower router CPU use.
Limited propagation: A change to an area-scoped LSA does not require a topology calculation in every other area. The effects of a flapping link remain more local.

OSPF router roles

The area structure defines the following router roles:

Internal router: A router whose directly connected networks all belong to one area.
Backbone router: A router with an interface in Area 0. An ABR is also a backbone router when it connects to Area 0.
Area Border Router (ABR): A router attached to multiple areas. It keeps separate data for those areas, summarizes their topology, and advertises information between Area 0 and the other areas.
Autonomous System Boundary Router (ASBR): A router that exchanges information with another Autonomous System or redistributes routes from an external source, such as BGP, RIP, or static routes.

DR and BDR on multi-access networks

On a multi-access network such as Ethernet, many routers can share one segment. OSPF uses a Designated Router and a Backup Designated Router there to limit the number of full adjacencies.

Potential adjacency count

Assume that 10 routers are connected to one Ethernet segment. If every pair had to synchronize its database directly, the number of potential relationships would be $\frac{n(n-1)}{2}$ , or 45 for 10 routers. Full synchronization between every pair would increase the number of messages and repeated LSA exchanges.

Electing the DR and BDR

OSPF elects a Designated Router (DR) and a Backup Designated Router (BDR) for each multi-access segment. The election considers interface priority and uses the highest Router ID to break a tie. Keeping the same DR when possible avoids rebuilding adjacencies after every change.

Instead of every router synchronizing with every other router, the following model is used:

All other routers on the segment, called DROthers, form full adjacencies with the DR and BDR. They remain in 2-Way state with one another.
When a DROther sends an update, it uses multicast to reach the DR and BDR.
The DR floods that update to the other routers on the segment so their LSDBs remain synchronized.
The BDR maintains adjacencies and an up-to-date LSDB, so it can take over after a DR failure without forming every relationship again.

The DR and BDR arrangement limits the number of full adjacencies and the synchronization traffic on a multi-access network. A point-to-point link with two routers does not require a DR or BDR election.