Understanding the OSPF Link-State Routing Protocol
To complete this chapter, this final major section examines one more routing protocol: Open Shortest Path First (OSPF) Protocol. Like EIGRP, OSPF converges quickly. Like EIGRP, OSPF bases its metric by default on link bandwidth, so that OSPF makes a better choice than simply relying on the router hop-count metric used by RIP. But OSPF uses much different internal logic, being a link-state routing protocol rather than a distance vector protocol.
This section introduces OSPF, first by listing some of the more obvious similarities and differences between OSPF and EIGRP. The rest of this section then explains a few of the internals of OSPF, again not a comprehensive look at OSPF internals, instead giving you some insights into a few key differences between OSPF and other IGPs.
OSPF Comparisons with EIGRP
Like all the IGPs discussed in this chapter, OSPF causes routers to learn routes, choose the best route to each subnet based on a metric, and to converge to choose new best routes when the network changes.
Although EIGRP uses DV logic, and OSPF uses LS logic, OSPF and EIGRP have three major activities that, from a general perspective, appear to be the same:
- Both OSPF and EIGRP use a hello protocol to find neighboring routers, maintain a list of working neighbors, monitor ongoing hello messages to make sure the neighbor is still reachable, and to notice when the path to a neighbor has failed.
- Both OSPF and EIGRP exchange topology data, which each router stores locally in a topology database. The topology database describes facts about the network, but is a different entity than the router’s IPv4 routing table.
- Both OSPF and EIGRP cause each router to process its topology database, from which the router can choose the currently best route (lowest metric route) to reach each subnet, adding those best routes to the IPv4 routing table.
For instance, in a network that uses Nexus Layer 3 switches, you could use OSPF or EIGRP. If using OSPF, you could display a Layer 3 switch’s OSPF neighbors (show ip ospf neighbor), the OSPF database (show ip ospf database), and the IPv4 routing table (show ip route). Alternatively, if you instead used EIGRP, you could display the equivalent in EIGRP: EIGRP neighbors (show ip eigrp neighbor), the EIGRP topology database (show ip eigrp topology), and the IPv4 routing table (show ip route).
However, if you dig a little deeper, OSPF and EIGRP clearly use different conventions and logic. The protocols, of course, are different, with EIGRP being created inside Cisco and OSPF developed as an RFC. The topology databases differ significantly, with OSPF collecting much more detail about the topology, and with EIGRP collecting just enough to make choices about successor and feasible successor routes. The method of processing the database, which then determines the best route for each subnet, differs significantly as well.
Most of the similarities end here, with OSPF, as an LS protocol, simply using an entirely different approach to choosing the currently best route for each subnet. The rest of this section describes LS behavior, using OSPF as the example.
Building the OSPF LSDB and Creating IP Routes
Link-state protocols build IP routes with a couple of major steps. First, the routers build a detailed database of information about the network and flood that so that all routers have a copy of the same information. (The information is much more detailed than the topology data collected by EIGRP.) That database, called the link-state database (LSDB) , gives each router the equivalent of a roadmap for the network, showing all routers, all router interfaces, all links between routers, and all subnets connected to routers. Second, each router runs a complex mathematical formula (the details of which we can all ignore) to calculate the best route to reach each subnet.
The next few pages walk through both parts of the process: building the LSDB, and then processing the LSDB to choose the best routes.
Topology Information and LSAs
Routers using LS routing protocols need to collectively advertise practically every detail about the internetwork to all the other routers. At the end of the process of flooding the information to all routers, every router in the internetwork has the exact same information about the internetwork. Flooding a lot of detailed information to every router sounds like a lot of work, and relative to DV routing protocols, it is.
OSPF, the most popular LS IP routing protocol, organizes topology information using link-state advertisements (LSAs) and the link-state database (LSDB). Figure 20-12 represents the ideas. Each LSA is a data structure with some specific information about the network topology—for instance, each router must be described by a separate LSA. The LSDB holds the collection of all the LSAs known to a router. Think of the LSDB as having one LSA for every router, one for every link, with several other types as well.
){kind=link}
Figure 20-12 LSA and LSDB Relationship
LS protocols rely on having all routers knowing the same view of the network topology and link status (link state) by all having a copy of the LSDB. The idea is like giving all routers a copy of the same updated road map. If all routers have the exact same road map, and they base their choices of best routes on that same road map, then the routers, using the same algorithm, will never create any routing loops.
To create the LSDB, each router will create some of the LSAs needed. Each router floods both the LSAs it creates, plus others learned from neighboring routers, so that all the routers have a copy of each LSA. Figure 20-13 shows the general idea of the flooding process, with R8 creating and flooding an LSA that describes itself (called a router LSA). The router LSA for router R8 describes the router itself, including the existence of subnet 172.16.3.0/24, as shown on the right side of the figure. (Note that Figure 20-13 actually shows only a subset of the information in R8’s router LSA.)
)
Figure 20-13 Flooding LSAs Using an LS Routing Protocol
Figure 20-13 shows the rather basic flooding process, with R8 sending the original LSA for itself and with the other routers flooding the LSA by forwarding it until every router has a copy. The flooding process has a way to prevent loops so that the LSAs do not get flooded around in circles. Basically, before sending an LSA to yet another neighbor, routers communicate and ask “do you already have this LSA?” Then they avoid flooding the LSA to neighbors that already have it.
Applying Dijkstra SPF Math and OSPF Metrics to Find the Best Routes
Although incredibly detailed and useful, the LSDB does not explicitly state each router’s best route to reach a destination. Instead, it lists the data from which a router can derive its currently best route to reach each subnet, by doing some math.
All LS protocols use a type of math algorithm called the Dijkstra shortest path first (SPF) algorithm to process the LSDB. That algorithm analyzes (with math) the LSDB, and builds the routes that the local router should add to the IP routing table—routes that list a subnet number and mask, an outgoing interface, and a next-hop router IP address.
Although engineers do not need to know the details of how SPF does the math, you can easily predict what SPF will choose, given some basic information about the network. The key is that once SPF has identified a route, it calculates the metric for a route as follows:
The sum of the OSPF interface costs for all outgoing interfaces in the route
The OSPF metric for a route is the sum of the interface costs for all outgoing interfaces in the route. By default, a router’s OSPF interface cost is actually derived from the interface bandwidth: The faster the bandwidth, the lower the cost. So, a lower OSPF cost means that the interface is better than an interface with a higher OSPF cost.
Armed with the facts in the previous few paragraphs, you can look at the example in Figure 20-14 and predict how the OSPF SPF algorithm will analyze the available routes and choose a best route. This figure features the logic on router R1, with its three competing routes to subnet X (172.16.3.0/24) at the bottom of the figure.
)
Figure 20-14 SPF Tree to Find R1’s Route to 172.16.3.0/24
As a result of the SPF algorithm’s analysis of the LSDB, R1 adds a route to subnet 172.16.3.0/24 to its routing table, with the next-hop router of R5.
Table 20-4 lists the three routes shown in Figure 20-14, with their cumulative costs, showing that R1’s best route to 172.16.3.0/24 starts by going through R5.
Table 20-4 Comparing R1’s Three Alternatives for the Route to 172.16.3.0/24
Route |
Location in Figure 20-14 |
Cumulative OSPF Cost |
R1–R7–R8 |
Left |
10 + 180 + 10 = 200 |
R1–R5–R6–R8 |
Middle |
20 + 30 + 40 + 10 = 100 |
R1–R2–R3–R4–R8 |
Right |
30 + 60 + 20 + 5 + 10 = 125 |
Scaling OSPF Through Hierarchical Design
OSPF can be used in some networks with very little thought about design issues. You just turn on OSPF in all the routers, and it works! However, in large networks, engineers need to think about and plan how to use several OSPF features that allow OSPF to scale well. For instance, the OSPF design in Figure 20-15 uses a single OSPF area, because this small internetwork does not need the scalability benefits of OSPF areas.
Using a single OSPF area for smaller internetworks, as in Figure 20-15, works well. The configuration is simple, and some of the hidden details in how OSPF works remain simple. In fact, with a small OSPF internetwork, you can just enable OSPF, with all interfaces in the same area, and mostly ignore the idea of an OSPF area.
)
Figure 20-15 Single-Area OSPF
Now imagine a network with 900 routers, instead of only 11, and several thousand subnets. In that size of network, the sheer amount of processing required to run the complex SPF algorithm might cause convergence time to be slow just because of the time it takes each router to process all the math. Also, the routers might experience memory shortages. The problems can be summarized as follows:
- A larger topology database requires more memory on each router.
- The router CPU time required to run the SPF algorithm grows exponentially with the size of the LSDB.
- With a single area, a single interface status change (up to down, or down to up) forces every router to run SPF again!
OSPF provides a way to manage the size of the LSDB by breaking up a larger network into smaller pieces using a concept called OSPF areas. The engineer places some links in one area, some in another, others in yet a third area, and so on. OSPF then creates a separate and smaller LSDB per area, rather than one huge LSDB for all links and routers in the internet-work. With smaller topology databases, routers consume less memory and take less processing time to run SPF.
OSPF multi-area design puts all ends of a link—a serial link, and VLAN, and so on—inside an area. To make that work, some routers (Area Border Routers, or ABRs) sit at the border between multiple areas. Routers D1 and D2 serve as ABRs in the area design shown in Figure 20-16, which shows the same network as Figure 20-15, but with three OSPF areas (0, 1, and 2).
)
Figure 20-16 Three-Area OSPF
Figure 20-16 shows a sample area design and some terminology related to areas, but it does not show the power and benefit of the areas. By using areas, the OSPF SPF algorithm ignores the details of the topology in the other areas. For example, OSPF on router B1 (area 1), when doing the complex SPF math processing, ignores the topology information about area 0 and area 2. Each router has much less SPF work to do, so each router more quickly finishes its SPF work, finding the currently best OSPF routes.