Subject: [OSPF] intra area prefix lsa change requires spf

From: [email-masked]
Date: Wed, 09 Aug 2006 17:40:28 +0000

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-masked]
https://www1.ietf.org/mailman/listinfo/ospf

---

From: Roch Guerin <[email-masked]>
Date: Wed, 09 Aug 2006 13:57:42 -0400

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.

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

---

From: Acee Lindem <[email-masked]>
Date: Wed, 09 Aug 2006 14:07:38 -0400

Hi Roch,
Agree with your explainatoin - rrSee one additional comment below.
Roch Guerin wrote:
> 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.
>
> 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

---

From: Dave Katz <[email-masked]>
Date: Wed, 9 Aug 2006 12:45:03 -0600

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:

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

---

From: Erblichs <[email-masked]>
Date: Wed, 09 Aug 2006 13:49:51 -0700

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

---

From: Roch Guerin <[email-masked]>
Date: Wed, 09 Aug 2006 17:08:23 -0400

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

---

From: Erblichs <[email-masked]>
Date: Wed, 09 Aug 2006 15:12:35 -0700

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

---

From: Dave Katz <[email-masked]>
Date: Wed, 9 Aug 2006 17:54:01 -0600

> 	than we can improve by about 40%.

This is all *extremely* dependent on hardware architecture, and  
further makes the assumption that the largest component of time is  
the memory access speed, which is very unlikely.  For the  
architectures I'm familiar with, updating the forwarding table is  
*much* more expensive than tinkering with internal OSPF stuff, and  
that has *nothing* to do with memory speed.

> 	chance that a improvent elsewhere would be more beneficial.

You're further making an assumption that reducing the overall  
instruction count over time is (a) beneficial, and (b) worth adding  
system complexity for.  Both are debatable and lie at the heart of  
system design.

You seem to be making a common mistake, which is looking at a small  
piece of the puzzle and trying to optimize that, while ignoring the  
cost of doing so in reliability and stability.  Taking your earlier  
example, where you wish to switch the forwarding table as fast as  
possible in the face of a failure, you have to take a look at the  
entire time budget between the event causing the problem (the backhoe  
cuts the fiber) and the restoral time.  The cost of doing a full SPF  
is likely to be a small fraction of this process, and the gains in  
optimizing the process will be a small fraction of that small  
fraction.  If you can get the time budget for all the rest of this so  
that it doesn't overwhelm the cost of a full SPF versus some kind of  
shortcut, then it's time to start talking about gains in route  
calcuation.

--Dave

---

From: Curtis Villamizar <[email-masked]>
Date: Wed, 09 Aug 2006 21:56:05 -0400

> 	table memory is 4x faster than routing table memory,

Nice try but ...

The forwarding memory is on another card in a reasonably big router
and therefore the information has to be trasferred from one processor
to another and then installed in the forwarding memory.

Also the forwarding memory is primarily used for forwarding and in a
big busy router not too many cycles are left over for the writes that
update the forwarding memory due to the reads that are occurring
concurrently.  In some architectures this is minimized.  For example,
some may use memory caching techniques others dual memory banks, etc.

But perhaps the biggest factor is that the few hundred or few thousand
IGP routes are the basis for BGP next hops so after they are computed
the few 100,000 BGP routes and forwarding entries are mapped onto the
SPF results.  Since there are usually more than 100 times as many BGP
routes as IGP routes doubling the speed of the SPF has no effect.

In any case, Dave is right.  The SPF typically takes far less time
than the things that happen as a result of the SPF.

Curtis

ps - OTOH the speed of the MPLS/TE CSPF is very significant.

---

From: Erblichs <[email-masked]>
Date: Fri, 11 Aug 2006 13:40:08 -0700

