Group,
I am not sure I completely aggree with Mr. Katz..
I am also abit more verbose.
Their are times within within large areas, over a period of
time, where the number of changing (new) LSAs are significant.
With cheaper slow main memory, the size of the SPF routing tables
can grow. It is sometimes worth while to minimize the amount
of summarization of routes, so the now non summarized routes
can be differentiated in their costs. Additionally, a BGP draft is
currently looking at increasing the number of redundant/alternate
routes that could be advertised. So, these routing tables can
grow unbounded with some scaling SPF issues. Some implementations
require about 2 dozen main memory lookups just to determine if
a LSA is new.
During these times, you COULD be trying to minimize the number
of repeated SPF calculations. Their are some optimizations that
can be done for some types of LSAs, but consume more memory. some
of the optimizations allow very fast routing table changes at
a fraction of normal time.
It is important to at least minimize the local forwarding
abnomalies and where fast (10Gb Eth) interfaces are present,
where even a short delay can result in longer term disruptions.
If a flow was a TCP flow, even a single mis-routed segment,
can result in a temporary drop to 50% of the pre-loss bandwidth.
TCP with its then congestion avoidance functionally can take
1 round-trip-time per loss of the 50% of in-flight segments
to regain its previous bandwidth.
Just trying to show some interaction...
So, lets continue..
The forwarding tables are rather limited in size due to the
additional cost of the forwarding table memory. The cost is
their to allow very fast forwarding. This limits
the amount of time one can spend changing the forwarding tables.
Sometimes the design requires extra cycles to change the
forwarding tables versus just making forwarding decisions based
on them. Some implementations may use default type routes.
One can not change how fast a UPdate OSPF pkt will be recieved
and processed by a neighbor which will result in a forwarding
change. However if a implementation was smart enough to
determine that a recieved LSA would result in a SPF calc trigger,
one might want to force a immediate Update that only includes
those LSA(s)to the next neighbors. This would prioritize those
LSAs to the neighbor, and then after a short time, send the
normal age update LSAs..
Mitchell Erblich
----------------------
Dave Katz wrote:
>
> 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
_______________________________________________
OSPF mailing list
[email protected]
https://www1.ietf.org/mailman/listinfo/ospf
