IPv4 Routing Protocol Concepts

Date: Dec 3, 2014

This chapter from CCNA Data Center DCICN 640-911 Official Cert Guide introduces the concepts behind Interior Gateway Protocols (IGPs), typically used inside one company. In particular, this chapter discusses the theory behind types of routing protocols, including distance vector and link-state logic. The chapter also introduces the Routing Information Protocol (RIP), Enhanced Interior Gateway Routing Protocol (EIGRP), and Open Shortest Path First (OSPF) routing protocol.

Routers and Layer 3 switches add IP routes to their routing tables using three methods: connected routes, static routes, and routes learned by using dynamic routing protocols. The routing process forwards IP packets, but if a router does not have any routes in its IP routing table that match a packet’s destination address, the router discards the packet. Routers need routing protocols so that the routers can learn all the possible routes and add them to the routing table, so that the routing process can forward (route) routable protocols such as IP.

IPv4 supports several different routing protocols, some of which are primarily used inside one company, while one is meant primarily for use between companies to create the Internet. This chapter introduces the concepts behind Interior Gateway Protocols (IGPs), typically used inside one company. In particular, this chapter discusses the theory behind types of routing protocols, including distance vector and link-state logic. The chapter also introduces the Routing Information Protocol (RIP), Enhanced Interior Gateway Routing Protocol (EIGRP), and Open Shortest Path First (OSPF) routing protocol.

“Do I Know This Already?” Quiz

Use the “Do I Know This Already?” quiz to help decide whether you might want to skim this chapter, or a major section, moving more quickly to the “Exam Preparation Tasks” section near the end of the chapter. You can find the answers at the bottom of the page following the quiz. For thorough explanations, see Appendix A, “Answers to the ‘Do I Know This Already?’ Quizzes.”

Table 20-1 “Do I Know This Already?” Foundation Topics Section-to-Question Mapping

Foundation Topics Section	Questions
Distance Vector Routing Protocol Features	1–2
RIP Concepts and Operation	3–4
EIGRP Concepts and Operation	5–6
OSPF Concepts and Operation	7–8

Which of the following distance vector features prevents routing loops by causing the routing protocol to advertise only a subset of known routes, as opposed to the full routing table, under normal stable conditions?
1. Route poisoning
2. Dijkstra SPF
3. Hello
4. Split horizon
Which of the following distance vector features prevents routing loops by advertising an infinite metric route when a route fails?
1. Dijkstra SPF
2. Hello
3. Split horizon
4. Route poisoning
Which of the following is true about both RIPv1 and RIPv2? (Choose two answers.)
1. Uses a hop-count metric
2. Sends update messages to multicast address 224.0.0.9
3. Supports authentication
4. Uses split horizon
Router R1 uses RIPv1, and learns one possible route to reach subnet 10.1.1.0/24. That route would have a metric of 15 from R1’s perspective. Which of the following is true?
1. R1 cannot use the route, because metric 15 is considered to be infinity.
2. R1 will add the route to its routing table.
3. The cumulative bandwidth between R1 and subnet 10.1.1.0/24 is 15 Mbps.
4. The slowest bandwidth of the links between R1 and subnet 10.1.1.0/24 is 15 Kbps.
Routers A and B use EIGRP. How does router A watch for the status of router B so that router A can react if router B fails?
1. By using EIGRP hello messages, with A needing to receive periodic hello messages to believe B is still working
2. By using EIGRP update messages, with A needing to receive periodic update messages to believe B is still working
3. Using a periodic ping of B’s IP address based on the EIGRP neighbor timer
4. None of the other answers are correct.
Which of the following affect the calculation of EIGRP metrics when all possible default values are used? (Choose two answers.)
1. Bandwidth
2. Delay
3. Load
4. Reliability
5. Hop count
Which of the following routing protocols are considered to use link-state logic?
1. RIPv1
2. RIPv2
3. EIGRP
4. OSPF
Which of the following is true about how a router using a link-state routing protocol chooses the best route to reach a subnet?
1. The router finds the best route in the link-state database.
2. The router calculates the best route by running the SPF algorithm against the information in the link-state database.
3. The router compares the metrics listed for that subnet in the updates received from each neighbor and picks the best (lowest) metric route.
4. The router uses the path that has the lowest hop count.

