Quick Notes: DUAL (CCIE Official Cert Guide: Chapter 8)

From: CCIE Routing and Switching v5.0 Official Cert Guide, Volume 1, 5th Edition

Diffusing Update Algorithm (DUAL)

A convergence algorithm that replaces the Bellman-Fordman algorithm used by other distance-vector protocols.
DUAL uses a concept of diffusing computations to perform distributed shortest-path computation while maintaining freedom from loops during those calculations.
DUAL is at the center of the EIGRP routing protocol.

Topology Table

The central data store of an EIGRP process.
Unconvetional naming because EIGRP has no information about the network's topology per se.
EIGRP stores its entire routing information in the topology table, including:

The prefix of each known destination network (address/netmask).
Feasible Distance of the destination network
Address of each neighboring router that advertised the destination network, including the egress interface toward the neighbor.
Metrics of the destination network as advertised by each neighbor, and the resulting metrics of the path through that neighbor
State of the destination network
Additional information about the network (various internal flags, network type and origin, and others)

Populated and updated by locally injected networks (directly connected EIGRP interfaces, routes redistributed locally) and by contents of received EIGRP messages.
The least total cost and loop-free paths are installed into the routing table.
Each network in the topology table is associated with a state.
Passive meaning that the shortest path to the network has already been found, and EIGRP is satisfied with it.
Active meaning that EIGRP is currently actively involved in a search for a new shortest path.
In a stable topology, all routes shall be in the Passive state.
The Active state is always related to the router sending Query packets, asking its neighbors for cooperation in the search for a new path.
While in an Active state, the router is prohibited from modifying the routing table entry (not removed or its next-hop changed).
Whenever a router needs to select a new shortest path and the neighbor providing that path can be proven not to create a routing loop, the route stays in the Passive state because the router already has all the information to make a correct choice.
If the neighbor providing the least-cost path cannot be guaranteed not to create a routing loop, or if no such neighbor exists, the route will need to enter the Active state.

Computed, Reported, and Feasible Distances, and Feasibility Condition

R1# show ipv6 eigrp topology all-links
IPv6-EIGRP Topology Table for AS(1)/ID(10.255.255.1)
Codes: P - Passive, A - Active, U - Update, Q - Query, R - Reply,
r - reply Status, s - sia Status
P 2001:DB8:CC1E::/64, 1 successors, FD is 2560, serno 4
via FE80::2 (2560/256), Serial1/0
via FE80::3 (5120/1280), Serial1/1
via FE80::4 (4096/3072), Serial1/2

The "via" lines describe a possible route to the destination through a particular neighbor.
Contains the next-hop's IPv6 address, egress interface, and two numbers enclosed in parentheses.
The number after the slash sign is called Reported Distance (RD).
RD is the neighbor's distance to the destination as reported in an EIGRP packet received from that neighbor.
The number before the slash sign is called the Computed Distance (CD).
CD shows the total metric of reaching the destination over the particular neighbor.
The CD is computed as the RD of neighbor plus the cost of the link between R1 and the neighbor.
The Feasible Distance (FD) is a record of the lowest known distance since the last transition from the Active to Passive state.
In other words, FD is a historical record, or a historical copy, of the smallest known CD toward a particular destination since the last Active-to-Passive transition.
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.
FD describes the metric of the best path to the destination this router has known (the smallest known distance to a destination since the last time the route went Passive).
Any neighbor whose Reported Distance is strictly smaller than this router's Feasible Distance cannot form a routing loop.
The Feasibility Condition states that every neighbor satisfying the inequality RD < FD provides a loop-free path, also sometimes called the Source Node Condition.
The FC is a sufficient condition, not a necessary condition.
Every neighbor satisfying the FC provides a loop-free path, but not every loop-free path satisfies the FC.
The FC basically splits all neighbors into two groups: 1) neighbors that are guaranteed to provide a loop-free path, and 2) all other neighbors about which the router cannot be sure.
Feasible Successor: all neighbors that pass the FC and thus are safe to use as next-hops.
Successor: the Feasible Successor with the least CD to the destination.
show ip eigrp topology displays Successors and Feasible Successor.
show ip eigrp topology all-links displays all EIGRP routes.

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 distance change can be detected either through receiving an EIGRP packet, or because a local interface metric has changed.
Also, a neighbor failure is processed by setting the CD/RD of all networks reachable through that neighbor to infinity.