Curtis Villamizar and Mr Katz,

	First, let me state as I did earlier, I do feel more resources
	dealing with handling of Updates pkts containing refresh age
	LSAs WOULD yield a higher benefit. And since we are not able
	to speed up a REMOTE router's execution of of various tasks, we
	need to concentrate on our on local tasks to allow US to LOCALLY
	converge ASAP.

	But, we are in this forwarding table vs OSPF routing table
	costs, benefit analysis..

	Lets see if we agree on these things.

	1) Most LSAs recieved are just age refresh LSAs, thus they
	   have no effect on SPF calcs.

	2) Most SPF calcs do not result in a lower cost route or
	   in some implementations a additional equal cost route.

	3) Even if a OSPF routing table will yield a better cost
	   route than earlier in time, due to administrative
	   distances that newer cost, may not still be used.

	   Then the forwarding table mods are rarely even done!
	   So, why would you want to spend time to decrease the
	   latency of a operation on such a infrequent event?????

	If subsec hellos or equivalent operation was used, I would
	first verify that nbr lookups are efficent..

	The freq/repeativeness of a operation, if speeded up, should
	yield the best results..

	So, if we aggregate the number of repeativeness operations, we
	need to do 1 lookup per recived LSA within our routing table.
	Most of these will result in age refreshes. So, first, the
	LSA lookup is stressed the most. 

	Then if we had a extremely fast SPF type calcs based on different
	LSA types / triggers, we COULD re-run repetive calcs withoout forcing
	a delay. A delay is standand in our industry. However, if we agree
	with #2 and #3, then the only reason for the delay is due to slower
	SPF calcs. I agree some minimal delay is necessary to verify that
	all new LSAs within a single Update, given that a full ajacency has
	already been established, should be implemented.

	Lastly, bringing back up the forwarding table. The table COULD be
	considered somewhat like a cache. Specific atomic operations are
normally
	implimented because of single change entries. A operation could
	simply Invalidate an entry. This is a single small amount of data that
	needs to be transfered and even slow PCI buses are capable of handling
	a infrequent data with minimal latency. Most of this is done in
	hardware. Sorry, it is a don't care whether their are multiple readers
	for a entry if that entry needs to be invalidated or updated. We don't
	wait for the readers to finish. We need to pre-empt them NOW.

	Thus, given appropriate resouces, I would creare a set of equal LM
Bench
	micro benchmarks, against the routing table and identify what items are
	given higher priorities. I would not be surprised if these items had
	not already been given quite a bit of fine tuning..

	The only major issues are the best case versus worse case numbers,
	and whether those best case numbers can be improved while not
	increasing the worse case numbers.

	Lastly, the assumption is whether BGP is in the environment? If it is,
	IMO TCP would be the limiting factor. TCP will not allow a large burst
	of data on a periodiclly idle connection. Most implmentations will fall
	into a slow start methodology. This is the same problem with LDP even
	when a path has been established with a specified bandwidth. TCP most
	likely will initially get in the way and only after a sustained number
	of segments transmitted will it allow the bandwidth to increase 1
	segment per round-trip-time (rtt). This is known as the congestion
	avoidance (CA) phase.

	Mitchell Erblich
	
	-------------------

---

From: Dave Katz <[email-masked]>
Date: Fri, 11 Aug 2006 16:16:55 -0600

Rather than dragging this on any further, I'll just restate my basic  
point, and then drop it, which is that optimization must be viewed  
holistically, at a system-wide (and network-wide) level.

The fact is that the folks implementing the most widely-used protocol  
code choose their optimizations carefully.  There is a cost to every  
optimization, in the time and effort (and money) to do it, and in the  
additional complexity that inevitably comes with it, which impacts  
stability and maintainability.

There are obvious, easy optimizations (don't run SPF when a leaf node  
changes, don't run SPF if you know that the LSA contents didn't  
change, etc.) that everybody does.  However, when you get into the  
more arcane stuff (like partial SPFs and the like) where the code is  
decidedly nontrivial and the systemic benefits are marginal, it  
becomes much more murky.  In the case of large routers, where the  
forwarding engine is typically somewhat decoupled from the route  
engine, the value such optimizations is marginal indeed.

I'm happier, and my customers are happier, when I can give them a box  
that works and is stable and doesn't break when the code gets  
changed.  Could I shave cycles off of the process?  Absolutely.  Do I  
care?  No, because I'm not in any danger of running out of cycles,  
and the benefit of shaving those cycles is low, and I worry about  
optimizing the cases that really *do* matter.  This is what's known  
as "engineering."

--Dave

---

From: "Tony Li" <[email-masked]>
Date: Fri, 11 Aug 2006 15:28:02 -0700

> This is what's known as "engineering."

And the converse is known as "pointless micro-optimization".

;-)

Tony