OVERVIEW OF ROUTING PROTOCOLS

As you've learned, a protocol is a formalized system for exchanging a specific type of information in a certain way, and an algorithm is a system of rules carefully crafted to control a process that must contend with varying factors.

In our context, a routing protocol formalizes the ongoing exchange of route information between routers. Messages called routing updates pass information used by routing algorithms to calculate paths to destinations. A routing algorithm is a system of rules that controls an internetwork's behavior in such a way that it adapts to changing circumstances within the internetwork's topology. Ongoing changes include such things as which links are up and running, which are fastest, whether any new equipment has appeared, and so on. Each router uses its own copy of the algorithm to recalculate a map of the internetwork to account for all the latest changes from its particular perspective.

Routing protocols use a peer arrangement in which each router plays an equal role. Those new to internetworking often think that routers are somehow coordinated by a centralized management server, maybe an SNMP server. They are not. There is no routing protocol server to centrally manage routing processes. Ongoing routing table maintenance is handled in real time through an arrangement in which each router makes its own route selection decisions. To configure a routing protocol for an internetwork, the routing protocol process must be configured in each router that will be involved in the arrangement. In practical terms, the IOS config file for every router must have parameters set to send and receive routing updates, run the algorithm, and so forth. Properly configured, the routing protocol is able to collectively influence all these machine-made decisions so that they work in harmony. The area within which routing information is exchanged is called a routing domain, sometimes also referred to as an autonomous system.

Note 

The terms "path" and "route" are synonymous. "Path" is widely used for no other reason than it's hard to discuss routing protocols that use routing algorithms to calculate new optimal routes for distribution in routing updates sent to all routers for use in recalculating their respective routing tables. You get the point.

Routing Protocol Basics

Of the many routing protocols, some are standards-based and others are proprietary. Several are old and fading from use, a few are used only within narrowly defined market niches, and others are in such wide use that they are de facto standards. Routing protocols also differ in the types of internetworks they're designed to manage and in the size of internetworks they can handle. Naturally, these differences are mani fested in each routing protocol's algorithm. Yet all their algorithms share these two basic processes:

• Routers send one another update messages, advising of changes in internetwork topology and conditions.

• Each router recalculates its own routing table based on the updated information.

Updating one another helps each individual router know what's going on. More importantly, it helps orchestrate an internetwork's routers by maintaining a common set of information with which to operate.

The Routing Table's Central Role

A routing table is a list of routes available to forward traffic to various destinations. Every router in an internetwork maintains its own routing table, the contents of which differ from those maintained by other routers. Each router maintains a single routing table (not one per interface). The majority of routers run just one routing protocol, although specialized border routers run two in order to pass routes between areas using different protocols (more on that later).

Note 

Routing tables often refer to multiple tables for a given routing protocol. For instance, Open Shortest Path First (OSPF) maintains multiple tables of information that are all part of the routing table.

A routing table constitutes the router's self-centered view of the internetwork's topology-sort of its personal formula for conducting business. Every time an update is received, the routing protocol takes the information and mashes it through its algorithm to recalculate optimal paths to all destinations deemed reachable from that router. Figure 12-1 illustrates the routing table update process.

Figure 12-1: Routing update messages coordinate routing tables

Each router must have its own routing table to account for conditions specific to its location in the internetwork. In a routing domain, the routers collectively share the same news about any change, but then each puts that information to use individually.

The Routing Protocol Is an Internetwork's Intelligence

The goal of routing protocols is to let an internetwork respond to change. They do this by providing routers with a common framework for decision-making about how to respond to topology changes within the internetwork. The routing protocol coordinates the passing of updates between routers, and then each router recalculates optimal routes in its own table. If, after recalculation, all the routing tables have arrived at a common view of the topology-albeit each from its self-centered perspective-the internetwork is said to have reached convergence (so called because the router community has converged on a singular view of the topology). A converged topology view means all the routers agree on which links are up, down, running fastest, and so on.

Routing protocols are the quintessence of high-tech internetworking. They represent the ability of individual devices, and even whole networks, to help manage themselves. One could say that internetworks have become organic in the sense that routing protocols make them self-aware and self-correcting. As topologies grow from day to day or circumstances change from moment to moment, internetworks can respond, because routing protocols enable the router community to converse intelligently about what to do.

A trendy marketing cliché holds that "the network is the system." If that's true, then routing protocols serve as the network's operating system. Routing protocols raise the limit on what is practical in terms of internetwork size and complexity. It's no exaggeration to state that the development of sophisticated routing protocols is what has made the Internet's explosive growth possible.

