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

Atis Elsts atis at mikrotik.com
Mon Aug 6 17:19:16 BST 2007

On Monday 06 August 2007 17:42:23 Paul Jakma wrote:
> On Mon, 6 Aug 2007, Atis Elsts wrote:
> > Hi,
> > there seems to be a problem with shortest path tree calculations - for
> > setups that contain loops. The optimal path is not always found. I
> > believe that vertex relaxation in Dijkstra algorithm is done incorrectly.
> That's interesting, could you give more details though, to help
> others understand?
> regards,

OK, here is setup where we have this problem:

    100   10
    /       \
   /         \
  10          200  <-- the problematic cost
 D 200 ----  200 B
 100          10
   \         /
    \       / 
     10   100

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)

After this fix, table is always calculated correctly e.g.
- when interface cost < 30 route goes through A
- when interface cost > 30 route goes through C
- when interface cost = 30 there is ECMP.

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.
At least thats how I see it.


More information about the Quagga-dev mailing list