Link-State Routing Protocol

With link-state protocols, each router within the routing domain discovers and builds a complete and consistent view of the network topology as a weighted directed graph. Routers of the domain are nodes of the graph, and links between neighboring routers represent unidirectional edges or arcs. Weights on links are administratively assigned.

Routers advertise link-state information, including networks that they are attached to, or network reachability that is being redistributed via another RP. When the router boots up, it obtains a complete database image from its neighbors and builds the routing table by computing best routes to each destination prefix. Later, the link-state RP receives only deltas and recomputes routes to reflect the changes. The route computation uses the shortest path first (SPF) algorithm, also known as the Dijkstra algorithm, named after a Dutch mathematician. SPF can run periodically and recompute the entire set of routes to destinations (full SPF) or it can perform partial route calculation (PRC) when only a single external route changes. Incremental SPF (iSPF) can also be used to recompute only the affected part of the routing tree, thus allowing OSPF to converge faster on a new routing topology in reaction to a network event. This typically happens when the state of leaf elements changes.

Link-state algorithms adapt dynamically and quickly to changing network conditions because the changes are propagated independently of each router's route computation. They also allow routes to be selected based on more complex metrics than just the number of hops between networks. On the dark side, they are complicated to set up and can be slow to compute routes in large networks if design recommendations and constraints are not observed. They also require more complex troubleshooting knowledge. The two most deployed representatives of this family of RPs are IS-IS and OSPF, which both have an IPv6 counterpart: IS-IS for IPv6 and OSPFv3. They both implement mechanisms to enhance scalability, by enabling a two-level hierarchical routing model.