"Dijkstra's algorithm begins with the source node and finds the least-cost path to every other node in the network. It is the algorithm that runs inside OSPF and IS-IS routers, re-executed every time the topology changes." -- Kurose & Ross, Computer Networking: A Top-Down Approach, 9th ed., Ch. 5.2
Lecture (50 min, first of two routing weeks)
1.1 The Problem Routing Solves
NET-101 introduced routing as "the process of finding a path between source and destination." That definition is correct but incomplete. Routing answers a harder question: given a constantly changing topology where routers fail, links go down, and traffic patterns shift, how does every router maintain a consistent, loop-free map of the network?
There are two fundamental approaches to answering this question, each represented by a family of protocols:
Link-state routing (OSPF, IS-IS): every router floods its local link information to all other routers. Every router then independently runs Dijkstra's algorithm on the complete topology map (the Link State Database, LSDB) to compute shortest paths. All routers converge to the same map; loop-free paths follow from the math.
Distance-vector routing (RIP, older IGRP): every router tells its immediate neighbors what it thinks the best path is to each destination. Neighbors update their own tables accordingly and tell their neighbors. The algorithm converges to correct paths, but only through iterative rounds of announcements, and it is susceptible to "counting to infinity" loops when topology changes occur.
Path-vector routing (BGP): an extension of distance-vector where the entire AS path is advertised rather than just a distance metric. BGP is the inter-AS protocol of the Internet; it is covered in Week 3-4. This week focuses on link-state.
1.2 OSPF: Open Shortest Path First
OSPF (RFC 2328 for OSPFv2, RFC 5340 for OSPFv3 for IPv6) is the dominant interior gateway protocol (IGP) in enterprise and service-provider networks.
OSPF router types:
| Type | Role |
|---|---|
| Internal Router | All interfaces in one area |
| Backbone Router | Has at least one interface in Area 0 |
| ABR (Area Border Router) | Connects Area 0 to a non-backbone area; maintains separate LSDBs for each area |
| ASBR (AS Boundary Router) | Redistributes routes from another routing protocol into OSPF |
OSPF neighbor establishment (the 3-step handshake):
- Down state: router sends Hello packets on all OSPF-enabled interfaces
- Init state: Hello received from a neighbor; neighbor's RID (Router ID) appears in its own Hello
- 2-way state: both routers see each other's RID in received Hellos
- Exstart/Exchange state: Master/Slave election; Database Description (DBD) packets exchange LSDB summaries
- Loading state: Link State Request (LSR) and Link State Update (LSU) fill in missing LSA details
- Full state: LSDBs are synchronized; adjacency established
The "3-step handshake" reference in Lab 1 refers to the Discovery (Hello exchange) + Database Exchange (DBD) + Loading (LSR/LSU/LSAck) sequence that brings two OSPF neighbors to Full state.
1.3 LSA Types and the LSDB
The LSDB is built from Link State Advertisements (LSAs). Key types:
| LSA Type | Generated by | Describes | Scope |
|---|---|---|---|
| Type 1 (Router LSA) | Every router | Router's own links + costs | Flood within area |
| Type 2 (Network LSA) | DR (Designated Router) | Multi-access network segment | Flood within area |
| Type 3 (Summary LSA) | ABR | Inter-area routes | Flood into areas from Area 0 |
| Type 4 (ASBR Summary) | ABR | Location of ASBR | Flood into areas from Area 0 |
| Type 5 (External LSA) | ASBR | External routes redistributed into OSPF | Flood entire OSPF domain |
The Designated Router (DR): on a multi-access segment (Ethernet), OSPF elects a DR and Backup DR (BDR). All routers form full adjacencies with the DR; other routers form only 2-way state with each other. The DR floods LSA updates on the multi-access segment, reducing the number of full adjacencies from O(n^2) to O(n).
1.4 Dijkstra's Algorithm and Cost Metric
OSPF uses cumulative link cost as its metric. The default cost formula is: cost = 10^8 / bandwidth (bps). A FastEthernet link (100 Mbps) has cost 1; a T1 (1.544 Mbps) has cost 64; a 1 Gbps link gets cost 1 (same as FastEthernet -- a well-known OSPF tuning issue; reference bandwidth should be raised on modern networks).
Dijkstra's shortest path tree:
- Place source node in SPF tree with cost 0
- For each neighbor of tree nodes, compute tentative cost = parent_cost + link_cost
- Add the lowest-cost tentative node to the tree
- Repeat until all nodes are added
The result is a tree rooted at the computing router giving the least-cost path to every destination. Every router independently computes its own tree from the same LSDB; consistent results produce loop-free forwarding.
1.5 OSPF Areas and Scalability
A flat OSPF domain with 1000 routers floods LSAs to all 1000 routers on every change. Every router runs Dijkstra across a 1000-node graph. This does not scale.
OSPF areas solve this by creating a two-level hierarchy:
- Area 0 (backbone): all non-zero areas must connect to Area 0 via ABRs
- Stub areas: do not accept Type 5 (external) LSAs; ABR injects a default route instead. Reduces LSDB size in edge areas with no external connectivity
- Totally stubby areas (Cisco proprietary): also block Type 3 summary LSAs; smallest possible LSDB for simple branch sites
- NSSA (Not So Stubby Area): allows ASBR to inject external routes into a stub area via Type 7 LSAs, which ABRs translate to Type 5 at the area boundary
Lab Preview
Lab 1 builds a 4-router OSPF multi-area topology in GNS3 (or Containerlab). You will observe LSDB synchronization from Hello packets to Full adjacency, run show ip ospf database to inspect LSA types, and deliberately force a link failure to observe reconvergence.
Homework
Reading (45 min): Kurose-Ross 9e Ch 5.2 (Routing Algorithms) and Ch 5.3 (Intra-AS Routing in the Internet: OSPF). For those with Doyle-Carroll Vol. 1: read Chapter 4 (OSPF Design), focusing on the area hierarchy model.
Hands-on (60 min): Using your Containerlab FRR setup, bring up a minimal two-router OSPF topology and confirm adjacency:
# topo-ospf2.clab.yml
name: ospf2
topology:
nodes:
r1:
kind: linux
image: frrouting/frr:latest
r2:
kind: linux
image: frrouting/frr:latest
links:
- endpoints: ["r1:eth1", "r2:eth1"]
containerlab deploy -t topo-ospf2.clab.yml
# Configure OSPF on both routers via vtysh
# Confirm: docker exec -it clab-ospf2-r1 vtysh -c "show ip ospf neighbor"
Document: what state does the adjacency reach? How many LSAs are in the LSDB? Run show ip ospf database and describe each LSA you see.
Toolchain Diary Entry
First-introduce this week: FRRouting (FRR), GNS3 advanced topologies
vtysh: FRRouting's unified CLI (analogous to Cisco IOS enable mode). Access inside a container: docker exec -it CONTAINER_NAME vtysh.
show ip ospf neighbor: lists all OSPF neighbors and their current state (Down, Init, 2-Way, Exstart, Exchange, Loading, Full).
show ip ospf database: lists all LSAs in the LSDB (by type, advertising router, and age).
show ip route ospf: shows only OSPF-derived routes in the routing table.
debug ospf hello: real-time Hello packet debugging. Warning: verbose on busy networks.
Key Terms
- IGP: Interior Gateway Protocol; routing protocol for within a single autonomous system
- LSDB: Link State Database; the complete topology map each OSPF router maintains; synchronized across all routers in an area
- LSA: Link State Advertisement; a typed topology record flooded by OSPF routers to build the LSDB
- DR / BDR: Designated Router / Backup Designated Router; elected on multi-access segments to reduce adjacency count
- ABR: Area Border Router; connects Area 0 to a non-backbone area; summarizes routes between areas
- Convergence: the process by which all routers in an OSPF domain reach agreement on the topology after a change
- Cost: OSPF's metric; default 10^8/bandwidth; lower is preferred; directly affects SPF tree construction