What is the count-to-infinity problem?

It is a distance-vector pathology in which, after a link fails, routers slowly increase their distance estimates to an unreachable destination by exchanging stale information, mistakenly believing a path still exists through each other. Mitigations include split horizon, poisoned reverse, and bounding the maximum distance.

Why are link-state and distance-vector both used?

They suit different scopes. Link-state protocols like OSPF give fast, loop-free convergence within a single administrative domain where sharing full topology is acceptable. Distance-vector and path-vector approaches scale better and reveal less internal detail across domains, which is why BGP uses a path-vector design between networks.

Routing Algorithms

Routing algorithms compute the paths that packets follow through a network, typically by finding least-cost routes over a graph of routers and links using either a global link-state view or a distributed, neighbor-by-neighbor distance-vector computation.

Gjeni temë me PaperMindSë shpejtiFind papers & topics

Tools & resources

Shkarko diapozitivat

Learn & explore

VideoSë shpejti

Definition

A routing algorithm is a procedure that determines least-cost (or otherwise preferred) paths through a network modeled as a weighted graph, producing the forwarding decisions that routers use to move packets toward their destinations.

Scope

This topic covers the algorithms that populate forwarding tables: the graph model of a network with link costs; link-state routing using Dijkstra's shortest-path algorithm with a globally shared topology; distance-vector routing using the distributed Bellman-Ford computation with neighbor exchanges; their convergence behavior and pathologies such as the count-to-infinity problem; and hierarchical routing for scalability. It treats the algorithms abstractly, leaving the concrete protocols (OSPF, RIP, BGP) and their intra/inter-domain organization to the routing-protocols topic.

Core questions

How is a network modeled as a weighted graph for routing?
How does a link-state algorithm compute shortest paths from a full topology view?
How does a distance-vector algorithm converge using only neighbor exchanges?
What are the convergence and stability problems, such as count-to-infinity, and how are they mitigated?
Why is routing made hierarchical, and how does that affect path optimality?

Key concepts

weighted network graph
least-cost paths
link-state routing
Dijkstra's algorithm
distance-vector routing
Bellman-Ford equation
count-to-infinity problem
split horizon and poisoned reverse
hierarchical routing

Key theories

Link-state routing (Dijkstra): Each router floods its link costs so that all routers share the full topology, then independently runs Dijkstra's algorithm to compute shortest paths; this converges quickly and predictably but requires global information exchange.
Distance-vector routing (Bellman-Ford): Routers exchange their current least-cost estimates to each destination with their neighbors and update via the Bellman-Ford equation; the computation is distributed and uses only local information but can converge slowly and suffer count-to-infinity.
Hierarchical routing: Because flat routing does not scale to the whole Internet, routers are grouped into regions (autonomous systems) with routing handled locally inside each region and summarized between them, trading some path optimality for scalability and administrative autonomy.

Clinical relevance

Routing algorithms determine how efficiently and reliably traffic flows: link-state algorithms underlie interior protocols such as OSPF that converge fast after failures, while distance-vector ideas appear in RIP and in the path-vector approach of BGP. Understanding their convergence behavior is essential for designing stable networks and diagnosing routing loops and slow recovery after link or router failures.

History

The shortest-path algorithms at the heart of routing predate computer networks: Bellman's and Ford's work on routing problems in the late 1950s and Dijkstra's 1959 shortest-path algorithm. As packet networks grew, these were adapted into distance-vector and link-state routing, and hierarchical structuring into autonomous systems made routing scale to the global Internet.

Debates

Link-state versus distance-vector routing: Link-state routing converges fast and avoids count-to-infinity but requires every router to hold the full topology and do more computation, while distance-vector is simpler and more local but can converge slowly and form transient loops; real networks combine both ideas at different scales.

Key figures

Edsger W. Dijkstra
Richard Bellman
Lester Ford

Seminal works

dijkstra1959
bellman1958
kurose2021

Frequently asked questions

What is the count-to-infinity problem?: It is a distance-vector pathology in which, after a link fails, routers slowly increase their distance estimates to an unreachable destination by exchanging stale information, mistakenly believing a path still exists through each other. Mitigations include split horizon, poisoned reverse, and bounding the maximum distance.
Why are link-state and distance-vector both used?: They suit different scopes. Link-state protocols like OSPF give fast, loop-free convergence within a single administrative domain where sharing full topology is acceptable. Distance-vector and path-vector approaches scale better and reveal less internal detail across domains, which is why BGP uses a path-vector design between networks.