The idea
Link state routing says every router needs the full topology, but that does not mean every router floods its entire routing table at every neighbour. OSPF’s trick is that each router only ever describes itself — its own links and their metrics — and lets the flooding process assemble those self-descriptions into a full picture at every router independently.
How it works
OSPF overview
Each router sends only the portion of the routing table that describes the current state of its own links to the internetwork:
- Information on attached interfaces
- Metrics used (minimum delay, maximum throughput, etc.)
- Other variables
Every router collects this from every other router and builds a picture of the entire network in its own routing table. A Shortest Path First (SPF) algorithm — Dijkstra’s algorithm, or link state routing generally — is then used to calculate the shortest path to each node from that assembled picture.
Aside
The lecture points to an external video walkthrough of the OSPF protocol for a further look at the mechanics. That content is not reproduced on this page — the mechanism above and the worked exercise below are what the lecture’s own slides state directly.
How it works
The Shortest Path First algorithm
OSPF sends hello packets to its neighbours and receives their hello packets in return. These also act as a keep-alive, letting routers know that their neighbours are still functional — a failed router can be detected quickly, and the network’s topology altered appropriately once it is.
Each router calculates a shortest-path tree, with itself as the root. That shortest-path tree, in turn, yields a routing table.
Worked example
Configuring routers with cost 64
Every link in this small network is configured with OSPF cost 64. Trace
the SPF computation from R0.
Step 1.
N' = {R0}.R1andR2are direct neighbours ofR0, each at cost64viaR0.R3is not a direct neighbour, so its cost isinf.Step 2.
R1joinsN'(it is one of the minimum-cost candidates).R2’s cost is unchanged at64viaR0— going throughR1would cost64 + 64 = 128, which is worse.R3’s cost updates to128viaR1, sinceR1’s own link toR3also costs64.Step 3.
R2joinsN'.R3’s cost stays at128viaR1— a path throughR2does not improve on it.
Resulting SPF table:
| Step | N’ | D(R1), p(R1) | D(R2), p(R2) | D(R3), p(R3) |
|---|---|---|---|---|
| 1 | R0 | 64, R0 | 64, R0 | inf |
| 2 | R0, R1 | — | 64, R0 | 128, R1 |
| 3 | R0, R1, R2 | — | — | 128, R1 |
Resulting routing table, as the lecture states it:
| Destination | Next-hop | OSPF cost |
|---|---|---|
30.0.0.0 | 10.0.0.2 | 128 |
40.0.0.0 | 20.0.0.2 | 128 |
10.0.0.0 | Directly connected | — |
20.0.0.0 | Directly connected | — |
AnswerR1 and R2 are each directly reachable from R0 at cost 64; R3 is reachable at cost 128 via R1
Aside
The lecture does not state explicitly which router in the topology this
final IP-addressed table belongs to — it follows straight on from the
abstract R0/R1/R2/R3 computation, and the two “directly connected”
entries (10.0.0.0 and 20.0.0.0) suggest it is the routing table of one
of the interior routers rather than R0 itself. Treat the table as the
lecture’s own stated answer to the exercise rather than something derived
independently on this page.
How it works
The Packet Tracer exercise
This lecture is accompanied by a Cisco Packet Tracer file,
OSPF_lab_Ed_1.pkt. The lecture directs students to download it and
complete the accompanying Ed lesson to practise configuring OSPF routes
hands-on.
Check yourself
- OSPF routers advertise only their own link state, not their whole table — the full topology is assembled from everyone’s self-description.
- Hello packets are the keep-alive; a missing one signals a failed neighbour.
- Each router computes its own shortest-path tree, rooted at itself, which yields its routing table.
- In the cost-64 exercise, direct neighbours cost 64; a two-hop path costs 128, and Dijkstra’s minimum rule never lets a worse path overwrite a better one already found.
In the exam
- Say precisely what an OSPF router sends: the state of its own attached links and their metrics, not the whole routing table. This is a common point of confusion with plain link state flooding described generically.
- Hello packets are for neighbour liveness, not for carrying routing information itself — do not conflate them with LSPs.
- Trace the cost-64 exercise the same way as any Dijkstra example: apply
the
min(D(v), D(w)+c_{w,v})rule at each step, and note when an update does not change an existing estimate. - OSPF cost is just Dijkstra’s algorithm on the assembled topology — if a question asks “what algorithm does OSPF use,” the answer is Dijkstra’s / Shortest Path First, by name.