Note 

Cisco Discovery Protocol (CDP), the Hot Standby Routing Protocol (HSRP), and other specialized protocols are sometimes also referred to as routing protocols. For our purposes, a routing protocol is a protocol that coordinates the exchange of routing updates to notify other routers of topology changes and applies an algorithm to recalculate optimal routes through an internetwork.

Comparing Routed Networks to Switched Networks

A good way to explain routing protocols is by comparison. Remember switching tables from Chapter 5? To refresh: Switches keep track of switched network topologies by brute force. Every time a message arrives, the switch associates the frame's source MAC address (layer 2 physical address) with the switch port it came in on and then makes an entry into its MAC address table. In this way, the switch builds a list of destination MAC addresses for each switch port. Here's the basic layout of a switch's address table:

Destination MAC Address	Destination Switch Port
0060.2fa3.fabc	Fast Ethernet0/8
0050.0465.395c	Fast Ethernet0/4
0010.5a9b.b5e6	Fast Ethernet0/12
.	.
.	.
.	.

This isn't a particularly intelligent way to map routes, because the switch's MAC address table only sees the next step. The table says nothing about the complete route to the destination; it merely shows you out the next door. The only way a switch can reduce the number of hops a frame must take between switches is to compile bigger and bigger MAC address tables, thereby increasing the odds that the best path will be encountered. Switch designers call this "optimization," but what's really being optimized is MAC addresses. (In case you're wondering how switches choose among alternative paths, they favor those most frequently used, which appear higher in the MAC address list.)

Routers, by contrast, can see more than one step ahead. Routing tables give routers the ability to see farther into an internetwork without expanding their lists. Where switches substitute quantity for quality, routers apply intelligence. Here's the basic layout of a simple type of routing table:

Destination	Next Hop	Hop Count
209.98.134.126	209.126.4.38	3
	127.197.83.128	5
	202.8.79.250	9
.	.	.
.	.	.
.	.	.

This example may not look like much, but it's "smarter" than the switch table in a fundamental way. The switch plays the odds, but the router plays it smart, because the Hop Count column gives the router additional information about the entire route. Knowing how many routers a packet must hop through to reach its destination helps the sending router choose the best path to take. This kind of measurement is called a routing metric, or metric for short. Metrics such as hop count are what separate routing from the switch's abrupt "out this door, please" approach. Metrics supply the intelligence needed by routing algorithms to calculate best paths through internetworks.

Routing Updates Are Control Messages

Routed networks carry an undercurrent of specialized traffic that exchanges routing update messages. Switched networks do no such thing; they guess at what's going on by looking only at the source MAC address and incoming port of payload packets. A payload message, by the way, is one that carries content useful for an application instead of for the internetwork's internal operations. Figure 12-2 outlines the difference.

Figure 12-2: Routers use control messages to update routing tables; switches don't

Routing updates aren't payload messages, they're control messages. The content they deliver is used by the internetwork for internal operations. This second type of traffic carrying routing updates is the lifeblood of internetworking, delivering the intelligence an internetwork must have to act in a unitary fashion and survive in the face of change. Given their importance, to reach a basic understanding of routing protocols, you need to know what routing updates contain, how and where they're sent, and how they're processed.

Dynamic vs. Static Routing

Before we go further, a little background is in order. There are two basic types of routing:

• Static routing A static route is a fixed path preprogrammed by a network administrator. Static routes cannot make use of routing protocols and don't self-update after receipt of routing update messages; they must be updated manually.

• Dynamic routing This is the type of routing made possible by routing protocols, which automatically calculate routes based on routing update messages. The majority of all internetwork routes are dynamic.

This distinction is made here to drive home a key point. Not all routes are automatically (dynamically) calculated by routing protocols, and for good reason. In most situations, network administrators will opt to retain direct control over a minority of routes.

The best example of how static routes are used is the default gateway. A router can't possibly know all routes to all destinations, so it's configured with a default gateway path to which packets with unknown destinations are sent. Default gateways are entered as static routes to make sure undeliverable traffic is steered to a router that has routing table entries leading outside the internetwork. Figure 12-3 shows a default gateway in action in two places: first at the PC, which has been told its default gateway is on an interface of a particular router; then at the router, where its default gateway is out of its Internet interface.

Figure 12-3: The classic example of a static route is a network's default gateway

