EIGRP Query process

[Wajih Rehman]

Hello,

As we know that if there is a route which is not FS then it is still kept in the topology table. In case when Successor or Feasible Successor are lost , then router performs a query process to identify if routes are still available.

My question is then what is the point to keep non-FS route in topology table if EIGRP does not process them and go for the query process? When EIGRP use that information?

Wajih

[akumarka]

if both FS and S routes are lost then only eigrp performs query process.topology table consists of successors and non successor routes also

[Peter Paluch · Accepted solution]

Wajih,

Consider the following topology:

We are interested in the path from R1 to R5. The path R1-R2-R5 is the best one, with the total metric of 20. As a result, R2 is a Successor, and the metric of 20 will also become the Feasible Distance because it is the best metric to the destination R1 has encountered so far.

The path R1-R3-R5 is more expensive, with the total metric of 25, but R3 still meets the Feasibility Condition (its Reported Distance of 15 is still strictly less than R1's Feasible Distance of 20), and so R3 will be a Feasible Successor.

The path R1-R4-R5 has the total metric of 21. This path is actually cheaper than the FS path R1-R3-R5, but because R4 does not meet the Feasibility Condition (its Reported Distance of 20 is not stricly less than R1's Feasible Distance of 20), it is not considered to be a Feasible Successor. As a result, the path through R4 is a non-FS route. However, R1 will still keep the information about this route in its topology table.

Assume now that R2 suddenly fails. R1 now looks into its topology table, first looking for the next shortest path to R5 - and it will come across the path through R4, with the total metric of 21. However, at the same time, R1 will find out that R4 is not a Feasible Successor. Therefore, R1 will go to Active state, send out Queries, and after receiving Replies from R3 and R4 (both claiming the same distance as before as they are not affected by R2's outage), R1 will be allowed to reset the Feasible Distance and set it to the metric of the new shortest path - which is 21, through R4, with R4 becoming Successor right away and R3 remaining the Feasible Successor.

Notice that if R1 decided to throw away the information about the path through R4 as a non-FS route, then after R2 fails, R1 would not know that there is possibly a shorter path available than the path through the current Feasible Successor (R3), and it would stick to using a path through R3 that is usable but not the shortest available.

So, even though non-FS routes can not be used right away, EIGRP needs to keep track of them because in the moment of a topology change, these paths may actually provide better paths than current FS routes - even though this has to be verified by entering the Active state.

Feel welcome to ask further!

Best regards,
Peter

P.S.: You have posted the same question twice here as well:

https://supportforums.cisco.com/discussion/12704636/eigrp-query-process

Please delete the other thread that responses to your question are not spread across multiple threads.

[paul driver]

Hello Peter

Would just like to say your teaching style is very inpressivie and easy to follow I have dyslexia which can be very impeding sometimes in my studies but I never fail to understand your posts. Kudos to you!

Res Paul 

[Peter Paluch]

Hi Paul,

I am lost for words. This is one of the deepest and most touching things anyone ever said regarding my way of explaining things.

Thank you, my friend.

Best regards,
Peter

[Wajih Rehman]

Hello Peter,

I need some further explanation. As you commented:

"Assume now that R2 suddenly fails. R1 now looks into its topology table, first looking for the next shortest path to R5 - and it will come across the path through R4, with the total metric of 21. However, at the same time, R1 will find out that R4 is not a Feasible Successor. Therefore, R1 will go to Active state, send out Queries, and after receiving Replies from R3 and R4 (both claiming the same distance as before as they are not affected by R2's outage), R1 will be allowed to reset the Feasible Distance and set it to the metric of the new shortest path - which is 21, through R4, with R4 becoming Successor right away and R3 remaining the Feasible Successor."

My understanding of this situation was that if R2 lost then feasible successor will be promoted to successor . Router1 in this situation will not go to ACTIVE. Please correct me if I am wrong.

Now if my understanding is correct then R1-R3-R5 will be next successor route. If this path is also lost then Router1 will go to active and send the query message. My question was , then what is the point of keep non-FS route in the topology if we have to discover the new route through Query message.

Many thanks for your time and support.

Wajih

[Peter Koltl]

I have the same question:

What is the point of feasible successor if the router does not switch over to it at once?

[Peter Paluch]

Wajih, Peter,

Let's go over it one step at a time.

The use of Feasible Successors in EIGRP has been usually explained in the following terms: If the current Successor to a destination fails but a Feasible Successor is still known, then promote the Feasible Successor to the new Successor. If there are multiple Feasible Successors then choose the one that provides the least total cost and promote that one to the Successor.

I have intentionally written the text above in a strikethrough style because that explanation is wrong. EIGRP works differently.

First of all, keep in mind that EIGRP is a distance-vector protocol (not a hybrid - that's yet another popular mistake), and as every other distance-vector protocol, it makes its best path choices based on a simple basic rule: Always try to use neighbor that provides the least total cost path. This is obviously what RIP does, and this is what EIGRP also does, but with an additional check: In EIGRP, all path choices are additionally subject to a loop freedom check to avoid causing any routing loops. This is the well-known Feasibility Condition. If the neighbor providing the least total cost path also passes the Feasibility Condition, it can be promoted to the Successor role right away. If, however, the neighbor providing the least cost path does not meet the Feasibility Condition, the router will put the route into the Active state. Doing so allows to explicitly verify whether that path is looped or not (keep in mind that routes that pass the Feasibility Condition are guaranteed to be loop-free but routes failing the Feasibility Condition check may or may not be looped - there is no way to tell based on the Feasibility Condition alone).

So the process of path selection in EIGRP is in fact as follows:

1. After detecting a topology change (change in the Reported Distance of a neighbor, change in the cost of the link to a neighbor, detecting a new neighbor or losing an existing neighbor), record the updated distances in the topology table so that it contains up-to-date information.
2. In the updated topology table, find the neighbor that newly provides the least cost path (this is the common distance-vector path selection step).
3. Verify whether this neighbor satisfies the Feasibility Condition. If it does, promote it to the new Successor. If it does not, go to the Active state.

As you may see, this sequence of steps does not really refer to any Feasible Successor.

My understanding of this situation was that if R2 lost then feasible successor will be promoted to successor . Router1 in this situation will not go to ACTIVE. Please correct me if I am wrong.

Unfortunately, this is wrong - even though many courses about EIGRP would state the same. If R1 simply promoted R3 (the FS) to the new Successor, it would deprive itself of the possibility to use a path that is objectively shorter (the one through R4). Surely, we do not want EIGRP to use just about "any good" path - we want it to use the shortest path, even if it means verifying it using the Active state.

Once again, if R1 finds out that its current Successor has failed (R2), it will try to look up the neighbor providing the next best path, which is R4. But because R4 does not meet the Feasibility Condition, R1 needs to find out if the path through R4 is looped or not, and that is why it enters the Active state.

What is the point of feasible successor if the router does not switch over to it at once?

In its very essence, the Feasible Successor is only a byproduct of how the Feasibility Condition works, and its importance is overstated. The Feasibility Condition states that every neighbor whose Reported Distance is strictly lower than the route's Feasible Distance provides a guaranteed loop-free path. That allows you to do unequal cost load balancing, and perhaps in very recent IOSes, IP Fast Reroute.

Arguably, during the time the route is in the Active state, R1 could forward packets for R5 through R3. However, it is not implemented this way, and the original papers by Dr. Jose Joaquin Garcia-Luna-Aceves who developed the DUAL algorithm do not suggest any such possibility.

Please feel welcome to ask further!

Best regards,
Peter

[Wajih Rehman]

Hello Peter,

Based on the steps you mentioned:

1. After detecting a topology change (change in the Reported Distance of a neighbor, change in the cost of the link to a neighbor, detecting a new neighbor or losing an existing neighbor), record the updated distances in the topology table so that it contains up-to-date information.
2. In the updated topology table, find the neighbor that newly provides the least cost path (this is the common distance-vector path selection step).
3. Verify whether this neighbor satisfies the Feasibility Condition. If it does, promote it to the new Successor. If it does not, go to the Active state ( here R3 satisfies the condition already but not R4)

We can say that once R2 fails , R3 will be promoted to successor and R1 will not go to active. This is what I also wrote.

Again, my question is what if R3 also fails and there is another route in topology which does not satisfy the Feasibility condition then R1 will not use it and will go active. It will send the Query and find out R4 is a suitable successor. So what is the point to have R4 in topology if Query has to be perform for such routes? R1 is not going to trust it and will use query all neighbours.

[Peter Paluch]

Wajih,

3. Verify whether this neighbor satisfies the Feasibility Condition. If it does, promote it to the new Successor. If it does not, go to the Active state ( here R3 satisfies the condition already but not R4)

No, we do not understand each other. The neighbor mentioned in Step 3 is the neighbor providing the least total distance identified from Step 2, not just any neighbor.

In my example topology, before R2 fails, the situation is:

R2: 20/10 (Total Distance / Reported Distance)
R3: 25/10 (Total Distance / Reported Distance)
R4: 21/20 (Total Distance / Reported Distance)

If we were to sort these neighbors based on the total distances they provide to R5, the order would be

R2 (20)
R4 (21)
R3 (25)

Notice that R4 provides a better path than R3, but because the Feasible Distance is 20, R4 is not a Feasible Successor.

After R2 fails, the distance over the failed neighbor is set to infinity:

R2: infinity/infinity
R3: 25/10
R4: 21/20

This was step 1. Now, the Step 2 identifies who is the next neighbor providing the least cost distance, and obviously, it is R4 with the total distance of 21. And after Step 2, Step 3 verifies whether R4 as the neighbor providing the least cost distance also satisfies the Feasibility Condition (i.e. it is a Feasible Successor). In this case, because FD is unchanged and remains set to 20, R4 is not a Feasible Successor even though it provides the least cost path, and therefore R1 needs to put this route into Active state.

We can say that once R2 fails , R3 will be promoted to successor and R1 will not go to active.

Certainly not, as I just explained above. EIGRP does not use Feasible Successors just because they are there. After the Successor fails, EIGRP will use a Feasible Successor if and only if that Feasible Successor also happens to provide the least cost path to the destination. In my example, R3 does not fit this requirement, and so it will not be promoted to the Successor role.

So what is the point to have R4 in topology if Query has to be perform for such routes? R1 is not going to trust it and will use query all neighbours.

I have answered this question already in my first post. I stand by my claim that after a topology change is detected and processed, EIGRP first selects any neighbor that provides the least total cost path, and then it checks whether the neighbor is a Feasible Successor by passing the Feasibility Condition check - and if it does not, EIGRP will go Active.

If, in our example, the path through R4 was not installed in the topology table on R1, then after R2 fails, R1 would use the path through R3 without even going Active. However, that would cause R1 to use a longer-than-shortest-available path to R5 for an unlimited period of time, believing that this is a stable situation and there is no better path available. This would reduce EIGRP from optimal routing protocol computing true shortest paths to just a heuristic using just about any path available, without making sure it is the shortest one. Having the path through R4 in the topology table, even though unusable at present, gives R1 a hint that there may be actually a shorter path available, but if R1 decides to go for it, it must first go Active to check whether the path is in fact loop-free. It might, and it might not - the fact that the path is a non-FS path does not truly prove either. That's why Active state is needed, and that's why the path through R4 has to be installed in R1's topology table - otherwise, R1 would be making incorrect choices with a limited knowledge.

Feel welcome to ask further!

Best regards,
Peter

[InayathUlla Sharieff]

Hi Peter,

You are our insipiration when it comes to technology part. We always look for your post before we look any other queries..

I always talk about you with my friends.(hope one day comes when we get a chance to meet you!) I had the knowledge of EIGRP as others do , but didnt understand this way which you have described above which makes more sense and understanding this protocol in a very good manner.

Thank you a ton for this and we see more for this kind of thing which we cant find in books.

Regards

Inayath

[Peter Paluch]

Hi Inayath,

I am honored beyond words - I really mean it. And I really do hope that we meet in person soon.

Best regards,
Peter

[Majid Jalinousi]

Hi Peter, 

Thanks a lot for your impressive explanation,

I have another question about diffusing calculation, as you better know when a router finds a higher CD to a particular destination, it will send a query to rest of network informing this change, I want to know with this query it will send the new discovered CD to this destination or the current CD three is in topology table?

And when it will change FD value with this new discovered CD?

Thanks in advance. 

[Majid Jalinousi]

Hi Peter, 

Thanks a lot for your impressive explanation,

I have another question about diffusing calculation, as you better know when a router finds a higher CD to a particular destination, it will send a query to rest of network informing this change, I want to know with this query it will send the new discovered CD to this destination or the current CD three is in topology table?

And when it will change FD value with this new discovered CD?

Thanks in advance.