When a failure occurs in the network, such as a neighbor becomes unreachable, link-state protocols flood LSAs using a special multicast address throughout an area. Each link-state router takes a copy of the LSA, updates its link-state (topological) database, and forwards the LSA to all neighboring devices. LSAs cause every router within the area to recalculate routes. Because LSAs need to be flooded throughout an area and all routers within that area need to recalculate their routing tables, you should limit the number of link-state routers that can be in an area.
A link is similar to an interface on a router. The state of the link is a description of that interface and of its relationship to its neighboring routers. A description of the interface would include, for example, the IP address of the interface, the mask, the type of network to which it is connected, the routers connected to that network, and so on. The collection of link states forms a link-state, or topological, database. The link-state database is used to calculate the best paths through the network. Link-state routers find the best paths to a destination by applying Dr. Edsger Dijkstra's SPF algorithm against the link-state database to build the SPF tree. The best paths are then selected from the SPF tree and placed in the routing table.
As networks become larger in scale, link-state routing protocols become more attractive for the following reasons:
Link-state protocols always send updates when a topology changes.
Periodic refresh updates are more infrequent than for distance vector protocols.
Networks running link-state routing protocols can be segmented into area hierarchies, limiting the scope of route changes.
Networks running link-state routing protocols support classless addressing.
Networks running link-state routing protocols support route summarization.
Link-state protocols use a two-layer network hierarchy, as shown in Figure 3-27.
Link-State Network Hierarchy
The two-layer network hierarchy contains two primary elements:
Area: An area is a grouping of networks. Areas are logical subdivisions of the autonomous system (AS).
Autonomous system: An AS consists of a collection of networks under a common administration that share a common routing strategy. An AS, sometimes called a domain, can be logically subdivided into multiple areas.
Within each AS, a contiguous backbone area must be defined. All other nonbackbone areas are connected off the backbone area. The backbone area is the transition area because all other areas communicate through it. For OSPF, the nonbackbone areas can be additionally configured as a stub area, a totally stubby area, a not-so-stubby area (NSSA), or a totally not-so-stubby area to help reduce the link-state database and routing table size.
Routers operating within the two-layer network hierarchy have different routing entities. The terms used to refer to these entities are different for OSPF than IS-IS. Refer to the following examples from Figure 3-27:
Router A is called the backbone router in OSPF and the L2 router in IS-IS. The backbone, or L2, router provides connectivity between different areas.
Routers B and C are called area border routers (ABR) in OSPF, and L1/L2 routers in IS-IS. ABR, or L1/L2, routers attach to multiple areas, maintain separate link-state databases for each area to which they are connected, and route traffic destined for or arriving from other areas.
Routers D and E are called nonbackbone internal routers in OSPF, or L1 routers in IS-IS. Nonbackbone internal, or L1, routers are aware of the topology within their respective areas and maintain identical link-state databases about the areas.
The ABR, or L1/L2, router will advertise a default route to the nonbackbone internal, or L1, router. The L1 router will use the default route to forward all interarea or interdomain traffic to the ABR, or L1/L2, router. This behavior can be different for OSPF, depending on how the OSPF nonbackbone area is configured (stub area, totally stubby area, or not-so-stubby area).
Link-State Routing Protocol Algorithms
Link-state routing algorithms, known collectively as SPF protocols, maintain a complex database of the network topology. Unlike distance vector protocols, link-state protocols develop and maintain full knowledge of the network routers and how they interconnect. This is achieved through the exchange of link-state packets (LSP) with other routers in a network.
Each router that has exchanged LSPs constructs a topological database using all received LSPs. An SPF algorithm is then used to compute reachability to networked destinations. This information is employed to update the routing table. The process can discover changes in the network topology caused by component failure or network growth.
In fact, the LSP exchange is triggered by an event in the network, instead of running periodically. This can greatly speed up the convergence process because it is unnecessary to wait for a series of timers to expire before the networked routers can begin to converge.
If the network shown in Figure 3-28 uses a link-state routing protocol, connectivity between New York City and San Francisco is not a concern. Depending on the actual protocol employed and the metrics selected, it is highly likely that the routing protocol could discriminate between the two paths to the same destination and try to use the best one.
Link-State Algorithms
Table 3-2 summarizes the contents of the routing database of each router in the figure.
Table 3-2 Link-State Routing Database
Router | Destination | Next Hop | Cost |
A | 185.134.0.0 | B | 1 |
192.168.33.0 | C | 1 | |
192.168.157.0 | B | 2 | |
192.168.157.0 | C | 2 | |
B | 10.0.0.0 | A | 1 |
192.168.33.0 | C | 1 | |
192.168.157.0 | D | 1 | |
C | 10.0.0.0 | A | 1 |
185.134.0.0 | B | 1 | |
192.168.157.0 | D | 1 | |
D | 10.0.0.0 | B | 2 |
10.0.0.0 | C | 2 | |
185.134.0.0 | B | 1 | |
192.168.33.0 | C | 1 |
As shown in the table link-state database entries for the New York (Router A) to Los Angeles (Router D) routes, a link-state protocol would remember both routes. Some link-state protocols can even provide a way to assess the performance capabilities of these two routes and bias toward the better-performing one. If the better-performing path, such as the route through Boston (Router C), experienced operational difficulties of any kind, including congestion or component failure, the link-state routing protocol would detect this change and begin forwarding packets through San Francisco (Router B).
Link-state routing might flood the network with LSPs during initial topology discovery and can be both memory- and processor-intensive. This section describes the benefits of link-state routing, the caveats to consider when using it, and the potential problems.
The following list highlights some of the many benefits that link-state routing protocols have over the traditional distance vector algorithms, such as RIP-1 or the now obsolete Interior Gateway Routing Protocol (IGRP):
Link-state protocols use cost metrics to choose paths through the network. For Cisco IOS devices, the cost metric reflects the capacity of the links on those paths.
By using triggered, flooded updates, link-state protocols can immediately report changes in the network topology to all routers in the network. This immediate reporting generally leads to fast convergence times.
Because each router has a complete and synchronized picture of the network, it is difficult for routing loops to occur.
Because LSPs are sequenced and aged, routers always base their routing decisions on the latest set of information.
With careful network design, the link-state database sizes can be minimized, leading to smaller SPF calculations and faster convergence.
The link-state approach to dynamic routing can be useful in networks of any size. In a well-designed network, a link-state routing protocol enables your network to gracefully adapt to unexpected topology changes. Using events, such as changes, to drive updates, rather than fixed-interval timers, enables convergence to begin that much more quickly after a topological change.
The overhead of the frequent, time-driven updates of a distance vector routing protocol is also avoided. This makes more bandwidth available for routing traffic rather than for network maintenance, provided you design your network properly.
A side benefit of the bandwidth efficiency of link-state routing protocols is that they facilitate network scalability better than either static routes or distance vector protocols. When compared to the limitations of static routes or distance vector protocols, you can easily see that link-state routing is best in larger, more complex networks, or in networks that must be highly scalable. Initially configuring a link-state protocol in a large network can be challenging, but it is well worth the effort in the long run.
Link-state protocols do, however, have the following limitations:
They require a topology database, an adjacency database, and a forwarding database, in addition to the routing table. This can require a significant amount of memory in large or complex networks.
Dijkstra's algorithm requires CPU cycles to calculate the best paths through the network. If the network is large or complex (that is, the SPF calculation is complex), or if the network is unstable (that is, the SPF calculation is running on a regular basis), link-state protocols can use significant CPU power.
To avoid excessive memory or CPU power, a strict hierarchical network design is required, dividing the network into smaller areas to reduce the size of the topology tables and the length of the SPF calculation. However, this dividing can cause problems because areas must remain contiguous at all times. The routers in an area must always be capable of contacting and receiving LSPs from all other routers in their area. In a multiarea design, an area router must always have a path to the backbone, or it will have no connectivity to the rest of the network. In addition, the backbone area must remain connected at all times to avoid some areas becoming isolated (partitioned).
The configuration of link-state networks is usually simple, provided that the underlying network architecture has been soundly designed. If the network design is complex, the operation of the link-state protocol might have to be tuned to accommodate it.
During the initial discovery process, link-state routing protocols can flood the network with LSPs and significantly decrease the capability of the network to transport data because no traffic is passed until after the initial network convergence. This performance compromise is temporary but can be noticeable. Whether this flooding process will noticeably degrade network performance depends on two things: the amount of available bandwidth and the number of routers that must exchange routing information. Flooding in large networks with relatively small links, such as low-bandwidth links, is much more noticeable than a similar exercise on a small network with large links, such as T3s and Ethernet.
Link-state routing is both memory- and processor-intensive. Consequently, more fully configured routers are required to support link-state routing than distance vector routing. This increases the cost of the routers that are configured for link-state routing.
The following are some of the benefits of a link-state routing protocol:
Troubleshooting is usually easier in link-state networks because every router has a complete copy of the network topology, or at least of its own area of the network. However, interpreting the information stored in the topology, neighbor databases, and routing table requires an understanding of the concepts of link-state routing.
Link-state protocols usually scale to larger networks than distance vector protocols, particularly the traditional distance vector protocols such as RIPv1 and IGRP.
You can address and resolve the potential performance impacts of both drawbacks through foresight, planning, and engineering.
Advanced Distance Vector Protocol Algorithm
The advanced distance vector protocol, or hybrid routing protocol, uses distance vectors with more accurate metrics to determine the best paths to destination networks. However, it differs from most distance vector protocols by using topology changes to trigger routing database updates, as opposed to periodic updates.
This routing protocol converges more rapidly, like the link-state protocols. However, it differs from link-state protocols by emphasizing economy in the use of required resources, such as bandwidth, memory, and processor overhead.
An example of an advanced distance vector protocol is the Cisco Enhanced Interior Gateway Routing Protocol (EIGRP).
Summary of Reviewing Routing Operations
The following list summarizes the key points discussed in this section:
Dynamic routing requires administrators to configure either a distance vector or a link-state routing protocol.
Distance vector routing protocols incorporate solutions such as split horizon, route poisoning, and hold-down timers to prevent routing loops.
Link-state routing protocols scale to large network infrastructures better than distance vector routing protocols, but they require more planning to implement.
Implementing Variable-Length Subnet Masks
Variable-length subnet masks (VLSM) were developed to enable multiple levels of subnetworked IP addresses within a single network. This strategy can be used only when it is supported by the routing protocol in use, such as Routing Information Protocol version 2 (RIPv2), OSPF, and EIGRP. VLSM is a key technology on large, routed networks. Understanding its capabilities is important when planning large networks.
Reviewing Subnets
Prior to working with VLSM, it is important to have a firm grasp on IP subnetting. When you are creating subnets, you must determine the optimal number of subnets and hosts.
Computing Usable Subnetworks and Hosts
Remember that an IP address has 32 bits and comprises two parts: a network ID and a host ID. The length of the network ID and host ID depends on the class of the IP address. The number of hosts available also depends on the class of the IP address.