Chapter 6: Meeting the Routing Protocols

In This Chapter

Seeing how your router chooses between installed protocols

Weighing benefits and drawbacks of distance-vector routing protocols

Checking out the pros and cons of link-state routing protocols

When your network grows to the point where static routes are unmanageable, it is time to consider what routing protocol to use on your network. Unlike static routing table management, dynamic routing table management adjusts automatically for topology and traffic changes. In this process, the routers exchange information between devices, which allows the routers to build complex routing tables that span your network. These protocols include Interior Gateway Protocols (IGP), used inside your network, and Exterior Gateway Protocols (EGP), used to join your network to exterior or other networks.

Do not confuse routing protocols with routed protocols. The routed or routable protocols’ list includes protocols, such as IPX/SPX and TCP/IP, and are able to move data between network segments by having the data pass through a router. In this chapter, I discuss routing protocols, which are protocols such as RIP, OSPF, EIGRP, and BGP, which I first mention in Book IV, Chapter 1. A routing protocol exchanges routing tables on routers, allowing global routing tables to be dynamically built, rather than your having to plan all your routing tables entries on all routers manually.

This chapter gives you a good idea about how these two classes of routing protocols function: IGP and EGP. The chapter also covers their strengths and weaknesses, as well as how your router decides which routing protocol to use when multiple protocols are installed on your router.

Checking Out Criteria for Routing Protocol Selection

People use two basic methods to classify protocols — by where they are used and by how they calculate routing. In this section, you see how to choose protocols based on where you plan to use them, the way the protocol manages data, and how your router chooses which protocol to use when more than one protocol is installed.

Classifying by where protocols are used

When classifying protocols by where they are used, you are talking about interior (IGP) versus exterior (EGP). In most cases, people are most concerned with the protocols that are running on the inside of their networks and maintaining their routing data because this is where most of their traffic is concentrated. In making your decisions about which protocol class you want to apply first to your network, it is likely the interior protocol because the exterior protocols typically pass information that was generated by the interior protocols. The two main breakdowns for protocols are

• Interior protocols include RIP, EIGRP, OSPF, and ISIS.

• Exterior protocols include BGP.

Classifying by how protocols calculate routing

In addition to classifying protocols by where they are used, you can also choose to classify protocols by how they calculate routing. When classifying them this way, you are talking about distance-vector protocols versus link-state protocols:

• Distance-vector protocols include RIP, BGP, and EIGRP.

• Link-state protocols include OSPF and IS-IS.

Distance-vector protocols

RIP, BGP, and EIGRP are in the distance-vector category. Distance-vector protocols base their routing choices on two things: the direction or vector they need to send the data, and the distance of the target network, which is calculated as hops or routers that the data needs to pass through.

Link-state protocols

Link-state protocols include OSPF and ISIS. Link-state protocols gather information about network connections known by all the routers in their group and build topology maps identifying how they see all the connections across the entire network or area in which they function. They then use this information to build their own routing table. In link-state routing, routing tables are not passed between routers; only the connection information is transferred between routers.

Other types of protocols

The exception to this grouping is EIGRP, which Cisco developed and calls an Advanced Distance Vector or hybrid protocol. EIGRP shares its routing table with its neighbors like a distance-vector protocol does. However, it sends the entire table only at startup; then it only sends updates like a link-state protocol does, so it has a bit of both sets of features. It is not uncommon to find that EIGRP has been added to either classification list, though in most cases you see it on the distance-vector protocol list when people have not separated EIGRP by itself.

Administrative distance

You can enable several routing protocols on your router at the same time, so you could be using EIGRP, OSPF, and RIP on your network simultaneously. If this is the case, your router will learn about routes to the same network through each of the available protocols, so it must choose the route to take to any given network. Because routers are not good at making these judgment calls, administrative distances are used. The administrative distance for a routing protocol is a numeric representation of how accurate the routing protocol is expected to be, where the lowest number is given to the most accurate protocol. This administrative distance is sometimes referred to as how believable a routing protocol or routing table entry is.