Foundation Topics

Introduction to Routing Protocols

Many IP routing protocols exist, in part due to the long history of IP; however, if you compare all the IP routing protocols, they all have some core features in common. Each routing protocol causes routers (and Layer 3 switches) to

Learn routing information about IP subnets from other neighboring routers
Advertise routing information about IP subnets to other neighboring routers
Choose the best route among multiple possible routes to reach one subnet, based on that routing protocol’s concept of a metric
React and converge to use a new choice of best route for each destination subnet when the network topology changes—for example, when a link fails

All the routing protocols discussed in this chapter do these same four functions, but the protocols differ in other ways. The rest of this chapter works through enough of the logic and features of each routing protocol so that you can see the differences, while understanding the basics of how each routing protocol learns routes, advertises routes, picks the best route, and converges when the network changes.

History of Interior Gateway Protocols

Historically speaking, RIP Version 1 (RIPv1) was the first popularly used IP routing protocol, with the Cisco-proprietary Interior Gateway Routing Protocol (IGRP) being introduced a little later, as shown in Figure 20-1.

Figure 20-1 Timeline for IP IGPs

By the early 1990s, business and technical factors pushed the IPv4 world toward a second wave of better routing protocols. RIPv1 and IGRP had some technical limitations, even though they were great options for the technology levels of the 1980s. The huge movement toward TCP/IP in the 1990s drove the need for better IPv4 routing protocols. In the 1990s, many enterprises migrated from older vendor-proprietary networks to networks built with routers, LANs, and TCP/IP. These businesses needed better performance from their routing protocols, including better metrics and better convergence. All these factors led to the introduction of a new wave of IPv4 Interior routing protocols: RIP Version 2 (RIPv2), OSPF Version 2 (OSPFv2), and EIGRP.

Comparing IGPs

What is an IGP in the first place? All the routing protocols mentioned so far in this chapter happen to be categorized as Interior Gateway Protocols (IGPs) rather than as Exterior Gateway Protocols (EGPs). First, the term gateway was used instead of router in the early days of IP routing, so the terms IGP and EGP really do refer to routing protocols. The designers of some routing protocols intended the routing protocol for use inside one company or organization (IGP), with other routing protocols intended for use between companies and between Internet service providers (ISPs) in the Internet (EGPs).

This chapter falls back to using the term IGP when talking about all the routing protocols mentioned in this chapter.

When deploying a new network, the network engineer can choose between a variety of IGPs. Today, most enterprises use EIGRP and OSPFv2. RIPv2 has fallen away as a serious competitor, in part due to its less robust hop-count metric, and in part due to its slower (worse) convergence time. This chapter discusses enough of the basics of all of these IGPs so that you get a sense of some of the basic trade-offs when comparing these routing protocols. A few key comparison points are as follows:

The underlying routing protocol algorithm: Specifically, whether the routing protocol used logic referenced as distance vector (DV) or link state (LS).
The usefulness of the metric: The routing protocol chooses which route is best based on its metric; so the better the metric, the better the choices made by that routing protocol.
The speed of convergence: How long does it take all the routers to learn about a change in the network and update their IPv4 routing tables? That concept, called convergence time, varies depending on the routing protocol.
Whether the protocol is a public standard or a vendor-proprietary function: RIP and OSPF happen to be standards, defined by RFCs. EIGRP happens to be defined by Cisco, and until 2013, was kept private.

For example, RIP uses a basic metric of hop count. Hop count treats each router as a hop, so the hop count is the number of other routers between a router and some remote subnet. RIP’s hop-count metric means that RIP picks the route with the smallest number of links and routers. However, that shortest route may have the slowest links; a routing protocol that uses a metric based in part on link speed (called bandwidth) might make a better choice. In contrast, EIGRP’s metric calculation uses a math formula that gives routes with slow links a worse metric, and routes with fast links a lower metric, so EIGRP prefers faster routes.

For example, Figure 20-2 shows two copies of the same topology. The topology shows three Nexus switches configured to act as Layer 3 switches. The figure focuses on router B’s route to a subnet off router A. As you can see on the left in the figure, RIP on router B chooses the shorter hop route over the top of the network, over the single link, even though that link runs at 1 Gbps. EIGRP, on the right side of the figure, chooses the route that happens to have more links through the network, but both links have a faster bandwidth of 10 Gbps.

