And I'll just throw in my standard rant, which is that I've yet to
see an operational network where the computational cost of an SPF was
enough of a concern to go to the effort of getting fancy.
The costly part is seldom the SPF itself, but rather the side effects
of doing it (how you handle updating forwarding tables, interaction
with BGP, etc.) Those are the places to spend the effort in
optimization, IMHO.
--Dave
On Aug 9, 2006, at 12:07 PM, Acee Lindem wrote:
Hi Roch,
Agree with your explainatoin - rrSee one additional comment below.
Roch Guerin wrote:
Rick,
Not sure there is a unique explanation, but I would take the
statement with a grain of salt as I know of a couple of
implementations that do things more intelligently and indeed avoid
a Dijkstra recomputation (full SPF) when the change only affects a
stub network in an area (in Section 16 of RFC 2328, the intra-area
routing table computation is actually broken into two steps, with
the second step being dedicated to adding stubs).
I think the origin of this statement is that unlike IS-IS where
because reachability information is encoded into separate TLVs
there is a clean demarcation between running the (full) SPF
(Dijkstra) using routers, pseudo-nodes and links connecting them,
and what is called the partial route computation (PRC) that
involves only the prefixes and not the topology, the situation is
a bit murkier in OSPF. In particular, unless you do a detailed
parsing of the RouterLSAs and NetworkLSAs to determine what has
changed, the receipt of a changed one will often be used as a
sufficient trigger to schedule a Dijkstra computation.
Now this is again a necessary but not a sufficient condition, and
some implementations will perform the additional parsing required
to avoid a full SPF (Dijsktra) when it is not needed.
Exactly, in fact, this is stated explicitly in RFC 2328.
The specification does not require that the above two stage
method be used to calculate the shortest path tree.
However, if
another algorithm is used, an identical tree must be produced.
For this reason, it is important to note that links between
transit vertices must be bidirectional in order to be included
in the above tree. It should also be mentioned that more
efficient algorithms exist for calculating the tree; for
example, the incremental SPF algorithm described in [Ref1].
Thanks,
Acee
hope this helps,
roch
In section 3.5.3, RFC2740 indicates the the entire routing table
is recalculated when there's a change to the router,network,
intra-area and link LSAs. Why is it that a change to an intra
area prefix would require a full SPF?
thanks
/rg
--------------------------------------------------------------------
----
_______________________________________________
OSPF mailing list
[email protected]
https://www1.ietf.org/mailman/listinfo/ospf
---------------------------------------------------------------------
---
_______________________________________________
OSPF mailing list
[email protected]
https://www1.ietf.org/mailman/listinfo/ospf
_______________________________________________
OSPF mailing list
[email protected]
https://www1.ietf.org/mailman/listinfo/ospf
_______________________________________________
OSPF mailing list
[email protected]
https://www1.ietf.org/mailman/listinfo/ospf
