Exercises — Link state routing — OSPF, Dijkstra

(c) its own LSP = {its ID, list of (neighbor, cost)}. It floods only its local roads, not computed distances (that would be distance-vector) and not full routing tables. Each router then assembles all LSPs into the same map.

Protocol number 89; Open Shortest Path First. It is an intra-domain IGP (interior gateway protocol), see OSPF Areas for how it scales.

(i) LS, (ii) DV, (iii) DV. See Distance Vector Routing and Bellman–Ford Algorithm for why DV suffers count-to-infinity while LS does not.

We repeatedly pick the smallest unfinalized $d$, lock it, relax its edges. Non-negative weights make this greedy step safe.

• $d[C]$ drops $5\to 3$ because A→B→C ($2+1$) beats direct A→C ($5$).
• $d[E]$ drops $9\to 7$ because relaxing D→E gives $6+1=7$, beating C→E's $9$.
• Final: $d[B]=2,d[C]=3,d[D]=6,d[E]=7$.

Trace each shortest path back to its first hop out of A:

• To C: path A→B→C ⇒ next hop B.
• To D: path A→B→C→D ⇒ next hop B.
• To E: path A→B→C→D→E ⇒ next hop B.

A stores only destination → next-hop, never the whole path (see Routing Table vs Forwarding Table). Every destination here begins with the hop to B.

Nothing can lower a finalized distance in a valid Dijkstra run — unless a negative edge exists. The candidate $8<10$ means a path reached X more cheaply after X was locked, which is only possible if some edge on that path had negative weight. Conclusion: the graph violates Dijkstra's non-negativity assumption; you must use Bellman–Ford Algorithm instead.

Let edges be: S→A = 2, S→B = 5, A→B = −4.

• Dijkstra from S: $d[A]=2,d[B]=5$. It finalizes A first (min = 2), then relaxes A→B: $d[B]=\min (5,2+(-4))=\min (5,-2)=-2$. Here B is corrected to −2, but consider instead B finalized before A's edge is relaxed in a variant where B is reached first cheaply. The clean failure: with S→B = 1, S→A = 2, A→B = −4: Dijkstra pops B first (min = 1), locks $d[B]=1$, then can never apply A→B = −4 which would give $2-4=-2$.
• Correct shortest $d[B]=-2$; Dijkstra returns $d[B]=1$. Wrong, because B was locked before the cheaper negative path appeared.

This is exactly why the greedy invariant needs $w\ge 0$.

(a) B and C each detect the dead link (missed HELLOs), each builds a new LSP with a higher sequence number, and floods it. Every router replaces its old LSP-from-B and LSP-from-C with the newer ones, rebuilds an identical map, and reruns Dijkstra. No count-to-infinity — everyone recomputes on the same fresh map.

(b) New edges: A–B=2, A–C=5, B–D=7, C–D=3, C–E=6, D–E=1 (B–C gone).

Final: $d[B]=2,d[C]=5,d[D]=8,d[E]=9$. Losing the cheap B–C shortcut raised C from 3→5 and cascaded downstream.

Trade-off: areas cut flooding scope and LSP-database size (better scaling), but a router no longer has the full map — it sees summarized routes between areas, so paths can be slightly sub-optimal. See OSPF Areas; across domains you switch to BGP entirely.

Let $S$ be the finalized set, and suppose $u$ is the popped minimum. Assume for contradiction a shorter true path $P$ to $u$ exists with length $L<d[u]$.

• $P$ starts inside $S$ (at the source) and ends at $u\notin S$, so it must cross the boundary: let $y$ be the first node on $P$ not in $S$, reached from $x\in S$.
• When $x$ was finalized, its edge to $y$ was relaxed, so $d[y]\le d[x]+w(x,y)=(\text{prefix of }P\text{ up to }y)$.
• Since all remaining edges of $P$ from $y$ to $u$ are $\ge 0$, the whole path satisfies $L\ge (\text{prefix up to }y)\ge d[y]$.
• But $u$ was chosen as the minimum, so $d[u]\le d[y]$. Chaining: $d[u]\le d[y]\le L<d[u]$ — a contradiction.

Hence no shorter path exists; $d[u]$ is final. The non-negativity was used exactly at "remaining edges $\ge 0$."

Edges: A–D = 10 (direct, 1 hop), A–B = 3, B–C = 3, C–D = 3.

• Direct: cost 10, 1 hop.
• Detour A→B→C→D: cost $3+3+3=$ 9, 3 hops.
• $9<10$: the longer-hop path wins. Dijkstra finalizes D at $d[D]=9$ (via C), and A's forwarding next hop to D is B. This shows hop count ≠ cost; OSPF optimizes cost, not hops.

• After a link fails, how many flooding passes does LS need to reconverge, roughly? ::: One reflood of the new LSPs, then each router reruns Dijkstra once.
• Can a finalized Dijkstra distance ever decrease? ::: No — unless a negative edge exists (then use Bellman–Ford).
• Does the cheapest path always have the fewest hops? ::: No; cost and hop-count are independent (Problem 5.2).
• What exactly does non-negativity guarantee in the proof? ::: The tail of any alternative path can't be negative, so it can't undercut the popped minimum.