Figure 20-2 EIGRP Choosing the Longer but Better Route to Subnet 10.1.1.0

On another comparison point, the biggest negative about EIGRP has traditionally been that it required Cisco routers. That is, using EIGRP locked you into using Cisco products, because Cisco kept EIGRP as a Cisco proprietary protocol. In an interesting change, Cisco published EIGRP as an informational RFC in 2013, meaning that now other vendors can choose to implement EIGRP as well. In the past, many companies chose to use OSPF rather than EIGRP to give themselves options for what router vendor to use for future router hardware purchases. In the future, it might be that you can buy some routers from Cisco, some from other vendors, and still run EIGRP on all routers.

For reference and study, Table 20-2 lists several features of OSPFv2 and EIGRP, as well as RIPv2. Note that the table includes a few features that have not yet been introduced (but will be introduced before the end of the chapter).

Table 20-2 Interior IP Routing Protocols Compared

Feature	RIPv1	RIPv2	EIGRP	OSPF
Distance vector (DV) or link state (LS)	DV	DV	DV ¹	LS
Default metrics based on link bandwidth	No	No	Yes	Yes
Convergence time	Slow	Slow	Fast	Fast
Originally Cisco proprietary	No	No	Yes	No
Uses areas for design	No	No	No	Yes
Routing updates are sent to a multicast IP address	No	Yes	Yes	Yes
Classless/supports VLSM	No	Yes	Yes	Yes

Distance Vector Basics

Each IGP can be categorized based on its internal logic, either DV or LS. As a starting point to better understand IGPs, the next few pages explain more about how a DV protocol actually exchanges routing information. These pages use RIP as an example, showing RIP’s simple hop-count metric, which, although a poor option in real networks today, is a much simpler option for learning.

The Concept of a Distance and a Vector

The term distance vector describes what a router knows about each route. At the end of the process, when a router learns about a route to a subnet, all the router knows is some measurement of distance (the metric) and the next-hop router and outgoing interface to use for that route (a vector, or direction).

Figure 20-3 shows a view of both the vector and the distance as learned with RIP. The figure shows the flow of RIP messages that cause R1 to learn some IPv4 routes, specifically three routes to reach subnet X:

The four-hop route through R2
The three-hop route through R5
The two-hop route through R7

Figure 20-3 Information Learned Using DV Protocols

DV protocols learn two pieces of information about a possible route to reach a subnet:

The distance (metric)
The vector (the next-hop router)

In Figure 20-3, R1 learns three routes to reach subnet X, through three different neighboring routers. If R1 had learned only one route to subnet X, R1 would use that route. However, having learned three routes to subnet X, R1 picks the two-hop route through next-hop router R7 because that route has the lowest RIP metric.

While Figure 20-3 shows how R1 learns the routes with RIP updates, Figure 20-4 gives a better view into R1’s DV logic. The figure shows R1’s three competing routes to subnet X as vectors, with longer vectors for routes with larger metrics. R1 knows three routes, each with

Distance: The metric for a possible route
Vector: The direction, based on the next-hop router for a possible route

figure 20-4 Graphical Representation of the DV Concept

Full Update Messages and Split Horizon

Some DV protocols, such as RIP (both RIPv1 and RIPv2), send periodic full routing updates based on a relatively short timer. Specifically, full update means that a router advertises all its routes, using one or more RIP update messages, no matter whether the route has changed or not. So, if a route does not change for months, the router keeps advertising that same route over and over.

Figure 20-5 illustrates this concept in an internetwork with two Nexus switches configured as Layer 3 switches, with four total subnets. The figure shows both routers’ full routing tables, and lists the periodic full updates sent by each router.

Figure 20-5 Normal Steady-State RIP Operations: Full Update with Split Horizon

This figure shows a lot of information, so take the time to work through the details. For example, consider what switch S1 learns for subnet 172.30.22.0/24, which is the subnet connected to S2’s E1/4 interface:

