|
|
Bridging must keep track of every host MAC address. The workload in bridging is proportional to the number of hosts. This may work perfectly well with hundreds or low thousands of machines, but tends to die at 8,000 to 16,000.
Where bridging keeps track of the coordinates of every "house," basic flat routing only tracks streets (i.e., media or subnets), and assumes that layer 2 mechanisms will ensure delivery to the right house once routing delivers a packet to the right street. Since routing only tracks media, and media have tens or hundreds of devices, the workload of routing is at least one or two orders of magnitude less than in bridging.
Still, flat routing has its limitations. Just as bridging becomes unmanageable with a sufficient number of hosts, plain routing can become unmanageable with enough subnets. Changes in Asia will affect routers in Africa. By introducing hierarchy, you localize the effects of changes to where they are actually significant. Hierarchical routing is an example of the principle of "information hiding," a computer science term introduced by D.L. Parnas in the early 1970s. It is quite relevant to routing design. The fundamental idea is that each processing component should know only those items of information that will actually help it make decisions. For example, if there is only one exit from a non-backbone area, but fifty different routers with optimal paths to different parts of the Internet connected to the backbone, the non-backbone area will not do anything differently if it has complete Internet routing information.
Real life is like this. While George W. Bush may find it interesting to track the progress of a fourth-grade English class in Austin, Texas, if he tried to track all classes in all states, he would have no time to do anything else. Hierarchy is as much a means of delegating responsibility as it is a means of giving power to the top of the structure.
There are several ways to introduce hierarchy. It can be based on topology only, as in the tree structure of Figure 1, where the customer site routers only need to know about the local networks and how to default to the distribution tier. I find that the best understanding of hierarchical routing comes from first understanding it first purely from a perspective of static routing and then adding dynamic features.
Figure 1. Hierarchy through Topology
|
This section discusses accepted best practices in real-world routing. There have been many suggestions, however, that the CCIE lab specifically bans or limits solutions using static routing. It certainly is true that people will sometimes use an ill-considered static route to work around a problem. It would appear, however, that Cisco is most interested in seeing how well candidates understand routing protocol commands; their written and laboratory tests emphasize dynamic rather than static techniques |
Hierarchical routing, whether static or dynamic, depends on hierarchical addressing. Look at routers oregano and basil in Figure 2. Even if these routers received the extended global routing table, how would it help them make decisions? Each router in this graphic has only that which is necessary and sufficient to do its job.
Figure 2. Dumb Stub
Now, consider cumin and cardamon in Figure 3. They can make alternative decisions -- but is the overhead of OSPF what they really need? Given that the only alternatives are the floating static links initiated when these edge routers detect a failure, there's a minimum need for routing information.
Figure 3. Floating Static
You can achieve useful link backup on cumin and cardamon with quasi-static routes. Some people might argue that using static routes means more configuration, but remember that you have to manage the address space for the remote sites. It should not be complicated to have the software that assigns remote address space to generate, as well, the static route statements, and automatically include these into distribution configurations with copy tftp running startup (with the network, not host, option) or with telnet.
When there are multiple distribution tier routers (Figure 4), dynamic routing becomes more important in the access routers. It is a practical necessity among the distribution routers.
Figure 4. Full Redundancy
Large routing systems, of which the public Internet is the largest, have multiple levels of hierarchy. While administrative controls and filtering are important in implementing hierarchical routing, the most important mechanism remains hierarchical addressing. If the addresses in a growing network were randomly assigned, they will, at some point, need to be reassigned if the network can continue to grow. Luckily, hierarchy usually allows you to renumber only part of the network at a time.
Figure 5. Levels of Hierarchy
In the center of Figure 5, the lowest level of the routing hierarchy is individual IP hosts located on subnets. In the CIDR context, hosts have /32 prefixes (i.e., subnet masks of 255.255.255.255).
Subnets describe media to which two or more devices are attached. The smallest scope of transmitted routing information is the subnet. For example, local broadcasts (i.e., to 255.255.255.255) have a scope of a single subnet. Further, many routing and other management packets, while destined for multicast or unicast addresses, effectively are limited to subnet scope because they are created with a Time To Live (TTL) value of 1.
In link state protocols such as OSPF and IS-IS, the computational workload involved in determining the optimal paths through a set of routers and subnet prefixes is proportional to:
(prefixes)2 * log routers
In other words, the workload goes up exponentially with an increasing number of network links. To constrain the workload, hierarchical routing splits the routers and prefixes into areas. Areas define subsets of the full list of routers and prefixes.
Area-based hierarchical routing establishes a system in which more-specific routes, those with longer prefixes, are summarized -- aggregated -- as they propagate to higher levels in a hierarchy. In OSPF and IS-IS, a boundary at which summarization takes place is called an area, as seen in Figure 6.
Figure 6. Basic Area Structure
Both of these protocols have a concept of two levels of areas, with a backbone and some number of non-backbone areas. The backbone connects the non-backbone areas. Continuing to use the street model, the backbone is the freeway that has only limited exits. In this paper, the drawing convention for areas shows the routes advertised into the backbone are in the top triangle of each area, but the rectangle below the triangle shows all routes in the area.
A backbone and a set of nonbackbone areas, a standalone backbone, or a single nonbackbone area constitute a routing domain.
OSPF and ISIS define a backbone area and a set of non-backbone areas. Nonbackbone areas can reach one another only via the backbone. Routes inside an area are, in OSPF terminology, intra-area. Each non-backbone area reports either all of its routes, or a summary of its routes, into the backbone.
From the perspective of a given area, the backbone may advertise only the default route into the area, or may also advertise routes in other areas: inter-area routes. Depending on configuration options, the backbone may or may not advertise inter-area routes into non-backbone areas. Especially when only one physical router interconnects a non-backbone area with the backbone, knowledge of inter-area routes will not necessarily be useful to a non-backbone area.
The routing system may also import routes from other routing domains or from more distant sources such as the global Internet. Routes that originate outside the routing domain are called external routes.
When a change takes place, route recomputation is based on the number of routers in the affected areas, the main computational load is reduced. For an area k,
IntraAreaLoad = (prefixes_in_k)2 * log routers_in_k
Remember that the Dijkstra algorithm proper computes only intra-area routes. An area contains a set of cooperating routers that share a synchronized and distributed topological database. Routers connected to multiple areas have multiple databases. Even though this example has a strongly hierarchical topology and addressing plan, the number of routes is sufficiently small that summarization is not required.
There is additional load for inter-area and external routes that are leaked into the non-backbone area, either from the backbone or an external router connected to the non-backbone area. Total load is proportional to:
TotalLoad = IntraAreaLoad
+ InterAreaRoutes_in_k
+ ExternalRoutes_in_k
TotalLoad is the actual Dijkstra computation. The product of the number of intra-area routes in Area K and the logarithm of the number of routers in Area K.
InterAreaRoutes_in_k is number of summarized or explicit inter-area routes seen in Area K. Summarization affects the second term, although total stubbiness or the use of strict IS-IS L1 also affects it.
ExternalRoutes_in_k routes is the load from sources external to the routing domain seen in Area K. Stubbiness and external aggregation affects the third term.
Area SizingThe more areas you put on any one physical router, the more likely it is that there will be a simultaneous recomputation in more than one area. Cisco gives a conservative recommendation of not connecting more than two non-backbone areas to a single router, but this number can be exceeded when the areas are known to be highly stable, or the router has a fast CPU. On a largely optical network, I have had seven areas connected to a 7000-series router and had little operational problem. However, this deals with a single computation. The real CPU requirements are going to come from how often it will be recomputed. The most basic need for recomputation comes from unstable routes. The guideline of 50 routers per area tends to assume a 2500-class router (i.e., a 68030 CPU) and a mix of decent LAN and WAN links. Do you have enough CPU? You want to keep the 5-minute utilization under 50-60%, especially on routers that do not have separate forwarding processors. If you don't have enough CPU, decrease the number of links in the area or get routers with faster CPUs. |
In OSPF, the backbone area has a specific identifier, 0.0.0.0, often simply called Area 0. IS-IS does not have a specific identifier for the backbone, which is simply the set of interconnections among its inter-area routers (i.e., level 2 routers).
Areas are the basic building blocks of hierarchy with interior routing protocols. There are higher-level building blocks that deal with multiple instances of routing protocols under common administration, and communications among different administrations. Let us consider this higher level before delving into the details of areas.
"Area" is used here in a general sense, not being limited to formal areas in OSPF or IS-IS but also referring to areas of address aggregation in OSPF. The function of an area can be created in any protocol that supports arbitrary prefix lengths and has a summarization mechanism. Think of the "information hiding" mentioned earlier.
|
It's good practice always to write out area identifiers in full, such as OSPF area 0.0.0.1 rather than OSPF area 1. Not all vendors' implementations will produce the same binary area identifier from these two equivalent human-readable notations. |
OSPF has explicit identifiers for areas and the interfaces in them. IS-IS has explicit area identifiers for entire routers and implicitly assigns interfaces to areas. EIGRP does not have area identifiers but can achieve the equivalent through aggregation structures.
Figure 7 shows an example where both areas 0.0.0.1 and 0.0.0.2 have both reachable and unreachable destinations. Areas 0.0.0.1, 0.0.0.2, and 0.0.0.3 are all reachable via the core. Areas 0.0.0.1 and 0.0.0.3 only advertise summaries of their routes into the core area. Area 0.0.0.1 hides the details of its internal reachability from the backbone, while area 0.0.0.2 advertises its detailed routes into the backbone. The core area can not know, due to summarization and the resulting information hiding, that network 10.1.1.0/24 is down.
Figure 7. Hiding Details
Perhaps counterintuitively to many beginners, having the 10.1.1.0/24 hidden from the core is usually excellent practice. It increases stability by reducing the requirement to have many and large routing tables recomputed.
Assume that a host in area 0.0.0.3 wants to send to a host on 10.1.1.0/24. If all routes were advertised everywhere, as soon as 10.1.0.0/24 went down, areas 0.0.0.0, 0.0.0.1, 0.0.0.2, and 0.0.0.3 would all recompute their routing tables. A router in area 0.0.0.3 would return "ICMP destination unreachable" to the sending router.
With the summarization shown, however, the change in status of prefix 10.1.1.0/24 affects only the routing table of area 0.0.0.1. When the area 0.0.0.3 router sends its packet, that packet will take the default route to area 0.0.0.0. Area 0.0.0.0 sees that the destination is within the summary route 10.1.0.0/16, which it associates with area 0.0.0.1. The backbone will forward the packet to area 0.0.0.1, where a router there will return the destination unreachable message.
While summarization of this sort can cause an increased amount of traffic to flow, practical experience shows that routing stability is generally more important than minimizing traffic. I emphasize "generally." If area 0.0.0.1 were in Japan and area 0.0.0.3 were in Peru, traffic minimization would become much more important given the cost of transoceanic bandwidth.
OSPF and IS-IS do have additional concepts of scopes of internal routes. Conceptually, an internal route stays in its own area. In actuality, OSPF intra-area routes will propagate outside the originating area to other non-stub areas and area 0.0.0.0.
The protocols define characteristics of routers and of areas with respect to routes originating outside their areas. See Tables 1 and 2.
Table 1. OSPF Router Types
| Type | Function | Area 0.0.0.0 | Nonzero Area | Other |
| Internal | Passes intra-area routes inside its area. Sends them to connected ABRs and ASBRs. | No inter-faces | No more than 1 | None |
| Backbone | Passes intra-area routes inside its area. Sends them to connected ABRs and ASBRs. | 1 or more | 0 or more | None |
| Area border | Accepts all types from nonbackbone to backbone. Depending on the type of stubbiness in the non-backbone area, may send some or no routes from backbone to non-backbone | 1 or more | 1 or more | |
| Autonomous system border | Accepts all types from external to backbone or non-backbone. Depending on the type of stubbiness in the non-backbone area, may send some or no routes from backbone to non-backbone | 0 or more | 0 or more | redistribute and/or default-information-originate |
IS-IS refers differently to routers, reflecting its approach that a router, not interfaces of a router, is of a single type.
Table 2. IS-IS Router Types
| Type | Routes known | External Connectivity | Other |
| Level 1 | Generated with single NET | No | None |
| Level 1 (multi-area) | Generated with multiple NET assigned to one area | No | None |
| Level 2 | Backbone | Optional | |
| Level 1/2 | 1 or more non-backbone areas Selected inter-area or externals | Optional | redistribute and/or default-information-originate |
Standard IS-IS level 1 routes only propagate into the backbone. There are new extensions that allow controlled leakage of IS-IS level 2 routes into nonbackbone areas, but otherwise, IS-IS nonbackbone areas behave like OSPF totally stubby areas.
OSPF's external relationships are not particularly associated with areas. You can reasonably argue that OSPF assumes that an AS is a set of areas (i.e., a single area, or an area 0.0.0.0 and some number of nonzero areas), which exchange routing information. Externals come from redistribution or default information origination.
Table 3. OSPF Area Types
| Area type | Can contain ASBR? | Can pick optimum exit among multiple area border routers? | Can be traversed by a virtual link? |
| Regular | Yes | Yes | Yes |
| Stubby | No | Yes | No |
| Not-so-stubby (NSSA) | Yes | Yes | No |
| Totally stubby | No | No | No |
| NSSA + totally stubby | Yes | No | No |
There still may be legitimate reasons to advertise more-specific, non-summarized routes. See Figure 8. Area 0.0.0.2 has two border routers, basil and bran, that give it connectivity to the core. Inside area 0.0.0.2, the routers and hosts on the left side of the network are in 10.2.0.0/18, while the right side has routers and hosts numbered in 10.2.64.0/18.
Figure 8: Areas with Multiple Exits
Assume that the two left-right links inside the area (dotted red lines) fail. basil and bran still are announcing 10.2.0.0/16 into the core, but basil can actually reach only 10.2.0.0/18 and bran can reach only 10.2.64.0/18. The core has a 50% chance of sending traffic to a router that will blackhole the traffic.
Cisco has chosen to make the summary fixed, regardless of internal failures, because it believes that stability is more important than optimal reachability. Nortel, in Bay RS, makes a different assumption: if any part of the summarized address space becomes unreachable, the router stops summarizing and announces all specific routes to the backbone.
I truly wish that both vendors would add each other's approach, because they each are a valid technique, depending on the design priorities of the specific network.
All of the loose hierarchical categories mentioned above are autonomous systems (AS). Be aware that most discussions of interior routing protocols use an old definition of AS. RFC 1930 describes an AS as a set of addresses (and, by association, routers), under one or more administrations, that present a common routing policy to the internet.
RFC 1771, the BGP specification, says "the classic definition of an Autonomous System is a set of routers under a single technical administration, using an interior gateway protocol and common metrics to route packets within the AS, and using an exterior gateway protocol to route packets to other autonomous systems. Since this classic definition was developed, it has become common for a single AS to use several interior gateway protocols and sometimes several sets of metrics within an AS. The use of the term Autonomous System here stresses the fact that, even when multiple IGPs and metrics are used, the administration of an AS appears to other autonomous systems to have a single coherent interior routing plan and presents a consistent picture of what destinations are reachable through it."
OSPF and EIGRP consider an AS a set of addresses and routers under a single administration. More current practice tends to call this a routing realm or a routing domain. Cisco training materials do not necessarily use the current definitions.
What is called an "AS number" in (E)IGRP, for example, is really a routing domain identifier with a scope of the entire routing domain. EIGRP domains will not automatically exchange routing information unless they have the same AS number. OSPF does not explicitly use the AS number, but has process IDs that have a scope limited to a single physical router.
OSPF and IS-IS are not explicitly concerned with AS numbers, but both have a concept of external routes. External routes are any that are not generated by the local dynamic routing domain (i.e., a backbone and a set of subordinate areas). OSPF and IS-IS need to know what is external to them, but not what number is associated with the externals.
A routing process runs on a single physical router and contributes routes to the RIB of that router. This process may include multiple areas. It does not, however, automatically share raw routing information with other processes of the same type on the same router.
A single physical router may contain more than one routing process. The process identifier is on the router command. You must specify a process identifier with OSPF, even if you have only one process. With IS-IS, you only need to specify it if you have more than one process.
A routing domain can contain multiple physical routers under common administration. The term routing realm has the same meaning as "routing domain."
The relationships between the routing computation and the main routing table are subtle. Routing processes will maintain separate topological databases, but there is only one main routing table or routing information base (RIB). The RIB is a formal name for the routing table, or that which is displayed by show ip route.
Figure 9. Multiple OSPF Processes
Let's say OSPF #1 produces an intra-area route 192.0.2.0/24 with metric 100, while OSPF #2 produces an intra-area route 192.0.2.0/24 with metric 50. Also, let's say OSPF #1 produces an inter-area route 192.0.3.0/24 with metric 10, while OSPF #2 produces an intra-area route 192.0.3.0/24 with metric 50. Remember that intra-area routes are always preferred to "inter-area."
The routing table will install the OSPF #2 route to 192.0.2.0/24 and the OSPF #2 route to 192.0.3.0/24. In the main routing table display, they will both simply show with source code "O." I think -- but would have to verify -- that show ip route 192.0.2.0/24 would reveal the process that generated the route.
[IE-SCRT-WP1-F03]
[2001-02-27-04]
|