Subject: [OSPF] doubt in SPF calculation

From: sinbad <[email-masked]>
Date: Wed, 19 Sep 2007 16:19:55 +0530

Hi,

In SPF calculation. RFC section 16.1 step (3)

I am not getting how we can only find equal-cost paths , if we select
network vertices

before router vertices.Pls someone explain the text in the quotes ...

Section 16.1 step (3) from RFC 2328

(3) If at this step the      candidate list is empty, the shortest-

path tree (of transit vertices) has   been completely    built

and this stage of the procedure terminates. Otherwise,

choose the vertex belonging to the candidate list that is

closest to the root, and add it to the shortest-path tree

(removing it from the candidate list in the process). 

"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."

This is consistent with the tie-breakers that were introduced in the

modified Dijkstra algorithm used by OSPF's Multicast routing

extensions (MOSPF).

thanks

sinbad

_______________________________________________
OSPF mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ospf

---

From: Roch Guerin <[email-masked]>
Date: Wed, 19 Sep 2007 06:57:35 -0400

The reason for considering network vertices before router vertices is
because the outgoing edge of network vertices has a cost of zero and
because of how the Dijkstra algorithm operates.  When Dijkstra moves a
vertex out of the candidate list, it never re-examines it.  Hence, if in
case of ties you moved the router vertex before the network vertex, you
would never discover any (equal cost) path to that router vertex that
uses the network (remember that the edge out of a network has cost zero).
Hope this helps.
Roch

sinbad wrote:
> ------------------------------------------------------------------------
>