The ability of routing protocols to automate routing table selection is a good thing, but only in measured doses. The use of static routes as default gateways to handle unanticipated messages exemplifies this.

Routers Collaborate to Attain Convergence

Convergence is when all routers in an internetwork have agreed on a common topology. For example, if a particular network link has gone down, the internetwork will have converged when all the routers settle on new routes that no longer include that link. Yet each router must have its own routes to account for its unique position in the network topology. Thus, the routers act collectively by sharing updates, yet take independent action by calculating their own routes. When the process is complete, they have converged, in the sense that all the routes were calculated based on a common set of assumptions about the network's current topology.

This collaboration is orchestrated by the internetwork's routing protocol. Having routers work collectively gives internetworks their strength, because it may take more than one router to isolate a network problem. And, until a problem is isolated, no router has the information needed to calculate new routes around the problem.

How Routers Sense Topology Change

Routers use gateway discovery protocols to keep track of one another. A gateway discovery protocol is a system that coordinates the exchange of small "Are you still there?" messages between routers in an internetwork, mainly as a way of sensing downed links:

• Each router broadcasts "hello" messages to its immediate neighbor routers at a fixed interval (say, once every 90 seconds).

• If no ACK (acknowledgment message) is received back within a specified period (three minutes), the route is declared invalid.

• If no ACK has returned within a longer period (seven minutes), the router and its routes are removed from the sending router's table, and a routing update is issued about all routes that incorporated the nonresponding router as a link.

Gateway discovery protocols are low-overhead control protocols that in IP networks are sent using the UDP transport protocol. Figure 12-4 illustrates how they work.

Figure 12-4: Gateway discovery protocols use timers to detect topology changes

In addition to sensing problems, gateway discovery protocols detect the appearance of new equipment. The four types of gateway discovery messages in Figure 12-4 are collectively referred to as timers.

How Routing Updates Converge

Sensing a topology change is only the first step. From the point of discovery, routing updates must be passed until all routers can converge on a new topology by incorporating the change.

Let's take an example. Figure 12-5 shows a relatively simple four-router topology with route redundancy, in that messages have alternative paths to destinations. A message sent from Manufacturing to Accounting could travel through either the R&D or Marketing router. If packets sent from Manufacturing through the R&D router to the Expense Report server suddenly become undeliverable, the Accounting router can't be relied upon to diagnose the problem on its own. This is because there are so many potential sources for the problems, as depicted by the question marks in Figure 12-5. Here's a roundup of the most likely suspects of what caused the problem:

1. The Expense Report server has crashed.

2. The LAN connection to the Expense Report server has failed.

3. The Accounting router's interface to the Expense Report server's LAN segment has failed.

4. The Accounting router has totally failed.

5. The Accounting router's serial interface to the R&D router has failed.

6. The serial transmission line connecting Accounting with R&D is down.

7. R&D's serial interface to the Accounting router has failed.

8. The R&D router has totally failed.

9. R&D's serial interface to the Manufacturing router has failed.

10. The serial transmission line connecting R&D with Manufacturing is down.

11. Manufacturing's serial interface to the R&D router has failed.

Figure 12-5: Routers must collaborate to locate network problems

The Accounting router can't have definitive knowledge as to problems 1, 7, or 8 because it's not directly responsible for these network devices, and the Accounting router would be of no use at all in the event of problem 4.

Packets can't be routed to detour around the failure until the problem has been located. Also, the problem must be located in order for the routers to converge on a new (post-failure) network topology.

If, in our example topology, the serial line between Accounting and R&D has failed, both routers would sense this at about the same time and issue updates. Figure 12-6 tracks the routing update as it flows from the Accounting and R&D routers. Once the router has sensed the problem, it deletes the failed path from its routing table. This, in turn, causes the routing algorithm to calculate a new best route to all destinations that had incorporated the failed link. When these new routes are calculated, the router issues them in a routing update message sent out to other routers in the internetwork.

Figure 12-6: Only two routing updates are necessary to converge

Updated routing information is sent from the Accounting and R&D routers to announce that they are no longer using the serial line in their routes. These are routing update messages. The Manufacturing and Marketing routers, in turn, replace any routes they have using the serial link. In the example in Figure 12-6, it took two routing updates for the internetwork to converge on a new topology that's minus the serial line. When the serial line is brought back online, the connected routers will also sense the topology change, and the whole route update process will repeat itself in reverse.

