Routing algorithms and convergence
Goals and model
Compute shortest routes, distinguish forwarding from routing, and explain how distributed information converges. Assume nonnegative link costs and explicitly stated topology; costs need not be physical distances. Forwarding selects an outgoing interface for a packet using the installed table. Routing builds those tables. A shortest path minimizes the sum of link costs, not necessarily the number of routers.
1. Shortest paths with Dijkstra
Link-state routing gives each router a topology database assembled from flooded link-state advertisements. Each router runs a shortest-path algorithm with itself as root. Dijkstra repeatedly finalizes the unsettled vertex with smallest tentative distance, then relaxes its outgoing edges: d(v)=min(d(v),d(u)+w(u,v)). Once finalized, a vertex's distance is optimal under nonnegative edge costs. A predecessor tree can be converted into next-hop entries by following each path from the source to its first neighbor. Equal-cost paths may give multiple valid trees; a unique next hop requires a tie-breaking rule.
Worked undirected topology: AB=2, AC=5, BC=1, BD=6, CD=2. From A, initialize B=2,C=5,D=infinity. Finalize B: C becomes3 via B and D becomes8 via B. Finalize C: D becomes5 via C. Finalize D. Paths are A-B, A-B-C, A-B-C-D; all use first hop B. The direct edge AC exists but does not make it the cheapest route. Check final distance5 against path sum2+1+2.
2. Distance vectors and Bellman–Ford
A distance-vector router exchanges destination costs with its neighbors, rather than requiring the entire graph. The update at x is D_x(y)=min over neighbors v of [c(x,v)+D_v(y)]. Store the minimizing neighbor as next hop. A neighbor's advertised distance excludes the local link to that neighbor. Directly connected destinations and self-distance0 supply initial information; unreachable destinations begin at infinity. Updates may be periodic or triggered and do not all arrive simultaneously.
Example: X has neighbor costs c(X,A)=3 and c(X,B)=1. For destination Z, A advertises4 and B advertises8. Candidate costs are7 and9; choose A with cost7. If B later advertises2, X changes to B with cost3. A smaller advertisement is not alone sufficient: the local link cost matters. Under a stable topology, suitable assumptions about message delivery and updates allow convergence; intermediate tables can be inconsistent.
3. Failures, loops and count to infinity
Consider A-B-C with unit links and destination A. Initially B advertises1 and C advertises2. After AB fails, B may receive C's stale advertisement2 and infer a false route of3 via C, even though C's route uses B. C then learns4 via B, B learns5, and so on. This is count to infinity: bad news can propagate slowly because an advertisement does not carry its whole dependency path.
Split horizon suppresses advertisement of a route back on the interface from which it was learned. Poison reverse advertises that route back with infinite metric. Triggered updates reduce delay after changes. These mechanisms mitigate failures but poison reverse does not eliminate every loop involving three or more routers. A finite protocol infinity bounds counting but also limits usable path metrics. Do not replace a mathematical infinity with a particular numeric protocol threshold unless the question specifies that protocol.
Link-state routing floods changed local information and recomputes shortest paths. It avoids the particular neighbor-distance counting mechanism, but it is not instantaneously loop-free during all asynchronous transitions. Routers can temporarily have different databases or install new tables at different times. Convergence time includes failure detection, information dissemination, computation and installation.
4. Flooding safely
Uncontrolled flooding copies a packet to all eligible outgoing links except its arrival link. Without limits and duplicate suppression, cycles create repeated copies. A hop limit bounds lifetime; a source identifier plus sequence number allows a router to recognize already processed information. Link-state advertisements also need freshness handling so an older version cannot overwrite a newer one. Reliable dissemination uses acknowledgments/retransmission in protocols that specify them. Flooding is a dissemination technique, not another name for broadcasting on one Ethernet LAN.
With first-seen-only forwarding, a router processes each identified advertisement once and forwards it on the allowed links. Exact transmission counts depend on whether duplicate arrivals are acknowledged, whether reverse links are excluded, and how simultaneous arrivals are ordered. State those rules before counting. A shortest-path tree can reduce data replication, but constructing and maintaining that tree is a separate task.
5. Routing design distinctions and exam traps
Static routes are configured; dynamic protocols adapt through exchanges. Routing within an administrative system and routing between systems solve different policy problems. A mathematically shortest path need not satisfy an operator's policy, and interdomain policy routing is not simply global Dijkstra. The syllabus focus here is shortest paths, flooding, distance vectors and link state; detailed protocol configuration is outside this lesson.
Separate topology knowledge from algorithm output: link-state advertisements describe links; a distance vector describes destination distances. For a numerical question write the neighbor candidates, compare sums and retain the first hop. For convergence questions draw the actual next-hop dependencies, not just metrics. Positive metrics do not prevent transient forwarding loops. Hop limits terminate looping packets but do not repair routing tables.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. In the worked graph, what is A’s minimum cost to D?
A. 3 B. 5 C. 7 D. 8
Answer: B
A: 3 reaches C, not D.
B: 2+1+2=5 via B and C.
C: The path A-C-D costs7 but is not minimum.
D: A-B-D costs8 and is longer.
P02. X has neighbor link costs 2 to P and 5 to Q. Their advertised distances to Z are 8 and 1. Which route wins?
A. Via P, cost8 B. Via P, cost10 C. Via Q, cost1 D. Via Q, cost6
Answer: D
A: Local cost2 was omitted.
B: 10 is valid but exceeds6.
C: Local cost5 was omitted.
D: Compare2+8=10 with5+1=6.
P03. What does poison reverse advertise to the neighbor used as next hop for a route?
A. The route with infinite metric B. The full topology database C. Only the destination MAC D. The route with metric zero
Answer: A
A: This prevents that neighbor from treating the advertised route as a finite alternative through this router.
B: Topology flooding is link-state behavior.
C: MAC resolution is not poison reverse.
D: Zero falsely suggests no cost.
P04. Which pair directly supports duplicate suppression during flooding?
A. Destination address and packet size B. Source identifier and sequence number C. Link cost and interface speed D. Checksum and propagation delay
Answer: B
A: Many distinct packets share destination and size.
B: Together they identify a particular source advertisement instance.
C: These do not identify repeated advertisements.
D: Neither pair uniquely identifies an advertisement instance.
P05. Which statement about link-state convergence is correct?
A. All routers always install routes simultaneously B. A hop limit repairs inconsistent tables C. Temporary forwarding loops can occur during changes D. No topology information is exchanged
Answer: C
A: Update and installation timing can differ.
B: Hop limits bound packet lifetime, not table inconsistency.
C: Different database or installation times can produce transient inconsistency.
D: Link-state information is disseminated.
P06. Which assumption supports Dijkstra’s usual finalization argument?
A. Every link has equal cost B. The graph must be a tree C. Every destination is one hop away D. Link costs are nonnegative
Answer: D
A: Unequal nonnegative costs are allowed.
B: Cycles are allowed.
C: Multihop paths are supported.
D: Negative edges can invalidate finalization of the current smallest tentative distance.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Computer Networks syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in