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 protected]> Subject: Re: [OSPF] Question about SPF Date: Mon, 27 Dec 2010 10:17:13 -0500 Message-ID: <[email protected]> > 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: > > 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 > > > > > > _______________________________________________ > > OSPF mailing list > > [email protected] > > https://www.ietf.org/mailman/listinfo/ospf > > _______________________________________________ OSPF mailing list [email protected] https://www.ietf.org/mailman/listinfo/ospf
