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.

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.

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]