Short convergence time is a primary design goal when laying out an internetwork's topology. In big networks, it can take several updates to converge. The length of convergence time depends on the routing protocol used, the size of the internetwork, and where in the topology a change takes place. For example, if the problem in Figure 12-5 had occurred behind the Accounting router's gateway, only the Accounting router would have originated a routing update, which would have resulted in a convergence time of three updates.

Long convergence time is a symptom of a poorly functioning internetwork. Many factors can slow convergence, but the major factor in convergence times is propagation delay.

Propagation Delay

A network phenomenon called propagation delay is the delay between the time a packet is sent and when it arrives at its destination. Propagation delay isn't a simple matter of geographical distance or hop count; other factors can also have an influence. Figure 12-7 shows various propagation delay factors.

Figure 12-7: Several factors can influence the length of propagation delay

Obviously, something as basic as the time required for data to travel over a network is important to all areas of internetworking. But propagation delay is a factor for routing protocols, because not all routers receive a routing update at the same moment. No matter how fast the network medium, convergence takes time, as a routing update is passed from router to router until it arrives at the farthest router.

The importance of propagation delay grows with an internetwork's size. Big internet-works have dozens of routers and hundreds of connected LAN segments-each a potential source of topology change. All other things being equal, the bigger the network, the greater its propagation delay; and the more redundant paths are used, the greater the potential for confusion.

Routing Loops

Propagation delay wouldn't pose a problem to routing protocols if routers always converged before any new changes emerged. But they don't. The longer propagation delay is in an internetwork, the more susceptible it is to something called a routing loop. A routing loop is when payload packets can't reach their destinations because of conflicting routing table information. This happens in large or change-intensive internetworks when a second topology change emerges before the network is able to converge on the first change.

Taking the example shown in Figure 12-8, the R&D router senses that network 10.1.1.12 has gone down and issues a routing update. But before the Manufacturing router receives the update, it issues a routing update indicating that network 10.1.1.12 is still good (because the update has paths that incorporate this network). The updates from R&D and Manufacturing conflict and, depending on how the timing works out, can confuse the other routers and even each other, throwing the internetwork into a routing loop.

Figure 12-8: A routing loop can start when routing updates overlap

Routing loops can be self-perpetuating. If the conflicting routing updates are persistent enough, each repeatedly nullifies the other in route decisions made by the affected routers. If the router's primary route vacillates each time it receives an update, the internetwork has become unstable. If things go too far out of balance (for example, there are too many loops in progress and primary route selections are flapping), the protocol's collective topology can begin to disintegrate altogether. The downward spiral goes like this:

• Two or more conflicting routing updates cause messages to be routed via downed routes, and thus they are not delivered.

• As the loop persists, more bandwidth is consumed by inefficiently routed payload packets and routing updates trying to fix the problem.

• The diminishing bandwidth triggers still more routing updates in response to the worsening throughput.

The vicious circle of a routing loop is depicted in Figure 12-9.

Figure 12-9: If network events outpace convergence, infinite loops can occur

Mechanisms to Keep Internetworks Loop-Free

A scenario like the one just described is unacceptable to effective network operations. Routing protocols incorporate a number of sophisticated mechanisms to thwart the onset of routing loops:

• Hold-downs Suppression of advertisements about a route that's in question long enough for all the routers to find out about its true status.

• Split horizons The practice of not advertising a route back in the direction of the route itself.

• Poison reverse updates A routing update message that explicitly states a network or subnet is unreachable (instead of a nearby router merely dropping it from its routing table for lack of use).

• Maximum hop count Packets traverse a maximum number of hops between source and destination. Once they have exceeded their limit, they are dropped, thus avoiding a loop.

Hold-Downs A hold-down is a way to help prevent bad routes from being reinstated by mistake. When a route is placed in a hold-down state, routers will neither advertise the route nor accept advertisements about it for a specific interval called the hold-down period. Hold-downs have the effect of flushing information about a bad route from the internetwork. It's a forcible way to take a bad apple from the barrel to help reduce the chances of it starting a routing loop. At the extreme, a hold-down period would be an interval slightly longer than it normally takes for the entire network to learn of a routing change-its average convergence time.

But holding back the release of routing updates obviously slows convergence, so there's a harsh trade-off between the loop-prevention benefit of hold-downs and the quality of network service. This is because delaying the release of an update leaves a bad route in play for a longer period. In internetworks of any size, setting hold-down intervals to match average convergence time results in frequent timeout messages to end users. In the real world, hold-down times are often set to an interval far less than the network's average convergence time to partially ameliorate loop risk, but at the same time avoid most network timeouts for users. This trade-off is depicted in Figure 12-10.

