EIGRP Discovery, Selection, and Route Maintenance

Routers that are loaded with the EIGRP routing protocol use the Hello protocol packets for the neighbor discovery process. The router discovery process is a dynamic activity via the Hello protocol. The Hello packets are sent to the 224.0.0.10 multicast address to determine whether a neighbor is available. An adjacency relationship is a formal agreement between EIGRP neighbor devices established for the goal of exchanging routing information. When EIGRP routers receive Hello packets from a router in the same autonomous system, they will establish an adjacency (neighbor relationship). EIGRP adjacencies must occur within the same AS; therefore neighbor relationships will not form if the devices are in different ASs. In addition, EIGRP uses the primary, not secondary, address on interfaces to build its adjacencies. The actual time interval of Hello packets is dependent on the media being used. For example, on an ethernet, token ring, fiber distributed data interface (FDDI) LAN, and on faster WAN links, Hello packets are sent every 5 seconds. Hello packets are generated every 60 seconds, however, on slower links such as ISDN BRI and multipoint serial interfaces.

Neighbor Table

The information that is learned from the contents of the Hello packets are subsequently stored in the neighbor table. EIGRP, like OSPF, uses multicast Hellos for neighbor discovery and route update trades. This table is responsible for maintaining the EIGRP holdtime value. The holdtime value is measured in seconds and represents the amount of time that a router waits to hear from a neighbor before declaring it "down." When you execute the show ip eigrp neighbors command, as shown in Listing 7.1, the holdtime value in the output determines a neighbor's availability. When a neighbor is affirmed as dead, the neighbor relationship is reset and any routes for which this neighbor is responsible are dropped from the table. If the dead neighbor becomes available again, the EIGRP routers exchange Hello packets and reestablish the neighbor relationship. The default EIGRP holdtime is three times the Hello interval. This results in a default holdtime of 15 seconds for LAN and faster WAN interfaces and 180 seconds (3 minutes) on slow WAN links. The holdtime value can be manually configured on a per-interface basis using the following command:

 RouterA(config-if)#  ip hold-time eigrp   autonomous-system-number seconds  

Listing 7.1 Sample Output from a show ip eigrp neighbors Command Showing Holdtime Values

 RouterA# show ip eigrp neighbors IP-EIGRP Neighbors for process 20 Address          Interface    Holdtime    Uptime    Q      Seq      SRTT                               (secs)      (h:m:s)   Count  Num      (ms)  10.10.10.1       Ethernet1    9           0:00:33   0      13        6 10.10.20.2       Serial0      16          0:00:07   0      10        11 10.10.30.3       Ethernet0    12          0:00:09   0       6        3 

In the previous neighbor table in Listing 7.1, the Address field shows the IP address of the EIGRP neighbor and the Interface field displays the interface on RouterA by which the neighbor can be reached. The Holdtime field is the maximum amount of time that the router will wait without receiving anything ”not just a Hello packet ”from this neighbor before regarding it as down. If it receives any subsequent packets, it resets this timer. Uptime is the elapsed time, in hours, minutes, and seconds, since the router first heard something from this neighbor. The field designated simply as Q refers to the queue count. The queue count is the number of packets sitting in the queue and waiting to be sent. A value greater than 0, on a regular basis, indicates a possible congestion issue.

The next field in the neighbor table is the sequence number of the last update, reply, or query that was obtained from this particular neighbor.

Smooth round trip time (SRTT) is the elapsed time, expressed in milliseconds , between the time that the local router sent its last update packet and when the acknowledgement was received from its neighbor. The router also uses the SRTT value to calculate the retransmission timeout (RTO) value. RTO is the length of time, expressed in milliseconds, that the router will wait between sending update packets to its neighbor. The exact order and format of these fields in the neighbor table may differ depending on the router model and IOS version, but the stored information is basically consistent.

Two EIGRP routers that have different Hello and holdtime values can still establish a neighbor relationship. However, if you modify the Hello interval on an individual router you must also manually configure the holdtime value to mirror the change. Setting these values independently may cause topology discrepancies. If a packet is not received before the hold time value expires , a topology change is detected and the neighbor adjacency can be dropped, affecting all the topology table entries learned from that particular neighbor.

Topology Table

