Compute paths from topology or neighbor estimates

In a simplified single-area link-state view, routers advertise local connectivity and costs. Flooding spreads newer information so each router can construct a topology database and compute shortest paths from itself. OSPF uses this family of mechanisms, with areas and route types adding structure beyond our small graph. A link cost is an administrative metric, not inherently a measured millisecond delay. A path minimizing summed cost can therefore differ from the path with the fewest hops or smallest measured latency.

Given nonnegative link weights, shortest-path computation compares complete accumulated costs rather than greedily choosing the cheapest immediate link. If A reaches B at cost two, B reaches D at three, and A reaches D directly at nine, the path through B costs five and beats the direct edge. Each router installs its own next hop toward the resulting path. Equal-cost alternatives can exist, but the way packets use them depends on forwarding behavior and configuration.

A distance-vector router can estimate its distance to a destination by adding the cost to a neighbor to that neighbor's advertised distance. The minimum over eligible neighbors gives the update. This is a distributed version of Bellman-Ford reasoning. A router need not receive the complete topology to make the calculation, but its neighbors' estimates may be stale or depend indirectly on itself. That dependence explains why a removed route can appear to remain reachable through a chain of mistaken beliefs.

RIP illustrates a concrete distance-vector protocol with hop-count metrics, a finite unreachable value, and mechanisms such as split horizon and triggered updates. These details matter: an abstract recurrence alone is not a complete protocol. Count-to-infinity is the gradual escalation of mutually dependent incorrect estimates after a failure. Split horizon and poison reverse address important cases, yet should not be described as universal instantaneous loop elimination for every topology and timing. Examine the actual protocol and failure sequence.

After a failure, detection, advertisement, propagation, computation, and forwarding installation occur at different devices. A stable final shortest-path solution does not imply safe intermediate forwarding. Distinguish a control-plane database that has learned a change from hardware that has installed it. Also separate an administrative metric change from a physical link failure: detection and information distribution differ. A useful test records packet loss and actual next hops throughout the transition, not only the final route table.

The optimization lab provides a limited analogy for iterative adjustment: change step size η and initial value x₀ in the scalar recurrence xₙ=(1−η)ⁿx₀. With a nonzero x₀, predict alternating contraction for η=1.5 and growth for η above two, then step through it. This is gradient descent on a quadratic, not Bellman-Ford, OSPF, or a routing convergence proof. The lesson is to demand a mechanism-specific stability argument; a graph that appears to settle under one update rule cannot certify a different distributed protocol.