[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)

Interesting..

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.

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



More information about the Quagga-dev mailing list