[quagga-dev 5026] Re: OSPF shortest path computation
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?
OK, here is setup where we have this problem:
10 200 <-- the problematic cost
D 200 ---- 200 B
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