Class in Session: Cisco

Continuing with our discussion of OSPF summarization options, refer to the figure below…

When we left off, we had reduced the number of Type-5 LSAs being injected into the OSPF cloud from two hundred to two, a summary route from each ASBR. But what if the prefixes that lie within the RIP or EIGRP clouds cannot be easily summarized (a situation which occurs all too often in real life)? In that case, instead of one large summary block, we could configure the ASBRs with multiple smaller summary blocks, by using multiple OSPF “summary-address” commands. The resulting Type-5 LSAs would then flood through Area 0 and into Area 1, but this is better than having every router know about each individual external prefix.

Notice that to reach any external prefix, R5 must send the packet towards Area 0. We can take advantage of this by configuring Area 1 as an OSPF “stub” area.  To do this, we use the OSPF “area stub” command on all routers connected to the area (including any ABRs). If we do, each ABR will inject a default route into Area 1, and no Type-5 LSAs are injected.

Continue reading ‘OSPF Part 11 – Summarization Options’

Having discussed how OSPF works without summarization options, let’s take a look at the various summarization options and their effects.

If there are 100 prefixes in the RIP cloud, and another 100 in the EIGRP cloud, each being injected into the OSPF domain by the ASBRs, each OSPF router will be tracking over 200 individual prefixes, and using RAM to store each in its LSDB and routing table. Also, a change to any external prefix will require advertisement of the change to all OSPF routers, which consumes bandwidth. Finally, any change to a router’s LSDB triggers Dijkstra’s SPF algorithm, which consumes CPU. For this reason, running a large OSPF topology “wide open” (without summarization) is not scalable.

Let’s start by using the OSPF “summary-address” command on R3, an ASBR. If we’re lucky (in other words, if the addresses in the RIP cloud have been allocated correctly), we can summarize the prefixes in the RIP cloud into one summary block. Assuming that’s the case, R3 will now be injecting only one Type-5 LSA into the OSPF cloud.

One might wonder, “What OSPF cost will be assigned to the Type-5 LSA for the summary block?” There are two options. One is to set the cost of the block equal to that of the lowest-cost prefix within the block, in accordance with RFC 1583. This is the default method. The second option is to set the cost of the block equal to that of the highest-cost prefix within the block, in accordance with RFC 2328. This is configured with the OSPF command “no compatible rfc1583”. In general, it probably doesn’t matter which method is used, but to prevent sub-optimal routing, it should be consistent within the OSPF autonomous system. We’ll just go with the default (“compatible rfc1583”).

If the EIGRP prefixes fall into a nice block, we can use the OSPF “summary-address” command on R4 to advertise that block into OSPF. At this point, the best paths from R5’s perspective are:

• Subnet A via R3 (cost = 3)
• Subnet B via R3 (cost = 3)
• Subnet C via R4 (cost = 3)
• Subnet D via R4 (cost = 3)
• RIP cloud via R3 (1 summary route at cost = 21)
• EIGRP cloud via R4 (1 summary route at cost = 21)

Note that we’ve saved RAM, bandwidth and CPU within the OSPF cloud due to the reduction in Type-5 LSAs being generated, advertised and stored. We’ve also saved additional RAM due to the reduction in sizes of the routing tables. So far, so good.

Next time, we’ll discuss additional summarization options.

Author: Al Friebe

Continuing on with our detailed discussion of OSPF, let’s look at how OSPF routers handle prefixes from external routing domains. Refer to Figure 1:

Let’s say that there are 100 subnets in the RIP cloud. If we configure R3 to redistribute the RIP routes into OSPF (using the “redistribute” command under OSPF), R3 will be an ASBR (Autonomous System Boundary Router). Likewise, let’s assume that there are also 100 prefixes within the EIGRP cloud, and that we have configured R4 as an ASBR, redistributing EIGRP into OSPF. As part of their ASBR function, R3 and R4 will advertise each individual prefix within their respective external routing domain into Area 0, using a Type 5 (external) LSA. Since by default Type 5 LSAs have autonomous system flooding scope, they will be passed into Area 1 by R3 and R4. Thus, R5 will have two possible paths (via R3 or R4) to all 200 external prefixes.

When configuring an ASBR, we have the option of including or ignoring internal costs (those of the links within the OSPF cloud) when calculating the metrics to external destinations. Let’s assume that “O E1” (“OSPF External Type 1”) routes are used, for which the internal metrics are considered. If we look at things from R5’s perspective, each of the destinations listed would be reached using the lowest-cost path, via the specified next hop:

• Subnet A via R3 (cost = 3)
• Subnet B via R3 (cost = 3)
• Subnet C via R4 (cost = 3)
• Subnet D via R4 (cost = 3)
• RIP cloud via R3 (100 prefixes, each at cost = 21)
• EIGRP cloud via R4 (100 prefixes, each at cost = 21)

At this point, each router within the OSPF routing domain will know the best path to each individual prefix within the OSPF cloud, as well as to each individual prefix within the RIP and EIGRP clouds. The best path to each external prefix will appear in R5’s IP routing table as “O E1” route.

Next time, we’ll take a detailed look at OSPF’s route summarization features, including possible unintended consequences of their use.

Author: Al Friebe

Having discussed OSPF route summarization and the various types of stub areas, let’s look at the potential drawbacks of using those features. We’ll start by reviewing how OSPF acts before any summarization features are configured. Refer to Figure 1:

As you can see, R3 connects Area 0 and Area 1 together, making R3 an OSPF ABR (Area Border Router), and likewise for R4 (for fault-tolerance, it’s always a good idea to have two ABRs connecting a pair of areas). As part of their ABR function, both R3 and R4 will advertise each individual prefix within Area 0 into Area 1 (and vice-versa) using a Type 3 (Summary) LSA (Link State Advertisement). Each individual Type 3 LSA sent into Area 1 by the ABRs will appear in R5’s LSDB (Link State Data Base).

As we know, each OSPF router uses Dijkstra’s SPF (Shortest Path First) algorithm to determine the lowest-cost path to each prefix. For this simple topology, we can see by inspection that R5 (an OSPF internal router) will have two possible paths (via R3 or R4) to each prefix within Area 0.

Assuming that all of the links within the OSPF domain are Fast Ethernet, each link will have an OSPF cost of 1 (by default Cisco routers set the OSPF link cost equal to 100 Mbps divided by the bandwidth). Therefore, from R5’s perspective, we should have the following lowest-cost paths:

• Subnet A via R3 (cost = 3)
• Subnet B via R3 (cost = 3)
• Subnet C via R4 (cost = 3)
• Subnet D via R4 (cost = 3)

Note that all four subnets can also be reached the “long way around” (for example, Subnet A via R4 at a cost of 4), but those paths would not be used if a lower-cost path exists. The best path to each prefix within Area 0 will appear in R5’s IP routing table as an “O IA” (OSPF Inter-Area) route.

Next time, we’ll discuss how R5 sees the prefixes within the RIP and EIGRP clouds.

Author: Al Friebe

Yep, we’re up to part seven … there is a lot you can do with OSPF! For this discussion, we’ll use the example topology shown in Figure 1.

From here, we can see that R2, R3 and R5 are ABRs (connecting OSPF areas), and that R5 and R6 are ASBRs (connecting the OSPF autonomous system to other routing domains). Because they are not ABRs, R1, R4 and R6 are referred to as “internal routers”. Also, because R2, R3, R4 and R5 have connections to Area 0 (the OSPF backbone), they are “backbone” routers. Note that a router can play several roles simultaneously, such as R5, which is a backbone router, an ABR, and an ASBR. When assigning a router multiple functions, take care that you don’t run it out of RAM and/or CPU.

Let’s assume that we have configured summarizations on the ABRs for routes being advertised from Area1 and Area 2 into Area 0, and on the ASBRs for routes being redistributed from RIP and EIGRP into OSPF. Instead of summarizing routes from Area 0 into Area 1 or Area 2, though, we’ll make use of another common OSPF feature, the “stub” area.

As you can see from Figure 1, the only way to get from Area 1 to the EIGRP and RIP routing domains is via R2 or R3. We can exploit this by configuring Area 1 as an OSPF stub area. The effect will be that instead of advertising external routes into Area 1, the ABRs will each advertise a default route. R1 will now know:

• All of the individual subnets within Area 1
• Summary routes via R2 and R3 for the other areas
• Default routes via R2 and R3 which allow it to reach the outside world.

R1 will choose the lowest-cost paths between R2 and R3 to the other areas and the outside world, and load-share between them in case of a tie.

So far, so good, but when it comes to conserving RAM, bandwidth and CPU on R1, we can do even better by configuring Area 1 as “totally stubby”. R2 and R3 will now suppress the advertisements of inter-area routes into Area 1, with the result that R1 will now know:

• All of the individual subnets within Area 1
• Default routes via R2 and R3 which allow it to reach everything beyond Area 1