Figure 12-10: Hold-downs prevent routing loops, but can slow down network performance

Split Horizons A split horizon is a routing configuration that stops a route from being advertised back in the direction from which it came. The theory is that it's basically useless to send information back toward its source. An example of this is outlined in Figure 12-11. Router B, in the middle, received a route to network 10.1.99.0 from Router A on the left. The split-horizon rule instructs Router B not to include that route in updates it sends back toward Router A. The assumption is that Router A was probably the source of the route (given that it is in the direction of network 10.1.99.0), and, therefore, it doesn't need to be informed of the route. If Router A's interface to network 10.1.99.0 went down and it didn't have enough built-in intelligence, it might take its own routing update back from Router B and try to use it as a way around the downed interface.

Figure 12-11: A split horizon stops a routing update from echoing back to its source

Hold-downs can normally prevent routing loops on their own, but split horizons are generally configured as a backup measure because there's no particular trade-off in using them.

Poison Reverse Updates By now, you've probably noticed that routing protocols work implicitly. In other words, they steer traffic around a bad link by not including routes involving that link in routing updates. Poison reverse updates, by contrast, explicitly state that a link is bad. Poison reverse works by having a router check for overlarge increases in metrics. Routing metrics are designed such that an increase reflects deterioration. For example, an increase in the number of hops a route must take makes it less desirable. A router compares an incoming routing update's metric for a route against what it was when the router itself had issued an earlier update including that same route. The routing protocol is configured with an acceptable increase factor that, if exceeded, causes the router to assume the route is a "reversing" message. Figure 12-12 depicts the process.

Figure 12-12: Most routing updates are implicit corrections; poison reverse updates are explicit

In Cisco routing protocols, the default increase for a routing metric is a factor of 1.1 or greater. In other words, if a route returns in an update with a metric that is 110 percent or more of what it was on the way out, it's assumed that a loop is in progress. For example, if a router sends out an update with a route with a hop count metric of 1, and it returns in someone else's update with a hop count of 2, the assumption is that a loop is under way. When this happens, the router is placed into a hold-down state in which it neither sends nor receives updates on that route. The hold-down state stays on for a period deemed sufficiently long to flush the problem from the update system-thus the name poison reverse. The loop is a bad metric "reversing" onto the router; the hold-down is a way of "poisoning" (or killing) updates that could contain the bad metric.

Split horizons are a good way to prevent routing loops among adjacent routers. But in large internetworks in which routing updates are passed between routers far removed from one another, poison reverse updates help prevent bad routes from starting to loop before update convergence can take place.

Maximum Hop Count This refers to the number of routers a packet can move through. Every time a packet moves through a router, another hop is added to the count. Once it reaches the given number of hops, the packet is discarded.

Hop counts are used to avoid problems caused by loops. For example, if the maximum hop count is 15, then if the packet moves through 14 routers, if the next hop does not take it to its destination, it will be dropped. This prevents packets from eternally hopping from one router to the next.

Routing Metrics

A routing metric is a value used by a routing protocol to influence routing decisions. Metric information is stored in routing tables and is used by routing algorithms to determine optimal routes to destinations. The terminology takes some getting used to, but here are the most widely used metrics:

• Cost Not financial cost, but a theoretical "cost" number used to represent the time, difficulty, risk, and other factors involved in a route.

• Distance Not physical distance in miles or cable feet, but a theoretical "distance" number. Most distance metrics are based on the number of hops in a route.

• Bandwidth The bandwidth rating of a network link (100 Mbps, for example).

• Traffic load A number representing the amount of traffic (such as the number and size of packets) that traveled over a link during a specified period of time.

• Delay In this context, the time between the start of a routing update cycle and when all routers in an internetwork converge on a single topology view (also called propagation delay or latency).

• Reliability A relative number used to indicate reliability of a link.

• MTU The maximum packet size (maximum transmission units) that a particular network interface can handle, usually expressed in bytes.

Note 

Sometimes, "cost" is used as a general term for the result calculated by an equation inside the routing protocol algorithm. For example, someone might state that the overall cost of one route was more than another's, when actually the routing algorithm used metrics for distance, bandwidth, traffic load, and delay.

Some simple routing protocols use just one metric. However, usually more than one routing metric goes into determining optimal routes. For example, a two-hop route traversing a 9,600-Kbps serial line is going to be much slower than a three-hop route going over T3 circuits at 44 Mbps. You don't have to be Euclid to figure out that moving bits 4,000 times faster more than compensates for an extra hop.

