Search the Catalog
Managing IP Networks with Cisco Routers

Managing IP Networks with Cisco Routers

By Scott M. Ballew
1st Edition October 1997
1-56592-320-0, Order Number: 3200
352 pages, $34.95 US

Sample Chapter 5: Routing Protocol Selection

In this chapter:
Static vs. Dynamic Routing
Classification of Dynamic Routing Protocols
Selecting a Routing Protocol

In previous chapters, I have focused the discussion on network design and router selection. While these topics are important if you are building a new network or planning whole or partial replacement of an existing network, they're only of theoretical interest if you already have a network in place. In this case, which is far more common, you don't get to choose your topology, media, or router vendors. You're stuck with the decisions you and your predecessors have made. At best, you can design your ideal network, and think about how to migrate to that design over the coming years.

This chapter shifts from the theoretical aspects of network design to the more practical aspects of network management. While there will certainly be some theoretical discussion, especially in the first few sections, theory will be balanced with a more practical discussion of configuration issues, whether for a new network or an existing network.

Static vs. Dynamic Routing

Before exploring the issues surrounding the selection and configuration of dynamic IP routing protocols, it is appropriate to discuss static routing as an alternative. In Chapter 1, The Basics of IP Networking, we saw that each machine in an IP network makes decisions about how to reach a destination by consulting its own private routing table. Rather than computing the entire path to a destination, it merely selects the next hop leading to that destination, and relies on the next hop machine to select a further hop that gets the packet closer to its destination. Independent hop-by-hop routing requires that all machines have a consistent view of how to reach all destinations in the network. If consistency is lost, two or more machines (presumably routers) can form a routing loop, and the packet never makes it to its destination.

To achieve consistency, a network administrator can either manually configure each machine with a precomputed set of routes that he or she knows to be consistent, or the machines can communicate routing information to each other through some kind of protocol. The first approach is known as static routing, and the second as dynamic routing.

Advantages of Static Routing

Static routing has some enormous advantages over dynamic routing. Chief among these advantages is predictability. Because the network administrator computes the routing table in advance, the path a packet takes between two destinations is always known precisely, and can be controlled exactly. With dynamic routing, the path taken depends on which devices and links are functioning, and how the routers have interpreted the updates from other routers.

Additionally, because no dynamic routing protocol is needed, static routing doesn't impose any overhead on the routers or the network links. While this overhead may be minimal on an FDDI ring, or even on an Ethernet segment, it could be a significant portion of network bandwidth on a low-speed dial-up link. Consider a network with 200 network segments. Every 30 seconds, as required by the RIP specification, the routers all send an update containing reachability information for all 200 of these segments. With each route taking 16 octets of space, plus a small amount of overhead, the minimum size for an update in this network is over three kilobytes. Each router must therefore send a 3 Kb update on each of its interfaces every 30 seconds. As you can see, for a large network, the bandwidth devoted to routing updates can add up quickly.

Finally, static routing is easy to configure on a small network. The network administrator simply tells each router how to reach every network segment to which it is not directly attached. Consider the network shown in Figure 5-1. This network has three routers connecting five network segments together. Clearly, the only path from Router1 to a host on 172.16.3.0/24 goes through Router2. Likewise, the only path to hosts on subnet 172.16.4.0/24 goes through Router3.

Figure 5-1. A small network using static routing

 

Here are the relevant fragments of the configurations of these three routers using static routing. Note that each router configuration must contain a static route for the networks attached to the other routers, but not those directly attached to the router itself.

Configuration for Router1:

hostname router1
!
interface ethernet 0
	ip address 172.16.1.1 255.255.255.0
!
interface ethernet 1
	ip address 172.16.2.1 255.255.255.0
!
ip route 172.16.3.0 255.255.255.0 172.16.1.2
ip route 172.16.4.0 255.255.255.0 172.16.1.2
ip route 172.16.5.0 255.255.255.0 172.16.1.2
 
Configuration for Router2:
hostname router2
!
interface ethernet 0
	ip address 172.16.1.2 255.255.255.0
!
interface ethernet 1
	ip address 172.16.3.1 255.255.255.0
!
interface ethernet 2
	ip address 172.16.5.1 255.255.255.0
!
ip route 172.16.2.0 255.255.255.0 172.16.1.1
ip route 172.16.4.0 255.255.255.0 172.16.3.2
 
Configuration for Router3:
hostname router3
!
interface ethernet 0
	ip address 172.16.3.2 255.255.255.0
!
interface ethernet 1
	ip address 172.16.4.1 255.255.255.0
!
ip route 172.16.1.0 255.255.255.0 172.16.3.1
ip route 172.16.2.0 255.255.255.0 172.16.3.1
ip route 172.16.5.0 255.255.255.0 172.16.3.1