Note that “totally-stubby” is a Cisco term, but other vendors’ routers may have a functionally-equivalent mode.

Continue reading ‘OSPF, Part 7′

In our previous discussion, we saw that dividing an OSPF autonomous system into multiple areas can improve the scalability. An example of a multi-area OSPF topology is shown in Figure 1:

Let’s imagine that we’ve allocated the IP address space as follows:

• Area 0: 10.0.0.0/24 through 10.0.255.0/24 (256 subnets)
• Area 1: 10.1.0.0/24 through 10.1.255.0/24 (256 subnets)
• Area 2: 10.2.0.0/24 through 10.2.255.0/24 (256 subnets)

Our OSPF autonomous system contains a total of 768 subnets, and unless we prevent it, each subnet will be known by every router. With a little configuration, however, we can do much better. As you can see, the subnets within the areas fall into three blocks:

• Area 0: 10.0.0.0/16
• Area 1: 10.1.0.0/16
• Area 2: 10.2.0.0/16

What we can do is configure the ABRs (R2 and R4) so that instead of advertising each individual prefix from one area to another, they will instead advertise summary blocks. For example, we will configure R2 to advertise the 10.1.0.0/16 block from Area 1 into Area 0, and likewise the 10.0.0.0/16 block from Area 0 to Area 1. Similarly, we’ll have R4 advertise the 10.2.0.0/16 block from Area 2 into Area 0, and the 10.0.0.0/16 block from Area 0 into Area 2. What will be the result?

Each internal router (R1, R3 and R5) has the LSDB for its particular area, and running SPF will send that area’s prefixes into its routing table. Thus, for the prefixes within their respective areas, the internal routers see things as follows:

• R1: 10.1.0.0/25 through 10.1.255.0/24 (the 256 subnets in Area 1)
• R3: 10.0.0.0/25 through 10.0.255.0/24 (the 256 subnets in Area 0)
• R5: 10.2.0.0/25 through 10.2.255.0/24 (the 256 subnets in Area 2)

Being an ABR, R2 will have the LSDB for both Area 2 and Area 0, and therefore will see 512 prefixes total for those two areas. Likewise, R4, the ABR connecting Area 2 to Area 0, will also see 512 prefixes for those areas.

In addition, since the ABRs are advertising the blocks of subnets from one area to another, each router will see one prefix for each area to which it is not directly connected. Therefore, the total numbers of prefixes known to the routers will be:

• R1: 258 prefixes (256 for Area 1, summaries for Area 0 and Area 2)
• R2: 513 prefixes (256 for Area 1, 256 for Area 0, summary for Area 2)
• R3: 258 prefixes (256 for Area 0, summaries for Area 1 and Area 2)
• R4: 513 prefixes (256 for Area 2, 256 for Area 0, summary for Area 1)
• R5: 258 prefixes (256 for Area 2, summaries for Area 0 and Area 1)

In the case of the internal routers (R1, R3 and R5), the routing tables have gone from 768 to 258 entries, a reduction of nearly two-thirds. In the case of the ABRs (R2 and R4), the number of routing tables has gone from 768 to 513, a reduction of nearly one-third. As you can imagine, as the total number of subnets goes up, the savings that can be realized by using multiple areas becomes even greater.

Since OSPF area numbers are thirty-two bit variables, they can be represented in dotted-decimal format, which can sometimes be convenient. For example, instead of numbering our areas 0, 1 and 2, we could make them Area 0.0.0.0, Area 10.1.0.0, and Area 10.2.0.0, deriving the area numbers from the IP address ranges within them.

What about Area 0, which contains the 10.0.0.0/16 block? Can we make that Area 10.0.0.0, then? No, because there are some rules we must follow when it comes to multiple areas.

• First, if we have more than one area, one of them must be Area 0 (or Area 0.0.0.0, if you prefer).
• Also, unless special arrangements are made, the topology of an OSPF autonomous system must be a simple hub-and-spoke, with Area 0 (the backbone) in the middle.
• One last thing … we can’t run a link directly from Area 1 to Area 2, bypassing Area 0, because OSPF won’t like that at all!

There are additional rules and options, some of which we’ll discuss in the next installment.

Author: Al Friebe

Let’s talk about some issues that arise when we scale an OSPF internetwork up to a large size. As usual when it comes to scalability, there are three issues involved:

• Bandwidth
• RAM
• CPU

First, as the internetwork grows, there are more routers. Recall that with link-state protocols such as OSPF, every router’s LSA (Link State Advertisement) is flooded throughout the internetwork. Obviously, the more routers, the more LSAs must be flooded, which results in more LSU (Link State Update) packets, consuming more bandwidth on the links.

