Subject: [OSPF] Question about SPF

From: Yasuhiro Ohara <[email-masked]>
Date: Tue, 28 Dec 2010 00:09:31 +0900 (JST)

Hi list.

RFC 2328 16.1. "Calculating the shortest-path tree for an area"
(3) says that:
                                                          Note
   that when there is a choice of vertices closest to the root,
   network vertices must be chosen before router vertices in
   order to necessarily find all equal-cost paths.

I couldn't think of any possible case that we fail to find
all equal-cost paths when the router vertices are chosen
first. Is there any ?

When I first felt that I understood this, I remember 
that this seemed to be due to the fact that the cost is
implicitly ZERO from a network vertex to a router vertex.
But I can't think of any case now.

Even if the network vertices are chosen later, they are added
eventually, and all the equal-cost multipaths are correctly
calculated.

Would someone please explain ?

thanks in advance,
best regards,

yasu

---

From: Roch Guerin <[email-masked]>
Date: Mon, 27 Dec 2010 10:17:13 -0500

Once a node is added to the "labeled set" of the Dijkstra algorithm, it 
is never revisited.  Hence, you wont be able to discover additional next 
hops for it.
Consider a scenario where the shortest path to router C is either 
directly over a  p2p link with a cost of 1 or through network N, also 
with a cost of 1.  If you move router C to the labeled set first, you 
will never discover the path through N (the outgoing link from N to C 
indeed has a cost of 0).

Roch

On 12/27/2010 10:09 AM, Yasuhiro Ohara wrote:
> _______________________________________________
> OSPF mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ospf
>

---

From: Yasuhiro Ohara <[email-masked]>
Date: Tue, 28 Dec 2010 01:19:15 +0900 (JST)

Ah, I get it. RFC 2328 requests that all mulitpaths are found when the
vertex is in the candidate list.

When the multipaths to a destination in the shortest path tree
can be added later, then we don't need to care the order of the
vertex type to install.

(My implementation does this, taking another requirement that the
nexthop calculation is done after the entire SPF tree is decided.)

Thank you.

regards,
yasu

From: Roch Guerin <[email-masked]>
Subject: Re: [OSPF] Question about SPF
Date: Mon, 27 Dec 2010 10:17:13 -0500
Message-ID: <[email-masked]>

> Once a node is added to the "labeled set" of the Dijkstra algorithm, it is never revisited.  Hence, you wont be able to discover additional next hops for it.
> Consider a scenario where the shortest path to router C is either directly over a  p2p link with a cost of 1 or through network N, also with a cost of 1.  If you move router C to the labeled set first, you will never discover the path through N (the outgoing link from N to C indeed has a cost of 0).
> 
> Roch
>