| Note |
|
This chapter introduces EIGRP terminology and operations, and explains how to plan for, configure, and verify EIGRP. The chapter explores considerations for deploying EIGRP in enterprise WANs, and how to configure and verify EIGRP authentication. The chapter concludes with a discussion of optimizing EIGRP implementations.
Understanding EIGRP Terminology and Operation
This section introduces EIGRP, describes its capabilities, and explains its terminology. EIGRP operation, including how EIGRP’s tables are created, is examined. This section also describes the Diffusing Update Algorithm (DUAL) and provides a detailed example. The EIGRP metric calculation is also described.
EIGRP Capabilities and Attributes
EIGRP is a Cisco-proprietary protocol that combines the advantages of link-state and distance vector routing protocols. EIGRP has its roots as a distance vector routing protocol and is predictable in its behavior. Like its predecessor IGRP, EIGRP is easy to configure and is adaptable to a wide variety of network topologies. What makes EIGRP an advanced distance vector protocol is the addition of several link-state features, such as dynamic neighbor discovery. EIGRP is an enhanced IGRP because of its rapid convergence and the guarantee of a loop-free topology at all times. Features of this protocol include the following:
- Fast convergence— EIGRP uses DUAL to achieve rapid convergence. A router running EIGRP stores its neighbors’ routing tables so that it can quickly adapt to changes in the network. If no appropriate route exists in the local routing table and no appropriate backup route exists in the topology table, EIGRP queries its neighbors to discover an alternative route. These queries are propagated until an alternative route is found or until it is determined that no alternative route exists.
- Partial updates— EIGRP sends partial triggered updates rather than periodic updates. These updates are sent only when the path or the metric for a route changes. They contain information about only that changed link rather than the entire routing table. Propagation of these partial updates is automatically bounded so that only those routers that require the information are updated. As a result, EIGRP consumes significantly less bandwidth than IGRP. This behavior is also different from link-state protocol operation, which sends a change update to all routers within an area.
- Multiple network layer support— EIGRP supports IP Version 4 (IPv4), IP Version 6 (IPv6), AppleTalk, and Novell NetWare Internetwork Packet Exchange (IPX) using protocol-dependent modules that are responsible for protocol requirements specific to the network layer. EIGRP’s rapid convergence and sophisticated metric offer superior performance and stability when implemented in IP, IPv6, IPX, and AppleTalk networks.
Note Note Only the IP implementation of EIGRP is thoroughly covered in this chapter. EIGRP for IPv6 is covered in Chapter 8, “Implementing IPv6 in the Enterprise Network.”AppleTalk and IPX are legacy protocols. See the Cisco IOS technical documentation at Cisco.com for information about how EIGRP operates, and how to configure it, for AppleTalk and IPX. - Use of multicast and unicast— For communication between routers, EIGRP uses multicast and unicast rather than broadcast. As a result, end stations are unaffected by routing updates or queries. The multicast address used for EIGRP is 224.0.0.10.
| Note |
|
Other EIGRP features include the following:
- Variable-length subnet masking (VLSM) support— EIGRP is a classless routing protocol, which means that it advertises a subnet mask for each destination network. This enables EIGRP to support discontinuous subnetworks and VLSM.
- Seamless connectivity across all data link layer protocols and topologies— EIGRP does not require special configuration to work across any Layer 2 protocols. Other routing protocols, such as Open Shortest Path First (OSPF), require different configurations for different Layer 2 protocols, such as Ethernet and Frame Relay (as you will see in Chapter 3, “Configuring the Open Shortest Path First Protocol”). EIGRP was designed to operate effectively in both LAN and WAN environments. In multiaccess topologies, such as Ethernet, neighbor relationships (also known as neighborships) are formed and maintained using reliable multicasting. EIGRP supports all WAN topologies: dedicated links, point-to-point links, and nonbroadcast multiaccess (NBMA) topologies. EIGRP accommodates differences in media types and speeds when neighbor adjacencies form across WAN links. The amount of bandwidth that EIGRP uses on WAN links can be limited.
- Sophisticated metric— EIGRP uses the same algorithm for metric calculation as IGRP, but represents values in a 32-bit format, rather than IGRP’s 24-bit format, to give additional granularity (thus, the EIGRP metric is the IGRP metric multiplied by 256). A significant advantage of EIGRP (and IGRP) over other protocols is its support for unequal metric load balancing that allows administrators to better distribute traffic flow in their networks.
Like most IP routing protocols, EIGRP relies on IP packets to deliver routing information.
The EIGRP routing process is a transport layer function. IP packets carrying EIGRP information have protocol number 88 in their IP header, as illustrated in Figure 2-1 (similar to how the Transmission Control Protocol [TCP] is protocol number 6 and the User Datagram Protocol [UDP] is protocol number 17).
Figure 2-2 illustrates how EIGRP performs automatic route summarization at major network boundaries. You can disable this feature. Administrators can also configure manual summarization on arbitrary bit boundaries on any router interface (as long as a more-specific route exists in the routing table) to shrink the size of the routing table. EIGRP also supports the creation of supernets or aggregated blocks of addresses (networks).
| Note |
|
EIGRP supports hierarchical addressing to enable EIGRP summarization and also supports nonhierarchical IP addressing.
EIGRP uses the following four key technologies that combine to differentiate it from other routing technologies:
- Neighbor discovery/recovery mechanism— EIGRP’s neighbor discovery mechanism enables routers to dynamically learn about other routers on their directly attached networks. Routers also must discover when their neighbors become unreachable or inoperative. This process is achieved with low overhead by periodically sending small hello packets. As long as a router receives hello packets from a neighboring router, it assumes that the neighbor is functioning, and the two can exchange routing information.
- Reliable Transport Protocol (RTP)— RTP is responsible for guaranteed, ordered delivery of EIGRP packets to all neighbors. RTP supports intermixed transmission of multicast or unicast packets. For efficiency, only certain EIGRP packets are transmitted reliably.For example, it is not necessary to send hello packets reliably to all neighbors individually, so EIGRP sends a single multicast hello packet containing an indicator that informs the receivers that the packet need not be acknowledged. Other types of packets, such as updates, indicate in the packet that acknowledgment is required. RTP contains a provision for sending multicast packets quickly even when unacknowledged packets are pending, which helps ensure that convergence time remains low in the presence of varying speed links.
- DUAL finite-state machine— DUAL embodies the decision process for all route computations. DUAL tracks all routes advertised by all neighbors and uses distance information, known as the composite metric or cost, to select efficient, loop-free paths to all destinations.
- Protocol-dependent modules— EIGRP’s protocol-dependent modules are responsible for network layer protocol-specific requirements. As mentioned earlier, EIGRP supports IP, IPv6, and the legacy protocols AppleTalk, and IPX. Each protocol has its own EIGRP module and operates independently from any of the others that might be running. The IP-EIGRP module, for example, is responsible for sending and receiving EIGRP packets that are encapsulated in IP. Likewise, IP-EIGRP is also responsible for parsing EIGRP packets and informing DUAL of the new information that has been received. IP-EIGRP asks DUAL to make routing decisions, the results of which are stored in the IP routing table. IP-EIGRP is also responsible for redistributing routes learned by other IP routing protocols.
EIGRP Terminology
The following terms are related to EIGRP and are used throughout the rest of this chapter:
- Neighbor table— EIGRP routers use hello packets to discover neighbors. When a router discovers and forms an adjacency with a new neighbor, it includes the neighbor’s address and the interface through which it can be reached in an entry in the neighbor table. This table is comparable to the neighborship (adjacency) database used by link-state routing protocols (as described in Chapter 3). It serves the same purpose—ensuring bidirectional communication between each of the directly connected neighbors. EIGRP keeps a neighbor table for each network protocol supported. In other words, the following tables could exist: an IP neighbor table, an IPv6 neighbor table, an IPX neighbor table, and an AppleTalk neighbor table.
- Topology table— When the router dynamically discovers a new neighbor, it sends an update about the routes it knows to its new neighbor and receives the same from the new neighbor. These updates populate the topology table. The topology table contains all destinations advertised by neighboring routers. In other words, each router stores its neighbors’ routing tables in its EIGRP topology table. If a neighbor is advertising a destination, it must be using that route to forward packets. This rule must be strictly followed by all distance vector protocols. An EIGRP router maintains a topology table for each network protocol configured (IP, IPv6, IPX, and AppleTalk).
- Advertised distance and feasible distance— DUAL uses distance information, known as a metric or cost, to select efficient, loop-free paths. The lowest-cost route is calculated by adding the cost between the next-hop router and the destination—referred to as the advertised distance (AD)—to the cost between the local router and the next-hop router. The sum of these costs is referred to as the feasible distance (FD).
- Successor— A successor, also called a current successor, is a neighboring router that has a least-cost path to a destination (the lowest FD) that is guaranteed not to be part of a routing loop. Successor routes are offered to the routing table to be used for forwarding packets. Multiple successors can exist if they have the same FD.
- Routing table— The routing table holds the best routes to each destination and is used for forwarding packets. EIGRP successor routes are offered to the routing table. (As discussed in Chapter 1, if a router learns more than one route to exactly the same destination from different routing sources, it uses the administrative distance to determine which offered route to keep in the routing table.) By default, each protocol can add up to four routes to the same destination with the same metric to the routing table (recall that the router can be configured to accept up to 16 per destination). The router maintains one routing table for each network protocol configured.
- Feasible successor— Along with keeping least-cost paths, DUAL keeps backup paths to each destination. The next-hop router for a backup path is called the feasible successor (FS). An FS is a neighbor that is closer to the destination, but it is not in the least-cost path and, therefore, is not used to forward data. To qualify as an FS, a next-hop router must have an AD less than the FD of the current successor route. This ensures a loop-free topology. Feasible successors are selected at the same time as successors but are kept only in the topology table. The topology table can maintain multiple feasible successors for a destination.
EIGRP uses DUAL to calculate the best route to a destination. DUAL selects successor routes and FS routes based on the composite metric and ensures that the selected routes are loop-free.
EIGRP Operation
This section explains the mechanisms for creating the various EIGRP tables and describes the five types of EIGRP packets. This section also explains how EIGRP routers become neighbors, the initial route discovery process, how routes are selected, and how the DUAL algorithm functions.
Populating EIGRP Tables
The EIGRP route selection process is perhaps what most distinguishes it from other routing protocols. EIGRP selects primary (successor) and backup (feasible successor) routes. These are marked as such in the topology table. The primary (successor) routes are then moved to the routing table.
EIGRP supports several types of routes: internal, external, and summary. Internal routes originate within the EIGRP autonomous system (AS). External routes are learned from another routing protocol or another EIGRP autonomous system. Summary routes are routes encompassing multiple subnets.
Figure 2-3 illustrates the three tables that EIGRP uses in its operation:
- The neighbor table lists adjacent routers.
- The topology table lists all the learned routes to each destination.
- The routing table contains the best route (the successor route) to each destination.
Neighbor Table
The neighbor table includes the address of each neighbor and the interface through which it can be reached. The neighbor table entry also includes information required by RTP. Sequence numbers are used to match acknowledgments with data packets, and the last sequence number received from the neighbor is recorded, to detect out-of-order packets. A transmission list is used to queue packets for possible retransmission on a per-neighbor basis. Round-trip timers are kept in the neighbor table entry to estimate an optimal retransmission interval.
Topology Table
Each EIGRP router forwards a copy of its IP routing table to all its adjacent EIGRP neighbors, as specified in its EIGRP neighbor table. Each router then stores the routing tables of the adjacent neighbors in its EIGRP topology table (database). The topology table also maintains the metric that each neighbor advertises for each destination (the AD) and the metric that this router would use to reach the destination via that neighbor (the FD). The show ip eigrp topology all-links command displays all the IP entries in the topology table, while the show ip eigrp topology command displays only the successors and feasible successors for IP routes.
The topology table is updated when a directly connected route or interface changes or when a neighboring router reports a change to a route.
A topology table entry for a destination can exist in one of two states: active or passive. A route is considered passive when the router is not performing recomputation on that route. A route is active when it is undergoing recomputation (in other words, when it is looking for a new successor). Note that passive is the operational, stable state.
If the route via the successor becomes invalid (because of a topology change) or if a neighbor is lost or changes the metric, DUAL checks for feasible successors to the destination. If an FS is found, DUAL uses it, thereby avoiding recomputing the route. This results in fast convergence. If feasible successors are always available, a destination never has to go into the active state, thereby avoiding a recomputation.
A recomputation occurs when the current route to a destination, the successor, goes down and there are no feasible successors for the destination. Although recomputation is not processor intensive, it does affect convergence time, so it is advantageous to avoid unnecessary recomputations. The router starts the recomputation by sending a query packet to each of its neighboring routers. If the neighboring router has a route for the destination, it will send a reply packet. If it does not have a route, it sends a query packet to its neighbors. In this case, the route is also in the active state in the neighboring router; while a destination is in the active state, a router cannot change the routing table information for the destination.
This process continues. Routers that have no other neighbors and routers that know that the destination is unreachable reply to queries immediately, indicating the route is unreachable. When a router receives all replies to its query, it replies to queries from its neighbor, and so on. If there is at least one topology table entry for the destination after a router has received a reply from each neighboring router, the destination returns to the passive state, and the router select a successor for it. If there are no topology table entries for the destination, it is no longer reachable from that router. (The “Stuck-in-Active Connections in EIGRP” section, later in this chapter, describes what happens if not all replies are received for a query in a timely manner.)
Routing Table
Each router examines its EIGRP topology table and determines the best route and other feasible routes to every destination network. A router compares all FDs to reach a specific network and then selects the route with the lowest FD and places it in the IP routing table. This is the successor route. The FD for the chosen successor route becomes the EIGRP routing metric to reach that network in the routing table.
EIGRP Packets
EIGRP sends out five different types of packets: hello, update, query, reply, and acknowledge (ACK). These packets are used to establish the initial adjacency between neighbors and to keep the topology and routing tables current. When troubleshooting an EIGRP network, network administrators must understand what the EIGRP packets are used for and how they are exchanged. For example, if routers running EIGRP do not form neighbor relationships, those routers cannot exchange EIGRP updates with each other. Without EIGRP routing updates, users cannot connect to services across the internetwork.
EIGRP uses the following five types of packets:
- Hello— Hello packets are used for neighbor discovery. They are sent as multicasts and do not require an acknowledgment. (They carry an acknowledgment number of 0.)
- Update— Update packets contain route change information. An update is sent to communicate the routes that a particular router has used to converge. An update is sent only to affected routers. Update packets are sent as multicasts when a new route is discovered, and when convergence is complete (in other words, when a route becomes passive). To synchronize topology tables, update packets are sent as unicasts to neighbors during their EIGRP startup sequence. Update packets are sent reliably.
- Query— When a router is performing route computation and does not have an FS, it sends a query packet to its neighbors, asking whether they have a successor to the destination. Queries are normally multicast but can be retransmitted as unicast packets in certain cases. They are sent reliably.
- Reply— A reply packet is sent in response to a query packet. Replies are unicast to the originator of the query and are sent reliably. A router must reply to all queries.
- ACK— The ACK is used to acknowledge updates, queries, and replies. ACK packets are unicast hello packets and contain a nonzero acknowledgment number. (Note that hello and ACK packets do not require acknowledgment.)
The hello packet is the first type exchanged by EIGRP routers. The following section provides details of the hello protocol and how hello packets are used. The details of how the other packet types are used are provided throughout the rest of the chapter.
EIGRP Hello Packets
Through the hello protocol, an EIGRP router dynamically discovers other EIGRP routers directly connected to it. The router sends hello packets out of interfaces configured for EIGRP using the EIGRP multicast address 224.0.0.10. When an EIGRP router receives a hello packet from a router belonging to the same autonomous system, it establishes a neighbor relationship (adjacency).
| Note |
|
The time interval of hello packets varies depending on the medium. By default, hello packets are sent every 60 seconds on T1 or slower NBMA interfaces and every 5 seconds on other serial interfaces and on LANs.
| Note |
|
You can adjust the rate at which hello packets are sent, called the hello interval, on a per-interface basis with the ip hello-interval eigrp as-number seconds interface configuration command.
Hello packets include the hold time. The hold time is the amount of time a router considers a neighbor up without receiving a hello or some other EIGRP packet from that neighbor. The hold-time interval is set by default to three times the hello interval. Therefore, the default hold-time value is 15 seconds on LAN and fast WAN interfaces and 180 seconds on slower WAN interfaces. You can adjust the hold time with the ip hold-time eigrp as-number seconds interface configuration command.
| Note |
|
If a packet is not received before the expiration of the hold time, the neighbor adjacency is deleted, and all topology table entries learned from that neighbor are removed, as if the neighbor had sent an update stating that all the routes are unreachable. If the neighbor is a successor for any destination networks, those networks are removed from the routing table, and alternative paths, if available, are computed. This lets the routes quickly reconverge if an alternative feasible route is available.
EIGRP Neighbors
Two routers can become EIGRP neighbors even though the hello and hold time values do not match. This means that the hello interval and hold-time values can be set independently on different routers.
Secondary addresses can be applied to interfaces to solve particular addressing issues, although all routing overhead traffic is generated through the primary interface address. EIGRP will not build peer relationships over secondary addresses because all EIGRP traffic uses the interface’s primary address. To form an EIGRP adjacency, all neighbors use their primary address as the source IP address of their EIGRP packets. Adjacency between EIGRP routers takes place if the primary address of each neighbor is part of the same IP subnet. In addition, peer relationships are not formed if the neighbor resides in a different EIGRP autonomous system or if the metric-calculation mechanism constants (the K values) are misaligned on that link. (K values are discussed in the “EIGRP Metric Calculation” section, later in this chapter.)
Neighbor Table Contents
An EIGRP router multicasts hello packets to discover neighbors. It forms an adjacency with these neighbors so that it can exchange route updates. Only adjacent routers exchange routing information. Each router builds a neighbor table from the hello packets it receives from adjacent EIGRP routers running the same network layer protocol. EIGRP maintains a neighbor table for each configured network-layer protocol. You can display the IP neighbor table with the show ip eigrp neighbors command, as shown in Example 2-1.
Example 2-1: Sample Output for the show ip eigrp neighbors Command
IP-EIGRP neighbors for process 100
H Address Interface Hold Uptime SRTT RTO Q Seq
(sec) (ms) Cnt Num
0 192.168.1.102 Se0/0/1 10 00:07:22 10 2280 0 5
R1#
This neighbor table includes the following key elements:
- H (handle)— A number used internally by the Cisco IOS to track a neighbor. This column lists the order in which a peering session was established with the specified neighbor, starting with 0.
- Interface— The interface on this router through which it is receiving hello packets for the neighbor, and therefore through which the neighbor can be reached.
- Hold Time— The maximum time, in seconds, that the router waits to hear from the neighbor without receiving anything from a neighbor before considering the link unavailable. Originally, the expected packet was a hello packet, but in current Cisco IOS software releases, any EIGRP packets received after the first hello from that neighbor resets the timer.
- Uptime— The elapsed time, in hours, minutes, and seconds since the local router first heard from this neighbor.
- Smooth Round Trip Timer (SRTT)— The average number of milliseconds it takes for an EIGRP packet to be sent to this neighbor and for the local router to receive an acknowledgment of that packet. This timer is used to determine the retransmit interval, also known as the retransmit timeout (RTO).
- RTO— The amount of time, in milliseconds, that the router waits for an acknowledgment before retransmitting a reliable packet from the retransmission queue to a neighbor.
- Queue (Q) count— The number of EIGRP packets (update, query, and reply) waiting in the queue to be sent out. If this value is constantly higher than 0, a congestion problem might exist. A 0 indicates that no EIGRP packets are in the queue.
- Seq Num— The sequence number of the last update, query, or reply packet that was received from this neighbor.
EIGRP Reliability
EIGRP’s reliability mechanism ensures delivery of critical route information to neighboring routers. This information is required to allow EIGRP to maintain a loop-free topology. For efficiency, only certain EIGRP packets are transmitted reliably.
All packets carrying routing information (update, query, and reply) are sent reliably (because they are not sent periodically). A sequence number is assigned to each reliable packet and an explicit acknowledgment is required for that sequence number.
Recall that RTP is responsible for guaranteed, ordered delivery of EIGRP packets to all neighbors. RTP supports an intermixed transmission of multicast and unicast packets.
RTP ensures that ongoing communication is maintained between neighboring routers. As such, a retransmission list is maintained for each neighbor. This list indicates packets not yet acknowledged by a neighbor within the RTO. It is used to track all the reliable packets that were sent but not acknowledged.
If the RTO expires before an ACK packet is received, the EIGRP process retransmits another copy of the reliable packet, up to a maximum of 16 times or until the hold time expires.
The use of reliable multicast packets is efficient. However, a potential delay exists on multiaccess media where multiple neighbors reside. The next reliable multicast packet cannot be transmitted until all peers have acknowledged the previous multicast. If one or more peers are slow to respond, this adversely affects all peers by delaying the next transmission. RTP is designed to handle such exceptions: Neighbors that are slow to respond to multicasts have the unacknowledged multicast packets retransmitted as unicasts. This allows the reliable multicast operation to proceed without delaying communication with other peers, helping to ensure that convergence time remains low in the presence of variable-speed links.
The multicast flow timer (seen in the show ip eigrp interfaces command output) determines how long to wait for an ACK packet before switching from multicast to unicast. The RTO determines how long to wait between the subsequent unicasts. The EIGRP process for each neighbor calculates both the multicast flow timer and RTO, based on the SRTT. The formulas for the SRTT, RTO, and multicast flow timer are Cisco-proprietary.
In a steady-state network where no routes are flapping, EIGRP waits the specified hold-time interval before it determines that an EIGRP neighbor adjacency is down. Therefore, by default, EIGRP waits up to 15 seconds on high-speed links and up to 180 seconds on slower WAN links. When EIGRP determines that a neighbor is down and the router cannot reestablish the adjacency, the routing table removes all networks that could be reached through that neighbor. The router attempts to find alternative routes to those networks so that convergence can occur.
The 180-second hold time on low-speed links can seem excessive, but it accommodates the slowest-speed links, which are generally connected to less-critical remote sites. In some networks with mission-critical or time-sensitive applications (such as IP telephony), even on high-speed links, 15 seconds is too long. The point to remember is that other conditions can override the hold time and allow the network to converge quickly. For example, if the network is unstable and routes are flapping elsewhere because a remote site is timing out on its adjacency, EIGRP hold timers begin counting down from 180 seconds. When the upstream site sends the remote site an update, and the remote site does not acknowledge the update, the upstream site attempts 16 times to retransmit the update. The retransmission occurs each time the RTO expires. After 16 retries, the router resets the neighbor relationship. This causes the network to converge faster than waiting for the hold time to expire.
Initial Route Discovery
EIGRP combines the process of discovering neighbors and learning routes. Figure 2-4 illustrates the initial route discovery process.
The following describes the initial route discovery process:
- A new router (Router A in Figure 2-4) comes up on the link and sends out a hello packet through all of its EIGRP-configured interfaces.
- Routers receiving the hello packet on an interface (Router B in Figure 2-4) reply with update packets that contain all the routes they have in their routing table, except those learned through that interface (because of the split horizon rule). Router B sends an update packet to Router A, but a neighbor relationship is not established until Router B sends a hello packet to Router A. The update packet from Router B has the initial bit set, indicating that this is the initialization process. The update packet contains information about the routes that the neighbor (Router B) is aware of, including the metric that the neighbor is advertising for each destination.
- After both routers have exchanged hellos and the neighbor adjacency is established, Router A replies to Router B with an ACK packet, indicating that it received the update information.
- Router A inserts the update packet information in its topology table. The topology table includes all destinations advertised by neighboring (adjacent) routers. It is organized so that each destination is listed, along with all the neighbors that can get to the destination and their associated metrics.
- Router A then sends an update packet to Router B.
- Upon receiving the update packet, Router B sends an ACK packet to Router A.
After Router A and Router B successfully receive the update packets from each other, they are ready to chose the successor (best) and FS (backup) routes in the topology table, and offer the successor routes to the routing table.
Split horizon controls the sending of IP EIGRP update and query packets. When split horizon is enabled on an interface, no update or query packets for destinations for which this interface is the next hop are sent out of this interface. This reduces the possibility of routing loops. By default, EIGRP split horizon is enabled on most interfaces. (The “EIGRP over Frame Relay and on a Physical Interface” section notes an exception.)
Split horizon blocks information about a destination from being advertised by a router out of any interface that the router uses to route to that destination. This behavior usually optimizes communications among multiple routers, particularly when links are broken.
When a router changes its topology table in such a way that the interface through which the router reaches a network changes, it turns off split horizon and poison reverses the old route out of all interfaces, indicating that the route is unreachable. This ensures that other routers will not try to use the now-invalid route.
DUAL
Diffusing Update Algorithm (DUAL) is the finite-state machine that selects which information is stored in the topology and routing tables. As such, DUAL embodies the decision process for all EIGRP route computations. It tracks all routes advertised by all neighbors, uses the metric to select an efficient and loop-free path to each destination, and inserts that choice in the routing table.
Advertised Distance and Feasible Distance
The AD is the EIGRP metric for an EIGRP neighbor router to reach a particular network. This is the metric between the next-hop neighbor router and the destination network.
The FD is the EIGRP metric for this router to reach a particular network. This is the sum of the AD for the particular network learned from an EIGRP neighbor, plus the EIGRP metric to reach that neighbor (the metric between this router and the next-hop router).
A router compares all FDs to reach a specific network in its topology table. The route with the lowest FD is offered to its IP routing table. This is the successor route. The FD for the chosen route becomes the EIGRP routing metric to reach that network in the routing table.
For example, in Figure 2-5, Routers A and B send their routing tables to Router C, whose tables are shown in the figure. Both Routers A and B have paths to network 10.1.1.0/24 (among many others that are not shown).
The routing table on Router A has an EIGRP metric of 1000 for 10.1.1.0/24. Therefore, Router A advertises 10.1.1.0/24 to Router C with a metric of 1000. Router C places the 10.1.1.0/24 network from Router A in its EIGRP topology table with an AD of 1000. Router B has network 10.1.1.0/24 with a metric of 1500 in its IP routing table. Therefore, Router B advertises 10.1.1.0/24 to Router C with an AD of 1500. Router C places the 10.1.1.0/24 network from Router B in the EIGRP topology table with an AD of 1500.
Router C in Figure 2-5 has two entries to reach 10.1.1.0/24 in its topology table. The EIGRP metric for Router C to reach either Router A or B is 1000. This cost (1000) is added to the respective AD from each router, and the results represent the FDs that Router C must travel to reach network 10.1.1.0/24. Router C chooses the least-cost FD (in this case 2000, via Router A) and installs it in its IP routing table as the best route to reach 10.1.1.0/24. The EIGRP metric in the routing table is the best FD from the EIGRP topology table. In this case Router C’s routing table shows the route to 10.1.1.0/24 is via Router A with a metric of 2000.
Successor and Feasible Successor
A successor, also called a current successor, is a neighboring router used for packet forwarding that has a least-cost path to a destination that is guaranteed not to be part of a routing loop.
The FD, not the AD, affects the selection of the best routes for incorporation in the routing table. The AD is used only to calculate the FD. A router is chosen as a successor because it has the lowest FD of all possible paths to that destination network. The successor is the next router in line to reach that destination—it is the next-hop router in the best path to reach that destination network.
An EIGRP router selects the best path to reach a given network and then installs the destination network, the metric to reach that network, the outbound interface to reach the next-hop router, and the IP address of the next-hop router into the IP routing table. If the EIGRP topology table has many entries that have an equal-cost FD to a given destination network, all successors (up to four by default) for that destination network are installed in the routing table.
All IP routing protocols can install only the next-hop router information in the routing table. Information about the subsequent routers in the path is not put in the routing table. Each router relies on the next-hop router to make a reliable decision to reach a specific destination network. The hop-by-hop path through a network goes from one router to the next. Each router makes a path selection to reach a given network and installs the best next-hop address along the path to reach that destination network. A router trusts a route’s successor (the best next-hop router) to send traffic toward that destination address.
The routing table is essentially a subset of the topology table. The topology table contains more detailed information about each route, any backup routes, and information used exclusively by DUAL.
An FS is a router providing a backup route. The route through the FS must be loop free. In other words, it must not loop back to the current successor. FSs are selected at the same time the successors are identified. These FS routes are kept in the topology table. The topology table can retain multiple FS routes for a destination.
An FS must be mathematically proven. To qualify as an FS, a next-hop router must have an AD less than the FD of the current successor route for the particular network. This is known as the feasibility condition. This requirement ensures that the FS cannot use a route through the local router (which would be a routing loop), because the AD through the FS is less than the best route through the local router. For example, as shown in Router C’s topology table in Figure 2-6 (for the network shown earlier in Figure 2-5), Router B is an FS, because the AD through Router B (1500) is less than the FD of the current successor, Router A (2000).
Figure 2-6: Router C’s Topology Table: Feasible Successor’s AD Must Be Less Than the Successor’s FD. When a router loses a route, it looks at the topology table for an FS. If one is available, the route does not go into an active state. Instead, the best FS is promoted as the successor and is installed in the routing table. The FS can be used immediately, without any recalculation. If there are no FSs, a route goes into active state, and route computation occurs. Through this process, a new successor is determined (if there is one). The amount of time it takes to recalculate the route affects the convergence time.
Figure 2-7 illustrates another example. Router C’s initial topology table is shown at the top of the figure. Router B is the successor for network 10.1.1.0/24, and Router D is the FS.
In Figure 2-7, the link between Router B and Router C fails. Router C removes the route 10.1.1.0/24 through Router B from its routing table and searches the EIGRP topology table for an FS; Router D is an FS. Because Router D can still reach the network and does not send an update or query packet to inform Router C of the lost route, Router C immediately uses the path through Router D. Router C chose this path as an FS because the AD through Router D (1500) is less than the FD of the best route, through Router B (2000). This path is guaranteed to be loop free.
Figure 2-8 illustrates another scenario that shows how DUAL ensures a loop-free network. Router B sends the routing update about network 10.0.0.0/8, with an AD of 30. Router A receives the update, calculates the FD value (130), and sends an update to both of its neighbors, routers C and D. Routers A, C, and D are in a loop. The update sent to Router C is sent on to Router D, which then sends it to Router A. The AD of the route that Router D sends to Router A is 330. This AD value is higher than the FD (130) on Router A, calculated from the original update received from Router B. Because the FD of the route on Router A is smaller than the AD of the update coming from Router D, the route via Router D does not become an FS. Thus, DUAL ensures there will be no routing loop in the network.
DUAL Example
The mathematical formula to ensure that the FS is loop free requires that the AD of the backup route be less than the FD of the successor. When the AD of the second-best route is greater than or equal to the FD of the successor, an FS cannot be chosen. In this case, a discovery process that uses EIGRP queries and replies must be used to find any alternative paths to the lost networks.
The following example examines partial entries for network 10.1.1.0/24 in the topology tables for Routers C, D, and E in Figure 2-9, to give you a better understanding of EIGRP behavior. The partial topology tables shown in Figure 2-9 indicate the following:
- AD— The advertised distance is equal to the cost of the path to network 10.1.1.0/24 as advertised by neighboring routers. For example, consider Router E’s neighbors: Router D has an AD of 2 and Router C has an AD of 3, for 10.1.1.0/24.
- FD— The feasible distance is equal to the sum of the AD for a neighbor to reach 10.1.1.0/24, plus the metric to reach that neighbor. For example, again consider Router E: The FD of the route to 10.1.1.0/24 via Router D is Router D’s AD (2) plus the metric to reach Router D from Router E (1), for a total of 3. The FD of the route to 10.1.1.0/24 via Router C is Router C’s AD (3) plus the metric to reach Router C from Router E (1), for a total of 4.
- Successor— The successor is the forwarding path used to reach network 10.1.1.0/24. The cost of this path is equal to the FD. For example, Router E chooses the path to 10.1.1.0/24 with the lowest FD, which is via Router D. This is the route that Router E puts in its routing table.
- FS— The feasible successor is an alternative loop-free path to reach network 10.1.1.0/24. For example, in Router C, the path via Router D is an FS because the AD (2) is less than the FD (3) via the successor Router B. Routers D and E do not have any FSs because the AD of the alternate routes are not less than the FD of their current successors.
The network shown in Figure 2-9 is stable and converged.
| Note |
|
In Figure 2-10, Routers B and D detect a link failure. In Router D, DUAL marks the path to network 10.1.1.0/24 through Router B as unusable after being notified of the link failure,
The following steps then occur, as shown in Figure 2-11:
- At Router D, there is no FS to network 10.1.1.0/24, because the AD via Router C (3) is greater than the FD via Router B (2). Therefore, DUAL does the following:
- Sets the metric to network 10.1.1.0/24 as unreachable (–1 is unreachable).
- Because an FS cannot be found in the topology table, the route changes from the passive state to the active state. In the active state, the router sends out queries to neighboring routers looking for a new successor.
- Sends a query to Routers C and E for an alternative path to network 10.1.1.0/24.
- Marks Routers C and E as having a query pending (q).
-
- At Router E, DUAL marks the path to network 10.1.1.0/24 through Router D as unusable.
- At Router C, DUAL marks the path to network 10.1.1.0/24 through Router D as unusable.
The following steps then occur, as shown in Figure 2-12:
- At Router D:
- DUAL receives a reply from Router C that indicates no change to the path to network 10.1.1.0/24.
- DUAL removes the query flag from Router C.
- DUAL stays active on network 10.1.1.0/24, awaiting a reply from Router E to its query (q).
-
- At Router E, there is no FS to network 10.1.1.0/24, because the AD from Router C (3) is not less than the original FD (also 3).
- At Router C, DUAL marks the path to network 10.1.1.0/24 through Router E as unusable.
The following steps then occur, as shown in Figure 2-13:
- At Router D, DUAL stays active on network 10.1.1.0/24, awaiting a reply from Router E (q).
- At Router E:
- DUAL receives a reply from Router C indicating no change.
- It removes the query flag from Router C.
- It calculates a new FD and installs a new successor route in the topology table.
- It changes the route to network 10.1.1.0/24 from active to passive (converged).
-
The following steps then occur, as shown in Figure 2-14 at Router D:
- DUAL receives a reply from Router E.
- It removes the query flag from Router E.
- It calculates a new FD.
- It installs new successor routes in the topology table. Two routes (through Routers C and E) have the same FD, and both are marked as successors.
- It changes the route to network 10.1.1.0/24 from active to passive (converged).
The following steps then occur, as shown in Figure 2-15:
- At Router D, two successor routes are in the topology table for network 10.1.1.0/24. Both successor routes are listed in the routing table, and equal-cost load balancing is in effect.
- The network is stable and converged.
Figure 2-9, the original topology before the link failure, shows traffic from Router E for 10.1.1.0/24 passing through Routers D and B. In Figure 2-15, the new topology shows traffic from Routers D and E for 10.1.1.0/24 going through Routers C and B. Notice that throughout the entire convergence process, routes to network 10.1.1.0/24 become active only on Routers D and E. The route to network 10.1.1.0/24 on Router C remains passive because the link failure between Routers B and D does not affect the successor route from Router C to network 10.1.1.0/24.
EIGRP Metric Calculation
DUAL selects routes based on the EIGRP composite metric. Five criteria are associated with the EIGRP composite metric, but EIGRP uses only two by default:
- Bandwidth— The smallest (slowest) bandwidth between the source and destination
- Delay— The cumulative interface delay along the path
The following criteria, although available, are not commonly used, because they typically result in frequent recalculation of the topology table:
- Reliability— The worst reliability between the source and destination, based on keepalives.
- Loading— The worst load on a link between the source and destination based on the packet rate and the interface’s configured bandwidth.
- Maximum transmission unit (MTU)— The smallest MTU in the path. (MTU is included in the EIGRP update but is actually not used in the metric calculation.)
EIGRP calculates the metric by adding together weighted values of different variables of the path to the network in question. The default constant weight values are K1 = K3 = 1, and K2 = K4 = K5 = 0.
In EIGRP metric calculations, when K5 is 0 (the default), variables (bandwidth, bandwidth divided by load, and delay) are weighted with the constants K1, K2, and K3. The following is the formula used:
- metric = (K1 * bandwidth) + [(K2 * bandwidth) / (256 − load)] + (K3 * delay)
If these K values are equal to their defaults, the formula becomes
- metric = (1 * bandwidth) + [(0 * bandwidth) / (256 − load)] + (1 * delay)
- metric = bandwidth + [0] + delay
- metric = bandwidth + delay
If K5 is not equal to 0, the following additional operation is performed:
K values are carried in EIGRP hello packets. Mismatched K values can cause a neighbor to be reset (even though only K1 and K3 are used, by default, in metric compilation). These K values should be modified only after careful planning; changing these values can prevent your network from converging and is generally not recommended.
It is important to note that the format of the delay and bandwidth values is different from those displayed by the show interfaces command, as follows:
- The EIGRP delay value is the sum of the delays in the path, in tens of microseconds, multiplied by 256. The show interfaces command displays delay in microseconds.
- The EIGRP bandwidth is calculated using the minimum bandwidth link along the path, represented in kilobits per second (kbps). 107 is divided by this value, and then the result is multiplied by 256.
EIGRP uses the same metric formula as IGRP did, but EIGRP represents its metrics in a 32-bit format rather than the 24-bit representation used by IGRP. This representation allows a more granular decision to be made when determining the successor and feasible successor.
The EIGRP metric value ranges from 1 to 4,294,967,296. (The IGRP metric value ranged from 1 to 16,777,216.) EIGRP metrics are backward compatible with IGRP, as illustrated in Figure 2-16. When integrating IGRP routes into an EIGRP domain using redistribution, the router multiplies the IGRP metric by 256 to compute the EIGRP-equivalent metric. When sending EIGRP routes to an IGRP routing domain, the router divides each EIGRP metric by 256 to achieve the proper 24-bit metric.
Figure 2-17 illustrates an example network used to illustrate the metric calculation. In this figure, Router A has two paths to reach Router D (and therefore any networks behind Router D). The bandwidths (in kbps) and the delays (in tens of microseconds) of the various links are also shown in the figure.
The least bandwidth along the top path (A —> B —> C —> D) is 64 kbps. The EIGRP bandwidth calculation for this path is as follows:
- bandwidth = (107 / least bandwidth in kbps) * 256
- bandwidth = (10,000,000 / 64) * 256 = 156,250 * 256 = 40,000,000
The delay through the top path is as follows:
- delay = [(delay A —> B) + (delay B —> C) + (delay C —> D)] * 256
- delay = [2000 + 2000 + 2000] * 256
- delay = 1,536,000
Therefore, the EIGRP metric calculation for the top path is as follows:
- metric = bandwidth + delay
- metric = 40,000,000 + 1,536,000
- metric = 41,536,000
The least bandwidth along the lower path (A —> X —> Y —> Z —> D) is 256 kbps. The EIGRP bandwidth calculation for this path is as follows:
- bandwidth = (107 / least bandwidth in kbps) * 256
- bandwidth = (10,000,000 / 256) * 256 = 10,000,000
The delay through the lower path is as follows:
- delay = [(delay A —> X) + (delay X —> Y) + (delay Y —> Z) + (delay Z —> D)] * 256
- delay = [2000 + 2000 + 2000 + 2000] * 256
- delay = 2,048,000
Therefore, the EIGRP metric calculation for the lower path is as follows:
Router A therefore chooses the lower path, with a metric of 12,048,000, over the top path, with a metric of 41,536,000. Router A installs the lower path with a next-hop router of X and a metric of 12,048,000 in the IP routing table.
The bottleneck along the top path, the 64-kbps link, can explain why the router takes the lower path. This slow link means that the rate of transfer to Router D would be at a maximum of 64 kbps. Along the lower path, the lowest speed is 256 kbps, making the throughput rate up to that speed. Therefore, the lower path represents a better choice, such as to move large files quickly.
This section concludes the discussion of EIGRP terminology and operation. The rest of the chapter explores planning, configuring, and verifying EIGRP implementation.
0 comments
Post a Comment