Distance Vector Routing Protocols IP routing protocols use two main technologies: link-state and distance vector technologies. This chapter deals with distance vector protocols. You will learn about link-state protocols in Chapter 5, "IP Link-State Routing Principles." Distance vector protocols are the first routing protocols that were designed and include RIPv1 and IGRP. These protocols are classful protocols designed for small networks. As the networks started to expand, enhancements were made to the distance vector protocols, with the creation of RIPv2 and EIGRP. Although these still use the distance vector routing algorithms, they were developed later and are examples of classless routing protocols. NOTE Although IGRP and EIGRP are defined by Cisco as distance vector routing protocols, they are proprietary protocols and therefore do not conform to all the characteristics of a distance vector protocol. For example, EIGRP is defined by Cisco as an advanced distance vector routing protocol, though it has adopted some of the link-state characteristics instead of the distance vector solution. It is sometimes referred to as a hybrid routing protocol. For the purposes of the exam, both IGRP and EIGRP are distance vector routing protocols.
Operation of Distance Vector Routing Protocols Distance vector protocols send periodic updates about the networks that the routing process has discovered and entered into its routing table. The update is sent to directly connected neighbors. The destination address of the distance vector periodic update is 255.255.255.255 (the broadcast address), meaning that all systems on the segment hear the update. The update is sent out periodically after a timer has expired . The timer is reset immediately after the router has sent an update. Thus, the routing protocol sends out the entire routing table to its neighbors, sets a clock, and after a predetermined amount of time (30 seconds in the case of RIPv1), sends out the entire routing table again. After receiving a neighbor's routing table, the router updates its own table and sends the modified table in subsequent updates. Because the router passes on information that it has heard from its neighbors, as opposed to an update propagated from one router to all other routers in the network, distance vector routing protocols are said to be "routing by rumor." Distance vector routing protocols are classful routing protocols, meaning that they naturally summarize at the IANA or major network boundary. They do this by following the first octet rule. The purpose of the distance vector protocol is to provide accurate, loop-free information to the routers. The update includes the entire routing table, excluding those networks that were learned from the interface through which the update is being sent. Thus, if a router knows of networks 1, 2, 3, 4, and 5, and it heard of networks 2 and 3 from an update received through E0, the routing update sent out of E0 would contain information about networks 1, 4, and 5. The rule of not repeating what you have heard back to the source is more than simply refined etiquette. It is the implementation of the split horizon rule . The purpose of this rule is to reduce network overhead and also prevent information from traveling in circles through the network, which can create routing loops . To prevent routing loops, distance vector routing protocols employ the following techniques, which are described in more depth in the section "RIPv1": Count to infinity is a condition that occurs when a route vanishes from the network. It is found in distance vector routing protocols, although strictly speaking, it is not a technique. The Distance Vector Routing Metrics The metric used by distance vector protocols is often stated as being distance measured in the number of hand-off points or hops (routers) encountered on the way to the end device. Cisco defines IGRP and EIGRP as distance vector routing protocols. This muddies the original definition, because IGRP and EIGRP, although they are distance vector routing protocols, do not use hop count to determine the metric for a route; instead, they use several variables to compute the best path to a destination network. This is referred to as a composite and complex metric. In distance vector routing protocols, the path selection is made using the Bellman Ford algorithm based on the metric or value of each available path, that of hop count. RFC 1058 discusses this in depth in reference to RIPv1. EIGRP, however, uses a proprietary algorithm called Diffusing Update Algorithm ( DUAL ) . NOTE If you are asked a question on distance vector metrics, it might be wise to use the RFC 1058 definition of hop count because IGRP and EIGRP are proprietary protocols. Cisco also uses the original definition in its documentation.
RIP Version 1 and RIP Version 2 The next sections briefly describe the distance vector routing protocols RIPv1 and RIPv2. RIPv1 Routing Information Protocol version 1 (RIPv1) is a simple routing protocol and, as such, works well in small networks that are unlikely to grow or change significantly. As a distance vector routing protocol, it sends updates every 30 seconds. These updates comprise the entire routing table. Because RIPv1 was the first distance vector routing protocol and became an open standard, administrators who subsequently wrote a routing protocol were obliged to conform to the existing structure if they wished to define their routing protocol as a distance vector routing protocol. Therefore, the following characteristics describe not only RIPv1, but in essence, any distance vector routing protocol. -
Count to infinity A router (A) hears about networks from its neighbors (B and C) and updates the routing table with the new networks. The routing table is then sent to all neighbors (B and C). However, if a neighbor (B) is sent information about networks for which it was the originating source, confusion can occur, which is referred to as a routing loop . The problem occurs when the path to a network goes down; each router might believe that there is an alternative path through its neighbor. The ramifications of this problem are limited because each router increments the hop count before it sends out the update. When the hop count reaches 16, the network is rejected as unreachable, because the diameter of a RIPv1 network cannot be greater than 15. This is called counting to infinity , where "infinity" equals 16. Although the liability is controlled, it will still slow convergence of the network. -
Split horizon This is a mechanism to prevent loops. If split horizon works, the need for "count to infinity" is eliminated. The split horizon rule states that the routing process will not advertise networks out of the interface through which those networks were heard. This prevents information about networks being repeated to the source of those networks. -
Split horizon with poison reverse Split horizon on its own might not prevent loops, though it prevents networks being advertised out of the interface from which they were learned. However, poison reverse overrides split horizon when a network is lost. Poison reverse includes all the networks that have been learned from the neighbor, but it sets the metric to infinity (16). By changing the metric value to 16, the networks are reported to be unreachable. The routing process acknowledges the network but denies a valid path. Although this increases network overhead by increasing the update size , split horizon with poison reverse can prevent loops. -
Holddown After deciding that a network in the routing table is no longer valid, the routing process waits for three routing updates (by default) before it believes a routing update with a less-favorable metric. Again, this is to prevent routing loops from generating false information throughout the network. -
Triggered updates As soon as a routing process changes a metric for a network in its routing table, it sends an update with the metric set to a value that states it is unusable. In RIP, this value is infinity, that is, 16. Triggered updates inform the other routers immediately. If there is a problem in the network, all the affected routers go into holddown immediately instead of waiting for the periodic timer. This mechanism increases convergence and helps prevent loops. -
Load balancing If the routing process sees multiple paths of equal cost to a remote network, it distributes the routed (datagram) traffic evenly among the paths. It will allocate datagrams to the different paths on a round-robin basis. The type of switching that is usedprocess switching or fast switchingwill determine whether the load balancing is done on a round-robin or session basis. Round- robin load balancing is used when there is process switching in effect. NOTE Because the metric used is hop count, one path can become saturated . A 56-kbps line and a 100-Mbps Fast Ethernet line might both offer paths of equal hop count; the user traffic would be divided equally between the links, but their bandwidths are disproportionate, allowing the slower link to become overwhelmed.
Cisco has implemented all the preceding options, which are defined in RFC 1058. RIPv1 is useful in small networks and is distributed with Berkeley Standard Distribution (BSD), which makes it widely available. It might not be suitable for large environments, however, because the protocol was not designed with the expectation of being used in huge organizations. One of the keys to RIP is an understanding that 16 is the magic number. As the network grows, you will see problems with applications timing out and congestion occurring on the network as the routers fail to adapt quickly to changes. When there has been a change in the network, the time that it takes for every router to register that change is known as the convergence time. The longer the convergence time, the greater the likelihood of problems on the network. Therefore, you need either to contain the growth of the network or to use a routing protocol that scales to a larger size. Open Shortest Path First (OSPF) is a link-state routing protocol that is designed to scale. It has the added advantage of being defined by the Internet Engineering Task Force (IETF), making it an industry standard in the public domain. RIPv2 RIPv2 is an enhanced version of RIPv1. The main enhancements are that RIPv2 sends the subnet mask with the updates and that the updates are multicast, using 224.0.0.9. The following list explains in more detail the main characteristics of RIP v2. -
Using a multicast address saves network resources, because all the nodes in the network can discard the packet at either Layer 2 or 3 instead of taking the packet all the way up to the transport layer, where the port number is rejected. Although this saves system resources, the same amount of bandwidth is consumed on each link that the multicast traverses. -
Sending the mask in the updates allows the network to support classless interdomain routing (CIDR), summarization for the Internet, and variable-length subnet mask (VLSM) summarization for the autonomous system. Summarization requires manual configuration at either the routing process or the interface. Figure 4-1 illustrates the configuration for Router A in Example 4-1. Figure 4-1. RIPv2 Configuration  The following example shows a sample configuration, with the version of RIP defined at the routing process. You can also define the RIP version at the interface level if greater granularity is needed. The highlighted commands illustrate how RIP is configured as version 2 and how to manually summarize at the interface level. Example 4-1. RIPv2 Configuration RouterA# Config Term RouterA(config)> enable RouterA(config)# RouterA(config)# router rip RouterA(config-router)# version 2 RouterA(config-router)# network 131.108.0.0 RouterA(config-router)# no auto-summary RouterA(config)# int s0 RouterA(config-if)# ip address 131.108.32.65 255.255.255.224 RouterA(config-if)# ip summary-address rip 131.108.32.0 255.255.224.0 IGRP and EIGRP The next sections briefly describe the distance vector routing protocols IGRP and EIGRP. IGRP Internet Gateway Routing Protocol (IGRP) is a distance vector routing protocol created by Cisco Systems in the mid-1980s. It is a distance vector routing protocol, but because it is proprietary, it has the advantage of being capable of improving many of the elements seen in RIPv1, including incremental updates, fewer network resources to maintain the routing protocol, a more complex and efficient metric, and no limitation in diameter (total hop count) of the network. As a proprietary protocol, IGRP can streamline its operation as a routing protocol, as described previously. A standard solution needs to implement all the options because by definition, it has to be all things to all people. The downside of a Cisco proprietary solution is that it can be implemented only on Cisco routers. However, IGRP is very efficient at sharing its information with other routing protocols using redistribution. IGRP was designed to overcome the limitations of RIPv1. These enhancements center on the speed of convergence, a sophisticated routing metric, and ensuring that the best path is selected and entered into the routing table. The use of triggered updates in IGRP reduces the network resources that are required, which allows for larger networks and, thus, network growth. The following list summarizes the characteristics of IGRP and demonstrates that despite the fact that it is proprietary, IGRP is nonetheless a distance vector routing protocol: -
Periodic updates In the spirit of a distance vector routing protocol, IGRP exchanges updates. IGRP sends updates every 90 seconds (by default), whereas RIP sends updates every 30 seconds. This update is a summary of the routing table and is exchanged only with adjacent routers. -
Broadcasting updates Because the updates are sent to adjacent routers on the same segment, it is convenient to send these updates with a broadcast address. This means that all systems running IGRP on that segment will hear the update. Some protocols developed after IGRP, such as RIPv2, use multicast addressing to reduce the network overhead, which allows the network to scale. -
Full routing table updates Although IGRP sends triggered updates whenever there is a change in the network, it also sends the full routing table every 90 seconds (by default) to ensure that all the routers have the same information. It is essential that the routers have the same information to avoid routing loops and to send packets via the best path. This allows other organizations or departments to merge or for a company to scale its network. -
Count to infinity Like other distance vector routing protocols, IGRP uses the count to infinity to remove bad routes from the routing table. If the hop count to a known route increases, the route is removed from the routing table. The assumption is that another router has poisoned the route. -
Split horizon Split horizon should prevent routing loops between adjacent routes. IGRP, like other distance vector routing protocols, believes that information about a route should never be sent back out of an interface through which it was heard. The theory is that if the updates are sent as broadcast, then every router on that segment has already received the information about that route. This not only prevents routing loops, but also reduces the size of the update by preventing redundant information from being included. -
Triggered updates with route poisoning Distance vector routing protocols attempt to converge the network as quickly as possible. IGRP sends out an update as soon as a change in the network is noticed. If a route has failed, the hop count for that route is set to unreachable. Route poisoning is used in this way to break larger routing loops. -
Load balancing on equal paths (up to four paths, by default) This is a Cisco feature that uses the network to achieve the greatest efficiency. -
Default routes IGRP uses default routes in a slightly different manner from the traditional distance vector routing protocol. Although IGRP accepts the configuration of a default route, it also flags candidates for a default route. The candidate is identified as a route on the edge of the network. The candidate with the lowest metric is selected as the default route. -
Bellman Ford routing algorithm This algorithm is the core of distance vector routing protocols, and IGRP modifies the algorithm in three important ways: -
- It uses a composite metric. -
- It is possible to configure more than one path to a destination. These are equal cost paths by default, but the variance command can be used to load balance across unequal paths. -
- The use of a composite metric uses more than one path to a destination, and triggered updates provide greater stability in the event of network change. IGRP differs from RIPv1 in the following ways: -
The metric is a composite calculated from bandwidth, delay, loading, reliability, and maximum transmission unit (MTU). In fact, although MTU was originally designed as part of the metric, it is tracked but not used in the calculation. It is possible to configure the use of all the calculated elements of the metric. If all elements are not configured, the system will use only bandwidth and delay by default. -
The hop count is 100, configurable to 255 (although the hop count is not used as a metric, but to age out datagrams). -
The update timer is set by default to 90 seconds (three times that of RIPv1). -
Unequal-cost load balancing occurs on multiple paths. -
A more efficient packet structure is used. -
Autonomous systems are used to allow multiple processes within a routing domain, which allows the network to scale. EIGRP Enhanced Interior Gateway Routing Protocol (EIGRP) is a proprietary interior gateway protocol that is based on IGRP. EIGRP strives to reduce the need for network resources while decreasing the convergence times. EIGRP is a proprietary protocol from Cisco and is sometimes referred to as an advanced distance vector protocol, an enhanced distance vector protocol, or a hybrid protocol. The term in current favor is advanced distance vector protocol. EIGRP diverges from a classic distance vector routing protocol in many ways, solving many limitations in scaling the network. EIGRP has the following characteristics: -
In a stable network, EIGRP uses few resources; using only hello packets to maintain the routing databases. -
Changes in the network topology result in propagating only the changes instead of broadcasting the entire routing table every 30 seconds, whatever the status of the network. -
In EIGRP, the initial update is the complete routing table with subsequent updates carrying only changes when those changes occur. A neighbor table is built from hellos, ensuring that both the neighbor and the link are up and running. If the neighbor table fails to hear a hello in the allotted time, the routing process sends an update to the other neighbors informing them of a change in the network. The neighbor table also keeps track of acknowledgments (ACKs) received for the updates that have been sent. Reliable updates mean EIGRP does not have to retransmit every 30 seconds like RIPv1. -
Using Diffused Update Algorithm (DUAL), the network converges quickly with a minimum of network traffic. -
Instead of having to wait for updates, as soon as a route goes down, EIGRP examines the topology table for an alternative route. If an appropriate route is found, it is immediately placed into the routing table. In the event that no alternative path is found in the routing table, the neighbors are polled for alternative routes. Choosing Between Routing Protocols Using Administrative Distance Clearly, there are many IP routing protocols from which to choose. Choosing a single routing protocol is better, because the resulting consistency relates directly to the strength of the network. The network is complicated when more than a single routing protocol attempts to perform the same job. When more than one routing protocol is running on the router, the routing process must make a decision to have one entry per prefix in the routing table. The choice cannot be based on the metric because metrics differ between routing protocols. Instead, another method, called administrative distance , was devised to solve the problem. NOTE The routing table on a router running more than one routing protocol knows about all the networks heard by the various protocols and sends data to all of the distant networks, choosing the best path via administrative distance. However, a routing protocol only sends updates about networks it has knowledge of, so if IGRP knows about networks 1, 2, and 3, it propagates knowledge of these networks out of IGRP-configured interfaces to other IGRP routers on the same segment. It will not send out information about networks 4, 5, and 6 that were placed into the routing table by RIP. In order for the IGRP routers to hear of networks 4, 5, and 6, it is necessary to share the network information between the routing protocols. This is called redistribution . However, the router that is responsible for redistribution will have more than one process running, which takes extra resources.
The administrative distance selects one or more paths to enter the routing table from several paths offered by multiple routing protocols. In Figure 4-2, for example, both RIP and EIGRP have paths to the network 140.100.6.0. RIP is configured on the FDDI ring and EIGRP is running on the rest of the network. On Router D, RIP is offering a metric of 2 hops, and EIGRP is offering a metric of 768. Without redistribution, no conversion or choice is possible, because there are no similar criteria for distinguishing the two paths. Therefore, the metric is ignored, and the administrative distance is used to make the selection. The administrative distance of EIGRP is lower than that of RIPv1, so the path advertised by EIGRP is chosen , despite the speed of Frame Relay set at 56 kbps as opposed to the 100 Mbps of FDDI. In this case, if it is not possible to run EIGRP on the FDDI ring because of proprietary restrictions, manually configuring the administrative distance on Router D would be advisable. Figure 4-2. Path Selection Using Administrative Distance  Administrative distance is a rather arbitrary set of values placed on the different sources of routing information. You can change the defaults, but proceed carefully when subverting the natural path selection. You must perform any manual configuration with careful reference to the network design of the organization and its traffic flow. The creation of floating static routes is an example of when the administrative distance is changed. A lower administrative distance reflects the preferred choice. Table 4-2 lists the administrative distance defaults. Table 4-2. Default Administrative Distance | Routing Source | Administrative Distance | | Connected interface or static route that identifies the outgoing interface rather than the next hop | | | Static route | 1 | | EIGRP summary route | 5 | | External BGP | 20 | | EIGRP | 90 | | IGRP | 100 | | OSPF | 110 | | RIP | 120 | | External EIGRP | 170 | | Internal BGP | 200 | | An unknown network | 255 or infinity | The administrative distance is looked at with total disregard of the metrics, which might result in a poor path selection. Problems can occur when redundancy is built into the network. For example, a low-cost, low-speed connection to a network can be used as a backup link to the core of the network or the segment that has the servers. The intention is for the link never to be used. The link is there as insurance against the primary link failing. Backup links for redundancy are often implemented over on-demand serial connections where the network charges are based on usage. However, in Figure 4-2, you have seen that this backup link would become the primary link. To make this truly a backup link, you must configure it as a static route. However, the administrative distance of a static route takes precedence over everything but a directly connected network. Therefore, you need to configure manually the static route's administrative distance to ensure that it takes precedence over any other route information only when the primary route fails. This design is called a floating static route. Convergence Convergence occurs when all the routers in the routing domain agree on the routes that are available. Convergence time is the time that it takes for every router's routing table to synchronize after there has been a change in the network topology. You need to ensure that the time taken is as short as possible, because while the routers disagree on the available networks, they cannot route data correctly or efficiently . Each routing protocol has a different method of updating the routing table. This affects convergence time. The following sections introduce new concepts by explaining the different protocol convergence methods . The sections show the relative merits of each approach. The concepts are explained in depth in the chapters that concentrate on the specific protocols. The terms shown in italics are defined in the final glossary at the end of the book. RIPv1 and RIPv2 Convergence The steps for RIPv1 and RIPv2 convergence are as follows : -
When the local router sees a connected route disappear, it sends a flash update and removes the route entry from its table. This is called a triggered update with poison reverse . -
The receiving routers send flash updates and put the affected route in holddown . -
The originating router queries its neighbor for alternative routes. If the neighbor has an alternative route, it is sent; otherwise , the poisoned route is sent. -
The originating router installs the best alternative route that it hears because it has purged the original routes. -
Routers that are in holddown ignore the alternative route. When the other routers emerge from holddown, they will accept the alternative route. Convergence takes the time for detection, plus holddown, plus the number of routing updates (equal to the hop-count diameter of the network). IGRP Convergence The steps for IGRP convergence are as follows: -
When the local router sees a connected route disappear, it sends a flash update and removes the route entry from its table. This is called a triggered update with poison reverse. -
The receiving routers send flash updates and put the affected route in holddown. -
The originating router queries its neighbor for alternative routes. If the neighbor has an alternative route, it is sent; otherwise, the poisoned route is sent. -
The originating router installs the best alternative route that it hears because it has purged the original routes. It sends a new flash update. This is the routing table, either with or without the network available, stating the higher metric. -
Routers that are in holddown ignore the alternative route. -
When the routers come out of holddown, they accept the alternative route. When the other routers emerge from holddown, they will accept the alternative route. Convergence takes the time for detection, plus holddown, plus the number of routing updates (equal to the hop-count diameter of the network). Because the time between updates is 90 seconds, this could take a very long time. EIGRP Convergence The steps for EIGRP convergence are as follows: -
When the local router sees a connected route disappear, it checks the topology table for a feasible successor. If no feasible successor exists, it moves into active state. -
The originating router queries its neighbor for alternative routes, and the receiving router acknowledges. -
If an alternative route exists, information about this route is sent to the querying router. -
If the router receives an acceptable successor, it adds the route to the table. -
The router sends out a flash update of the path with the higher metric. -
The receiving router acknowledges the update. Convergence is quick because it is the detection time plus query time, reply time, and update time. If there is a feasible successor, convergence is almost instantaneous. Interior and Exterior Gateway Protocols Routing protocols that operate within an organization are referred to as Interior Gateway Protocols (IGPs) or interior routing protocols (for example, RIPv1, RIPv2, IGRP, EIGRP, OSPF, and IS-IS). The boundaries of the organization are defined as the autonomous system . The unique number assigned to the autonomous system then identifies the organization. The autonomous system number might be viewed as another layer of hierarchy in the IP addressing scheme, because the number can represent a collection of IANA numbers . Routing protocols that exchange routing information between organizations are known as Exterior Gateway Protocols (EGPs). EGPs are highly complex. The complexity arises from the need to determine policies between different organizations. Border Gateway Protocol Version 4 (BGP-4) is the only current example of an EGP. |