Each configuration starts by giving the router a name, and then defines an IP address and subnet mask for each of the router's interfaces. For example, on Router2, the second Ethernet interface (ethernet 1) is assigned the IP address 172.16.3.1, and the netmask 255.255.255.0. Similar commands defining addresses and netmasks for local interfaces will appear in all router configurations, regardless of whether a router is participating in a dynamic routing protocol. If the configurations stopped here, each router would have entries in its routing table for the networks attached to its own interfaces, and no others. But the configurations go on to define static routes showing how to reach networks attached to the other routers. Each ip route statement defines a static route to the destination indicated by the network number and mask by way of the router IP address listed. For example, the first ip route statement in Router3's configuration defines a route to 172.16.1.0, with a mask of 255.255.255.0 (172.16.1.0/24) via the router at 172.16.3.1. The static routes, together with the the local interfaces, let each router populate its routing table with information about each destination and the next hop to reach it.

While this small network doesn't require many static routes to achieve complete connectivity, and Router1 and Router3 could get by with static default routes pointing to Router2, it is easy to see that the configurations for a large network with hundreds of network segments and routers would be very complex.

And the Disadvantages of Static Routing

While static routing has advantages over dynamic routing, it is not without its disadvantages. The price of its simplicity is a lack of scalability. For five network segments on three routers, computing an appropriate route from every router to every destination is not difficult. However, many networks are much larger. Consider what the routing might look like for a network with 200 network segments interconnected by more than a dozen routers. To implement static routing, you would need to compute the next hop for each network segment for each router, or more than 2,400 routes! As you can see, the task of precomputing routing tables quickly becomes a burden, and is prone to errors.

Of course, you could argue that this computation need only occur once, when the network is first built. But what happens when a network segment moves, or is added? While the computation may be relatively easy, to implement the change, you would have to update the configuration for every router on the network. If you miss one, in the best case, segments attached to that router will be unable to reach the moved or added segment. In the worst case, you'll create a routing loop that affects many routers.

Finally, because static routing is, by definition, static, it cannot use redundant network links to adapt to a failure in the network. Consider what would happen to our network if we add an additional interface to Router3 and connected it to 172.16.2.0/24, but left routing unchanged. If Router2 fails, Router3 would be unable to adapt to the change in the network topology and would still be unable to reach hosts on 172.16.1.0/24. This inability to adapt to network failures, even when redundant paths are available, and the problems associated with scaling, are the primary motivations behind dynamic routing.

Advantages of Dynamic Routing

The chief advantages of dynamic routing over static routing are scalability and adaptability. A dynamically routed network can grow more quickly and larger, and is able to adapt to changes in the network topology brought about by this growth or by the failure of one or more network components.

With a dynamic routing protocol, routers learn about the network topology by communicating with other routers. Each router announces its presence, and the routes it has available, to the other routers on the network. Therefore, if you add a new router, or add an additional segment to an existing router, the other routers will hear about the addition and adjust their routing tables accordingly. You don't have to reconfigure the routers to tell them that the network has changed. Similarly, if you move a network segment, the other routers will hear about the change. You only need to change the configuration of the router (or routers) that connect the segment that moved. This reduces the chance that errors will occur.

The ability to learn about changes to the network's configuration has implications beyond adding new segments or moving old ones. It also means that the network can adjust to failures. If a network has redundant paths, then a partial network failure appears to the routers as if some segments got moved (they are now reached via alternate paths), and some segments have been removed from the network (they are now unreachable). In short, there's no real difference between a network failure and a configuration change. Dynamic routing allows the network to continue functioning, perhaps in a degraded fashion, when a partial failure occurs.

And the Disadvantages of Dynamic Routing

I would be a liar if I told you that dynamic routing has no disadvantages. Chief among the disadvantages is an increase in complexity. Communicating information about network topology is not as simple as saying, "Hey, I can reach the following destinations..." Each router participating in the dynamic routing protocol must decide exactly what information to send to other routers; more important, it must attempt to select the best route for reaching other destinations from the candidates it learns about from other routers. In addition, if a router is going to adapt to changes in the network, it must be prepared to remove old or unusable information from its routing table. How it determines what is old or unusable adds to the complexity of the routing protocol. Unfortunately, the better a protocol handles the various different situations in a network, the more complex it is likely to be. This complexity tends to lead to errors in the protocol's implementation, or differences in how vendors interpret the protocol.

In order to communicate information about the topology of the network, routers must periodically send messages to each other using a dynamic routing protocol. These messages must be sent across network segments just like any other packets. But unlike other packets in the network, these packets do not contain any information to or from a user. Instead, they contain information that is only useful to the routers. Thus, from the users' point of view, these packets are pure overhead. On a low-speed link, these messages can consume much of the available bandwidth, especially if the network is large or unstable.

