Link state routing — OSPF, Dijkstra: Question bank

Two words you need before we start, both from the parent note:

LSP (Link State Packet) = a router's own postcard: its ID plus a list of (neighbor, cost) pairs. Nothing about far-away routers — only its own roads.
Relaxation = the update $d [v] \leftarrow min (d [v], d [u] + w (u, v))$ : "is going through $u$ a cheaper way to reach $v$ than what I knew before?"

Two symbols this page leans on — pin them down now so no reveal surprises you:

The picture below shows both at once — the growing shaded blob $S$ , and the nodes still sitting at $\infty$ outside it.

And here is the geometric heart of why non-negative weights make the greedy pick safe (referenced by TF7, WHY2, EC3) — trace the red detour and see it can only be longer:

Finally, an example LSP and a flooding wavefront so the abstract "flood your postcard" is concrete (referenced by TF1, TF5, WHY3):

True or false — justify

TF1. In link state routing, a router floods its entire computed routing table to the network.

False. It floods only its own LSP (its ID and directly-attached links, as in figure s03). Sharing computed distances is what distance-vector does — link state shares raw topology.

TF2. After flooding completes, every router in the same area holds an identical topology map.

True. That is the whole point: identical maps mean everyone runs Dijkstra on the same graph, so no two routers disagree and packets never loop.

TF3. Dijkstra can be safely used with negative link costs as long as there is no negative cycle.

False. Even without a negative cycle, greedy finalization can lock in a distance that a later negative edge would have shrunk. Use Bellman–Ford Algorithm for negative weights.

TF4. OSPF ever needs negative link costs, so it secretly uses Bellman–Ford.

False. OSPF costs are always positive (derived from bandwidth), so Dijkstra is valid and that is exactly what OSPF runs.

TF5. Flooding without sequence numbers still terminates because packets eventually get old.

False. Without a way to recognise "I've already seen the newest copy," duplicates bounce forever (imagine the wavefront in figure s03 echoing back on itself). Sequence numbers let a router keep only the newest LSP and drop the rest; age is a backup to expire stale info.

TF6. Link state converges faster than distance-vector because each router computes alone from the full map.

True. There is no round-by-round "convincing" of neighbors, so the count-to-infinity slow-convergence of Distance Vector Routing does not occur.

TF7. Once a node is finalized (added to the set

S

of done nodes), relaxing it again could still lower its distance.

False. A finalized node's distance is provably optimal — that's the greedy invariant of figure s02, valid because all edges are

\geq 0

. Relaxing it again can never improve it.

TF8. The forwarding table stores the complete shortest path to each destination.

False. It stores only destination → next-hop. Forwarding is hop-by-hop, so a router only needs the first neighbor; the rest of the path lives in the other routers' tables. See Routing Table vs Forwarding Table.

TF9. A HELLO packet's job is to carry topology information across the whole network.

False. HELLO only discovers neighbors and detects dead links on a single link. Topology is spread by flooding LSPs, not by HELLOs.

TF10. Two routers can compute different next-hops for the same destination and this is still loop-free.

True — as long as both used the same map. Each router correctly picks its own next hop on its own shortest path; the paths chain together consistently. Inconsistent maps (mid-flooding) are the only loop risk.

Spot the error

SE1. "Dijkstra picks the node with the largest tentative distance next, to finalize the hardest cases first."

Error: it picks the smallest tentative distance. The greedy proof only works for the minimum — that node cannot be reached more cheaply by any detour through unfinalized nodes.

SE2. "We initialize

d [s] = \infty

and

d [others] = 0

, then relax."

Error: it is reversed. The source starts at

d [s] = 0

(zero cost to reach yourself) and every other node at

\infty

("no route known yet").

SE3. "Relaxing edge

(u, v)

means

d [v] \leftarrow d [u] + w (u, v)

Error: it must be a min:

d [v] \leftarrow min (d [v], d [u] + w)

. Overwriting unconditionally could replace a better known distance with a worse one.

SE4. "When an LSP arrives, forward it out on every link including the one it came in on."

Error: forward on all links except the incoming one. Echoing it back wastes bandwidth and feeds duplicate copies straight back to the sender.

SE5. "A router keeps the LSP with the lowest sequence number per source, since lower means original."

Error: it keeps the highest sequence number — that is the newest, most current view of that source's links. Lower numbers are stale.

SE6. "Because distance-vector and link state both output shortest paths, they share the same failure modes."

Error: they share the goal, not the mechanism. DV shares computed distances (Bellman–Ford, prone to count-to-infinity); LS shares raw topology (each runs Dijkstra alone). Different info in, different failures out.

