Routing protocol algorithms can be classified by type. Key characteristics include the following categories:
We discuss these characteristics in more detail in the following sections. Static and DynamicThe static routing process is really not an actual algorithm but rather a set of table mappings established by the network administrator before the beginning of the routing process. These mappings do not change unless the administrator adjusts them. Static routes provide a high degree of administrative simplification, control, and security. They function best in environments in which network traffic is relatively predictable and the network design is relatively simple. The downside to static routing is the administrative overhead and lack of scalability. You use the following global configuration command to add a static route to an IP routing table: ip route prefix mask {address interface} [distance] Table 2.2 explains the ip route command options. Table 2.2. Description of the ip route Command
Static routing systems do not react to network changes; therefore, they are generally considered unsuitable for medium to large, constantly changing networks. If only one path exists to the Internet or another autonomous system, it might be appropriate to use a default or static route.
Static routes can complement dynamic routing algorithms when necessary. For example, a router of last resort (the router to which all unroutable packets are sent) can be designated to forward packets if no path to the destination exists in the routing table. If a network has only one outbound WAN connection to an ISP, for example, an administrator can configure a static default route to the provider. Most of the dominant routing algorithms used today are dynamic routing algorithms, which adjust to changing network circumstances by analyzing incoming routing update messages. If the message indicates that a network change has occurred, the routing software recalculates the routes and sends out new routing update messages. These communications filter through the network and motivate routers to recalculate their algorithms and update their tables accordingly . This book focuses almost exclusively on the operations of dynamic routing algorithms. Single-Path and MultipathSome advanced routing protocols support multiple paths to the same destination. Unlike a single-path algorithm, a multipath algorithm allows traffic to be multiplexed over multiple equal-cost or unequal -cost lines. All the covered IP dynamic routing protocols can load balance across multiple equal-cost paths to deliver packets.
The advantages of multipath are really seen on the routers that function at the highest hierarchical level (the backbone) of the routing topology. The principle benefit of hierarchical routing is that it can imitate the company's organizational structure and provide support for practical traffic patterns. Intradomain and InterdomainThe ISO created a hierarchical framework that helps describe the router switching process. Using this framework, network devices that do not have the means of forwarding packets between subnetworks are called end systems (ESs) , whereas network devices with these capabilities are called intermediate systems (ISs) . ISs are then divided into two subsystems: ISs that can communicate within routing domains are known as intradomain ISs, and those that communicate both within and between routing domains are called interdomain ISs.
A routing domain (or area ) is typically defined as a system that is part of an internetwork and under a common administrative authority controlled by a specific set of rules. Routing domains are also commonly known as autonomous systems. In addition, routing domains can be further divided into routing areas with certain routing protocols even though intradomain routing protocols are still used for switching both within and between areas. Interdomain protocols are sometimes generically referred to as Exterior Gateway Protocols (EGPs) . This is a broad term that represents protocols used to exchange routing information between autonomous systems. Border Gateway Protocol (BGP) is a commonly used interdomain EGP. Because the very nature of these two algorithm types is different, it stands to reason that the best choice for an intradomain routing algorithm would not necessarily be an optimal interdomain routing algorithm. Classful and ClasslessRouting protocols can also be categorized as classful or classless protocols. RIPv1 and IGRP are considered classful protocols because they do not send subnet mask information with the network address in the routing update message. Classful addresses use a scheme in which the major network number is either Class A, B, C, D, or E. In a classful protocol environment, all the subnets of the major network address class must use the same subnet mask. For instance, if a router receives an update that has the same major network number (for example, 172.16.0.0) that is configured on the inbound interface, the router applies the subnet mask configured for the interface. However, if the routing update is for a major network different from the inbound interface, the default Class A, B, or C subnet mask is used and applied to the routing table.
If routing information is swapped between networks using different major network numbers , the receiving routers will not know the subnet mask being implemented because the subnet information is not stored in the routing update packets. As a result, subnetwork information from all the major networks must be summarized to a classful network number using the default subnet mask before the update is added to the table. Only routers configured for the major networks to which the subnets belong can trade subnetted route information; the routers that belong to different major networks trade the classful summary routes. Classful routing protocols automatically generate a classful summary route at major network boundaries, as shown in Figure 2.2. Figure 2.2. RIPv1 routers do not deliver subnet mask information.
As you can see, only routing devices within the same major network share subnetworked route information. Classful summary routes are automatically generated at Class A, B, and C network boundaries by routers using classful routing protocols such as RIPv1 and IGRP.
Classless routing protocols were originally developed to overcome the limitations inherent to classful protocols such as RIPv1. The classless routing protocols commonly used by Cisco router devices are OSPF, EIGRP, RIPv2, IS-IS, and BGP-4. Classless protocols have the advantage of including the subnet mask for each route to perform a more advanced lookup in the routing table. Classless routing protocols also implement a manual summarizing technique that allows summarization at any bit position in the network. Route summarization is the process of consolidating advertised addresses in a routing table. This technique leads to smaller routing tables, reduced update traffic, and lower processing and memory overhead. This really comes in handy because the routing tables of the Internet routers seem to expand almost exponentially with the growth of the Web. Route summarization is also referred to as route aggregation. Classless routing protocols have the benefit of understanding the concept that different routes can have different masks in a major network. This technique of using different subnet masks is called variable-length subnet masking ( VLSM ) . VLSM enables network engineers to optimize the available address space and construct a hierarchical addressing scheme that fits the environment. This concept is explored in depth in Chapter 3. Distance Vector and Link-stateThe notion of a vector in networking relates to both the distance and the direction to a destination. Distance vector protocols, such as RIP, use the Bellman-Ford algorithm and call for each router to send all or some portion of the routing table to their directly connected neighbors. Distance vector routers know about, and send updates to, only these neighbors. Therefore, a router's picture of the network topology depends on the perspective of its neighbors. This process is also affectionately known as routing by rumor . The Cisco IOS supports several distance vector protocols, including RIPv1, RIPv2, and IGRP. As far as the OSI model is concerned , IGRP functions at the network layer with a protocol number of 9 in the IP header. RIP also functions primarily at the network layer, uses UDP port 520, and finds the best path to a remote network using hop count as a metric. IP RIP has a maximum hop count of 15, and IGRP has a maximum of 255. Tables 2.3 and 2.4 show the characteristics and comparisons of distance vector routing protocols, respectively. Table 2.3. Attributes of Distance Vector Protocols
Table 2.4. Contrasting IP Distance Vector Routing Protocols
Link-state algorithms, such as OSPF, are also referred to as shortest path first algorithms. Link-state protocols generate routing updates only when a change occurs and flood the resulting routing information to all nodes in the internetwork in the form of a link-state advertisement (LSA). Each router sends only a portion of the routing table that describes the state of its own links. Link-state routers build a picture of the entire network in a topology table and typically require a hierarchical design (except EIGRP). Because they can converge more quickly, link-state algorithms are somewhat less prone to routing loops than distance vector algorithms. On the other hand, link-state algorithms typically require more CPU power and memory than distance vector protocols. Although link-state protocols are generally more scalable than distance vector protocols, they can also be more expensive to implement and support. EIGRP is actually a hybrid routing protocol that has some attributes of link-state operation. Other link-state protocols covered in this book are OSPF and IS-IS. Tables 2.5 and 2.6 show the characteristics and comparisons of link-state routing protocols, respectively. Table 2.5. Attributes of Link-state Protocols
Table 2.6. Contrasting IP Link-state Routing Protocols
ConvergenceRouting algorithms must provide at least one single, loop-free route to every possible destination network. All the routing tables in the routing domain or area must eventually be synchronized and in agreement with a useable route to each destination network. This course of action is known simply as convergence. Convergence is defined as the rate and capability of a collection of router devices running a common routing protocol to agree on optimal routes. When a network event causes routes to either go down or become recently available, routers dispense routing update messages to permeate the network and stimulate the recalculation of optimal routes. The goal is to eventually cause all routers to agree on these optimal routes. Routing algorithms that suffer from slow convergence can create routing loops or even network outages. As with the other characteristics of routing protocols previously mentioned, convergence time varies depending on the efficiency of the routing algorithm being used, the size of the network, and several configurable timers.
Convergence is affected by changes in the status of network links, and several ways are available to detect them. For example, if a device functioning at OSI Layer 1 or 2 (an Ethernet network interface) fails to receive a certain number of consecutive keepalive messages, the link is marked as down. In addition, if the Layer 3 protocol fails to receive a number of consecutive hello packets or regular update messages, the link is marked as down. Most routing algorithms use different sets of timers for loop prevention and network topology stabilization during times of recalculation of routing tables.
RIPv1 and RIPv2 Convergence BasicsThe RIP version 1 routing protocol is one of the first interior gateway protocols used and has a long history in several routed network environments, including Unix and Microsoft. Besides the lack of scalability (it has a maximum hop count of 15), the other downside to RIPv1 is its rather high time to converge after a network event. Regardless, this routing protocol is the first example to help demonstrate the basic convergence process. Figure 2.3 shows how various routing protocols accomplish convergence. Figure 2.3. Sample network to demonstrate various methods of convergence.
In Figure 2.3, RouterC notices a failure on network 10.10.0.0 between itself and RouterA. RouterC generates an update, called a flash update , when an event occurs. This special update consists of the full routing table as well as a RIP poisoned route with a metric of 16 (unreachable). The flash update is sent to the neighbors of RouterC: RouterB and RouterD. Subsequently, RouterD generates a flash update and sends it to RouterE. Next, RouterC removes the entry for network 10.10.0.0 and all associated routes from its route table. Because this network is running RIPv2, RouterC sends a query to multicast address 224.0.0.9 to locate another path to network 10.10.0.0 (RIPv1 would use broadcast address 255.255.255.255). RouterD overrides the split horizon rule by sending a poison reverse to network 10.10.0.0. RouterB responds to RouterC with a higher hop count to RouterA, and RouterC adds it to the routing table because it purged it early in the process. Responses to queries are also complete routing tables.
Next, RouterD goes into a state of hold-down, and it eventually gets an advertisement from RouterC with the weaker metric it learned from RouterB. According to the rules of hold-down, RouterD ignores the weaker metric. Eventually, RouterD and RouterE come out of hold-down (180 seconds) and update their routing tables with the path to network 10.10.0.0 through RouterB. The time for RouterE to converge fully could be as much as 3 1/2 minutes.
IGRP Convergence BasicsUsing Figure 2.3 as the prototypical design, IGRP offers greater scalability and flexibility but typically a longer convergence time than RIP. After RouterC notices the failed Ethernet 10.10.0.0 it shares with RouterA, it poisons the route with a flash update to RouterB and RouterD.
Next, RouterD generates and sends its own flash update to RouterE as RouterC flushes the directly connected downed link from its routing table. Just as with RIP, an IGRP-loaded RouterC also eradicates all the routes related to that link from its routing table. Next, RouterC broadcasts all its interfaces, using logical network address 255.255.255.255, to its neighbors in search of another path to 10.10.0.0. RouterD generates a poison reverse, and RouterC then issues a flash update omitting the failed link that was purged.
Next, RouterB responds to RouterC with a poorer metric value to network 10.10.0.0 than the one originally held by RouterC. RouterC adds it to its routing table and floods the network with a flash update containing the new information. RouterD ignores this update from RouterC because it is in hold-down and the metric is poorer than the one originally known for network 10.10.0.0. It continues to send poisoned updates to RouterC, however. After RouterD and RouterE reach the hold-down timer interval (the default is 280 seconds), they update their tables with the new route from RouterC. The time for RouterE to converge fully could be almost 7 minutes taking into consideration all the IGRP timers.
EIGRP Convergence BasicsContinuing with the network infrastructure shown in Figure 2.3, EIGRP can provide very rapid convergence in contrast to RIP and IGRP. Although this process is covered in greater detail in later chapters, it is necessary to address some terminology before exploring the EIGRP convergence process. Table 2.7 introduces some key EIGRP concepts. Table 2.7. Survey of EIGRP Terminology Relating to Convergence
In this routing convergence scenario, the EIGRP-loaded RouterC observes a link failure between itself and RouterA on network 10.10.0.0. RouterC then looks in its topology table to find a feasible successor but does not find a suitable alternative route and begins to look for a new route (the Active state) by sending a query to neighbor routers on EIGRP multicast address 224.0.0.10. RouterD replies that there is no other path to network 10.10.0.0, and RouterB replies with an alternative route containing an entry with a higher feasible distance.
Next, RouterC sends a new message out all interfaces with this updated information from its topology and routing tables. All of RouterC's neighbors acknowledge the update and send their updates back to RouterC to synchronize and converge the EIGRP network topology. The time for RouterE to converge fully is very rapid and efficient, occurring in as few as 2 “3 seconds.
OSPF Convergence BasicsAlthough the OSPF routing protocol is covered extensively in later chapters, we should look at how OSPF converges compare to the previous distance vector protocol types. OSPF also has its own set of terms that set it apart from other algorithms, as shown in Table 2.8. Table 2.8. Survey of OSPF Terminology Relating to Convergence
Referring back to Figure 2.3, the moment that OSPF RouterC notices the failed link to RouterA, it attempts to carry out an election for a designated router (DR) on interface E0. When it fails to reach the neighbor, it deletes the route to network 10.10.0.0 from the routing table. Next, RouterC floods an LSA to RouterB and RouterD. These routers, in turn , flood a copy of this LSA packet out every interface other than the one on which it was received. By default, OSPF routers wait 5 seconds after they receive an LSA before recalculating the shortest path first algorithm. Next, RouterC adds the new route through 10.20.0.0 to its routing table, and RouterB, RouterD, and RouterE update the metric in their routing tables as well. After a 40-second dead interval, RouterA sends an LSA because it has not received a hello packet from RouterC. The DR on the network up to this point was RouterC, so RouterA becomes the DR and floods another advertisement on the network. The other routers wait 5 seconds and run the shortest path first algorithm so that, eventually, network 10.10.0.0 is reached via RouterB. RouterE eventually becomes converged based on the total detection time and the total LSA flooding time plus 5 seconds. The time for the entire network to converge, however, could take from 45 seconds to 1 minute based on the network design.
|