Finally, some or all of the machines in a network may be unable to speak any dynamic routing protocol, or they may not speak a common protocol. If that is the case, static routing may be your only option.

With all the disadvantages listed of both static and dynamic routing, you may be wondering what the best choice is. Only you can say for sure what is best for your network, but there is a reasonable middle ground that limits the complexity of dynamic routing without sacrificing its scalability. This middle ground is a hybrid scheme, in which part of the network uses static routing and part uses dynamic routing.

Hybrid Routing Schemes

In a hybrid routing scheme, some parts of the network use static routing, and some parts use dynamic routing. Which parts use static or dynamic routing is not important, and many options are possible. One of the most common hybrid schemes is to use static routing on the fringes of the network (what I have called the access networks) and to use dynamic routing in the core and distribution networks. The advantage of using static routing in the access networks is that these networks are where your user machines are typically located; these machines often have little or no support for dynamic routing. Additionally, access networks often have only one or two router attachments, so the burden of configuring static routing is limited. It may even be possible to define nothing more than a default route on these stub networks. Because of the limited connections to these networks, you usually don't need to reconfigure routing on a stub network when it gets moved to a new place in the network.

On the other hand, distribution and core networks often have many router connections, and therefore many different routes to maintain. Therefore, routers in these components of the network usually can't get by with a default route. Routers (and hosts) in the central parts of the network need complete routing information for the entire network. Furthermore, routers in the core and distribution networks usually need to be informed of changes in the connectivity of access networks. While it is certainly possible to inform each router manually when an change occurs, it is usually easier and more practical to allow a dynamic routing protocol to propagate the changes.

Another advantage of using static routes in your access networks is control. Depending on the structure of your network administration, you might not be able to control what happens in access networks. These may be handled by departmental LAN coordinators that do not report to you. When this is the case, it is often simpler to configure static routing with the access networks, and only run the dynamic routing protocol between routers and machines over which you have direct control. Because a dynamic routing protocol implies a certain level of trust, it is often safer not to use a dynamic routing protocol with such departmentally controlled access networks. In short, when dealing with routers not under your direct control, it is best to use static routing where you can, and to use dynamic routing only where you must.

Another type of hybrid routing structure to consider is based on network bandwidth issues rather than on administrative control. In this type of hybrid structure, you would run dynamic routing protocols on your high-speed LAN and WAN links, and use static routing for connections that cross lower-speed links. As an example, consider a multi-campus network at a university. Within each campus, there may be multiple routers, interconnected by Ethernets, FDDI, and other high-speed links. However, the link between the campuses may well be a 56 kbps WAN link. If the two campuses have separate network address spaces, it is unlikely that the routes between the campuses will change. In this case, the only advantage to using dynamic routing between the campuses is that packets that cannot be delivered to a machine on the other campus because of an internal network failure can be stopped before they traverse the low-speed link. However, this is the exceptional case. The normal case is that internal network operation is stable.

With this in mind, it is reasonable to ask how much bandwidth the dynamic routing protocol is taking on the low-speed link. While most routing protocols are designed to minimize the impact of the routing updates on the link, the overhead is non-zero. It may be better to use dynamic routing within each campus, but to use static routing for the inter-campus link, where bandwidth is at a premium.

Static routing between campuses connected by a slow link may even be worthwhile if the campuses share a common address space (perhaps a single class B-sized network aggregate). However, more work may be necessary. The problem with a common address space is that changes on one campus typically need to be visible to the dynamic routing protocol on the other campus. One solution to this problem is to divide the address space between the two (or more) campuses so that each is its own smaller aggregate, as shown in Figure 5-2. If you can divide the address space, you can simplify static routing between the campuses by working with the aggregates.

Figure 5-2. Two campuses sharing a common address space

 

In the figure, Router1 only needs a static route for the aggregate 172.16.128.0/17. Likewise, Router5 only needs a static route for the aggregate 172.16.0.0/17. This allows each campus to allocate subnets in their portion of the common address space independently, and yet keep static routing between the campuses simple.

A final problem with our multi-campus hybrid routing scheme occurs when the inter-campus link moves between routers. For example, what happens if the link is moved from Router1 to Router3? Router configurations on Campus 2 are unaffected, since the same IP addresses for the serial link can continue to be used, and the changes necessary on Campus 1 need not be extensive. Clearly, Router1 and Router3 must know of the change. After all, even without routing to deal with, they need to have interface configuration changes made. But does Router2 need to be reconfigured to know that the link to Campus 2 has moved? Not if the routers are all configured to include information about their static routes in the dynamic routing protocol.