SE7. "OSPF runs on top of TCP for reliable LSP delivery."

Error: OSPF runs directly over IP (protocol 89) and implements its own reliable flooding with acknowledgements — it does not use TCP.

Why questions

WHY1. Why does link state avoid count-to-infinity entirely rather than just reducing it?

Because no router ever trusts a neighbor's summary of far-away distances. Everyone computes from raw topology, so there is no chain of belief to slowly poison — the failure mode simply doesn't exist.

WHY2. Why is the greedy step in Dijkstra correct only for non-negative weights?

Any alternative path to the min-distance node must exit the finalized set

S

and then travel

\geq 0

-weight edges (the red detour in figure s02), so it can only be longer or equal. A negative edge could make that detour shorter, destroying the guarantee.

WHY3. Why does a router flood its LSP to the whole network instead of just its neighbors?

So every router can assemble the complete map. If LSPs stopped at neighbors, distant routers would never learn the topology and couldn't run Dijkstra correctly — the wavefront in figure s03 has to reach the whole graph.

WHY4. Why store next-hop instead of the full path in the forwarding table?

Forwarding is hop-by-hop and stateless per packet — a router only decides the immediate neighbor. The downstream routers repeat the decision, so the full path emerges without anyone storing it.

WHY5. Why do LSPs carry an age field on top of sequence numbers?

Sequence numbers order updates, but if a router dies and stops re-announcing, its old LSP must eventually vanish. Age counts down and expires stale topology so dead routers don't linger on the map.

WHY6. Why does skipping already-finalized nodes (those in

S

) during relaxation not change correctness?

Nodes in

S

already hold their optimal distance and can never improve, so relaxing toward them is simply wasted work — the answer is identical either way, just slower.

WHY7. Why can two routers safely run Dijkstra independently and still agree?

Because reliable flooding gives them identical input graphs. Dijkstra is deterministic, so identical maps yield mutually consistent shortest-path trees — hence loop-free routing without coordination.

Edge cases

EC1. A destination is unreachable from the source (disconnected graph) — what does Dijkstra report?

Its distance stays at the initial

\infty

(the "no route known yet" placeholder): no relaxation ever lowered it because no path exists. The router marks it unreachable rather than inventing a route.

EC2. Two paths to a destination have exactly equal cost — what does OSPF do?

It can install both as equal-cost multipath (ECMP), splitting traffic across them. Neither is "wrong"; the tie is a feature, used for load sharing.

EC3. A link has cost

0

— is Dijkstra still valid?

Yes. Zero is non-negative, so the greedy invariant of figure s02 still holds (an alternative path can only add

\geq 0

). Only negative edges break it.

EC4. Only one router exists (no neighbors). What LSP does it flood, and what does Dijkstra return?

Its LSP lists an empty neighbor set. Dijkstra returns

d [s] = 0

for itself and

\infty

("unreachable") for everyone else — there's nothing to reach.

EC5. A link goes down mid-flood, so routers briefly hold different maps — is routing loop-free during this window?

Not guaranteed. Transient loops or drops can occur until flooding re-synchronises every map. Loop-freedom is a property of consistent maps, which only holds after convergence.

EC6. During flooding, a router receives an LSP with a sequence number equal to the one it already has. What does it do?

It treats the copy as a duplicate and discards it without re-forwarding — same sequence means same information, so re-flooding would only echo noise.

Active recall

Recall Rapid-fire traps (hide answers)

Does a router flood its table or its LSP? ::: Its LSP (own links only), never the computed table.
Smallest or largest tentative distance finalized next? ::: Smallest — that's the greedy invariant.
Zero-cost edge: Dijkstra ok? ::: Yes, zero is non-negative.
Unreachable node's final distance? ::: Stays $\infty$ .
Keep highest or lowest LSP sequence number? ::: Highest (newest).
Loop-free during re-flooding? ::: No — only after all maps converge.
What is $S$ ? ::: The set of finalized (locked-in) nodes in Dijkstra.

Connections

Yeh note Hinglish mein padho →
Distance Vector Routing — the count-to-infinity contrast in TF6, SE6
Dijkstra's Algorithm — greedy invariant behind TF7, SE1, EC3
Bellman–Ford Algorithm — the negative-weight fix in TF3, TF4
Flooding — sequence numbers and age in TF5, WHY5, EC6
OSPF Areas — why "same area" matters in TF2
Routing Table vs Forwarding Table — next-hop-only storage in TF8, WHY4
BGP — the inter-domain protocol OSPF is not