Sophisticated routing protocols not only support multiple metrics, they also let you decide which to use. In addition, you can assign relative weights to metrics and more precisely influence route selection. If the network administrator sets the metrics properly, the overall behavior of the internetwork can be tuned to best fit the enterprise's objectives. Figure 12-13 shows some routing metrics in action.

Figure 12-13: Routing metrics are used to influence decisions that routing algorithms make

All Cisco routing protocols come with default settings for metrics. These default settings are based on design calculations made in Cisco's labs and on real-world experience gained in the field. If you ever get your hands on a routing protocol, think long and hard before you start changing routing metric default settings. The domino effect of a bad routing metric decision can be devastating. Out-of-balance metric settings can be manifested in the form of poor network performance and routing loops.

Routing Protocol Architectures

There are three basic types of routing protocol architectures:

• Distance-vector routing protocols Simple algorithms that calculate a cumulative distance value between routers based on hop count

• Link-state routing protocols Sophisticated algorithms that maintain a complex database of internetwork topology

• Hybrid routing protocols A combination of distance-vector and link-state methods that tries to incorporate the advantages of both and minimize their disadvantages

Distance-Vector Routing

Early distance-vector routing protocols used only a so-called distance metric to calculate the best route to a destination. The distance is the number of router hops to the destination. Distance-vector algorithms (also called Bellman-Ford algorithms) operate a protocol in which routers pass routing table updates to their immediate neighbors in all directions. At each exchange, the router increments the distance value received for a route, thereby applying its own distance value to it. The updated table is then passed further outward, where receiving routers repeat the process. The fundamental theory is that each router doesn't need to know all about other links, just whether they are there and what the approximate distance is to them. Figure 12-14 depicts the distance-vector routing update process.

Figure 12-14: Distance-vector routing propagates routing updates at fixed intervals

Distance-vector routing can be slow to converge. This is because routing updates are triggered by timers to take place at predetermined intervals, not in response to a network event that causes a topology change. This makes it harder for distance-vector protocols to respond quickly to the state of a link's current operating condition. If a network link goes down, the distance-vector system must wait until the next timed update cycle sweeps past the downed link to pick it up and pass an updated routing table-minus the downed link-through the internetwork.

Note 

The name "distance-vector" can be confusing, because some advanced distance-vector protocols use routing metrics other than theoretical distance. In fact, some newer so-called distancevector installations only partially rely on the hop count metric. The best way to think of distance-vector protocols is that they update routing topologies at fixed intervals.

Relying on fixed-interval updates renders distance-vector protocols slow to converge on topology changes and, therefore, more susceptible to routing loops. Also, most distance-vector protocols are limited to 16 hops and are generally used in internetworks with fewer than 50 routers.

Despite their unsophisticated ways, distance-vector protocols are by far the most widely used. While the distance-vector method is simple and easy to configure, it doesn't scale well. On the other hand, because it doesn't do a lot of calculating, it consumes little router CPU or memory resources. Generally, distance-vector algorithms are good enough to adapt to topology changes encountered in smaller internetworks. The most widely installed distance-vector routing protocols are RIP and IGRP.

Link-State Routing

Link-state routing is event-driven. Also known as shortest path first ( SPF ), link-state routing protocols focus on the state of the internetwork links that form routes. Whenever a link's state changes, a routing update called a link-state advertisement ( LSA ) is exchanged between routers. When a router receives an LSA routing update, the link-state algorithm is used to recalculate the shortest path to affected destinations. Link-state routing attempts to always maintain full knowledge of the internetwork's topology by updating itself incrementally whenever a change occurs. Figure 12-15 depicts the link-state process.

Figure 12-15: Link-state routing is event-driven

The link-state algorithm does much more than just have a router add its local distance value to a cumulative distance. After an LSA update is received, each router uses the algorithm to calculate a shortest path tree to all destinations. Link-state calculations are based on the Dijkstra algorithm. This process yields entirely new routes instead of merely applying new distance values to preexis ting routes. Think of it this way: Distance-vector routing places a new value on the same old route; link-state routing's SPF algorithm builds whole new routes piece by piece, from the link up. SPF is able to do this because the link-state database contains complete information on the internetwork's components and its topology.

New routes calculated by SPF are entered into the updated routing table. These entries include recalculated values for all metrics configured for use in the link-state implementation. Possible metrics include cost, delay, bandwidth, reliability, and others, with their values updated to reflect the new route. This is done by rolling up metric information for each link incorporated into the newly calculated route. Figure 12-16 shows how the SPF algorithm picks the best route.