Most routers have some ability to propagate information from one routing source to another. We usually think in terms of exchanging routing information between two dynamic routing protocols, but passing information about static routes into a dynamic routing protocol is really just a special case. We won't go into the details here of how this is done because it will be easier to explain once we have talked about the dynamic routing protocols and how to configure them, but you should be aware that including static routes in your dynamic routing protocol updates is an easy way to confine configuration of static routes to a minimum of routers.

Now that we have covered static, dynamic, and hybrid routing schemes, you should have a plan for where you would like to use dynamic routing, and where you will use static routing. The next step is to think more about dynamic routing protocols, and decide which are appropriate to use.

Classification of Dynamic Routing Protocols

Dynamic routing protocols can be classified in several different ways. I will discuss two classifications: exterior protocols versus interior protocols, and distance-vector versus link-state protocols. The first classification is based on where a protocol is intended to be used: between your network and another's network, or within your network. The second classification has to do with the kind of information the protocol carries and the way each router makes its decision about how to fill in its routing table.

Exterior vs. Interior Protocols

Dynamic routing protocols are generally classified as an exterior gateway[1] protocol (EGP [2]) or an interior gateway protocol (IGP). An exterior protocol carries routing information between two independent administrative entities, such as two corporations or two universities. Each of these entities maintains an independent network infrastructure and uses an EGP to communicate routing information to the other. Today, the most common exterior protocol is the Border Gateway Protocol (BGP). It is the primary exterior protocol used between networks connected to the Internet, and was designed specifically for such purposes.

In contrast, an interior protocol is used within a single administrative domain, or among closely cooperating groups. In contrast to the exterior protocols, IGPs tend to be simpler and to require less overhead in a router. Their primary drawback is that they can't scale to extremely large networks. The most common interior protocols in IP networks are the Routing Information Protocol (RIP), Open Shortest Path First (OSPF), and the Enhanced Interior Gateway Routing Protocol (EIGRP).[3] The first two are open standards adopted or developed by the Internet community, while the third is a proprietary protocol designed by Cisco Systems for use on their routers.

While it is possible to use an interior protocol as an exterior protocol, and vice versa, it is seldom a good idea. Exterior protocols are designed to scale to the largest of networks, but their inherent complexity and overhead can quickly overwhelm a small or medium-sized network. On the other hand, while interior protocols are fairly simple and have little inherent overhead, they don't scale well to larger networks. Because of the difference in focus between interior and exterior protocols, I will not discuss exterior protocols in this chapter. Instead, I will reserve our discussion of exterior protocols to later chapters where we will be discussing connections to the world outside of your organization.

Distance-Vector vs. Link-State Protocols

Another way to classify dynamic routing protocols is by what the routers tell each other, and how they use the information to form their routing tables. Most protocols fit into one of two categories.

The first of these categories is distance-vector protocols. In a distance-vector protocol, a router periodically sends all of its neighbors two pieces of information about the destinations it knows how to reach. First, the router tells its neighbors how far away it thinks the destination is; second, it tells its neighbors what direction (or vector) to use to get to the destination.[4] This direction indicates the next hop that a listener should use to reach the destination, and typically takes the form "send it to me, I know how to get there." For example, RIP route updates simply list a set of destinations that the announcing router knows how to reach, and how far away it thinks each destination is. The receiver infers that the next hop to use is the announcing router. However, an update can also take the form "send it to this other router who knows how to get there." This second form is usually used only when the router that should be used to reach the destination cannot (or will not) speak the routing protocol being used by the other routers. Not all routing protocols support this form of third-party route update.

The other part of the protocol, the distance, is where distance-vector protocols differ. In each case, the protocol uses some metric to tell the receiving routers how far away the destination is. This metric may be a true attempt at measuring distance (perhaps using a periodic measure of the round trip time to the destination), something that approximates distance (such as hop count), or it may not measure distance at all. Instead, it may attempt to measure the cost of the path to the destination. It may even involve a complex computation that takes into account factors like network load, link bandwidth, link delay, or any other measure of the desirability of a route. Finally, it may include an administrative weight that is set by a network administrator to try to cause one path to be preferred over another.

In any case, the metric allows a router that hears about a destination from multiple routers to select the best path by comparing the "distance" of the various alternatives. How the comparison is made depends heavily upon how metric is computed. For example, the metric in RIP route updates is defined to be a hop count, in which one hop is supposed to represent handling by one router. A destination with a hop count of 16 is considered unreachable. When a router receives RIP updates from different routers referring to the same destination network, it selects the router that is announcing the lowest metric. If this metric is lower than the metric for the route that is currently in its routing table, the router replaces its routing table entry with the new information from the other router.

In order to allow the information to propagate throughout the network, each router includes in its announcements all the destinations to which it is directly attached, as well as all destinations that it has heard about from other routers. When a router includes the information it has learned from other routers, the routing protocol requires it to adjust the metric to reflect the additional distance from itself to the router from which it learned the information. In the case of RIP, this means that before a router announces information that it has learned, it adds one hop to the metric for each of these destinations. In this way, the farther you get from the destination, the higher the metric will be.

