Shortest-path routing: 22-Elec-B4 Information Technology Networks, May 2014, Q5

Question 5: Shortest-path routing (25 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. The undirected network printed with the question, whose ten nodes and fourteen weighted edges are transcribed from the figure below; all costs are positive.

[Figure not reproduced: Figure 5.1 — The network as printed, with the edge costs read from the examination figure: A–B 1, A–C 5, B–D 5, B–E 2, C–E 1, D–E 1, D–F 3, E–G 1, F–G 1, F–H 4, F–I 2, G–I 2, H–J 3, I–J 2. See the official exam paper.]

Find. (a) the least-cost path and its cost from A to each of the other nine nodes, obtained by a correctly executed Dijkstra iteration; and (b) the smallest increase in the cost of link C–E that alters that answer, together with the alteration it produces.

Approach. Run Dijkstra's algorithm: maintain a set $S$ of nodes whose least cost is settled and a tentative label $d(v)$ for every other node; at each iteration move the unsettled node of least label into $S$ and relax the edges leaving it. Then, for part (b), treat $d(\mathrm{C})$ as a function of the C–E cost and find where the two candidate routes to C cross over.

(a) Dijkstra's algorithm from node A

The algorithm is stated once and then applied. At every iteration the node $u \notin S$ with the smallest label is made permanent, and each neighbour $v$ of $u$ is relaxed:

$$ d(v) \leftarrow \min\bigl(d(v),\; d(u) + w(u,v)\bigr) $$

with the predecessor of $v$ set to $u$ whenever the second term wins. Initially $d(\mathrm{A}) = 0$ and every other label is $\infty$.

Part (a), iteration 1 — make A permanent and relax its edges. $S = \{\mathrm{A}\}$. A's neighbours are B and C, so $d(\mathrm{B}) = 0 + 1 = 1$ (via A) and $d(\mathrm{C}) = 0 + 5 = 5$ (via A). All other labels remain $\infty$.
Iteration 2 — B is the smallest label, at 1. $S = \{\mathrm{A,B}\}$. Relaxing B's edges: $d(\mathrm{D}) = 1 + 5 = 6$ (via B) and $d(\mathrm{E}) = 1 + 2 = 3$ (via B). C stays at 5.
Iteration 3 — E is the smallest label, at 3, and it improves three neighbours. $S = \{\mathrm{A,B,E}\}$. Now $d(\mathrm{C}) = \min(5,\ 3+1) = 4$ (via E, which displaces the direct A–C link), $d(\mathrm{D}) = \min(6,\ 3+1) = 4$ (via E, displacing B) and $d(\mathrm{G}) = 3 + 1 = 4$ (via E). This is the iteration that does most of the work, and it is where a hand solution most often goes wrong by forgetting to re-examine C and D.
Iterations 4–6 — C, D and G are tied at 4, so any order is valid. Taking C first: C's only other neighbour is A, already permanent, so nothing changes. Taking D next relaxes D–F to give $d(\mathrm{F}) = 4+3 = 7$ (via D). Taking G then gives $d(\mathrm{F}) = \min(7,\ 4+1) = 5$ (via G, displacing D) and $d(\mathrm{I}) = 4 + 2 = 6$ (via G). The tie is real and harmless: Dijkstra guarantees the same final labels whichever tied node is chosen, because no negative edges exist and a settled label can never later be improved.
Iteration 7 — F, at 5. $d(\mathrm{H}) = 5 + 4 = 9$ (via F), and F–I offers $5 + 2 = 7$, which does not beat I's existing label of 6, so I keeps its route through G.
Iteration 8 — I, at 6. $d(\mathrm{J}) = 6 + 2 = 8$ (via I).
Iterations 9 and 10 — J at 8, then H at 9. From J, $8 + 3 = 11$ does not improve H's label of 9, so H keeps its route through F. H is the last node to settle and the whole set is now permanent: $$ \boxed{d = \{\mathrm{A}\,0,\ \mathrm{B}\,1,\ \mathrm{E}\,3,\ \mathrm{C}\,4,\ \mathrm{D}\,4,\ \mathrm{G}\,4,\ \mathrm{F}\,5,\ \mathrm{I}\,6,\ \mathrm{J}\,8,\ \mathrm{H}\,9\}} $$

Reading the predecessors back from each node gives the shortest-path tree, drawn in Figure 5.2. Note how the tree tells the story of the network: almost everything leaves A through the cheap A–B–E corridor, so the expensive direct A–C link and the B–D link are never used at all.

Figure 5.2 — The shortest-path tree rooted at A (heavy lines), with each node's least cost from A. Unused links are shown dashed: A–C (5), B–D (5), D–F (3), F–I (2) and H–J (3) are all more expensive than the route the tree already provides.

Table 5.1 — Dijkstra iteration table: the label of each node after each node is made permanent (a dash means the node is already settled)
Iteration	Made permanent	B	C	D	E	F	G	H	I	J
1	A (0)	1	5	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$
2	B (1)	—	5	6	3	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$
3	E (3)	—	4	4	—	$\infty$	4	$\infty$	$\infty$	$\infty$
4	C (4)	—	—	4	—	$\infty$	4	$\infty$	$\infty$	$\infty$
5	D (4)	—	—	—	—	7	4	$\infty$	$\infty$	$\infty$
6	G (4)	—	—	—	—	5	—	$\infty$	6	$\infty$
7	F (5)	—	—	—	—	—	—	9	6	$\infty$
8	I (6)	—	—	—	—	—	—	9	—	8
9	J (8)	—	—	—	—	—	—	9	—	—
10	H (9)	—	—	—	—	—	—	—	—	—

Table 5.2 — Final results, Question 5(a): shortest path from A to every node
Destination	Least-cost path	Cost	Cost re-added from its own links
B	A–B	1	1
C	A–B–E–C	4	$1+2+1$
D	A–B–E–D	4	$1+2+1$
E	A–B–E	3	$1+2$
F	A–B–E–G–F	5	$1+2+1+1$
G	A–B–E–G	4	$1+2+1$
H	A–B–E–G–F–H	9	$1+2+1+1+4$
I	A–B–E–G–I	6	$1+2+1+2$
J	A–B–E–G–I–J	8	$1+2+1+2+2$

(b) Sensitivity of the solution to the cost of link C–E

The question is a sensitivity analysis, and it is answered by asking which entries of the part (a) solution can depend on $w_{\mathrm{CE}}$ at all. Only two paths in the whole tree touch C: the path to C itself, and any path that passes through C on the way somewhere else. Inspecting Table 5.2, no path routes through C — C is a leaf of the tree, which makes sense because C's only other neighbour is A, the source. So the entire question reduces to $d(\mathrm{C})$, and every other row of Table 5.2 is unaffected no matter how large $w_{\mathrm{CE}}$ becomes.

Part (b) — write $d(\mathrm{C})$ as a function of the link cost. C has exactly two neighbours, A and E. Since $d(\mathrm{E}) = 3$ does not itself depend on the C–E link (E is reached from B), the least cost to C is the better of the two candidate routes: $$ d(\mathrm{C}) = \min\bigl(\underbrace{5}_{\text{direct A--C}},\ \underbrace{3 + w_{\mathrm{CE}}}_{\text{via E}}\bigr) $$ At the printed value $w_{\mathrm{CE}} = 1$ this is $\min(5, 4) = 4$, the answer from part (a).
Find the crossover. The route through E stops being strictly better when $3 + w_{\mathrm{CE}} \ge 5$, that is when $$ w_{\mathrm{CE}} \ge 5 - 3 = 2 $$ so the critical link cost is 2, reached from the printed value of 1 by an $$ \boxed{\text{increase of } 1 \text{ unit}} $$ At exactly $w_{\mathrm{CE}} = 2$ the two routes tie at cost 5 and the solution is no longer unique; for any $w_{\mathrm{CE}} > 2$ the direct link is strictly better and the tree definitely changes.
State the change that is made. C's parent in the shortest-path tree moves from E to A: the path becomes the direct A–C link, the cost to C rises from 4 to 5, and the edge C–E leaves the tree while A–C joins it. Because C carries no transit traffic, $d(\mathrm{C})$ is then capped at 5 and cannot rise further however expensive C–E becomes — raising it to 100 or to infinity produces exactly the same tree. No other entry of Table 5.2 changes at any value.

It is worth saying what this means operationally, since that is the point of asking. Link costs in a real link-state protocol such as OSPF are set by the network administrator, usually as a decreasing function of link bandwidth, and are re-advertised whenever they change. The calculation above is exactly what an OSPF router does when it receives a new link-state advertisement: it re-runs Dijkstra over the whole topology database. This example shows why that is usually cheap in its effect — a cost change on one leaf edge moved one entry of the forwarding table, and only past a definite threshold. It also shows the flip side: a change of a single unit on the wrong edge, one that carries transit traffic, would have re-parented every node downstream of it.

Table 5.3 — Final results, Question 5(b)
Quantity	Value
Printed cost of link C–E	1
Critical cost at which the two routes to C tie	2
Minimum increase that changes the solution	1 unit (strictly, any increase beyond 1)
Change made	C is reached by the direct link A–C instead of A–B–E–C
Cost to C after the change	5 (up from 4), and capped there for any larger cost
Other entries of the solution affected	none — C carries no transit traffic

Topic. Link-state routing: Dijkstra's shortest-path algorithm and the sensitivity of the resulting tree to a single link cost.

Key relations. Relaxation $d(v) \leftarrow \min(d(v), d(u) + w(u,v))$ applied to every neighbour of the newly-permanent node $u$; the algorithm terminates after $|V|$ iterations with $d(v)$ equal to the least cost from the source; for a leaf node reachable two ways, $d(v) = \min(w_{\text{direct}},\ d(\text{parent}) + w_{\text{alt}})$, so the crossover cost is $w^{*} = w_{\text{direct}} - d(\text{parent})$.

Why this works. Dijkstra's correctness rests on a single observation: with non-negative edge costs, the smallest tentative label in the frontier cannot be improved by any path that has not yet been explored, because such a path would have to leave the settled set through some other frontier node whose label is already at least as large, and would then only get longer. That is why a node's label may be made permanent as soon as it is the minimum, and why the algorithm never revisits a settled node. The same observation explains the sensitivity result: since a settled label never depends on edges outside the tree that were more expensive, raising the cost of a tree edge can only affect the subtree beneath it — and if that subtree is a single leaf, the effect is one table entry.

Common pitfall. Failing to re-examine a node that already has a finite label — here C was labelled 5 through the direct link at iteration 1 and must be improved to 4 at iteration 3 — which is the mistake that costs most of the fifteen marks, since the question warns that credit depends on the algorithm being correctly followed. Second, in part (b), stopping at "an increase of 1" without saying that at exactly 2 the two routes tie and only beyond 2 is the change unambiguous. Third, forgetting to check whether any other node routes through the affected node before declaring the rest of the tree unchanged.

Source. Leon-Garcia and Widjaja, Communication Networks, 2nd ed., §7.4 (shortest-path routing algorithms); Kurose and Ross, Computer Networking, 8th ed., §5.2; Tanenbaum and Wetherall, Computer Networks, 5th ed., §5.2.2; RFC 2328 for OSPF's use of the algorithm.

Question 5 of 5: Shortest-path routing

Question 5: Shortest-path routing (25 marks)

(a) Dijkstra's algorithm from node A

(b) Sensitivity of the solution to the cost of link C–E