Each routing protocol is assigned a default administrative distance (see Table 6-1). Although these are default distances, you can change them on a per-router, per-protocol, or per-route basis using IOS commands. Typically, you do not need to change these default distances because they have been ordered so that the most believable routes are given the shortest distance. Given a route to a network, such as 192.0.2.0/24, if two routes in my routing table are networking, one is directly connected and one is retrieved by RIP. The route that says the router is directly connected to the network is likely to be the most believable or accurate route.

The routes that are expected to be the most reliable routes are given preference over other options for a network. The networks that your router is directly connected to are the most reliable choices, and static routes that you have put in are only slightly less reliable. If you have put in a static route, the router determines that you must want to use it. If you have a choice, the shortest distance is always preferable.

Introducing the Protocols

Table 6-2, which can be used as part of your evaluation criteria, has the most common protocols and a number of points of evaluation.

• Convergence Time: Convergence time is the point at which all routers on your network know about all current routes for the network. When a router is added or removed from a network, a certain amount of time — convergence time — must pass before this change is propagated to all routers on the network.

• Variable length subnet masks (VLSM): This term refers to whether all routers on the network are required to use the same subnet mask. This requirement reduces your flexibility in assigning IP address network IDs to the network segments on your network.

• Bandwidth Consumption: This term refers to the amount of necessary network bandwidth to maintain and distribute routing table information on the network. To share and distribute routing table information, all routing protocols need to send an amount of data over the network, and some send more than others.

• Resource Consumption: In calculating and maintain routing table information on a router, a certain amount of processing power and memory is used.

• Multi-path Support: When routes are discovered on the network that have loops in their paths, some segments have two possible routes, which represent multiple paths. Some routing protocols have support for multiple paths, by storing alternative paths in their routing information.

• Scales Well: Some routing protocols operate well on small networks, but as the number of routers increases on the network, the routing protocol does not function as well. Routing protocols that can be used on small to very large networks scale well in size.

• Proprietary: The routing protocol based on open standards or a proprietary protocol owned by one company can affect the level of support and the speed of changes.

Distance-Vector Routing

Distance-vector routing functions by passing routing tables between devices on the network. So the first router looks at its connected interfaces, builds a routing table, and passes that information to other routers on its connected interfaces. If the router receives routing tables from other routers, it updates any metrics used for choosing routes, such as RIP’s hop count, and adds that information to its routing table. This information is then sent out with the routing table updates that are sent to neighboring routers.

Now, this process sounds really simple — the routers will just pass that information out and then everyone will know how to get to all other locations on the network — but there are some issues that affect most vector routing protocols. This section examines each of these problems.

Examining basic function of distance-vector routing

I said that these updates pass routing tables from router to router to get the information out to all routers, but what does this really look like? If you examine Figure 6-1, you see three routers with their interfaces configured according to the diagram, as well as the routing table on each router. In this instance, no routing protocol is running.

If you now enable a dynamic routing protocol and give it some time to propagate changes to all areas of the network or converge, the routing information will look more like Figure 6-2. Note that the routers on each end of the network now know about the network segments at the other end of the network and have associated a hop count with the path to those networks.

Setting up a routing protocol does not take much work; you need to give the routers only enough information to allow them to dynamically update their routing information between devices. Sharing of connection information or routing tables allows all routers in the routing group to know how to get to all the other network segments supported by the routing group.

Count to infinity and routing loops

In Figure 6-3, everything is working fine on the network, and the network is converged. Problems can happen with your routing protocol when a link or a router fails. In this figure, a failure happens on Router3 with interface fa0/0. When this link goes down, the route to 10.4.0.0/16 is no longer available; however, if you look at what follows, you can see the issue.

1. Router3 initially marks the route to 10.4.0.0 as a link down in its routing table.

2. Router2 sends out its routing table to each of its neighbors, which includes Router3, telling them that it has a path to 10.4.0.0 with a hop count of 1.

3. Router3 then updates its routing table with this new information, stating that the route to 10.4.0.0/16 is now 2 hops away, as shown in Figure 6-3.