In contrast, in a link-state protocol, a router doesn't provide information about destinations it knows how to reach. Instead, it provides information about the topology of the network in its immediate vicinity. This information consists of a list of the network segments, or links, to which it is attached, and the state of those links (functioning or not functioning). This information is then flooded throughout the network. By flooding the information throughout the network, every router can build its own picture of the current state of all of the links in the network. Because every router sees the same information, all of these pictures should be the same. From this picture, each router computes its best path to all destinations, and populates its routing table with this information. How a router determines which path is best is up to each protocol. In the simplest case, a router may simply compute the path with the least number of hops. In a more complex protocol, the link-state information may include additional information to help a router determine the best path. Such information may again include the bandwidth of the link, the current load on the link, administrative weights, or even policy information restricting which packets may traverse the link. For example, a given link might not be allowed to carry confidential information.

Distance-vector and link-state protocols have their own strengths and weaknesses. In a properly functioning and configured network, either type yields a correct determination of the best path between any two points. However, this is not to say that there are not tradeoffs involved in selecting one type of protocol over another.

The drawbacks of distance-vector protocols

In general, distance-vector protocols are simpler to configure and to understand than link-state protocols. They are also typically less processor intensive, freeing more of the router to other tasks, such as forwarding packets. Their major drawbacks, though, are often the result of their simplicity. One of the chief drawbacks is that there is typically no indication of how a router knows about a destination that it has included in an update. For example, consider the simple three-router network shown in Figure 5-3. Router1 tells Router2 about the network 192.168.100.0/24. Router2 will, of course, tell Router3 about it, but it may also tell Router1. Likewise, Router3 may tell Router2 that it knows how to get to the same network, even though its path to that network is through Router2.

Figure 5-3. A simple three-router network

 

Normally, this is not a problem because each router compares the metric it is hearing to the metric in its routing table and selects the best path. But what if Router1 loses its connection to 192.168.100.0/24 due to a hardware failure? It stops telling Router2 about it, and eventually Router2 removes the entry from its routing table (it will either time it out, or it will be told by Router1). However, it may then hear about the network from Router3, and think it should add this "new" path to its routing table and tell Router1. Of course, it also tells Router3, which discovers that the path through Router2 has gotten worse. No matter, it updates the metric in its routing table, and adjusts the metric it announces in its routing updates the next time it sends one to Router2. This now causes Router2 to update its metric, and announce a slightly worse route to Router3, which then re-announces it back to Router2 with an even higher metric. Eventually, they hit whatever value the protocol has declared to be "infinity." When this happens, both routers remove the route from their tables.

Depending on how high the protocol has set the infinity value, and depending on how often the routers send updates to each other, this period of unstable and inaccurate routing can last from fractions of a second to minutes. Clearly, you don't really want your routing tables to be unstable for minutes at a time every time a piece of your network fails! Most distance-vector protocols have added some additional complexity to help avoid these situations. The first thing they typically add is a concept called split-horizon. In split-horizon, when a router is building its routing update for a particular interface, it omits any reference to routes it has learned from routers reached by that interface. In our example, this means that Router2 tells Router3 about 192.168.100.0/24, which it learned from Router1, but it omits any reference to this network when it sends its update to Router1. Likewise, Router3 refrains from telling Router2 about this network, since it was Router2 that told it about it in the first place. A slight modification to split-horizon updates is poison reverse. In poison reverse processing, instead of omitting the route from its routing update, the router includes it, but flags it as unreachable. This causes any receiver that might be depending on the invalid route to remove the destination from its routing table.

The result is that simple network instability like the situation described above does not happen. However, neither split horizon nor poison reverse solves the whole problem. If there is a cycle in the network that connected Router3 to Router1, perhaps through Router4, as shown in Figure 5-4, a routing loop may occur even with poison reverse. In this network, Router1 tells Router2 and Router4 about its connection to 192.168.100.0/24, probably with the same metric value. They in turn tell Router3 about this network, again probably using the same metric. Router3 selects one of these paths (probably whichever it heard first) and enters it in its routing table.

Figure 5-4. Poison reverse is not sufficient to avoid routing loops in a network with a cycle

 

Let's assume that Router3 selects the path through Router2. Because of poison reverse, it would send that route back to Router2 with an unreachable metric, as it is supposed to. However, because it chose not to use Router4's path, it will not perform poison reverse processing on that link, but instead includes the route to 192.168.100.0/24 through Router2 in its updates to Router4, which ignores the update and prefers the route through Router1.

