Skip to content

Link-state Routing

Distribute local connectivity state so network nodes can calculate routes from a topology view.

Version
v1 · 2026-10-03 · History
Domain-specific #
13392
Domain group
Applied Sciences & Engineering
Origin domain
Computer Science & Software Engineering
Subdomains
Computer Networking, Routing Protocols → Computer Science & Software Engineering

Core Idea

Link-state routing is a way for network participants to determine routes by sharing information about local connectivity and computing paths from the resulting topology view. A participant originates descriptions of links or neighbor reachability within a defined routing scope; that information is disseminated; each participant calculates destination routes or next hops from the information it has received. The distinctive move is to distribute link state for local route calculation, rather than simply pass each neighbor's current destination-distance estimate onward.[1][2][3][4]

OSPF is a well-documented instance, not the identity itself. RFC 2328 describes OSPF routers distributing local state through flooding, maintaining an area-relevant link-state database, and constructing shortest-path trees. IS-IS exchanges Level 1 and Level 2 link-state packets under different packet and domain rules. OLSR uses selected multipoint relays in mobile ad hoc networks to reduce flooding, and can calculate routes from advertised links that do not include every physical connection. What transfers is the information architecture and route-computation role—not one identical full-network map, packet format, hierarchy or algorithm implementation.[1][2][3]

A sound claim about agreement is conditional. Once compatible participants have sufficiently synchronized relevant state and applied the protocol's route rules, their resulting paths can be assessed for consistency. RFC 2328 speaks of newly calculated loop-free OSPF routes after a convergence period; it does not license a promise that distributed forwarding never loops or drops traffic while information is inconsistent.[1]

Structural Signature

Sig role-phrases: network routing scope → locally originated connectivity report → scoped dissemination and freshness → local topology-derived route calculation → forwarding-state outcome; hierarchy and relay optimization are variants.

  • Network participants and scope. Routers or mobile nodes have destination identities and an advertisement domain within which local state will inform routes. An OSPF area, an IS-IS level and an OLSR mobile ad hoc routing domain are not interchangeable scopes.[1][2][3]
  • Locally originated connectivity state. A participant reports relevant attached links, neighbors, costs or selected reachability. The report need not enumerate every physical link: OLSR's selected MPR links are a counterexample to a universal full-map definition. Replace local-link information with destination-distance summaries alone and the information architecture changes.[1][3][4]
  • Distribution and state currency. Reports reach the participants that calculate routes within the applicable scope; changes must be distinguished from older information. OSPF floods LSAs and has recency machinery, IS-IS uses LSPs and sequence-number PDUs, and OLSR restricts relaying through MPRs. Those are different realizations of dissemination, not a single mandatory packet scheme.[1][2][3]
  • Local topology-derived calculation. Each participant turns the received connectivity information into routes or next hops under its metric and protocol rules. OSPF constructs per-router shortest-path trees. The constitutive role is local path derivation from distributed link state, not the requirement that every protocol run a particular Dijkstra implementation.[1][2][3]
  • Forwarding-state result. Route calculation produces state used by forwarding toward network destinations. Merely collecting link reports for visualization is topology monitoring rather than link-state Routing. Forwarding a packet using an already installed next hop is the separate execution step.[1]
  • Optional scale control. Areas, levels, summary information or selected relays can bound control traffic and computation, but no one hierarchy design is necessary to the genus. A single-area OSPF deployment still uses the core link-state process.[1][2][3]

What It Is Not

It is not OSPF itself. The frozen discovery candidate names OSPF, an IP interior-gateway protocol specified by RFC 2328; OSPF has protocol-specific LSA types, area behavior and packet rules. IS-IS and OLSR retain the broader pattern with materially different packet, domain and flooding designs. OSPF should therefore remain a narrower identity for separate adjudication, not become an alias for this entry.[1][2][3]

It is not distance-vector routing. RFC 2453 describes the RIP family as exchanging destination distances or route entries with adjacent participants. Link-state routing instead distributes local connectivity descriptions so route calculators can build their own topology-derived decisions. Both are routing and both exchange information, but the kind of shared information and computation differ.[4][1]

It is not a guarantee of one complete, identical map everywhere. Even OSPF hides area interiors from other areas, while OLSR may advertise only the selected reachability needed for its routes. Nor is it a guarantee of loop-free forwarding throughout updates; network participants may temporarily hold different information during convergence.[1][3]

Scope of Application

The pattern applies where multiple network nodes must maintain paths as local connectivity changes and where their control plane can distribute link descriptions for local route calculation. OSPF's interior IP routing within an autonomous system is one setting; its areas can limit topological detail outside the area. RFC 1195 extends IS-IS for IP and dual environments using Level 1/Level 2 link-state packets. OLSR places the pattern in a mobile ad hoc network, where selected relays reduce control transmissions and advertised topology can be intentionally partial.[1][2][3]

