Shortest Path First (SPF) Calculation in OSPF and ISIS .. !

Both the protocols use Shortest Path First (SPF) algorithm to calculate the best path to all known destinations based on the information in their link state database. The SPF algorithm works by building the shortest path tree from a specific root node to all other nodes in the area and thereby computing the best route to every known destination from that particular source/node.

IS-IS

- SPF for a given level is computed in a single phase by taking all IS-IS LSP's TLV's together.

- IP routing is integrated into IS-IS by adding some new TLVs which carry IP reachability information in the LSPs. All IP networks are considered externals, and they always end up as leaf nodes in the shortest path tree when IS-IS does a SPF run.

- Used narrow (6 bits wide) metrics which helped in some SPF optimization. However such small bits proved insufficient for providing flexibility in designing IS-IS networks and other applications using IS-IS routing (MPLS-TE). "IS-IS extensions for Traffic Engineering" RFC introduced new TLVs which defined wider metrics to be used for IS-IS thus taking away this optimization.

But then CPU are fast these days and there are not many very big networks anyway.

- Performs only the less CPU intensive Partial Route Calculation (PRC) when network events do not affect the basic topology but only the IP prefixes.

OSPF

- SPF is calculated in three phases. The first is the calculation of intra-area routes by building the shortest path tree for each attached area. The second phase calculates the inter-area routes by examining the summary LSAs and the last one examines the AS-External-LSAs to calculate the routes to the external destinations.

- Is built around links, and any IP prefix change in an area will trigger a full SPF.

- Only changes in interarea and external routes result in partial SPF calculations and thus IS-IS's PRC is more pervasive than OSPF's partial SPF. This difference allows IS-IS to be more tolerant of larger single area domains whereas OSPF forces hierarchical designs for relatively smaller networks. However with the route leaking from L2 to L1 incorporated into IS-IS the apparent motivation for keeping large single area domains too goes away.