All goes well until the link between Router1 and 192.168.100.0/24 fails. At that time, Router1 ceases advertising this route to Router2 and Router4. These routers, in turn, cease sending the route to Router3, but it is possible that Router4 will hear Router3's advertisement before the process is complete. Since it does not have this route, it installs it in its routing table, and informs Router1 of this apparently new information. Router1 then informs Router2, which continues sending the information to Router3.

The loop will eventually be broken, as each router will increase the metric as it passes routing information around the loop; eventually, the metric will reach the protocol's infinity value. How long it takes the routers to count to infinity, as this behavior is called, depends heavily on how often they update each other, what the protocol's infinity value is, and how many routers are involved in the loop. The solution to this new problem is to introduce a hold-down interval. When a router learns that a destination is no longer reachable along the path it was previously using, it starts a timer during which it ignores any other routing information it might hear about this destination. The idea is to allow other routers to learn about the failure before it starts depending on their routes. In our example, when Router1 determines that it can no longer reach 192.168.100.0/24, it begins a hold-down period for this destination. During that time it ignores the updates it hears from Router3. If the hold-down period is long enough, by the time Router1 starts listening again, Router3 will have learned that its path to the destination is invalid, and won't be advertising it.

The drawback to the hold-down interval is that it is hard to know how long the interval should be. After all, how long does it take for all of the routers that you might hear from to learn that a destination is not reachable? This is especially bad for a protocol like RIP. In its simplest form, RIP sends a routing update every 30 seconds. Because there is no acknowledgment of these updates, it is possible that one could get lost. Additionally, while an update includes information about what is reachable, it does not normally include information about what is no longer reachable, so there is no indication to a router that it should remove a route that is no longer valid.

To allow for lost updates, RIP sets a timer for each route that it learns. Every time it hears an update for a route, it resets the timer. If it doesn't hear an update for 180 seconds, it removes the route from the routing table and stops advertising it to its neighbors. In this way, if an update gets lost, the routes it would have contained do not immediately get removed from the routing table. Presumably, they will be in the next update, and their timers will be refreshed then.

In practice, this means that it can take a long time for a routing change to make it through a large network. Consider once again the network with three routers shown in Figure 5-3. When Router1 determines that it has lost its connection to 192.168.100.0/24, it simply ceases to advertise it in its updates to Router2. Router2, however, continues to believe that it has a route to this network for three minutes from the last time it heard about it from Router1, and continues to send updates containing this destination to Router3. After three minutes, Router2 determines that Router1 must have lost its route, so it removes the route for 192.168.100.0/24 from its routing table, and ceases informing Router3 about this destination. However, Router3 will continue to use the old information for up to three minutes more itself.

Now consider what happens if we keep adding to the network until we have dozens of routers. If each router has to wait three minutes from the time the router closer to a failed network stops advertising a route, it is conceivable that a route might not be completely gone from the network for as much as 45 minutes! It is clearly unreasonable that the hold-down interval for a network should be even a significant fraction of this time. To help reduce the time that a network has inconsistent routing information, distance-vector protocols often allow routers to include negative reachability information for routes that they have recently advertised, but can no longer reach. Negative reachability information allows routers to find out immediately that some route is no longer valid. For RIP, negative reachability information takes the form of a route with a metric of 16. Other protocols tag such information in whatever manner is appropriate.

Negative advertisement helps speed the propagation of route failure through the network, but it doesn't eliminate the delays. When Router1 discovers that its connection to 192.168.100.0/24 has been lost (or restored), its next update to Router2 will contain this information. In the case of RIP, if it just sent an update, it could be up to 30 seconds until this update occurs. Further, once Router2 hears from Router1, it may also have to wait up to 30 seconds before it can notify Router3, which will wait up to 30 seconds, and so on. Even though this information traverses a large network quickly, especially compared to the time it takes for a route to time out, it can still take a few minutes for all of the routers in the network to hear about the change and update their routing tables. This delay between the time a network change occurs and the time all of the routers have adjusted to it in a consistent manner is known as convergence time. A long convergence time is clearly a problem for any routing protocol.

To minimize convergence time, a distance-vector protocol may allow flash or triggered updates. A triggered update is sent whenever a router's routing tables change in a way that would affect its routing updates. If each router uses triggered updates, and includes negative reachability information, it is possible for information about the failure of Router1's connection to 192.168.100.0/24 to speed through the network to all routers in a matter of a few seconds, thereby shortening the convergence time and thus the time that routers need to be in a hold-down interval.

But, like everything else, it isn't that simple. If triggered updates aren't carefully controlled, an intermittent failure can ripple back and forth through the network, consuming the routers' time with processing routing updates rather than forwarding packets. A common solution is to lengthen the hold-down timer slightly, and to introduce a short interval timer that is set after every flash update. During this interval, the router suppresses new flash updates to help dampen the effects of the original failure.