S2 interface E1/4 has an IP address, and is in an up/up state.
S2 adds a connected route for 172.30.22.0/24, off interface E1/4, to R2’s routing table.
S2 advertises its route for 172.30.22.0/24 to S1, with metric 1, meaning that S1’s metric to reach this subnet will be metric 1 (hop count 1).
S1 adds a route for subnet 172.30.22.0/24, listing it as a RIP learned route with metric 1.

Also, take a moment to focus more on the route learned at Step 4: The bold route in S1’s routing table. This route is for 172.30.22.0/24, as learned from S2. It lists S1’s local E1/2 interface as the outgoing interface because S1 receives the update on that interface. It also lists S2’s IP address of 172.30.1.2 as next-hop router because that’s the IP address from which S1 learned the route.

Monitoring Neighbor State with Periodic RIP Updates

RIPv1 and RIPv2 also send periodic updates, as shown in the bottom of Figure 20-5. That means that each router sends a new update (a full update) on a relatively short time period (30 seconds with RIP).

Many of the early DV protocols used this short periodic timer, repeating their full updates, as a way to let each router know whether a neighbor had failed. Routers need to react when a neighboring router fails or if the link between two routers fails. If both routers on a link must send updates every 30 seconds, when a local router no longer receives those updates, it knows that a problem has occurred, and it can react to converge to use alternate routes.

Note that newer DV protocols, such as EIGRP, do not require routers to keep sending updates for the purpose of tracking the state of the neighbor. Instead, they both define a simple hello protocol that allows the routers to send short messages to each other, instead of the long full routing updates, for the purpose of knowing when a neighbor fails.

Split Horizon

Figure 20-5 also shows a common DV feature called split horizon. Note that both routers list all four subnets in their IP routing tables. However, the RIP update messages do not list four subnets. The reason? Split horizon.

Split horizon is a DV feature that tells a router to omit some routes from an update sent out an interface. Which routes are omitted from an update sent out interface X? The routes that would like interface X as the outgoing interface. Those routes that are not advertised on an interface usually include the routes learned in routing updates received on that interface.

Split horizon is difficult to learn by reading words, and much easier to learn by seeing an example. Figure 20-6 continues the same example as Figure 20-5, but focusing on S1’s RIP update sent out S1’s E1/2 interface to S2. Figure 20-6 shows S1’s routing table with three light-colored routes, all of which list E1/2 as the outgoing interface. When building the RIP update to send out E1/2, split-horizon rules tell S1 to ignore those light-colored routes. Only the bold route, which does not list E1/2 as an outgoing interface, can be included in the RIP update sent out E1/2.

Figure 20-6 R1 Does Not Advertise Three Routes Due to Split Horizon

Route Poisoning

DV protocols help prevent routing loops by ensuring that every router learns that the route has failed, through every means possible, as quickly as possible. One of these features, route poisoning, helps all routers know for sure that a route has failed.

Route poisoning refers to the practice of advertising a failed route, but with a special metric value called infinity. Routers consider routes advertised with an infinite metric to have failed.

Figure 20-7 shows an example of route poisoning with RIP, with S2’s E1/4 interface failing, meaning that S2’s route for 172.30.22.0/24 has failed. RIP defines infinity as 16.

Figure 20-7 Route Poisoning

Figure 20-7 shows the following process:

S2’s E1/4 interface fails.
S2 removes its connected route for 172.30.22.0/24 from its routing table.
S2 advertises 172.30.22.0 with an infinite metric (which for RIP is 16).
Depending on other conditions, S1 either immediately removes the route to 172.30.22.0 from its routing table, or marks the route as unusable (with an infinite metric) for a few minutes before removing the route.

By the end of this process, router S1 knows for sure that its old route for subnet 172.30.22.0/24 has failed, which helps S1 avoid introducing looping IP routes.

Each routing protocol has its own definition of an infinite metric. RIP uses 16, as shown in the figure, with 15 being a valid metric for a usable route. EIGRP has long used 2³² – 1 as infinity (a little more than 4 billion), with some Cisco products bumping that value to 2⁵⁶ – 1 (more than 10¹⁶). OSPFv2 uses 2²⁴ – 1 as infinity.

The previous few pages focused on DV concepts, using RIP as an example. This chapter next turns the focus to the particulars of both RIPv1 and RIPv2.

RIP Concepts and Operation