Second, as the LSAs are flooded, each router makes a copy of each LSA, which it keeps in its LSDB (Link State Database). Therefore, the more routers, the larger will be each router’s LSDB, and a larger LSDB requires more RAM to store it. Also, since there are a lot of prefixes, the resulting routing table will be large, requiring even more RAM.

Third, every time a router’s LSDB changes, the router runs Dijkstra’s SPF algorithm to generate its revised routing table. The larger the internetwork, the larger the LSDB, and the more frequently it’s likely to be changing. Thus, each router is running SPF more often on a larger LSDB, consuming more CPU cycles.

The bottom line is that since bandwidth, RAM, and CPU cost money (and we don’t have infinite money) there is some limit to how large an OSPF autonomous system can grow. There are two solutions to this scalability problem

1. Limit OSPF to small internetworks (bad idea!)
2. Modify OSPF to enhance its scalability (good idea!)

Of the two options, the latter was used, and we call it “multi-area OSPF”. What we do is divide the OSPF autonomous system into regions called “areas”. An example of a multi-area OSPF topology is shown here:

Here’s how it works

A router that lies completely within an area is called an “internal router”. Internal routers, such as R1, know the entire topology for that specific area (in R1’s case it’s Area 1). Using SPF on its LSDB, R1 builds its routing table by calculating the best path from itself to any prefix within Area 1. At this point, R1 knows the best route to all prefixes within Area 1. Likewise, internal routers R3 and R5 calculate their routing tables for Area 0 and Area 2, respectively.

A router that is attached to more than one area is called an Area Border Router (ABR), and it maintains an LSDB for each area to which it is attached. R2, for example, is an ABR which connects Area 0 and Area 1. R2 runs SPF on its Area 0 and Area 1 LSDBs, and the results go into its routing table. Thus, R2 knows the best path from itself to all prefixes within Area 0 and Area 1. In addition, R2 now advertises the prefixes that lie within Area 0 into Area 1, and vice-versa. Note that only the prefixes and their metrics are advertised, not the existence of individual routers within an area. Likewise, R4, the ABR between Area 2 into Area 0, advertises prefixes between them.

For reasons of fault-tolerance, it’s possible that there could be two or more ABRs joining two areas. Since each ABR advertises the cost for each prefix from its perspective, the routers in the area receiving the advertisements can make optimal routing decisions about the prefixes that lie in the other area. At this point, all routers know the best route to all prefixes within the areas to which they are attached, and to the prefixes within the adjacent areas.

Furthermore, the Area 1 prefixes that R2 is sending into Area 0 are flooded over to R4, which then floods them into Area 2. As a result, all routers in Area 2 know about the prefixes in Area 1. This happens in the opposite direction, as well, and when the flooding has completed, all routers will know about all of the prefixes within the entire OSPF autonomous system. Because it’s just the prefixes and their costs that are being advertised between areas, and not detailed topology information, this requires less bandwidth, RAM and CPU than if it were all one big OSPF area, with all routers knowing everything about the topology.

In the next installment, we’ll continue our discussion of multi-area OSPF, including some techniques to further increase the scalability.

Author: Al Friebe

Continuing on with our discussion of LSDB synchronization, we’ve seen that in the case of point-to-point links, the two OSPF neighbors always proceed to “Full” state. On multi-access media such as an Ethernet LAN or a Frame Relay WAN, however, things are more complicated. Let’s look at an Ethernet LAN as an example.

A typical topology is that several routers are connected by a switch. Assuming that the switch ports connected to the routers lie within a common VLAN, the routers are within a common broadcast domain (an IP subnet). If every router on the subnet directly compares its LSDB to that of each of its neighbors on that subnet, the number of comparisons is governed by the “full mesh” equation:

• c = n * (n – 1) / 2

Where:

• c = The number of comparisons
• n = The number of routers on the subnet

If we crank through the numbers, we obtain:

• n = 2: c = 1 (two routers on a point-to-point link)
• n = 3: c = 3
• n = 4: c = 6
• n = 5; c = 10
• n = 6: c = 15
• n = 10: c = 45
• n = 20: c = 190

If there are two routers on the subnet, only one comparison is required to ensure LSDB synchronization. In the case of five routers on the subnet (n = 5), ten comparisons are required. If the number of routers on the subnet doubles to ten (n = 10), the number of comparisons increases to 45. Doubling it again (n = 20) results in 190 comparisons. Thus, as the number of routers doubles, the number of comparisons approximately quadruples, which is what computer scientists would call “O(n²)” (order n-squared), an exponential increase.

