Roch Guerin,
Let me try to be abit more succinct. which restates
the below..
If one major component of cost is the time to
complete a task.
Then the cost or time is significantly greater
for the routing table than the forwarding table.
The biggest reason for this is because the forwarding
tables need faster memory. If we assume that forwarding
table memory is 4x faster than routing table memory,
then if we complete a forwarding table memory task 2x as
fast and keep the other constant, we only have about a
10% speeedup,
' however, if we double the speed of a routing table task,
than we can improve by about 40%.
Thus, improving the speed of the equiv of SPF processing
gives us a decent improvement, which leads to my disagreement.
Yes, this is Amdahls Law..
However, if we measure all of the tasks that are needed
for a rec'ved LSA over time, most are LSA age updates, which
removes the need for SPF calcs, and thus increases the
chance that a improvent elsewhere would be more beneficial.
Mitchell Erblich
-----------------
Roch Guerin wrote:
>
> 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