The Routing Information Protocol (RIP) was the first commonly used IGP in the history of TCP/IP. Organizations used RIP inside their networks commonly in the 1980s, and into the 1990s. RIPv2, created in the mid-1990s, improved RIPv2, giving engineers an option for easy migration and co-existence to move from RIPv1 to the better RIPv2.

This second of four major sections of the chapter compares RIPv1 and RIPv2, while discussing a few of the core features that apply to both.

Features of Both RIPv1 and RIPv2

Like all IGPs, both RIPv1 and RIPv2 perform the same core features. That is, when using either RIPv1 or RIPv2, a router advertises information to help other routers learn routes; a router learns routes by listening to messages from other routers; a router chooses the best route to each subnet by looking at the metric of the competing routes; and the routing protocol converges to use new routes when something changes about the network.

RIPv1 and RIPv2 use the same logic to achieve most of those core functions. The similarities include the following:

Both send regular full periodic routing updates on a 30-second timer, with full meaning that the update messages include all known routes.
Both use split-horizon rules, as shown in Figure 20-6.
Both use hop count as the metric.
Both allow a maximum hop count of 15.
Both use route poisoning as a loop-prevention mechanism (see Figure 20-7), with hop count 16 used to imply an unusable route with an infinite metric.

Although you might be puzzled why the creators of RIPv2 made it so much like RIPv1, the goal was simple: interoperability. A network that used RIPv1 could slowly migrate to RIPv2, enabling RIPv2 on some routers on one weekend, some more on the next, and so on. Done correctly, the network could migrate over time. The fact that both RIPv1 and RIPv2 used the same metric, and same loop-prevention mechanisms, allowed for a smooth migration.

Differences Between RIPv1 and RIPv2

Of course, RIPv2 needed to be better than RIPv1 in some ways, otherwise, what is the point of having a new version of RIP? RIPv2 made many changes to RIPv1: solutions to known problems, improved security, and new features as well. However, while RIPv2 improved RIP beyond RIPv1, it did not compete well with OSPF and EIGRP, particularly due to somewhat slow convergence compared to OSPF and EIGRP. However, for the sake of completeness, the next few pages walk through a few of the differences.

First, RIPv1 had one protocol feature that prevented it from using variable-length subnet masks (VLSMs). To review, VLSM means that inside one classful network (one Class A, B, or C network), that more than one subnet mask is used. For instance, in Figure 20-8, all the subnets are from Class A network 10.0.0.0, but some subnets use a /24 mask, whereas others use a /30 mask.

Figure 20-8 An Example of VLSM

RIPv1 could not support a network that uses VLSM because RIPv1 did not send mask information in the RIPv1 update message. Basically, RIPv1 routers had to guess what mask applied to each advertised subnet, and a design with VLSM made routers guess wrong. RIPv2 solved that problem by using an improved update message, which includes the subnet mask with each route, removing any need to guess what mask to use, so RIPv2 correctly supports VLSM.

RIPv2 fixed a couple of other perceived RIPv1 shortcomings as well. RIPv2 added authentication (RIPv1 had none), which can avoid cases in which an attacker introduces incorrect routes into a router’s routing table. RIPv2 changed from using IP broadcasts sent to the 255.255.255.255 broadcast address (as in RIPv1) by instead sending updates to the 224.0.0.9 IPv4 multicast address. Using multicasts means that RIP messages can be more easily ignored by other devices, wasting less CPU on those devices.

Table 20-3 summarizes some of the key features of RIPv1 and RIPv2.

Table 20-3 Key Features of RIPv1 and RIPv2

Feature	RIPv1	RIPv2
Hop-count metric	Yes	Yes
Sets 15 as the largest metric for a working route	Yes	Yes
Sends full routing updates	Yes	Yes
Uses split horizon	Yes	Yes
Uses route poisoning, with metric 16	Yes	Yes
Sends mask in routing update	No	Yes
Supports discontiguous classful networks	No	Yes
Sends updates to 224.0.0.9 multicast address	No	Yes
Supports authentication	No	Yes

EIGRP Concepts and Operation