The other major drawback to distance-vector protocols also stems from their simplicity. Because the network topology can change, either because of link failure or the addition or removal of network segments, all dynamic routing protocols must update routers about the changes. In a distance-vector protocol, updates are usually performed by periodically broadcasting (or multicasting) routing packets on some or all of a router's interfaces. Often, these routing updates contain complete routing information, as the sending router sees it. Periodic updates are useful for keeping the routers on a network segment informed, but they introduce additional network overhead during periods of network stability (the majority of the time, we hope). Some newer distance-vector protocols such as Cisco's EIGRP only announce changes to the routing tables, but these protocols still tend to be the exception, rather than the rule.

So, while a distance-vector protocol tends to be conceptually simple for humans to understand, and easy for a router's processor to work with, this simplicity can result in unusual behavior in response to a network failure, and often results in long convergence times between the failure of a network component and the re-establishment of consistent, stable routing in all routers. It may also result in the consumption of network bandwidth and router processing power even during periods of relative stability. While changes to the protocol can help lessen these problems, once you've added poison reverse, hold-down intervals, triggered updates, and so forth, the protocol is no longer simple, either to understand or to process.

The drawbacks of link-state protocols

Link-state protocols have some important advantages. Because a link-state protocol computes its routes based on the topology of the network as indicated by the link-state updates, it can't form a loop in response to a partial network failure, like a distance-vector protocol might. Further, because a change in link-state gets flooded throughout the network immediately and causes all routers to update their topology map and routing tables, convergence time is minimal. Finally, because most link-state protocols are designed to send link-state updates only when the state of a link changes, they tend to conserve network bandwidth and router processing power during periods of network stability.

While a link-state protocol avoids loop-forming behaviors, long convergence times, and stable-state resource consumption, they have their own drawbacks. Chief among these is complexity. Complexity is primarily an aspect of the protocol's implementation, but it often shows up in configuration as well. In fact, OSPF, an interior protocol, is a more complex protocol than even BGP, an exterior protocol. Fortunately, in a typical configuration, most of this complexity is hidden from the user.

Why are link-state protocols so complex? Consider what we have said about how the routers determine their routes. They collect all of the link-state updates from other routers and build a topology map of the network. Using this map, they compute the best path to each destination. The first complexity is generating the topology map. While a human being can easily draw pictures based on instructions about what is connected to what, a computer must have a way to represent the resulting picture in a way that allows it to carry out its processing. The standard way to do this is to use one of numerous types of graphs. Each type of graph has its own set of operations that it supports well, and another set that are nearly impossible to perform on it. A lot of research has been devoted to describing different types of graphs and the operations they support. Often, a protocol specification does not detail how the protocol should be implemented. It may not even specify what types of data are needed. However, even if the types of data are identified in the protocol specification, how the data are represented (i.e., which type of graph and how the graph is represented) is often left to the implementer. A poor selection can result in subtle failures in the resulting code on the router.

The second complexity in implementing a link-state protocol has to do with computing the best path to all destinations. While there are algorithms for computing the best path using a variety of graphs and metrics, it is again up to the implementer to select one and implement it correctly. Mistakes can also have interesting results in the finished product.

But implementation complexity shouldn't be a concern to the network administrator if the resulting code works correctly. However, even if the code is correct, a complex implementation usually requires more processing power and memory in the router. For example, the topology graph will take time to generate, and must be stored. In fact, it must be stored indefinitely, since link-state updates only contain information about changes in the network topology. The additional memory and processing requirements cause some network administrators to stay away from link-state protocols, but this is not their only concern. A greater concern is the complexity, or the perceived complexity, of configuring a link-state protocol.

Most link-state protocols are more complex to configure than most distance-vector protocols. However, if the configuration interface is implemented well, and if it includes a set of reasonable defaults, it is possible to configure a "no frills" link-state protocol with little more effort than a distance-vector protocol. The complexity of configuring a link-state protocol should only appear if you want to depart from the defaults.

Both link-state and distance-vector protocols will result in correct routing in a stable network, and should eventually converge on a new set of routes after a network failure. Therefore, which type of protocol you select for your network is a matter of personal preference. If the complexity of link-state protocols is not to your liking, or if you are concerned about the consumption of resources on your routers, try to select protocols that use a distance-vector algorithm. On the other hand, if you want the fast convergence and low bandwidth consumption of a link-state protocol, or don't want to deal with the odd loop-forming behavior of a distance-vector protocol, then select a protocol from the link-state family.

Selecting a Routing Protocol

Now that most of the background information about dynamic routing protocols is behind us, it is time to talk about what criteria you should consider when selecting a dynamic routing protocol. You may have a preference for either a link-state or a distance-vector protocol. But deciding what kind of protocol to use without considering other options can severely limit your choices, de-pending on what your router vendor supports. A more useful approach is to consider which protocol or protocols best suit your needs, and then use a preference for one type over another as a weighting factor later in the decision.