The scope is not every use of graph shortest paths. A single central service computing paths from a database has topology and a path algorithm but lacks the distributed local-state advertisement architecture. A static default route is Routing without link-state exchange. At the other extreme, the term does not itself specify wireless robustness, OSPF-area design, security against false announcements or a particular failure-recovery time; those claims require separate protocol and deployment evidence.[1][3]

Clarity

Ask who originates what and who computes what. In OSPF the router describes its local usable interfaces and neighbors, floods that state, and every participant calculates routes from its relevant database. In RIP a router exchanges destination-distance entries with neighbors. The words “both protocols share route information” hide the crucial distinction until the information item is typed as link description versus destination cost.[1][4]

Likewise, “everyone has the map” is too coarse. A topology view is sufficient for the routes computed within its declared scope, not necessarily a full physical inventory of an entire autonomous system. OSPF areas and OLSR MPR selectors show two different reasons that a participant may not possess every link. “Shortest path” should also name the metric and route scope rather than imply literal geometric distance or one algorithmic implementation.[1][3]

Manages Complexity

The abstraction compresses many protocol particulars into a five-part reasoning chain: local link information, distribution, state view, local calculation, and routing-table result. This makes independent implementations comparable without claiming their packet layouts or hierarchy coincide. It also separates failure modes: a wrong route may reflect a bad local report, delayed dissemination, different state versions, a calculation rule, or an installed forwarding entry.[1][2][3]

That compression does not make scaling free. More advertised detail gives richer local route views but costs control traffic and state; area/level boundaries or OLSR MPRs reduce some burden while limiting or selecting what is shared. The pattern therefore helps locate the precise control-plane tradeoff rather than treating every optimization as a departure from link-state routing.[1][2][3]

Abstract Reasoning

Given a claimed instance, identify the participating network and advertisement scope. Check that its reports originate from local connectivity or selected neighboring reachability, that the reports propagate to the route calculators, and that each calculator uses the received information to select destination paths or next hops. If a device merely forwards according to an existing table, the observed operation is forwarding, not route construction; if it receives only neighbors' destination metrics, test the distance-vector alternative.[1][4]

Then distinguish steady-state and transition reasoning. When an OSPF link changes, a revised state must propagate and each router must recompute; the RFC's loop-free statement is expressly after convergence. During the update, a mismatch between local views may matter. Finally ask whether each view contains all needed information for the route guarantee being claimed: OLSR shows that “all physical links” is an unnecessary requirement, but a selected subset must still support the protocol's intended destinations.[1][3]

Knowledge Transfer

The relation transfers literally from OSPF's area-scoped IP routing to IS-IS's level-scoped IP/OSI routing and OLSR's mobile ad hoc routing. In each, local connectivity information is distributed and individual nodes compute routes. What does not transfer automatically are OSPF's LSA formats, IS-IS level semantics, OLSR's MPR selector rule, or a universal control-traffic bound. Cross-protocol comparison works at the typed role level.[1][2][3]

A broader pattern—distribute local state and independently derive a decision from a sufficiently aligned shared view—could be posed as a future-prime question. A database replication scheme or logistics graph may resemble it, but without network destinations, route maintenance and forwarding-state output it is an analogy, not an instance of this domain-specific entry.

Examples

Canonical: OSPFv2 inside an IP routing domain

RFC 2328 specifies OSPF routers advertising local interface and neighbor state, flooding it, and calculating a shortest-path tree with each router as root. In an area configuration, the interior topology is scoped and border routers summarize information for other areas. The protocol's route-change statement says loop-free routes are calculated after convergence, not during every intermediate control-plane state. This is the original Wikipedia candidate's narrower protocol identity, used here as evidence for the broader pattern rather than renamed as its alias.[1]

Mapped back: Network participants and scope → OSPF routers in an applicable area/autonomous-system context; locally originated connectivity state → router LSAs describing interfaces and neighbors; distribution and state currency → LSA flooding and recency handling; local topology-derived calculation → per-router shortest-path tree plus applicable inter-area rules; forwarding-state result → routes and next hops; optional scale control → OSPF area boundaries and summaries.

Applied: OLSR mobile ad hoc routing

RFC 3626 specifies proactive link-state routing among mobile ad hoc nodes. A node selects multipoint relays from eligible neighbors; selected relays forward topology control information, lowering transmissions compared with unrestrained flooding. MPR-selector announcements supply sufficient selected links for OLSR's described shortest-path routes, without claiming that every possible neighbor link is advertised to everyone. This case tests the identity against mobile topology and selective dissemination instead of OSPF's fixed-area design.[3]

Mapped back: Network participants and scope → OLSR nodes in the ad hoc routing domain; locally originated connectivity state → selected neighbor/MPR reachability declarations; distribution and state currency → periodic control information forwarded by selected MPRs; local topology-derived calculation → route calculation from neighbor and topology information; forwarding-state result → next hops toward destinations; optional scale control → MPR optimization instead of OSPF areas.

Structural Tensions

