Mitchell,
I think that what Dave was pointing out is that in most (large) networks
where one could expect the cost of an SPF to be an issue, it is actually
not significant (per instance) compared to the cost of updating the
routing/forwarding table and other dependent processes.
The case of BGP provides a good example, as the issue is more the impact
on the BGP decision process that you will need to rerun and that could
involve scanning 250k entries, and that alone will take more time than
the SPF itself. And then you have the added cost of updating the
forwarding entries of all those BGP prefixes whose Next_Hop just changed
because of the SPF change. There is actually a reasonably good
discussion of this whole issue and how it is dealt with in two major
implementations in a recent book on IS-IS by Gredler and Goralski,
Springer, 2005 (no endorsement intended).
So in general, I agree with Dave that in most/all reasonably designed
networks, the actual SPF cost will pale in comparison to some of the
other overheads involved in updating routing tables. Now, you can
certainly create situations where the SPF computation does become a
bottleneck (I've seen a network with one huge OSPF area - several
hundred routers - and thousands of local prefixes, where one flaky
router was regularly bringing the network down because of SPF
computations), but they should be the exception rather than the rule.
Roch
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
_______________________________________________
OSPF mailing list
[email protected]
https://www1.ietf.org/mailman/listinfo/ospf