Enhanced Interior Gateway Routing Protocol (EIGRP) went through a similar creation process as compared to RIP, but with the work happening inside Cisco. Cisco has already created the Interior Gateway Routing Protocol (IGRP) in the 1980s, and the same needs that drove people to create RIPv2 and OSPF drove Cisco to improve IGRP as well. Instead of naming the original IGRP Version 1, and the new one IGRP Version 2, Cisco named the new version Enhanced IGRP (EIGRP).

EIGRP acts a little like a DV protocol, and a little like no other routing protocol. Frankly, over the years, different Cisco documents and different books (mine included) have characterized EIGRP as either its own category, called a balanced hybrid routing protocol, or as some kind of advanced DV protocol.

Regardless of what label you put on EIGRP, the protocol uses several features that work either like basic DV protocols such as RIP, or they work similarly enough. Routers that use EIGRP send messages so that other routers learn routes, they listen for messages to learn routes, they choose the best route among multiple routes to the same subnet based on a metric, and they react and converge when the network topology changes.

Of course, EIGRP works differently in several ways as compared to RIPv2. This third of four sections of the chapter discusses some of those similarities and differences, so you get a sense of how EIGRP works. Note that this section does not attempt to mention all the features of EIGRP, but instead to give some highlights that point out some of EIGRP’s unique features compared to other IGPs. Regardless, at the end of the day, once you enable EIGRP on all your routers and Layer 3 switches, the devices will learn good routes for all the subnets in the network.

EIGRP Maintains Neighbor Status Using Hello

Unlike RIP, EIGRP does not send full or partial update messages based on a periodic timer. When a router first comes up, it advertises known routing information. Then, over time, as facts change, the router simply reacts, sending partial updates with the new information.

The fact that EIGRP does not send routing information on a short periodic timed basis greatly reduces EIGRP overhead traffic, but it also means that EIGRP cannot rely on these updates to monitor the state of neighboring routers. Instead, EIGRP defines the concept of a neighbor relationship, using EIGRP hello messages to monitor that relationship. The EIGRP hello message and protocol defines that each router should send a periodic hello message on each interface, so that all EIGRP routers know that the router is still working. Figure 20-9 shows the idea.

Figure 20-9 EIGRP Hello Packets

The routers use their own independent hello interval, which defines the time period between each EIGRP hello. For instance, routers R1 and R2 do not have to send their hellos at the same time. Routers also must receive a hello from a neighbor with a time called the hold interval, with a default setting of three times the hello interval.

For instance, imagine both R1 and R2 use default settings of 5 and 15 for their hello and hold intervals. Under normal conditions, R1 receives hellos from R2 every 5 seconds, well within R1’s hold interval (15 seconds) before R1 would consider R2 to have failed. If R2 does fail, R2 no longer sends hello messages. R1 notices that 15 seconds pass without receiving a hello from R2, so then R1 can choose new routes that do not use R2 as a next-hop router.

EIGRP Topology and the Metric Calculation

One of the most compelling reasons to consider using EIGRP instead of other IGPs is the strength of the EIGRP metric. EIGRP uses a math function to calculate the metric. More importantly, that function uses two input variables by default:

The slowest link in the end-to-end route
The cumulative delay for all links in the route

As a result, EIGRP defines the concept of the best route based on the constraining bandwidth (speed) of the links in the route, plus the total delay in the route.

The words bandwidth and delay have specific meaning with EIGRP. Bandwidth refers to the perceived speed of each link. Delay refers to the router’s perception of the time it takes to send a frame over the link. Both bandwidth and delay are settings on router interfaces; although routers do have default values for both bandwidth and delay on each interface, the settings can be configured as well.

EIGRP calls the calculated metric value the composite metric, with the individual inputs into the formula being the metric components. The formula itself is not as important as the effect of the metric components on the calculation:

A smaller bandwidth yields a larger composite metric because less bandwidth is worse than more bandwidth.
A smaller delay yields a smaller composite metric because less delay is better than more delay.

Using these two inputs gives EIGRP a much better metric than RIP. Basically, EIGRP prefers routes with faster links, avoiding routes with slower links. Slow links, besides the obvious negative of being slow, also may experience more congestion, with packets waiting longer to get a turn to cross the link. For example, EIGRP could prefer a route with multiple 10-Gbps links rather than a single-hop route over a 1-Gbps or 100-Mbps link.

EIGRP Convergence

