Octet

Why does the feasibility condition guarantee a loop-free path, and why is it more conservative than it needs to be?

Show the answer

Say this first

If a neighbor's reported distance is lower than my feasible distance, the neighbor is closer to the destination than I have ever been since the route was last stable, so its path cannot pass through me: any path through me would cost at least my distance plus a link. DUAL proves this with one number per neighbor, without seeing the topology. It is conservative because many loop-free paths fail the test simply because the neighbor's own path is long. Those are only found by querying.

Go deeper

The argument

Suppose neighbor N reaches destination D through me. Then N's distance is my distance plus the cost of the link from N to me, which is always more than zero. So N's reported distance would be greater than my distance. If N reports less than my FD, N cannot be routing through me, so forwarding to N cannot loop back.

Why FD and not my current distance

The feasible distance is the lowest distance I have had since the route last went passive. Using that historical low means the check stays safe while metrics are rising: a neighbor has to beat my best recent distance, not just my current, possibly inflated, one.

Why it rejects good paths

In the classic example, R4 reaches the destination through its own slow link and reports 26112 against R1's FD of 3328. The path is loop-free, but the condition is sufficient, not necessary: it only proves safety for neighbors that are closer than me. For everything else DUAL falls back to a diffusing computation (going active and querying), which finds the new best path safely, just slower.

The same idea elsewhere

IP fast reroute loop-free alternates for OSPF and IS-IS (RFC 5286) use a very similar inequality: neighbor N is a safe alternate if N's distance to D is less than N's distance back to me plus my distance to D. Link state protocols can check it for every neighbor because they see the full map.

Traps

  • Saying a path that fails the feasibility condition must contain a loop. It only means DUAL cannot prove it is loop-free.
How did you do?Book 3.4 Routing