[quagga-dev 5027] Re: OSPF shortest path computation

Paul Jakma paul at clubi.ie
Mon Aug 6 19:38:35 BST 2007

On Mon, 6 Aug 2007, Atis Elsts wrote:

> OK, here is setup where we have this problem:
>        X
>        |
>        A
>    100   10
>    /       \
>   /         \
>  10          200  <-- the problematic cost
> D 200 ----  200 B
> 100          10
>   \         /
>    \       /
>     10   100
>        C
> Numbers are the assigned interface costs.
> The problem is on router B.
> When cost on router B interface to A is 201, table is calculated correctly.
> Else route to network X on goes through router A, not C as expected.
> (and route to router A has cost 200 instead of expected 30)


Out of curiosity, do you still have debug logs for SPF? Or do you 
remember the relevant IDs involved. I.e. what order does B explore 
the topology in, when doing SPF? Or even the order of the heap?

The problem case must be where a vertex in the queue changes cost so 
it /should/ be first (the top), but doesn't get sorted to top before 
the next dequeue (after which heap is sorted anyway)? Is that right?

I'd like to perhaps add a pqueue test-case.

> Quite obviously function trickle_up() can only move closer to the 
> root in pqueue and trickle_down() - further away from the root. And 
> since the root node has the lowest cost, after reducing cost for a 
> node (i.e relaxing it), it could possibly be moved only *closer* to 
> the root.

Ah, of course yes.

> At least thats how I see it.

Thanks for the report and analysis.

Paul Jakma	paul at clubi.ie	paul at jakma.org	Key ID: 64A2FF6A
Education is learning what you didn't even know you didn't know.
 		-- Daniel J. Boorstin

More information about the Quagga-dev mailing list