Convergence after a topology change:

The Feasible Successor providing the least CD is made the new Successor.
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 as its current value.
The routing table is updated to point toward the new Successor.
If the current distance to the destination has changed as a result of the new Successor, an Update packet is sent to all neighbors, advertising the router's updated distance.

This is a local computation, performed solely by using information already stored in the topology table, and not involving neighbors. The route has remained in the Passive state.

If, 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 cannot use this neighbor right away because it could cause a routing loop.
The router performs a diffusing computation:

The entry in the routing table 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.
The FD is set to the current (possibly increased) CD through the current unchanged Succesor. If the router ever needs to advertise its distance to the network while in the Active state, it will use the current CD.
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.

Each neighbor receiving a Query packet will process it by updating its own topology table using the distance information advertised in the Query and reevaluating its own choice of Successors and Feasible Successors.
Two possibilities: 1) the neighbor still has its own Successor or Feasible Success, or 2) the information in the Query causes the neighbor to stop considering the path through its current Successor the shortest path available and it has no Feasible Successors.
1) When the neighbor still has a Successor, it will simply send back a Reply packet, indicating the neighbor's current distance to the destination (performing its local computation if necessary). The neighbor did not become engaged in the diffusing computation, and did not need to put the network in the Active state itself.
2) 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. (EIGRP marketing term "partial, bounded updates": partial = only the changed information, bounded = only in the affected part of the network).

In the Active state, a router must wait for a Reply packet from each Queried neighbors.
Until then, the route remains in the Active state, and its routing table is unchanged.
Only after all Reply packets are received, the router can put the route back in the Passive state, simply choose the shortest path neighbor skipping the FC check, and reinitialize the FD to the CD of the selected neighbor.
The crucial information is simply the sender's current distance to the destination, informing its receiver about the packet originator's distance to the destination.
Whether the packet causes its receiver to go Active depends exclusively on how the information in the message impacts the receiver's choice of the shortest path and FC check.

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 (received EIGRP message) or was influenced by it (link metric change).
From among all neighbors that advertise the network, EIGRP identifies the on that provides the least CD, taking into account the updated CDs. Note that the FC is not invoked at this point.
Only after identifying the neighbor offering the least CD, EIGRP verifies whether this neighbor meets the FC and is a Feasible Successor. If it is, EIGRP will promote it to the Successor and start using it right away. If the neighbor does not meet the FC, EIGRP will put the route into the Active state and send out Queries.

Before convergence.
R1# show ipv6 eigrp topology all-links
! Legend removed for brevity
P 2001:DB8:CC1E::/64, 1 successors, FD is 2048, serno 9
via FE80::2 (2560/256), Serial1/0
via FE80::3 (5120/1280), Serial1/1
via FE80::4 (4096/3072), Serial1/2

After convergence.
R1# show ipv6 eigrp topology
! Legend removed for brevity
P 2001:DB8:CC1E::/64, 1 successors, FD is 4096
via FE80::4 (4096/3072), Serial1/2
via FE80::3 (5120/1280), Serial1/1

R1# show ipv6 route eigrp
! Legend removed for brevity
D 2001:DB8:CC1E::/64 [90/4096]
via FE80::4, Serial1/2

DUAL FSM

Assuming a router to efficiently compute a new path to a destination with no other topological changes taking place is a strong assumption.
EIGRP uses a control mechanism called the Diffusing Update Algorithm, or DUAL, to take care of handling multiple topology changes occurring during a single diffusing computation.

A0: Local Origin with Distance Increase
A1: Local Origin
A2: Multiple Origins
A3: Successor Origin
CD = Computed Distance
FC = Feasibility Condition

