Variations of SPF

In this article we are going to talk about different variation of SPF (Shortest Path First).

Dijkstra’s SPF is the algorithm that Link State Routing Protocols such as OSPF and IS-IS are using.

It has many variations which we will cover them here:

CSPF (Constraint Based SPF)

CSPF is being used in Traffic Engineering Dynamic Path calculation, the Protocols such as RSVP and Segment-Routing (In SR-TE) are considering some extra stuff like: Affinity (Link Coloring), Traffic-Engineering Metric, Available Bandwidth and etc… in SPF calculation.

The SPF itself is only considering the Link Costs along the path to reach to some node (of course it tries to find the shortest path with least cumulative metric). but in the case of CSPF, the algorithm needs to get more information involved in the calculations, as an example: Find the Shortest Path that excludes the links which are colored RED (It is an example, in fact we will use an Affinity value instead of configuring a color name like: RED, GREEN, GOLD, etc… ).

RSPF (Reverse SPF)

RSPF or Reverse SPF is another variation of SPF.

In the Normal SPF, the node which is running the Dijkstra algorithm is considering itself (The Local Node itself) as the Root of the Tree (Because the end goal of running this algorithm is to build a Tree structure, and it is obvious that we should have a Root node).

In the RSPF (Reverse SPF), the node which is running the SPF is considering a Remote Node as the Root of the Tree, in other words: The node is doing the calculation from another node’s Point Of View.

You may ask which technologies are using RSPF?

Before answering this question you should consider this requirement: To run RSPF you have to have the Topological view of your network (Yes! Link State Database is needed, you have no choice but to use OSPF or IS-IS).

These are the technologies which are using the RSPF:

• ORR (Optimal Route Reflection) feature on a BGP Route-Reflector

• FRR (Fast Reroute) to find an LFA (Loop Free Alternate)/Remote LFA/TI-LFA in Segment-Routing

Note: To achieve FRR with EIGRP, there is another approache which is beyond the topics of this article (Refer to Feasible Successor).

iSPF (Incremental SPF)

This kind of SPF seems to be beneficial at the first glance but it is not!

Imagine we have this kind of topology:

In the above topology if some link fails which is being considered as a transit link and impacts the entire topology (or the node graph), the full SPF shoud run (As an example: Gig2 of CSR1000v-4).

But in the case of Link Gi0/0/0/1 of XRv900-1 failure, we can do the calculation only for that part, in other words the SPF calculation can be done starting from CSR1000v-2 towards the XRv9000-1 (The leaf node). the reason is: Link Gi0/0/0/1 failure has not made a major topology change, it was just a simple change in some part of our topology.

This feature seems beneficial, but according to testings (as an example by: Juniper Networks) it does not worth the resource consumption which is required on a Router and also not bringing much value for us, that is why, ISPF has never been implemented on Junos (But Cisco IOS/IOS-XE) supports it.

PRC (Partial Route Calculation), sometimes called PSPF

This type of calculation is related to the prefixes or routes.

Imagine XRv9000-1 is advertinsing a prefix into the OSPF (1.1.1.1/32), and it is a connected route, in the Case of OSPFv2, that prefix is being carried inside the LSA Type 1 of XRv9000-1. Let’s say: that device changes the metric of that prefix or even removes that prefix, you can realize that: The Topology itself is not changed, the change only happened to the route, guess what happens?!

With the Partial Route Calculation enabled, the device should only compare the Updated (The new) LSA Type 1 with the Historical (The old) LSA, and compare them with each other, it realizes that the change was only on a prefix not a link, as a result: It is more optimal to do a Partial Route Calculation than running a Full SPF.

In the above explanation we have mentioned: OSPFv2, in this version of OSPF, the prefixes are being carried inside the LSA Type 1, so the device doing PRC should keep the Historical (The old) LSA for comparison purpose, which is not efficient, and the reson is: The device should compare all Link State information of LSA Type 1 Advertisement including the Topological info and also Prefix info. but in the Case of Summary (LSA Type 3) and External (LSA Type 5 and 7) Routes, it is more efficient, the router is just dealing with prefixes.

In the OSPFv3, the protocol inventors have made a major changes specially for prefix advertisement: The Prefix advertisement is seperated from Link State Topological information advertisement, so you can guess: CSPF is more happier with OSPFv3!

NOTE: IS-IS from the day zero has been advertising Topological and prefix information separately.