link-state routing

A routing method in which every router floods a description of its own links and computes paths from the shared map.

It is the family of OSPF and IS-IS. Each router keeps a link-state database that is identical on every router of an area, and runs Dijkstra's algorithm on it with itself as root. Changes travel as flooded advertisements of each router's local state.

RFC 2328 describes the database as a collection of each router's local state, its usable interfaces and reachable neighbours, distributed by flooding. All routers run the same algorithm in parallel and each builds a tree of shortest paths with itself as root; only the next hop from that tree is used for forwarding. The standard calls this a departure from the Bellman-Ford base of the older TCP/IP routing protocols.

Two safeguards keep the map consistent. A link is used only if the router at the far end lists a link back, and every advertisement carries a sequence number, a checksum and an age, which decide which copy is newer. RFC 4593 recalls why this matters: errors in a router of the original ARPANET link-state algorithm created three instances of one advertisement, which flooded continuously until the whole network was power cycled.

Scale comes from hierarchy, areas in OSPF and levels in IS-IS. A router keeps a separate database for each area it joins, and between OSPF areas only summaries pass, which FRRouting describes as distance-vector routing between areas. FRRouting also notes that the calculation is mostly negligible on modern CPUs; the real burden is flooding and the database as an area grows.

Also known as: link state, link-state protocol, link-state database, lsdb

Sources

← All glossary entries