Figure 12-16: Link-state routing's SPF algorithm builds the shortest paths from the link up

There are two other advantages to link-state routing; both have to do with bandwidth conservation. First, because LSA updates contain only information about affected paths, routing updates travel faster and consume less bandwidth. Second, in distance-vector routing, most update cycles are wasted because they take place even though there was no topology change. Unnecessary update cycles not only increase bandwidth overhead, but also boost the odds that conflicting routing updates will be converging simultaneously. By issuing LSA updates when required-in addition to their regular update intervals-link-state protocols diminish the opportunity for the self-perpetuating conflicts of routing loops.

Because link-state protocols are event-driven, adaptation to topology change need not wait for a series of preset timers to go off before the convergence process can begin.

This not only makes link-state protocols less prone to loops, but also makes them more powerful in that there is no limit on the number of hops in the routes they calculate.

The drawbacks to link-state routing protocols mainly have to do with logistics and expense. During the initial stages of implementation, LSA traffic tends to flood an internetwork with database-building control messages, making implementation expensive. Because it does so much more calculating, link-state routing also can consume considerable router CPU and memory resources when recalculation is necessary. This means that those considering an upgrade to a link-state routing protocol must face the prospect of spending money on equipment upgrades. Yet perhaps the biggest hurdle to link-state protocols is that they're complicated. These are sophisticated routing protocols that can be intimidating to network administrators, especially those set in their ways. The best known link-state protocols are OSPF and IS-IS.

Hybrid Routing

Hybrid routing protocols use more accurate distance-vector metrics in a protocol designed to converge more rapidly. Although open standards have been developed for so-called hybridized routing, the only Cisco product based on the concept is the Enhanced Interior Gateway Routing Protocol (EIGRP).

How Routing Protocols Are Implemented

Much like firewalls, routing protocols take their own particular view of the internetwork landscape. To a firewall, networks are either inside or outside, and connections are controlled accordingly. Routing protocols have as their overriding concern the gathering and dissemination of updated topologies, not connections. Thus, routing protocols define the networking landscape in terms of interior and exterior, where one routing domain ends and another begins. This is because a router needs to know which other routers are part of its own routing domain (are in the interior) and, therefore, should share routing updates.

Autonomous Systems

Administrative control is defined as who controls the configuration of equipment in a network. Because the Internet interconnects so many organizational entities, it has developed the concept of an autonomous system. An autonomous system is defined as a collection of networks that are under the administrative control of a single organization and that share a common routing strategy. Most autonomous systems are internetworks operated by corporations, Internet service providers (ISPs), government agencies, and universities.

Looking at the three autonomous systems in Figure 12-17, each regards the other two as exterior (or external) autonomous systems. This is because the other two are under the administrative control of someone else, and they are running a separate routing strategy. A routing strategy is a term used to describe the fact that routing updates are being exchanged under a common routing protocol configuration. Thus, a routing strategy implies running a single routing process to exchange updates and sharing other configuration parameters, such as the relative settings of each path's metrics.

Figure 12-17: Routing protocols draw maps largely based on administrative control

The three autonomous systems in Figure 12-17 could be running the same routing protocol software-even the same version of the same routing protocol-but because the autonomous systems aren't within the same routing process of update messages and relative metrics settings, they don't share a common routing strategy.

The Difference Between Interior and Exterior Gateway Protocols

So what we have, then, is a nice, neat little package where routing domains and administrative domains overlay one another, right? Well, as always seems to be the case in internetworking, things aren't quite so tidy. If routing strategy were as simple as configuring one routing protocol for every administrative domain, there could be no Internet. After all, if everything were internal, who or what would coordinate routing updates between the millions of autonomous systems making up the Internet?

The answer is exterior gateway protocols. An exterior gateway protocol runs on routers sitting at the edge of an autonomous system and exchanges routes with other autonomous systems. These edge routers are also called border routers, boundary routers, or gateway routers. A routing protocol that operates within an autonomous system is an interior gateway protocol. Figure 12-18 shows the two side by side.

Figure 12-18: Several differences exist between interior gateway protocols and exterior gateway protocols

In practical terms, the most obvious difference between the two is where the routers running the protocol sit in the topology. Exterior routers sit at the edge of autonomous systems; interior gateway routers sit toward the middle. A closer inspection of how the exterior protocols are implemented brings out more fundamental differences:

• An exterior protocol lets an autonomous system designate certain other routers as peers. The border router exchanges updates with its peer routers and ignores other routers (in interior protocols, all routers participate in router updates).

• Routing tables maintained by exterior protocols are lists of autonomous systems (interior protocols keep lists of LAN segments).

• Exterior protocols simply insert a new route received for a destination into the routing table; no recalculation of new best paths is computed after an update is received (interior protocols recalculate new routes based on weighted metrics).

Methods That Let Autonomous Systems Interconnect

Reaching beyond an autonomous system invites potential trouble. For a firewall, the potential trouble is a security breach. For an exterior gateway protocol, the trouble can be either bad information about routes to other autonomous systems or just too much information to handle. The problems inherent in connecting to the outside also hold for exterior and interior protocols alike:

• Without some way to filter route exchanges, exterior protocols would be overwhelmed by a torrent of traffic flowing in from the Internet.

• Interior protocols could be confused about the best connections to take to the outside without being able to identify and select from various sources providing new routes.

Interior and exterior gateway routing protocols use a set of techniques to handle these problems. As a group, these techniques are intended to cut down on the volume of routing information and to boost the reliability of new route information that is received:

• Route summarization A technique that divides an internetwork into logical areas, with the area's border router advertising only a single summary route to other areas, thereby cutting down on the size of routing tables.

• Route filtering Also called administrative distance, an add-on metric that rates the relative trustworthiness of individual networks as a source from which to learn optimal routes.

• Route tagging A technique that tags a route in a number of ways to identify the source from which it was learned. Tags can include router ID, autonomous system number, exterior protocol ID, and exterior protocol metric.

• Router authentication In effect, this requires a communicating router to present a password before the receiving router will accept routing updates from it.

It's notable that some of the techniques are implemented in both internal and external systems, not just one or the other. This is done to enable interior and exterior routing domains to act in concert as messages flow between the autonomous system and outside world. Another notable fact is that some of these techniques are applied between interior routing domains where differing routing protocols are being run within the same autonomous system (for example, route summarization between OSPF and RIP routing processes).

Routing Domains, Routing Areas, and Administrative Domains

A routing domain is a group of end systems within an autonomous system. An autonomous system, in turn, is defined as an administrative domain, where there exists singular administrative control over network policy and equipment.

Most routing protocol architectures coordinate the exchange of complete route information between all routers in the routing domain. However, this practice can become inefficient as internetworks grow, because that means more updated traffic traveling longer distances.

State-of-the-art routing protocols use the concept of routing domain areas. A routing area is a subdivision of a routing domain into logically related groups, with each area uniquely identified by an area name or number. The primary benefit of areas is that route information can be summarized when exchanged between areas, cutting down on network overhead and enhancing control over traffic flow. Routing domain areas are also used to unify several smaller routing domains into a single, larger routing process.

Routing area	Routing area	Routing area
Routing domain

The typical global enterprise implements a single routing domain worldwide. This is done so that employees on one continent can connect to company colleagues and resources anywhere in the world. So it would follow, then, that there is always a one-to-one relation between a routing domain and an administrative domain. Until recently, this was the case.

A new phenomenon called external corporate networks extends routing domains across administrative domains. An external corporate network is a configuration in which two or more enterprises build a unified routing domain to share routes between their respective organizations. The shared routing domain is the subset of each enterprise's overall autonomous system, and contains the resources and users that are to participate in the shared business process. Figure 12-19 illustrates how such a configuration is set up.

Figure 12-19: An external corporate network is a routing domain across autonomous systems

The thing to focus on with external corporate networks is that routes are being freely exchanged between enterprises-at least within the shared routing domain area in the middle. The external corporate network configuration enables routers within two or more enterprises to keep up an ongoing dialog on how to route cross-border connections. This is a relatively new internetworking practice. Not that long ago, the idea of directly trading route information between autonomous systems was unthinkable, not only out of concern for system security, but also for competitive reasons.

This is the most advanced form of extranet, in that one system is allowed behind another's firewall. Think of it this way: Most extranets involve a person logging on through a firewall by entering a user name and password. In the example in Figure 12-19, the system of one enterprise is able to freely conduct business behind the firewall of another, system to system (not person to system). Harking back to the coverage of firewalls in Chapter 7, in an external corporate network, the extranet is route-based, not connection-based. Put another way, routes are shared between enterprises for long-term use. In the traditional extranet relationship, a user is allowed to connect to a resource on a per-session basis.