Introduction to Link-State Routing Protocols

Link-state routing protocols are based on Edsger W. Dijkstra's Shortest Path First (SPF) algorithm, a result of applied graph theory. Link-state protocols establish and maintain adjacencies via hello packets (connection-oriented) with their neighbors (peers), speaking the same routing protocol. The name link-state stems from the underlying concept that every participant distributes (floods) all the information states and conditions of its directly attached links.

The routers communicate via link-state advertisements (LSAs) with all their established neighbors. This behavior is referred to as flooding. The receiving routers never alter the LSA information, but add a copy to their link-state databases. After some convergence time, all the participants have a full, identical, and complete view (graph) of the area topology stored in their topology databases. Every router now calculates its own best paths (SPF) for all prefixes from its individual point of view and position in this topology. Hellos are also used as a keepalive mechanism between adjacent neighbors.


A new approach referred to as incremental SPF (iSPF) or incremental Dijkstra allows SPF protocols to converge faster under certain conditions by recomputing only the part of the shortest path tree (SPT) that has changed. This calculation is considerably faster only under special circumstances. For more information, search for "incremental SPF" or "incremental Dijkstra." At the time of this writing, the implementation solely is a proprietary vendor playground.

The following discussion introduces two fundamental concepts of organizing routing realms: areas and autonomous systems.

Area Concepts

Areas are smaller realms (subsets) of a routing domain (autonomous system). It became obvious during the design of link-state protocols that the intrinsic mechanisms become problematic in large flat topologies with several hundreds to thousands of nodes. This involved convergence time, link bandwidth, node memory, and CPU consumption. The designers' response was a subdivision-area concept and, recently, incremental approaches to SPF.

Area separation in terms of a contiguous backbone area and attached leaf areas via area border routers (ABRs) considerably improved the matter by restricting LSA flooding to the area boundaries. This resulted in smaller topology databases, faster SPF computation with less memory/CPU consumption, and ultimately improved convergence behavior.

ABRs maintain several databases and need to be consulted for interarea routing. In general, ABRs inject default routes into the leaf area. OSPF has a "rich" repertoire of leaf-area flavors: stub areas, total stub areas, not so stubby areas (NSSAs), and NSSA total stub. For a concise discussion of the differences, see the "Recommended Reading" section at the end of this chapter.

All leaf areas need to have at least one connection to the backbone area. If this is not possible because of migration constraints or topology limitations, OSPF virtual links are used to establish backbone connectivity via a transit area. This concept is not implemented (or necessary) in IS-IS. Both protocols use a contiguous backbone.

Table 9-1 shows the four different area specifiers used within Cisco IOS Software and their GateD and Zebra counterparts if applicable.

Table 9-1. OSPF Area Flavors

Area Specifier

GateD Notation

Zebra Notation




Total stub

Stub + restrict clause

Stub, no summary


Not implemented


NSSA total stub

Not implemented

NSSA, no summary


One short bit of advice: Do not expect OSPF to compensate for poorly designed topologies or address planning!

The Full Picture?Autonomous Systems and Areas

Figure 9-2 shows a complete view of the macroscopic world. Autonomous systems can be organized into areas?either a flat backbone area or a backbone area with multiple connected leaf areas. Autonomous systems are not isolated; they communicate via Exterior Gateway Protocols (EGPs) with other autonomous systems, upstream carriers, or public peering points. BGPv4 is the dominant EGP used in today's Internet.

Figure 9-2. Autonomous Systems and Areas

[View full size image]


Chapter 10, "ISP Connectivity with BGPv4: An Exterior Gateway Path-Vector Routing Protocol for Interdomain Routing," is dedicated to BGPv4 and interdomain issues.