One of the most important criteria is how quickly the protocol adapts to changes in the network. Earlier, we identified this as convergence time and said that it was the amount of time between a change in the network and the reestablishment of consistent and correct routing tables. Ideally, you want this time to be small enough to be unnoticed by users.

Traditionally, the next most important criterion is resource consumption. However, with the current push for more efficient use of the IP address space, it is likely that you plan to use variable-length subnet masks. If this is the case, then support for variable-length masks is probably the most important feature your routing protocol must have. After all, if your routing protocol does not support your use of variable- length subnet masks, they won't do you much good.

The third criterion you should consider is how much of your network resources the routing protocol consumes. Consider not only the network bandwidth consumed by the protocol messages, but also how much processing power and memory is required in your routers. A link-state protocol will typically do better on the bandwidth consumption, and a distance-vector protocol will do better with processor and memory consumption, but this is not always the case.

Next, consider how well your prospective protocols deal with multiple paths to a destination. This may or may not be critical in your network, and how much weight you give it depends on your network design. If you have no redundant paths, you probably won't care about how well your protocol supports them. Still, while you may not have redundant paths today, you may add them in the future and you might need to change protocols to support them. Even if one of your prospective protocols does not normally support multiple paths, consider whether your router vendor's implementation does anyway. For example, RIP does not normally support multiple paths to a destination network, but the RIP implementation in a Cisco router does handle such redundancy, and will even do load sharing across multiple paths with equal costs (metrics).

You might also need to consider how well your network protocols will scale to the size you expect your network to achieve. Link-state protocols usually scale better, but some distance-vector protocols, such as Cisco's EIGRP, have proven themselves in networks with 1,000 or more routers.

Finally, you may have to consider whether a protocol is an open standard or a proprietary protocol. This may be because of policy constraints of your organization, or it may be because you must support multiple vendors' routers in your network. A protocol that is only spoken by half of your routers isn't terribly useful to the other half. Table 5-1 summarizes these criteria for the most common interior routing protocols you are likely to be considering.

Table 5-1: Summary of Common Routing Protocol Features

Protocol

RIP

OSPF

IGRP

EIGRP

Type

distance-vector

link-state

distance-vector

distance-vector

Convergence Time

slow

fast

slow

fast

VLSM

no

yes

no

yes

Bandwidth Consumption

high

low

high

low

Resource Consumption

low

high

low

low

Multi-path Support

no a

yes

yes

yes

Scales Well

no

yes

yes

yes

Proprietary

no

no

yes

yes

Routers Non-IP Protocols

no

no

no

yes

a Some vendors may support multiple paths in RIP.

From the table, it may seem that EIGRP is the ideal choice. It is fast, consumes little resources, supports VLSM, and scales well. But it is also proprietary, and unless you have a single vendor for all your routers, and that vendor happens to be Cisco Systems, you will immediately be faced with multiple routing protocols in your network. The complexity involved in running multiple routing protocols should not be taken lightly, so give careful thought to any proprietary routing protocol or solution before you make your decision.

Once you have selected a protocol, or have at least narrowed your choices down to one of two, it is time to start thinking about how you would configure your protocol to achieve your network goals and solve any problems that you may have in your network. The next chapter presents several common scenarios that are likely to arise, and shows how to use each of the protocols in Table 5-1 to solve that problem. While looking at these examples, you may discover that your chosen protocol may make it difficult for you to solve some specific problem in your network; or, if you have not chosen a specific protocol, seeing how each of your prospects works for or against your specific network situation may provide you with the remaining information you need to select between them.


1. The Internet Protocols originally called routers gateways. This usage is no longer common, but it still appears in routing protocol discussions.

2. Not to be confused with the Exterior Gateway Protocol version 2 (also known as EGP), which is one of many exterior gateway protocols.

3. EIGRP has largely supplanted IGRP, its predecessor, because EIGRP has all the advantages of flexibility and simple configuration while improving on speed and resource consumption. It is also capable of being a unified routing protocol both for IP and some non-IP protocols, eliminating the need to run multiple routing protocols in a multi-protocol network. I will point out any significant differences between the two.

4. The mathematical definition of a vector is direction and length. Unfortunately, when network engineers refer to a distance-vector protocol, they refer to the direction only. To avoid confusion, we will try to limit the use of the term.

Back to: Managing IP Networks with Cisco Routers


oreilly.com Home | O'Reilly Bookstores | How to Order | O'Reilly Contacts
International | About O'Reilly | Affiliated Companies | Privacy Policy

© 2001, O'Reilly & Associates, Inc.