T1: Topology detail versus control cost. More reported links can give route calculators additional path choices or redundancy, but create more dissemination and storage work. OLSR deliberately uses selected MPR information for its routes, whereas OSPF maintains richer area state. Diagnostic: Which link information is actually needed to sustain the route or path-quality claim?[1][3]

T2: Fast adaptation versus temporary disagreement. Prompt propagation and recalculation respond to changes; asynchronous updates can leave participants with mismatched views while they reconverge. Delaying decisions may reduce some inconsistency but delays recovery. Diagnostic: Is a loop-free or reachability assertion about the converged state, or about the transition interval?[1]

T3: Local detail versus scalable scope. OSPF areas and IS-IS levels restrain dissemination and computation, yet they hide internal topology and require border or cross-level route treatment. A flatter scope makes more detail locally visible at greater control-plane cost. Diagnostic: Does the destination require detailed internal paths, or is a summarized inter-scope route adequate?[1][2]

Structural–Framed Character

Link-state routing sits toward the structural end within a networking frame: the local-report → scoped-distribution → topology-derived-route relation can be recognized across unlike protocols. Evaluative weight: low traffic and quick convergence are design goals, not automatic membership criteria. Human-practice dependence: operators configure metrics and scope, but a local-link information architecture constrains what the protocol actually does. Institutional origin: IETF specifications establish OSPF, IS-IS-for-IP and OLSR versions; the general pattern is not owned by one standard. Vocabulary travel: distributed-state vocabulary extends elsewhere, but a database replica without destination routing does not become link-state routing. Import versus recognition: a new network protocol is recognized by its reports, dissemination and independent route calculation; importing “link-state” for any graph algorithm would misclassify a component as the whole. Its character: a strongly structural yet domain-specific distributed routing-control pattern, bounded by network scope, information currency and forwarding consequences.[1][2][3]

Structural Core vs. Domain Accent

Skeletal core. Participants publish local state to a bounded group and compute decisions from received state. The possible domain-independent pattern of distributed local-state synthesis is an explicit future-prime question, not an already established parent inferred from naming.

Domain-bound mechanism. The state describes network connectivity; the decisions are destination routes or next hops; the audience is a routing scope; information can be stale during topology changes. Different protocols instantiate that mechanism with OSPF areas, IS-IS levels or OLSR MPRs.[1][2][3]

Why not a prime. Outside networking, the full protocol roles cease to be literal. A map-sharing service does not automatically maintain forwarding routes, and generic pathfinding does not necessarily distribute local link state. The broad state-synthesis skeleton requires its own abstraction and cross-domain evidence; this named entry remains the specialized routing case.

This entry is a kind of Routing. Link-state routing is network routing with distributed local-link state and topology-derived route computation.

Relationships to Other Abstractions

Local relationship map for Link-state RoutingParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.Link-state RoutingDOMAINDomain-specific abstraction: Routing — is a kind ofRoutingDOMAIN

Current abstraction Link-state Routing Domain-specific

Parents (1) — more general patterns this builds on

  • Link-state Routing is a kind of Routing Domain-specific

    Link-state routing is network routing with distributed local-link state and topology-derived route computation.

Hierarchy path (1) — routes to 1 parentless root

Neighborhood in Abstraction Space

Link-state Routing sits in a sparse region of the domain-specific corpus (74th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Network Security Vulnerabilities & Trust (26 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With

  • Open Shortest Path First (OSPF). One IP link-state protocol with specified LSAs and area behavior. Tell: Are RFC 2328's protocol rules necessary, or only the broader link-state architecture?[1]
  • IS-IS. A different link-state protocol with Level ½ LSPs; it is an instance, not an alias. Tell: Which packet and level rules are actually in force?[2]
  • OLSR. An ad hoc link-state instance with MPR optimization and selected advertised links. Tell: Is the specific mobile relay scheme required?[3]
  • Distance-vector routing. Exchanges destination distances with adjacent routers. Tell: Are local-link reports disseminated for each node's own topology-based route calculation?[4]
  • Shortest-path algorithm. A computational step that need not include distributed advertisement, freshness or forwarding state. Tell: Is the whole network control process present?
  • Packet forwarding. Applies already chosen next hops to traffic. Tell: Is the action calculating and maintaining route state, or executing it?

References

[1] John Moy, RFC 2328, “OSPF Version 2” (1998), Abstract and §§1.1, 2, 3, 13, 16; original IETF specification. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v ↩w ↩x ↩y ↩z ↩27 ↩28

[2] Ross Callon, RFC 1195, “Use of OSI IS-IS for Routing in TCP/IP and Dual Environments” (1990), §§3.10, 5.1 and route-calculation clauses; original IETF specification. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o

[3] Thomas Clausen and Philippe Jacquet, RFC 3626, “Optimized Link State Routing Protocol (OLSR)” (2003), Abstract, §§1, 3, 8, 10; original experimental IETF specification. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u

[4] Gary Malkin, RFC 2453, “RIP Version 2” (1998), §3.4; original IETF specification of the contrasting distance-vector family. registry ↩a ↩b ↩c ↩d ↩e ↩f