Another compelling reason to choose EIGRP as an IGP has to do with EIGRP’s much better convergence time as compared with RIP. EIGRP converges more quickly than RIP in all cases, and in some cases, EIGRP converges much more quickly.

For perspective, with RIPv2 in normal operation, convergence could take several minutes. During those minutes, some user traffic was not delivered to the correct destination, even though a physical path existed. With EIGRP, those same worst cases typically experience convergence of less than a minute, often less than 20 seconds, with some cases taking a second or two.

EIGRP does loop avoidance completely differently than RIP by keeping some basic topological information. The EIGRP topology database on each router holds some information about the local router, plus some information about the next-hop router in each possible route for each known subnet. That extra topology information lets EIGRP on each router take the following approach for all the possible routes to reach one subnet:

Similar to how other routing protocols work, a local router calculates the metric for each possible route to reach a subnet, and chooses the best route based on the best metric.
Unlike other routing protocols, the local router uses that extra topology information to look at the routes that were not chosen as the best route, to find all alternate routes that, if the best route fails, could be immediately used without causing a loop.

That second bullet reveals the key to understanding how EIGRP converges very quickly. Without getting into all the details, a simple example of the power of this fast EIGRP convergence can help. To begin, consider Figure 20-10, which focuses on router E’s three possible routes to reach subnet 1 on the right.

Figure 20-10 Route Through Router D Is the Successor Route to Subnet 1

The upper left shows router E’s topology table information about the three competing routes to reach subnet 1: a route through router B, another through router C, and another through router D. The metrics in the upper left show the metrics from router E’s perspective, so router E chooses the route with the smallest metric: the route through next-hop router D. EIGRP on router E places that route, with next-hop router D, into its IP routing table, represented on the lower left of the figure.

At the same time, EIGRP on router E uses additional topology information to decide whether either of the other routes—the routes through B and C—could be used if the route through router D fails, without causing a loop. Ignoring the details of how router E decides, imagine that router E does that analysis, and decides that E’s route for subnet 1 through router B could be used without causing a loop, but the route through router C could not. Router E would call that route through router B a feasible successor route, as noted in Figure 20-11.

Figure 20-11 Route Through Router B Is a Feasible Successor

As long as the network stays stable, router E has chosen the best route, and is ready to act, as follows:

Router E uses the successor route as its only route to subnet 1, as listed in the IPv4 routing table.
Router E lists the route to subnet 1, through router B, as a feasible successor, as noted in the EIGRP topology table.

Later, when convergence to a new route to subnet 1 needs to occur—days later, weeks later, whenever—the convergence is almost instant. As soon as router E realizes that the current route through router D has failed, router E can immediately remove the old route from its IPv4 routing table, and add a route to subnet 1 listing router B as the next-hop router.

EIGRP Summary

As you can see, EIGRP provides many advantages over both RIPv1 and RIPv2. Most significantly, it uses a much better metric, and it converges much more quickly than does RIP.

The biggest downside to EIGRP has traditionally been that EIGRP was a Cisco proprietary protocol. That is, to run EIGRP, you had to use Cisco products only. Interestingly, Cisco has published EIGRP as an informational RFC in 2013, so now other vendors could choose to add EIGRP support to their products. Over time, maybe this one negative about EIGRP will fade away.

The next topic introduces the final routing protocol for this chapter, OSPF, which has always been a public standard.

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.

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.

Exam Preparation Tasks

Review All the Key Topics

Review the most important topics from this chapter, noted with the Key Topic icon. Table 20-5 lists these key topics and where each is discussed.

Table 20-5 Key Topics for Chapter 20

Key Topic Element	Description	Page Number
Table 20-3	Key features of RIPv1 and RIPv2	517
Paragraph	How SPF calculates the metric for a route	524
Figure 20-14	How OSPF’s SPF algorithm analyzes and selects the best route	525

Definitions of Key Terms

After your first reading of the chapter, try to define these key terms, but do not be concerned about getting them all correct at that time. Chapter 23, “Final Review,” directs you in how to use these terms for late-stage preparation for the exam.

convergence, distance vector, Interior Gateway Protocol (IGP), partial update, poisoned route, split horizon, feasible successor, successor, shortest path first (SPF) algorithm, link state, link-state advertisement (LSA), link-state database (LSDB)