4. Armed with the new information that 10.4.0.0/16 is available through another interface, Router3 sends out its routing table to its neighbors.

5. Router2 gets the update and identifies that the router that previously said it knew about 10.4.0.0/16 has updated the route from a hop count of 0 to 2, so Router2 updates its own routing table. The old route may have been identified as an updated route, or it may have timed out of the routing table, depending on the routing protocol that is in use.

6. Router2 then passes its own routing information out through its other interface (S0/0) to propagate the change to Router1, as illustrated in Figure 6-4.

7. Router3 eventually receives the update from Router2 telling it that the hop count to 10.4.0.0/16 has been updated to 3, and this process now continues.

This process continues to infinity because no mechanism is in place, in this case, to stop the process from continuing.

However, the RIP routing protocol has a built-in safety mechanism, to a degree. RIP has a maximum hop count of 16, and when the route to a network exceeds the 16-hop rule, the RIP protocol marks that network as unreachable so that it does not further propagate the route. This scenario does not change the information found in the router’s routing table — it only limits how far the error is propagated.

When you send data to a host or device on the 10.4.0.0/16 network, it comes through the fa0/0 interface on Router1 and Router1 thinks that it can get to 10.4.0.0/16 within 4 hops by sending the data out through interface S0/0 based on Router1’s routing table. Figure 6-5 shows what happens when the data is sent. As it arrives at Router3, Router3 determines that the route to 10.4.0.0/16 is back through Router2, which then causes the data to loop infinitely. There is a Time to Live (TTL) on IP packets (refer to Book II, Chapter 1 for more on TTL), which defines the maximum amount of time which an IP packet can remain on a network. After spending some time looping, the data will be dropped from the network and a message sent back to the sender of the data.

Preventing count to infinity issues

The following sections explore ways to prevent count to infinity and the resulting routing loops from happening on your network.

Split horizon

If you are using RIPv1, you have a solution in the form of a concept called split horizon. In this concept, if you receive routing on one interface, sending that information back out of that interface is not likely to be productive.

So, if you examine only the routing information for the network 10.4.0.0/16 in the routing process, the flow of the route information is passed as follows:

1. Router2 learns of the route to 10.4.0.0/16 through interface S0/1 facing Router3.

2. Router2 sends its routing table updates out through both of its interfaces, but filters the route to 10.4.0.0/16 out of the list when it sends the routes out through interface S0/1, as shown in Figure 6-6.

3. Router1 receives the route to 10.4.0.0/16 from Router2 on interface S0/0.

4. Router1 sends its routing table updates out through both of its interfaces, but filters the route to 10.4.0.0/16 out of the list when it sends the routes out through S0/0, also as shown in Figure 6-6.

Route poisoning

Rather than using split horizon, RIPv2 implements a process called route poisoning. Following is the sequence for the route poisoning process:

1. Router3 identifies that the link to 10.4.0.0/16 is down and immediately updates its metric for that network to infinity — or in the case of RIPv2, a hop count of 16 — and sends that routing table update out immediately, as illustrated in Figure 6-7.

2. Router2 gets the update and then updates its own routing table by removing the route to 10.4.0.0/16, because it is no longer valid. After this update is complete, Router2 sends its own update out through interface S0/0.

3. Router1 gets the update, which no longer includes a route to 10.4.0.0/16, causing Router1 to remove the route to that network.

With router poisoning, the update process escalates so that improper route information is removed from the network in a timely manner. You can extend this system using a process called poison reverse. In this case, after Router2 sees the hop count or metric go to infinity, it also sends a routing table update back to Router3 with an infinite metric telling it that the route to 10.4.0.0/16 is no longer available. This process reduces the chance that an improper update will make it through to Router3 and cause a loop.

Hold-down timers

Hold-down timers are another solution to routing loops that some routing protocols implement. Hold-down timers prevent protocol update messages from improperly updating routes for links that are currently down. Following is the hold-down timers implementation sequence:

1. Router2 receives an update telling it that the link to 10.4.0.0/16 is down.

2. Router2 marks the route as possibly down and sets a hold-down timer.

