EIGRP Theory - 2. Continued

Computed, Reported, and Feasible Distances, and Feasibility Condition

The number after the slash sign is called the Reported Distance(RD) and corresponds to the current best distance of the particular neighbor to the destination. In other words, the RD is the neighbor’s distance to the destination as reported in an EIGRP packet received from that neighbor. RD is also called an Advertised Distance. If all other metrics are equal, RD values corresponds to the delay value multiplied by 256.

The number in parentheses before the slash sign is called the  Computed Distance(CD) and shows the total metric of reaching the destination over the particular neighbor.

EIGRP also maintains a record of yet another distance for each destination: the Feasible Distance(FD) which is a record of the lowest known distance since the last transition from the Active to Passive state. FD is not necessarily equal to the current best CD to a destination. In the Passive state, after the FD has been initialized, it can only decrease(if the current best CD happens to fall below the current value of FD) or remain at its current value(if the current best CD
rises but the route remains Passive). There is exactly one FD per each destination, regardless of the number of neighbors.

When a route advertise its distance to the network, it would advertise its actual distance instead of FD. FD is an internal value that is used by EIGRP to select loop-free paths, but its value is never advertised in any EIGRP packets.

Feasibility Condition-any neighbor that is closer to the destination than this router has been since the last time the destination became Passive cannot form a routing loop, or more technically, any neighbor whose Reported Distance is strictly smaller than this router’s Feasible Distance cannot form a routing loop .

If a neighbor’s RD is equal to or higher than R1’s FD, it might or might not cause a routing loop. However, it is certain and guaranteed that if a neighbor’s RD is lower than R1’s FD(that is, if the neighbor is closer to  the destination than R1 has ever been since the last time the destination became Passive), it will not cause a routing loop.

For a destination, all neighbors that pass the FC and thus are safe to use as next hops are called  Feasible Successors . In other words, a Feasible Successor is a neighbor that is guaranteed to provide a loop-free path toward a destination; Feasible Successors are identified by passing the FC check. Among these Feasible Successors, one or more provide the least CD to the destination; these are called Successors.
All Successors and Feasible Successors to a destination can be seen in the show ip eigrp topology output. Neighbors that do not meet the FC are not displayed in this output; to display them as well, the show ip eigrp topology all-links command must be used.

Local and Diffusing Computations in EIGRP  

A topology change occurs whenever the distance to a network changes or a new neighbor comes online that advertises the network. The event of a neighbor going down is processed by setting the CD/RD of all networks reachable through that neighbor to infinity.Then, the router can immediately verify in its topology table whether there is a feasible successor. If there is, the router performs the following steps:
   1. The Feasible Successor providing the least CD is made the new Successor.
   2. If the CD over the new Successor is less than the current FD, the FD will be updated to the new CD; otherwise it stays at its current value.
   3. The routing table is updated to point toward the new Successor.
   4. If the current distance to the destination has changed as a result of switching to a new Successor, an Update packet is sent to all neighbors, advertising the router’s updated distance to the destination.  
This action is called a  local computation  in EIGRP, performed solely by using information already stored in the router’s topology table, without needing to coordinate with the neighboring routers. Throughout this procedure, the route has remained in the Passive state.

If, however, after detecting a topology change, the router finds out that the new shortest path is provided by a neighbor that is not a Feasible Successor, the router commences a diffusing computation by performing the following steps:
  1. The entry in the routing table, still pointing to the current unchanged Successor, is locked: It must not be removed nor its next hop changed until the diffusing computation is finished and the route has been moved to the Passive state again.
  2. The FD is set to the current (possibly increased) CD through the current unchanged Successor.
  3. The network is put into the Active state and the router sends out a Query packet to all its neighbors. This Query packet contains the Active network’s prefix and the router’s current CD toward it.  

Two possibilities now exist: Either the neighbor still has its own Feasible Successor or a Successor that provides it with the least-cost loop-free path, or none of its own neighbors that offer the shortest path are a Feasible Successor. In the first case, when the neighbor still has a Successor, it will simply send back a Reply packet, indicating the neighbor’s current distance to the destination. The neighbor did not become engaged in the diffusing computation as it did not need to put the network into the Active state itself.

In the second case, the neighbor will itself join the diffusing computation, send out its own Query packet, and advertise its own current distance through its current Successor. As a result, the wave of Query messages propagates through the part of the network that is affected by the change. Other parts of the network that are not affected will not engage in the diffusing computation. Only after all Reply packets are received, the router can put the route back to the Passive state, simply choose the neighbor offering the shortest path available while skipping the FC check, and reinitialize the FD to the CD offered by the selected neighbor. Now the routing table entry can finally be updated. If this router itself became Active by receiving a Query, it now starts sending its own Reply and possibly Update packets, as only now its own distance to the destination has been determined; otherwise, the router sends out Update packets only.