Also, once “Full” state is achieved, maintaining it will require that any router that detects a change to its LSDB will send an update to each of the other routers on the subnet, each of which will inform every other router on the subnet, etc. When many routers are involved, the large number of LSUs and LSAcks will consume excessive link bandwidth and router CPU cycles.

To solve this scalability problem, once the neighbors have reached “Two-Way”, multi-access media can elect a Designated Router (DR). The DR’s job is to maintain synchronization of the LSDBs for all routers within a subnet.

To elect the DR, the routers compare their DR election priorities, which are contained within the Hello packets. The DR priority is set per interface (or subinterface), and ranges from zero to 255, with a default value of 1. High priority wins, and the tie-breaker is highest OSPF router ID. The first runner-up is elected Backup DR (BDR). If the DR ever becomes unavailable, the BDR is promoted to DR, and a new BDR is elected.

Once the DR and BDR for the subnet have been elected, all other routers in the subnet will synchronize their LSDBs (go to “Full” state) with the DR. This has the effect of synchronizing all LSDBs on the subnet. The equation controlling the number of comparison is now:

• c = n – 1

Where:

• c = The number of comparisons
• n = The number of routers on the subnet

The number of comparisons now increases linearly with the number of routers on the subnet, and if we crank through the numbers we obtain:

• n = 2: c = 1 (two routers on a point-to-point link)
• n = 3: c = 2
• n = 4: c = 3
• n = 5; c = 4
• n = 6: c = 5
• n = 10: c = 9
• n = 20: c = 19

Key point: Because all routers on the subnet directly synchronize with the DR, they become synchronized with each other without having to directly compare their LSDBs.

Whenever a change to the topology occurs, the router detecting the change will inform the DR, which will inform the other routers on the subnet. In this manner, LSDB synchronization is maintained between the routers within the subnet. Those routers will then flood the LSA to other subnets to which they are attached.

Next time, we’ll examine multi-area OSPF, a technique for enhancing scalability.

Author: Al Friebe

In this installment, we’ll continue our look at OSPF (Open Shortest Path First). As we’ve seen, each router originates a Link State Advertisement (LSA), which is flooded throughout the internetwork. The LSA contains prefix and metric information for each link to which that router is directly connected. Each router maintains a Link State Database (LSDB) which contains copies of all LSAs the router has learned. Thus, the LSDB represents the detailed topology of the internetwork. Using Dijkstra’s SPF algorithm, each router independently uses its copy of the LSDB to develop its routing table.

So that all routers know which router originated which LSA, each LSA is uniquely identified by the originating router’s OSPF router ID. Like an IP address, an OSPF router ID is a 32-bit binary value that is commonly represented in dotted-decimal format. An OSPF router ID is assigned or selected as follows:

• If a “router-id” command appears under the OSPF process, that’s it.
• If not, it’s the highest IP address amongst the active loopback interfaces.
• If there are no active loopbacks, it’s the highest IP address amongst the active physical interfaces.

By active we mean not Administratively Down. In other words, a physical interface that’s Up/Down or Down/Down is still a candidate for OSPF router ID.

Note that although an OSPF router ID looks like an IP address, and may have been derived from an IP address, it is not an IP address. Instead, the router ID is used to uniquely identify the originator of a particular LSA within the LSDBs.

Key point: If you’re setting the OSPF router IDs manually using either router-id commands or loopbacks, they had better be unique! If not, corruption of the LSDBs and of the resulting routing tables can occur.

Two OSPF neighbors-to-be begin in the Down state. Once one of the potential neighbors has sent a hello, the neighbors move to Init state. To go further, the routers must agree on the following items with regard to the link which connects them:

• The subnet of the link
• The OSPF Hello and Dead intervals for the link
• The OSPF area within which the link resides
• Whether or not that area is an OSPF “stub” area
• Authentication type and keystring (if configured)

Assuming that the conditions are met, the neighbors proceed to Two-Way, which means that the neighbor relationship has been confirmed.

In the case of a point-to-point link (such as a serial link running HDLC or PPP), once the routers are Two-Way, they immediately proceed through Exstart, Exchange, and Loading, to Full state. Once they’ve reached Full state, their LSDBs are synchronized.

Next time, we’ll see how we handle LSDB synchronization on multi-access media, such as Ethernet LANs and Frame Relay WANs.

Author: Al Friebe