The Complete and Partial SPF in IS-IS


In the previous post I explained how the SPF algorithm works and how its used in the link state routing protocols. Click here to know the difference between SPF run for OSPF and IS-IS.

After the SPF run, IS-IS would have an SPF tree with the shortest path to reach each Intermediate System in its level. Fair enough – but how do we determine the IP networks that we can reach?

We earlier saw that at each step of the algorithm, the TENT is examined, and the node with the least cost from the root node is moved into PATHS. When a node is placed in PATHS, all IP prefixes/networks advertised by it are installed in the IS-IS Routing Information Base (RIB) with the corresponding metric and next hop. The directly connected IS-IS neighbors of the node that just made it into PATHS are then added to TENT if they are not already there and their associated costs adjusted accordingly, for the next selection.

The SPF tree thus computed considers the Intermediate Systems as nodes of the graph and the IP addresses advertised by these as the leaves, hanging off the nodes. Thus, the entire shortest path tree in IS-IS does not need to be recomputed if the network changes involved are only related to IP prefixes. Instead, the router can run a partial computation to find an alternative IP prefix if one exists – this partial run is called the partial SPF. More details here and here.

The network topology is computed and determined by the adjacencies advertised in the IS-IS LSPs. We already know that a full SPF is only required when the network topology changes. This implies that only a loss of an IS-IS adjacency would trigger a full SPF. To cite an example, when a point-to-point link goes down, the router loses its adjacency with the neighbor at the other end. This signals a change in topology and, a full SPF is scheduled. OTOH, when a route redistributed from a different routing protocol or a level 2 route leaked into the level 1 route goes away, then it does not bring about any topology change. Because the IP prefixes are only the leaves of the SPF tree, and this does not flag a change in network topology, only the partial route computation (PRC) is run to find an alternative path, if one exists.

Advertisements

3 thoughts on “The Complete and Partial SPF in IS-IS

  1. I’ve just found out your blog and I’m loving it. Thanks for this cool explanation. Theoretically, the SPF of OSPF could be able to do the same as long as they consider the router-id as just router-id and not a “IP” which lead to that router, therefore the router-id will just be literally a router-id and all prefixes will be just leaves like IS-IS. It is quite tricky though to implement, but it is possible.

    Thanks again, much appreciate.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s