The crucial information carried in Update, Query, Reply, SIA-Query, and SIA-Reply packets is always simply the sender’s current distance to a particular destination.

It is believed that if the current Successor fails, a Feasible Successor(if one exists) will always be promoted to the Successor role. This statement is not entirely correct, however. What really happens in EIGRP is 

  - Whenever EIGRP detects a topology change, it first records the change into the topology table and updates the RD and CD of the neighbor that advertised the change (in case of a received EIGRP message) or was influenced by it (in case of a link metric change).   

  - From among all neighbors that advertise the network, EIGRP identifies the one that provides the least CD, taking into account the updated CDs.

  - Only after identifying the neighbor offering the least CD, EIGRP verifies whether this neighbor meets the FC and is therefore a Feasible Successor. If it is, EIGRP will promote it to the Successor and start using it right away.

In other words, EIGRP—just like any other routing protocol—always tries to choose the shortest path toward a destination, but before using it, EIGRP verifies whether it meets the FC to be loop-free.

debug eigrp fsm is used to display EIGRP's DUAL FSM actions.

DUAL FSM  

EIGRP uses a control mechanism called the Diffusing Update Algorithm, or DUAL, that takes care of handling multiple topology changes occurring during a single diffusing computation. 

Stuck-In-Active State

If a router joins the diffusing computation for a particular destination by putting it into the Active state and sending out Queries, it must first wait for all its neighbors to send back a Reply before it can conclude the diffusing computation itself, make a new best-path selection, and start sending its own Replies. A router in the Active state is dependent on the entire chained sequence of routers that have become Active as a result of this router’s Query. Any single misbehaving router up this chain that is unable to send a Reply for whatever reason will cause all the routers depend-

ing on it to stall, possibly never being allowed to conclude the diffusing computation and converge.  

Common reasons why the EIGRP neighbor router(s) might not respond to the Query are 

 - The neighbor router’s CPU is overloaded and the router either cannot respond in time or is even unable to process all

Quality issues on the link are causing packets to be lost.   

 - links are congested and packets are being delayed or dropped.   

 - The network topology is excessively large or complex.

EIGRP implements multiple mechanisms to cope with this situation.

When a Query is first sent out by a router, a timer called the Active timer for the route is started. Default is 3 minutes. If all expected Replies are not received before the Active timer expires, the route in question will be designated as Stuck-In-Active (SIA). The neighbor or neighbors that did not reply will be removed from the neighbor table and their adjacencies torn down, and the diffusing computation will consider these neighbors to have responded with an infinite metric. SIA states in EIGRP are extremely unpleasant and generally difficult to diagnose.

Dropping an adjacency to a neighbor as a consequence of the SIA state can introduce further instability to the network, as all networks learned from that neighbor will be flushed and possibly learned again after the neighbor comes back up within the Hello interval time.  

If a neighbor does not respond to a Query message with its Reply within half of the Active timer time, the router will send the neighbor a SIA-Query message. The SIA-Reply is sent immediately as a response to the SIA-Query message. 

Receiving an SIA-Reply allows the Active timer to be reset, giving the diffusing computation an additional time to complete. At most three SIA-Queries can be sent, each after half of the Active timer. If the diffusing computation is not finished by the time the third SIA-Query was replied to by an SIA-Reply and the half of the Active timer expired again, 

the adjacency to the neighbor will be dropped. The same will happen if an SIA-Query is not responded  to by an SIA-Reply within the next half of the Active timer. With the default setting, it's 360 in total.

show ip eigrp topology 

show ip eigrp topology active 

show ip eigrp topology 10.255.255.1/32 

It is possible for a router to receive a Query for a destination while it is Active for that destination. 

Some sources state that precisely this situation causes the SIA states, as they assume that this causes a deadlock. A router in an Active state for a destination has not concluded its computation yet and cannot send Replies, causing the two or more routers to mutually wait for themselves and never receive the expected Reply to each other. In reality, when a router enters the Active state for a destination, it sends out a Query indicating its current distance to the destination after the topology  change that triggered the transition to the Active state. If, during the Active state, the router receives another Query for this destination, it simply sends back a Reply packet immediately, claiming exactly the same distance as originally advertised in its own Query packet. In other words, the router simply restates the same distance it has already advertised in its own Query. Any deadlock scenario is thereby averted.

To avoid SIA states, proper network design that limits the depth of Query propagation and the number of prefixes impacted by a link or node failure is crucial. Proper hierarchical network design coupled with judicious use of passive interfaces, appropriate route filtering and/or summarization, and the EIGRP Stub feature are the key tools that help limit the probability of an SIA state occurrence to an absolute minimum.