Question about OSPF's incremental SPF

[onemanarmy]

Hi all from Cisco Community,

I'm doing a research on Cisco incremental SPF. So far I know that there is Full SPF and Partial SPF (Which is run when type 3, 4, 5, or 7 LSAs is received -- this actually is the incremental SPF mention in RFC 2328). However, some Cisco IOS support a feature known as Incremental SPF (iSPF for short), configured by:

router ospf id

ispf

I've searched around for quite a bit and haven't found anywhere that explain the exact process (in which how LSA is evaluated, the process flow etc.). Would anyone kindly point me to the appropriate document? (I've also try and read the debug log but it doesn't make much sense to me)

Thanks in advance!

[paolo bevilacqua]

Which kind of document are you looking for ? Cisco doesn't disclose their code internals unless necessary, so if you want to enable the feature, you have to rely on what the public documentation says, in this case:

OSPF uses Dijkstra's SPF algorithm to compute the shortest path tree  (SPT). During the computation of the SPT, the shortest path to each node  is discovered. The topology tree is used to populate the routing table  with routes to IP networks. When changes to a Type-1 or Type-2  link-state advertisement (LSA) occur in an area, the entire SPT is  recomputed. In many cases, the entire SPT need not be recomputed because  most of the tree remains unchanged. Incremental SPF allows the system  to recompute only the affected part of the tree. Recomputing only a  portion of the tree rather than the entire tree results in faster OSPF  convergence and saves CPU resources. Note that if the change to a Type-1  or Type-2 LSA occurs in the calculating router itself, then the full  SPT is performed.

Incremental SPF is scheduled in the same way as the full SPF. Routers  enabled with incremental SPF and routers not enabled with incremental  SPF can function in the same internetwork.

[onemanarmy]

Thanks for the reply,

I'm looking for an explanation of what steps is taken in incremental SPF.

For example, you can partly refer to RFC 2328 (http://tools.ietf.org/html/rfc2328#page-160) to know what are the steps of a full SPF Algorithm. In this case, I'd like to know how the affected part of the tree is found and recompute, etc.

Cisco does include the process in their debug mode (debug ip ospf spf), but it would be really hard to get the concept from there, and it's hard to get an overview and all.

Is there any document (Cisco or non-Cisco) that thoroughly explain the process? (Not code internals but only the process in more details)

Regards

[Peter Paluch · Accepted solution]

Hello,

Information about the incremental SPF are quite rare, unfortunately. One of the better articles can be found here:

http://blog.ine.com/2009/12/31/tuning-ospf-performance/#more-3213

The article seems to suggest that the incremental SPF has been described in an semiannual report by Eric Rosen et al. - it can be found here (requires an access to ACM portal - I can download the document for you if you are interested).

http://portal.acm.org/citation.cfm?id=205453&dl=ACM&coll=DL&CFID=108592207&CFTOKEN=20336747

Best regards,

Peter

[onemanarmy]

Hello Peter,

I've already read the article on ine.com. I'll be very grateful if you can download the document from ACM. Please do.

Please post it here (if it's legal) or please email me the document.

Thanks again.

Regards,

N.

[Peter Paluch · Accepted solution]

Hello,

I've sent you the e-mail. Also, I've found an apparently Cisco-authored presentation at the ripe.net that also talks about the incremental SPF:

http://www.ripe.net/ripe/meetings/ripe-41/presentations/eof-isis/sld049.html

Best regards,

Peter

[onemanarmy]

Hello,

Thank you. This helps me a lot!

Regards,

N.

[jeffreyfxzh]

Hello Peter,

I'm also doing a research on Cisco incremental SPF , as you said information about the incremental SPF are quite rare, would you please  email me the document?

Tanks a lot.

Regards.

[Peter Paluch]

Hello,

Please contact me via e-mail - you can find my address in my profile.

Best regards,

Peter

[Peter Paluch]

To all who may be interested,

The presentation at the RIPE has moved to a new URL:

http://meetings.ripe.net/ripe-41/presentations/eof-isis/index.html

The iSPF part starts at

http://meetings.ripe.net/ripe-41/presentations/eof-isis/sld049.html

Best regards,

Peter