EIGRP DUAL FSM (Finite State Machine)

EIGRP has a mechanism called DUAL FSM (Diffusing Update Algorithm) that takes care of multiple changes that occur during a topology change. In this lesson, I’ll explain what the finite state machine is and how it works.

When the network is stable and there are no changes in the topology, each route will be passive. EIGRP will act whenever an input event occurs. The source of an input event can be:

• When the metric of a directly connected interface changes.
• A directly connected interface that goes up or down.
• When you receive an update, query, or reply packet.

When any of these input events occurs, the router will first do a local computation where it recalculates the distance for all feasible successors in the topology table. The possible results from this local computation are:

• If a feasible successor has a lower distance than the current successor, the feasible successor becomes the new successor.
• If the new distance is lower than the current feasible distance, we update the feasible distance.
• If the new distance is different than the current distance, we send an update with the new distance to all neighbors.

During this local computation, the route remains passive. If there is no feasible successor in the topology table, the router will start a diffusing computation and the route will go active. During this diffusing computation, the router is unable to:

• Change the successor of this route.
• Change the distance it is advertising for this route.
• Change the feasible distance for this route.
• Start another diffusing computation for this route.

The router will start the diffusing computation by sending a query to each of its neighbors. In this query, we will find the new distance that was calculated on our router.

When a neighbor router receives the query, it will start with its own local computation. If it has a feasible successor in its topology table, it will send a reply to the neighbor that sent the query which includes the distance to the destination. If the neighbor doesn’t have a feasible successor, it will start a diffusing computation on its own.

EIGRP keeps track of all neighbors that it has sent a query to, it does so with a reply status flag.  The diffusing computation is finished when we receive a reply from all our neighbors.

When the diffusing computation starts, the router will change the metric of the feasible distance to infinity to make sure that the route that its neighbors advertise in the reply is accepted and meet the “feasibility condition” (advertised distance of the feasible successor has to be lower than the feasible distance of the successor).

Once the router has received all outstanding replies, it will select a new successor based on the shortest distance to the destination and sets the new feasible distance. Any feasible successors that don’t meet the feasibility condition of this new successor are removed from the topology table.

There are multiple input events that can cause a route to change its state and some of these input events can occur while the route is already active.

Because of this, EIGRP doesn’t have just one “active” state but there are four active states. We can move from one state to another. Here is an overview of the EIGRP finite state machine, with all its different states and how we get there:

The diagram above needs some explanation. First of all, here are the acronyms:

• R: query reply status flag
• O: query origin flag
• IE: input event

Here are the input events that you see above:

• IE1: feasibility condition satisfied.
• IE2: received query from successor and feasibility condition is not satisfied.
• IE3: input event other than query from the successor where feasibility condition is not satisfied.
• IE4: input event other than last reply or query from the successor.
• IE5: input event other than the last reply, query from the successor, or distance to destination increased.
• IE6: input event other than the last reply.
• IE7: input event other than last reply or distance to destination increased.
• IE8: distance to destination increased.
• IE9: received all replies, feasibility condition not satisfied for current feasible distance.
• IE10: received query from the successor.
• IE11: received all replies, feasibility condition satisfied with current feasible distance.
• IE12: received all replies, feasible distance set to infinite metric.

The arrows in the diagram explain to which input events DUAL reacts to and to what state it changes. EIGRP uses the query origin flag to keep track of which state it is in. 

So how does it work? Let me walk you through one possible example. Take a look at the following topology:

We have three routers, running EIGRP:

• R1 is using R3 to reach 3.3.3.3/32.
• R2 is using R1 > R3 to reach 3.3.3.3/32.

Suddenly, the link between R1 and R3 fails:

R1 will now move from the passive state into the active state for 3.3.3.3/32 and sets the distance of the route that it lost to infinite. It also sends a query with the new distance to R2. The input event is IE3 since it wasn’t triggered by a query and there is no feasible successor. R1 expects a reply from R2 so it sets its reply status flag to 1. R1 also sets the query origin flag to 1.

Once R2 receives the query, it will do a local computation. R2, however, does have a feasible successor, it’s direct path to R3. R2 will remain in the passive state and installs R3 as the new successor. R2 sends a reply to R1 with the distance of its successor route.