3. Router2 waits for an update.

• If it gets an update with a metric better than the original one, Router2 records the route as up and accessible.

• If it does not get an update in the timer interval, Router2 removes the route from its routing table.

• Routes that Router2 receives with a metric worse than the original route are automatically removed.

During the hold-down period, if any data is being sent to the 10.4.0.0/16 network, the data is sent on as a delivery attempt. The delivery attempt is made in the event that the link to 10.4.0.0/16 is having an intermittent problem.

Triggered updates

Triggered updates deal with count to infinity issues by forcing an update as soon as the link changes.

So, going back to the network layout you have been using, when the link to network 10.4.0.0/16 goes down, Router3 sends an immediate update notifying its neighbors that the link is down. Router2 receives the update and immediately passes the update to its neighbors, such as Router1.

As part of its normal update schedule, Router2 might still receive another update from Router1 prior to getting the update to remove the route. The solution is to combine triggered updates with hold-down timers, which prevents routes with worse metrics from being added to a router’s routing table.

Link-State Routing

Compared to distance-vector routing, link-state routing optimizes routing structures by performing calculations on the best routes instead of just passing full routing table information between routers. Link-state routing only sends interface information about the different interfaces existing on a router and the networks to which the router is connected. So, rather than send a 20-to-50–entry routing table, link-state updates send only the information about the router’s four to six interfaces.

Understanding link-state protocol

Each router puts all the link-state information it receives in a topological database, which is a table that contains link information about all known routers. It does not define routes; instead, it records all the information required to get to every network segment connected to every router after the routing information is calculated.

There will probably be more than one route to each network, so it is important to evaluate each and every possible route to find the best route to each network segment. You can do so using the Shortest Path First (SPF) algorithm, which then builds the SFP tree. Since the router knows about all of the links on the network, it is able to evaluate all links from itself to determine the most efficient way to reach every other network segment on the network. This is referred to as the shortest path to each of those network segments. All of the shortest paths are stored in one location, which is referred to as the SFP tree.

After the SFP tree is built, the router reviews it to find the best possible route to each network. After the best routes are found, the router adds them to its own routing table. This routing table is built on each router, but it should be the same for all routers that receive the same updates, because they all use the same process to build the routing table.

When a router starts up and sends its initial link-state information to its neighbors, it reduces network overhead by only sending updates to its link information. These Link State Advertisements (LSA) are flooded out to all routers in their area or zone. LSAs are simply updates on their link status, so one is sent whenever a link is connected or disconnected.

Working with your strengths

This system of handling updates seems to be the key to the strength of link-state protocols. Although some variance occurs between the two protocols, in general, link-state protocols are different than distance-vector protocols in the following ways — you can decide if these differences represent benefits or drawbacks:

• Cost metrics are the main determining factor of route selection. These cost metrics are the point of evaluation to determine the best links, which may include the speed and capacity of the links.

• Less frequent routing updates.

• High degree of scalability to support much larger networks.

• Division of overall network into smaller segments to limit scope of routing changes.

• Only sends updates on link status and topology changes.

• Triggered updates can immediately notify systems of changes, reducing convergence times.

• Network design can reduce the size of the link-state database. When the network ID are laid out to support route summarization, then the reduce number of routes will reduce the size of the link-state database.

• Limited age of data, because LSA aging always keeps information current.

• Routing loops are almost eliminated because routers know what the entire network topology looks like.

• Large amounts of memory are required to support not only the routing table, but also the link-state database and adjacency database (which is table listing neighboring devices).

• Execution of the Dijkstra algorithm (the mathematical formula used to perform the shortest path calculation) requires the use of CPU cycles on the router, and for larger networks, this requirement means more CPU time spent on calculations.

• In large network implementations, link-state protocols can require a great deal of tuning to function properly. This necessity can present significant challenges to a network administrator.

If you have sufficient CPU and memory resources on your network routers and your network layout is not overly complicated, you should not suffer from the issues related to link-state protocols — but only reap the benefits. There is no reason that link-state protocols should not be used as primary routing protocol on your network.