EIGRP routers actually have three tables for each routable protocol that is configured on the router. We have just looked at the neighbor table, which catalogs the adjacent routers that are configured for EIGRP. When an EIGRP router discovers a new neighbor, it transmits an update to this neighbor and eventually obtains an update from this same neighbor. This information is used to construct an entity known as the topology table. The topology table stores all the learned routes to a destination. The third type of table, with which you are familiar, is the routing table, which keeps a record of the optimal routes to all destinations. These three tables are maintained separately for each protocol. Because EIGRP can support the IP, IPX, and AppleTalk routed protocols, an EIGRP router can maintain up to nine separate tables. In our scenario, the router maintains three tables: a neighbor table, a topology table, and a routing table for the IP protocol that is configured.

The topology table contains all the routes that it has gathered from neighboring routers, including the feasible distance to each destination network and the route status. The feasible distance (FD) is the lowest cost route to a particular destination. EIGRP uses bandwidth, delay, reliability, load, and Maximum Transmission Unit (MTU) as its metrics in determining the best path to a remote network. The metric that the router ultimately uses will be the sum of the best metric advertised by all the neighbors and the cost to reach the best neighbor router. Whenever a change takes place to a connected link or interface, or a peer advertises a change, the topology table is updated. The topology table also indicates whether the entry is static or passive. A route is passive if the router is not performing any recomputations on that route. The route is active, on the other hand, if recomputation activities are underway for that route entry.

The show ip eigrp topology EXEC -mode command is used to display the output shown in Listing 7.2.

Listing 7.2 Sample Output from a show ip eigrp topology Command

 RouterA# show ip eigrp topology IP-EIGRP Topology Table for process 20 Codes: P  Passive, A  Active, U  Update, Q  Query, R  Reply,        r  Reply status P 172.16.4.0/24, 1 successors, FD is 44132954            via 10.1.1.1 (44132954/43620954), Serial0/0 P 172.16.2.0/24, 1 successors, FD is 22910732            via 10.1.1.1 (22910732/20198510), Serial0/0 P 172.16.1.0/24, 1 successors, FD is 10797519            via Connected, Seial0/0 

In Table 7.2, you can observe the various contents of the EIGRP topology table or database.

Table 7.2. Contents of EIGRP Topology Table

Topology Table Item	Description
Codes:	The state or condition of this topology table entry.
P	Passive. No EIGRP calculations are being performed for this destination.
A	Active. EIGRP calculations are being performed for this destination.
U	Update. An update packet was sent to this destination.
Q	Query. A query packet was sent to this destination.
R	Reply. A reply packet was sent to this destination.
R	A reply status flag that indicates that the process has sent a query and is waiting for a reply packet.
172.16.4.0/24	The destination IP network and subnet mask.
Successors	The number of successors.
FD	The total distance from the local router to the destination network. The feasible distance used in a feasibility condition check.
Replies	The number of outstanding reply packets for this destination while in the active state.
State	The precise state in which the destination is presently.
Via	The IP address of the neighbor that tells the process about this destination.
(44132954/43620954)	The first number represents the EIGRP metric for cost to destination. The second is the EIGRP metric that this neighbor advertises.
Serial0/0	The interface from which this information was derived.

An EIGRP router extracts the best, or successor , routes to each destination network from the topology table and lists them in its routing table. The successor is the primary route from the topology table that is placed into the routing table because it has the best attributes for the particular destination. All successors are stored in the routing table. If you want to see all the IP entries in the topology table, you can issue the following command from the EXEC-mode prompt:

 RouterA# show ip eigrp topology all-links 

Routing Table

Like the topology table and the neighbor table, a separate routing table is maintained for each supported routable protocol. The routing table is basically a subset of the topology table, and the DUAL is the component that decides which information will be stored in the topology table. It enforces the decision-making process for all the routing calculations and traces routes advertised by EIGRP peers. The DUAL propagates the routing table by using the metric to determine the best loop-free path to every destination in the network. As mentioned earlier, the lowest cost route ends up being the cost between the local router and the next-hop router plus the advertised distance. Advertised distance is defined as the cost between the next-hop router and the destination. The resulting sum of these two distances is the FD. A successor, as defined in Table 7.1, is a neighboring EIGRP router that meets the requirements for forwarding packets because it has a loop-free least-cost path to a destination (feasibility). DUAL uses the detailed information from the topology table and ultimately adds all the successors to the routing table.