Summarization of DUAL FSM:

Unless a change in distance occurs such that the least CD neighbor fails to meet the FC, the route remains Passive.
If a Query is received from the current Successor and the least-cost CD neighbor fails to meet the FC, the route will enter the A3 active state (Successor Origin Active state). The router will send out Queries and wait for Replies. The last Reply allows the router to transition back to the Passive state, reinitialize the FD, and choose the least-cost CD neighbor as the new Successor.
If a distance change is not caused by a Query from a Successor (receiving an Update, changing an interface metric, or losing a neighbor) and the least CD neighbor does not meet the FC, the route will enter A1 active state (Local Origin Active state). The router will send out Queries and wait for Replies. The last reply allows the router to transition back to the Passive state, reinitialize the FD, and choose the least-cost CD neighbor as the new Successor.
If during the stay in the A 3 (Successor Origin) or A 1 (Local Origin) active states, another distance increase caused by other means than the Successor’s Query is detected, another topology change during the diffusing computation has occurred. Because the router cannot advertise this updated distance while it is in the Active state, other routers might not be informed about it and their Replies might not take this new increased distance into account. The state is changed from A3 (Successor Origin) to A2 (called Multiple Origins ), or from A1 (Local Origin) to A0 (no official name; we will call it Local Origin with Distance Increase ) states. In A2 or A0 states, the router waits to receive all remaining Replies. When the last Reply arrives, the router will first check whether the neighbor providing the least Computed Distance passes the Feasible Condition check using the Feasibility Distance value set when the route entered the Active state. If it does, the route becomes Passive again, and the neighbor is chosenas the Successor. If it does not, however, the route will return from A0 (Local Origin with Distance Increase) to A1 (Local Origin) or from A2 (Multiple Origins) to A3(Successor Origin) and the router will commence another diffusing computation by again sending a Query.
If during the stay in A 1 (Local Origin) or A 0 (Local Origin with Distance Increase) active states a Query from the Successor is received, another topology change during the diffusing computation has occurred. Because the router cannot advertise this updated distance while it is in the Active state, other routers might not be informed about it and their Replies might not take this new increased distance into account. The state is changed to A2 (Multiple Origins) and then proceeding from that state just like in the previous case.

Stuck-In-Active State

In the Active state, EIGRP must 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 route in the Active is dependent on the entire chained sequence of routers that have become Active as a result of its Query.
There are several reasons why a neighbor might not respond to a Query:

The CPU is overloaded and the router cannot respond or even process the Query.
Quality issues on the link are causing packets to be lost.
Low-bandwidth links are congested and packets are being delayed or dropped.
The network is excessively large or complex, either requiring the Query to propagate to a significant depth or causing an inordinate number of prefixes to be impacted by a single link or node failure.

Active timer: starts when the first Query is sent out. By default, 3 minutes (1-65535 minutes). Set to infinity using timers active-timer.
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(s) that did not Reply will be removed from the neighbor table and their adjacencies torn down.
Instability ensues. All networks learned from that neighbor will be flushed and possibly learned again after the neighbor comes back up within the Hello interval time.
Difficult to located the problem origin.
If the 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-Query: "Are you still working on my Query?"
If the neighbor is able to receive and process this SIA-Query, it will immediately respond with the SIA-Reply message.
SIA-Reply: "Yes, I'm still waiting for my own neigbors to send me Replies." or "No, the computation is finished. This is my current metric to the destination."
Receiving an SIA-Reply allows the Active timer to be reset, giving the diffusing computation 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 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 settings, the maximum time for SIA = 4 x 90 = 360 seconds (90 seconds for the first SIA-Query, plus each SIA-Query buying another 90 seconds).

It is possible for a router to receive a Query for a destination while it is Active for that destination.
Some sources claim that this situation causes the SIA states. In reality, this is a gross misunderstanding.
When a router enters the Active state, 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.
Any deadlock scenario is thereby averted.
Proper hierarchical network design coupled with judicious use of passive interfaces, appropritate 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.

Network Playroom

Search This Blog