Free lesson · Computer Networking

Link State Routing Ospf

Easy10 min readnetworkingcomputer-networkstcp-ip

Building a Complete Map

Distance vector protocols like RIP have a fundamental limitation: each router knows only what its neighbors tell it. This indirect, secondhand information propagates slowly and creates opportunities for routing loops and the count-to-infinity problem you learned about in the previous topic. Link-state protocols take a completely different approach.

OSPF (Open Shortest Path First) is a link-state routing protocol. Instead of sharing distance estimates with neighbors, each router discovers its own directly connected links, measures their cost, and floods this information to every other router in the network. Once every router has the same complete topology map, each independently runs Dijkstra's shortest-path algorithm to compute the optimal path to every destination.

The result is dramatically better than distance vector: faster convergence (seconds instead of minutes), no count-to-infinity problem (Dijkstra's algorithm on a complete map cannot produce loops), and a more intelligent metric (link cost based on bandwidth rather than simple hop count). OSPF is the dominant interior gateway protocol (IGP) in enterprise and service provider networks worldwide, and has been for over two decades. It is standardized in RFC 2328 for OSPFv2 (IPv4) and RFC 5340 for OSPFv3 (IPv6).

The Link-State Approach

The link-state approach works in five phases:

Phase 1 - Neighbor Discovery

When an OSPF router starts up, it sends Hello packets on all OSPF-enabled interfaces. Hello packets are sent to the multicast address 224.0.0.5 (AllSPFRouters). Neighboring routers that receive the Hello respond, and the two routers establish a neighbor relationship - they acknowledge each other's existence and begin exchanging routing information.

OSPF Hello packets serve three purposes: discovering neighbors, negotiating parameters (hello interval, dead interval, area ID), and acting as keepalives. The default hello interval is 10 seconds, and the dead interval is 40 seconds (4 missed hellos). If a router stops receiving hellos from a neighbor for 40 seconds, it declares the neighbor down and triggers a topology change.

Hello packets also carry the router's priority (used in DR/BDR election), its known neighbor list, and authentication information. Both routers must agree on certain parameters - hello interval, dead interval, area ID, subnet mask, and authentication - before they become neighbors. A mismatch in any of these parameters prevents the neighbor relationship from forming, which is one of the most common OSPF troubleshooting issues.

Phase 2 - Adjacency Formation

Not all OSPF neighbors become fully adjacent (exchange complete routing information). On broadcast networks like Ethernet, OSPF elects a Designated Router (DR) and a Backup Designated Router (BDR). All other routers form full adjacencies only with the DR and BDR, not with each other. This reduces the number of adjacencies from O(n²) to O(n) on networks with many routers, significantly reducing the routing update traffic.

The DR election is based on priority (configurable, default 1) and router ID (tiebreaker). The router with the highest priority becomes DR; second highest becomes BDR. If a DR fails, the BDR is promoted to DR and a new BDR is elected. The DR/BDR mechanism is specific to broadcast network types - on point-to-point links (connections between exactly two routers), the election is unnecessary and the two routers form a full adjacency directly.

Understanding the DR/BDR concept matters because it explains a common operational surprise: when the DR fails on a busy network segment, there is a brief convergence period as the BDR takes over and new adjacencies form. In data center environments with many routers on a shared segment, the DR role carries significant forwarding responsibility.

Phase 3 - Link-State Advertisement (LSA) Exchange

Each router generates a Link-State Advertisement (LSA) describing its directly connected links and their costs. An LSA contains:

• The router's ID (typically its highest IP address or a manually configured ID)
• A list of connected links (interfaces)
• The cost of each link
• A sequence number (incremented with each update)
• An age timer (LSAs expire after 60 minutes if not refreshed)

The router floods its LSA to all adjacent neighbors, which re-flood it to their adjacent neighbors, continuing until every router in the OSPF area has received the LSA. This is the flooding process - it ensures that every router has complete, consistent topology information.

Phase 4 - LSDB Construction

Each router stores all received LSAs in its Link-State Database (LSDB). The LSDB is the complete map of the network - every router, every link, every cost, and every network prefix. Because every router receives the same set of LSAs through flooding, every router's LSDB is identical - this consistency is the cornerstone of loop-free routing. This is the fundamental advantage over distance vector routing: every router has the same complete and current information, not secondhand summaries from neighbors.

Phase 5 - SPF Calculation

Each router independently runs Dijkstra's Shortest Path First (SPF) algorithm on its LSDB to compute the shortest path tree rooted at itself. The result is the optimal path from this router to every other network in the OSPF domain. These computed paths are installed in the routing table and subsequently in the forwarding table (FIB).

Because every router has the same LSDB and runs the same algorithm, the computed paths are consistent across all routers - traffic follows a single, loop-free shortest path. If multiple equal-cost paths exist, OSPF supports ECMP (Equal-Cost Multi-Path) routing, distributing traffic across all shortest paths for load balancing.

graph TD
    subgraph OSPFProcess["OSPF Operation Phases"]
        direction TB
        P1["Phase 1<br/>Neighbor Discovery<br/>(Hello packets)"]
        P2["Phase 2<br/>Adjacency Formation<br/>(DR/BDR election)"]
        P3["Phase 3<br/>LSA Exchange<br/>(Flood link info)"]
        P4["Phase 4<br/>LSDB Construction<br/>(Complete topology map)"]
        P5["Phase 5<br/>SPF Calculation<br/>(Dijkstra's algorithm)"]
        P1 --> P2 --> P3 --> P4 --> P5
    end

    style P1 fill:#4f46e5,stroke:#4338ca,color:#fff
    style P2 fill:#6366f1,stroke:#4f46e5,color:#fff
    style P3 fill:#7c3aed,stroke:#6d28d9,color:#fff
    style P4 fill:#8b5cf6,stroke:#7c3aed,color:#fff
    style P5 fill:#22c55e,stroke:#16a34a,color:#fff

This diagram shows the five operational phases of OSPF. Phase 1 is neighbor discovery using Hello packets. Phase 2 is adjacency formation with DR and BDR election. Phase 3 is the exchange of Link-State Advertisements, where each router floods its link information to all others. Phase 4 is LSDB construction, where each router builds a complete topology map from all received LSAs. Phase 5 is the SPF calculation, where each router runs Dijkstra's algorithm on the LSDB to compute shortest paths to every destination.

OSPF Cost Metric

OSPF uses a cost metric based on link bandwidth. The formula is:

Cost = Reference Bandwidth / Interface Bandwidth

The default reference bandwidth is 100 Mbps (10^8 bps). This produces costs like:

Notice that 10 Gbps, 1 Gbps, and 100 Mbps all have cost 1 with the default reference bandwidth - they are treated as equal. In modern networks where 10 Gbps and 100 Gbps links are common, administrators typically increase the reference bandwidth (e.g., to 100 Gbps = 10^11 bps) to differentiate between high-speed link types.

The cost metric is why OSPF makes better routing decisions than RIP. A path through two 10 Gbps links (cost 2) is preferred over a path through one 10 Mbps link (cost 10), even though the first path has more hops. RIP would choose the single-hop 10 Mbps path because it only counts hops, not bandwidth. OSPF correctly identifies that the faster path is better even if it traverses more routers.

OSPF Areas

Large OSPF networks are divided into areas to improve scalability. Without areas, every router in the network would need to store the complete LSDB and rerun SPF for every topology change anywhere in the network. In a network with thousands of routers, this would consume excessive memory (storing thousands of LSAs) and CPU (running Dijkstra's algorithm on an enormous graph after every change).

Area 0 - The Backbone

Every OSPF network has a backbone area called Area 0 (or Area 0.0.0.0). All other areas must connect to Area 0 - either directly or through a virtual link. Area 0 is the transit area that routes traffic between other areas.

Non-Backbone Areas

Other areas (Area 1, Area 2, etc.) contain routers and networks that are logically grouped together. LSA flooding is contained within each area - a topology change in Area 1 does not trigger SPF recalculation on routers in Area 2. This isolation is the primary scalability benefit of areas.

Area Border Routers (ABRs)

Routers that connect two or more areas are called Area Border Routers (ABRs). They have interfaces in multiple areas and maintain separate LSDBs for each. ABRs summarize routing information between areas - instead of flooding detailed LSAs from one area into another, they advertise compact summary routes. This reduces LSDB size and SPF computation in each area.

The area hierarchy means that routers within an area have a detailed map of their own area but only summary information about other areas. This is a deliberate trade-off: slightly less optimal inter-area routing in exchange for dramatically better scalability.

OSPF Convergence

When a link fails in an OSPF network, convergence follows a rapid sequence:

1. The router connected to the failed link detects the failure (either through interface state change or missed Hello packets)
2. The router generates a new LSA reflecting the topology change
3. The LSA is flooded to all routers in the same area
4. Each router that receives the new LSA updates its LSDB
5. Each router reruns the SPF algorithm on the updated LSDB
6. New shortest paths are computed and installed in the forwarding table

This entire process typically completes in under 1 second with tuned timers, compared to RIP's multi-minute convergence. The speed comes from three factors: immediate failure detection (interface state changes are instant), efficient flooding (LSAs propagate in milliseconds across the area), and efficient recalculation (modern routers run Dijkstra's algorithm on thousands of nodes in milliseconds).

For environments requiring even faster convergence, BFD (Bidirectional Forwarding Detection) can detect link failures in as little as 50 milliseconds, triggering OSPF reconvergence before the OSPF hello dead timer would have expired.

graph TD
    subgraph OSPFAreas["OSPF Area Hierarchy"]
        direction TB
        subgraph Area0["Area 0 (Backbone)"]
            ABR1["ABR 1"]
            ABR2["ABR 2"]
            BB1["Backbone<br/>Router"]
            ABR1 --- BB1 --- ABR2
        end

        subgraph Area1["Area 1"]
            R1["Router"] --- R2["Router"]
            R2 --- ABR1
        end

        subgraph Area2["Area 2"]
            R3["Router"] --- R4["Router"]
            R4 --- ABR2
        end
    end

    style ABR1 fill:#4f46e5,stroke:#4338ca,color:#fff
    style ABR2 fill:#4f46e5,stroke:#4338ca,color:#fff
    style BB1 fill:#7c3aed,stroke:#6d28d9,color:#fff
    style R1 fill:#8b5cf6,stroke:#7c3aed,color:#fff
    style R2 fill:#8b5cf6,stroke:#7c3aed,color:#fff
    style R3 fill:#a78bfa,stroke:#8b5cf6,color:#fff
    style R4 fill:#a78bfa,stroke:#8b5cf6,color:#fff

This diagram shows the OSPF area hierarchy. Area 0, the backbone, contains two Area Border Routers and a backbone router connecting them. Area 1 contains two routers, with one connecting to ABR 1 in the backbone. Area 2 contains two routers, with one connecting to ABR 2 in the backbone. Traffic between Area 1 and Area 2 must transit through the backbone via the ABRs. Each area maintains its own Link-State Database, and the ABRs summarize routing information between areas.

OSPF in Practice

OSPF is deployed across a wide range of environments:

Enterprise campus networks use OSPF to connect buildings, floors, and data centers within a single organization. The area hierarchy maps naturally to physical topology - each building or floor can be its own area, with Area 0 forming the backbone that connects them.

Service provider networks use OSPF (or IS-IS) as their IGP to route traffic within their autonomous system. The large number of routers in a service provider network makes areas essential - without them, every topology change would trigger SPF recalculation on every router.

Data center networks increasingly use OSPF or eBGP in leaf-spine (Clos) topologies. Each rack has a leaf switch running OSPF, connected to multiple spine switches. OSPF's ECMP support distributes traffic across the redundant spine paths automatically.

OSPF vs RIP - A Direct Comparison

Interview: OSPF knowledge signals depth in System Design interviews:

"How does internal routing work in a large data center?" - Data centers typically run OSPF or eBGP between top-of-rack switches and spine switches. OSPF with areas scales well for medium-sized data centers. Larger hyperscale data centers (AWS, Google, Meta) often use eBGP in a Clos fabric topology because it offers simpler configuration and better multi-path support than OSPF.

"Why does OSPF converge faster than distance vector protocols?" - OSPF detects failures immediately (interface state changes), floods the information to all routers in the area simultaneously (not hop-by-hop), and each router independently computes new paths using Dijkstra's algorithm on its complete topology map. There is no iterative convergence - one SPF run produces the correct result.

"What is Dijkstra's algorithm and where is it used in practice?" - Dijkstra computes the shortest path from a source node to all other nodes in a weighted graph. In networking, OSPF uses it to compute routing tables. In System Design, it appears in map routing services, network path computation, and any system that needs optimal paths through a graph.

What Comes Next

The next topic covers BGP (Border Gateway Protocol) - the routing protocol that connects autonomous systems (organizations) across the internet. While OSPF handles routing within a single organization's network, BGP handles routing between organizations - making it the protocol that literally holds the internet together.

Exercise: Starter: Draw a five-router network on paper with varying link bandwidths (10 Mbps, 100 Mbps, 1 Gbps). Calculate the OSPF cost for each link using the default reference bandwidth of 100 Mbps. Then run Dijkstra's algorithm by hand from one router to find the shortest path to every other router. Does the shortest path always have the fewest hops?

Intermediate: Research the difference between OSPF LSA types (Type 1 Router LSA, Type 2 Network LSA, Type 3 Summary LSA, Type 5 External LSA). What information does each carry? Why are different types needed? How do ABRs use Type 3 LSAs to summarize inter-area routing information?

Advanced: Compare OSPF and IS-IS (Intermediate System to Intermediate System), the other major link-state IGP. Both use Dijkstra's algorithm and achieve similar results. Why do some large service providers and hyperscale data centers prefer IS-IS over OSPF? Research the differences in TLV-based extensibility, multi-topology support, and the historical relationship between IS-IS and the OSI protocol stack. How does Facebook (Meta) use IS-IS in its data center fabric?

Back to Computer Networking