A next-hop router (or routers) that serves as a backup path is known as the feasible successor (FS). If a route is lost to a destination, the router looks in the topology table, not the routing table, for an FS. To qualify as an FS, a next-hop router must have an advertised distance less than the feasible distance of the current successor route, and you can have more than one feasible successor. If one is found, this FS is made the successor and injected into the routing table. If no feasible successors are found, then the router goes into active state and starts the process of calculating a new route topology. This process of recalculation has an effect on the overall convergence time. The show ip route command is used to view the EIGRP routing table.

EIGRP Discovery Process

When an EIGRP router, RouterA, comes up for the first time, it initializes and transmits a Hello packet out all its interfaces. As shown in Figure 7.1, RouterB receives the Hello packet from RouterA and responds with update packets that contain information about all routes in its routing table (metrics are also included). Because EIGRP uses the split horizon rule, it does not send information that it may have previously learned via that interface. This update packet from RouterB actually creates the neighbor relationship between the two routers. Returning to Figure 7.1, you can see that RouterA replies with an ACK packet and inserts the new information in its topology table. Next, RouterA shares this new information with its other neighbors in the form of an update message. Each router, in turn , acknowledges RouterA's update information. After all the information is added to all the router's topology tables, they can begin to select the routes to be added to the routing tables.

Figure 7.1. The initial EIGRP route discovery process.

The topology table contains all the destinations learned from the adjacent routers, along with a listing of all the neighbors that can get to the particular destination. After all the updates have been exchanged and acknowledged , the router can select the primary (successor) route and backup (feasible successor) routes to store in the topology database.

Table 7.3 lists the five different EIGRP packets that have been discussed and a brief description of each.

Table 7.3. The Types of EIGRP Packets in Their Respective Order During the Discovery and Selection Process

Packet Type	Description
Hello	A multicast packet used for neighbor discovery.
Update	A packet sent reliably to communicate routes used for convergence purposes. This packet is sent via multicast when new routes are discovered and if the route is passive when the convergence process is complete. Updates are sent as unicast packets during the EIGRP initial startup process to synchronize the topology database.
ACK	A unicast packet used for acknowledging EIGRP queries, replies, and updates.
Query	A reliable multicast packet sent when a router, performing computations , cannot find a feasible successor. This packet is sent to a neighbor looking for a feasible successor.
Reply	A unicast packet sent in response to a query.

EIGRP Selection Process

The characteristics surrounding EIGRP route selection are unique to this hybrid routing protocol. EIGRP chooses up to six routes (one primary [successor] and up to five backup [FD]) per destination and places them into the topology table, which is eventually moved into the routing table. Similar to OSPF, EIGRP also supports internal, external, and summary routes.

The EIGRP metric is fundamentally the same as IGRP except that it is multiplied by 256. Like IGRP, EIGRP uses the following five variables to compute the metric:

• Bandwidth ” A value represented as the smallest bandwidth between the source and destination

• Delay ” The collective delay of interfaces along the path

• Reliability ” The lowest (worst) reliability along the network path (see the "Reliability" sidebar)

• Load ” Represented by the worst load on a connection between the source and destination, in bps

• MTU ” The smallest maximum transmission unit value in the path

Reliability

The EIGRP reliability variable supplies crucial information to neighbor routers to help maintain a consistent loop-free topology. EIGRP uses a sequence number to facilitate this process by requiring an acknowledgement for a specific sequence number. The component that is responsible for this orderly delivery is the Reliable Transport Protocol (RTP). EIGRP update packets are an example of a message that demands a reliable acknowledgement, and RTP makes sure that communication channels are maintained between peers. RTP keeps a retransmission list on the EIGRP router for each neighbor that lists the packets that have not yet been acknowledged by a neighbor. Reliable packets that are not acknowledged can be retransmitted up to 16 times or up to the holdtime, whichever is longer.

EIGRP adds the weighted values (K) of different link variables together to derive the metric. These K values are stored and transported in Hello packets throughout the network. By default, only bandwidth (K1) and delay (K3) are used to compute the metric value, as shown in the following mathematical operation. It is not recommended that you modify these values.

The values of the default constants are as follows :

K1 = K3 = 1

And

K2 = K4 = K5 = 0

The weights that are attributed to the variables are as follows:

• K1 = bandwidth

• K2 = load

• K3 = delay

• K4 = reliability

• K5 = MTU

When K5 = 0 during metric calculation, variables will be weighted according to the constants K1, K2, and K3 with the following formula:

Metric=(K1 x bandwidth)+[(K2 x bandwidth) ·(256 “load)]+K3xdelay

If these constant values are the same as their defaults, the formula will be:

Metric=1xbandwidth+[(0xbandwidth) ·(256 “load)]+1xdelay

Which evaluates to

Metric=bandwidth+[0]+delay

Which evaluates to

Metric=bandwidth+delay

The bandwidth value is computed by taking the minimum bandwidth link on the path divided into 10 ⁷ and multiplied by 256. If K5 does not equal 0, you must perform this extra operation:

Metric=Metricx[K5 ·(reliability+K4)]

When you are injecting IGRP routes into your routing domain, you simply multiply the IGRP metric by 256 to get the equivalent EIGRP metric.

The EIGRP topology table subsequently stores all routes that have been learned by the router via the EIGRP routing updates. The topology table contains information such as the status of the routes, the number of successors to a destination network, and the FD to destination networks, as well as the IP address or interface number of the successor. Feasible distance is the router's best-calculated distance metric, or lowest-cost route, to a destination network. A successor is simply the best path to a route, and the successor route is the only route that is stored in both the topology database and the EIGRP routing table. EIGRP can store a total of six redundant routes in the topology table. The five backup routes are known as feasible successors.

Information regarding the router that is the best route for a particular destination, the successor, is maintained in the routing table. Backup routers, or feasible successors, are those routers that can be used to reach a specific destination, but do not represent the least-cost path to that destination. For instance, assume that a router has an established feasible distance value to a destination network 172.16.4.0 in its topology table. A newly advertised route by a neighbor has a lower advertised distance to network 172.16.4.0. Because the neighbor's advertised distance value is less than the router's FD to network 172.21.4.0, the new route becomes a feasible successor route and is stored only in the topology table. If the router holding the current successor route were to become unavailable, then the feasible successor with the next-lowest advertised distance would become the new successor route and would be added to the routing table.

A sample topology database table is shown in Listing 7.3.

Listing 7.3 A Sample Topology Database Table

 RouterA# show ip eigrp topology IP-EIGRP Topology Table for process 100 Codes: P  Passive, A  Active, U  Update, Q  Query, R  Reply,        r  Reply status P 172.16.4.0/24, 1 successors, FD is 44132954  via 10.1.1.1 (44132954/43620954), Serial0/0  P 172.16.2.0/24, 1 successors, FD is 22910732            via 10.1.1.1 (22910732/20198510), Serial0/0 P 172.16.1.0/24, 1 successors, FD is 10797519            via Connected, Seial0/0 

The first number that is displayed in brackets for each successor refers to the local router's distance metric to that destination network. The second number between the brackets designates the advertised distance. The advertised distance value is the next-hop routers reported or "advertised" distance metric to the destination network. Every time a route is newly advertised, the local EIGRP router conducts a feasibility check. If the neighbor router's advertised distance value is less than the local router's feasible distance to a destination network, the path will be selected as a feasible successor route. It is subsequently stored in the topology table as a backup route. Information about available feasible successors is kept in the topology table.

An EIGRP route is considered to be in a passive state when the router has a valid successor for that route and is not in the process of querying neighbors for any alternate paths. The term "query" refers to an EIGRP message that is sent to discover the status of network routes. If a route suddenly becomes unavailable because the successor route is no longer accessible via the local router's topology table, the router quickly queries other neighbors in an attempt to find another feasible successor for that route. During this time, the router recalculates in a state known as active mode.

Look back at Figure 7.1 and review the EIGRP process again with this new knowledge. When EIGRP RouterB receives an initial multicast Hello packet from RouterA, it sends unicast update packets that contain the contents of its routing table. Unlike OSPF routers, connected EIGRP routers establish a neighbor relationship (adjacency) after their initial exchange of Hello and update packets. After receiving the routing table contents from RouterA, RouterB acknowledges delivery by sending an ACK packet to RouterA. The process then reverses, with RouterB sending RouterA update packets that contain RouterB's routing table information, and RouterA returning an ACK packet to RouterB. When both routers have incorporated their neighbors' routing information, they select successor and feasible successor routes and inject them into their topology tables. Reply packets are reliable unicast packets that are sent by a router that has received query packets from an active state or stuck in active (SIA) state router (we will look at the SIA state in a moment) that is querying for an alternative network route.