Skip to main content
  1. Network Articles/
  2. IS-IS Articles/

IS-IS SPF Computation and Route Selection

Table of Contents

IS-IS SPF Computation and Route Selection

An IS-IS router collects LSPs from its neighbours and builds a link state database (LSDB). The LSDB is a map of the network, though, not a routing table. Turning that map into “which neighbour do I hand this destination to” is the job of the Decision Process, and SPF computation is what it does.

ISO/IEC 10589:2002 defines that process in clause 7.2. This article works through what SPF takes in and what it produces, why the cost of a broadcast subnetwork is counted only once, how many equal-cost paths survive, and how IOS XR runs a different computation for a topology change than for a prefix change, checking each against the standard and against real devices.

How the LSDB itself is built is covered in IS-IS LSPs and the Link State Database and IS-IS Flooding and LSDB Synchronisation.

What the Decision Process takes in and puts out

Clause 7.2.1 keeps this simple.

DirectionContents
InputThe LSDB (handed over by the Update Process), and notification that a link has changed
OutputForwarding databases, one per routeing metric and per level

The output being a forwarding database rather than a list of paths is the point. Clause 7.2.6.1 states that the algorithm “determines only the next hop, not the complete path” a PDU will take. An IS-IS router decides only its own next step; the router after it makes the same computation for the step after that.

Two properties have to hold for that to work, and 7.2.6.1 names them:

  • every IS in the domain converges on identical topology information, and
  • every IS generates the same set of routes from the same input

Break the first and you get loops. That is why so much care goes into keeping LSDBs identical. To secure the second, the standard specifies even the pruning of equal-cost paths deterministically, as below.

The computation runs separately for each level and each metric type (7.2.6.4). A router active at both levels runs SPF independently for each.

Which paths may be used

Clause 7.2.6.2 sorts the paths SPF finds into three kinds.

KindContents
Minimum cost pathA single path with the lowest metric sum
Equal minimum cost pathsSeveral tied at the lowest metric sum
Downstream pathsPaths that bring a PDU closer to the destination than the local system

Anything else is illegal and must not be used. So is any path whose metric sum exceeds the architectural constant MaxPathMetric (1023).

A link counts only if both ends report it

This is the two-way connectivity check of 7.2.8.2.

The Decision Process shall not utilise a link between two Intermediate Systems unless both ISs report the link.

A link that one router claims and the other does not is left out of the computation, so a malfunctioning router advertising a neighbour that is not there cannot attract traffic. Clause 7.2.4 adds that an IS which considers a link “down” must not mention it in its LSPs at all.

Reporting a link only means having a defined value for at least the default metric, and the two ends may report different values. When they do, the route is asymmetric.

A link at the maximum metric is excluded

RFC 5305, which defines wide metrics, gives the metric a second use.

If a link is advertised with the maximum link metric (2^24 - 1), this link MUST NOT be considered during the normal SPF computation.

The 24-bit ceiling of 16777215 does not mean “very expensive” but “do not use this link in SPF”. The adjacency stays up while the link alone leaves the computation, which is how traffic is drained from a link before maintenance. IOS XR configures it as metric maximum.

The cost of a broadcast subnetwork is counted once

A broadcast LAN is not treated as a fully connected mesh but as a pseudonode, one imaginary system with a link to each attached router (7.2.3). Each attached router reports only its link to the pseudonode, and the DIS builds the pseudonode’s LSP on its behalf.

In that LSP, every link from the pseudonode out to the routers carries a metric of zero. The standard gives the reason in a footnote:

They are set to zero metric values since they have already been assigned metrics by the link to the pseudonode. Assigning a non-zero metric in the pseudonode LSP would have the effect of doubling the actual value.

Crossing one LAN therefore costs the entry metric and nothing more, however many routers sit on it. How the DIS and the pseudonode are chosen is covered in IS-IS DIS and Pseudonodes.

How many equal-cost paths survive

When several equal-cost paths exist, the management parameter maximumPathSplits decides how many reach the forwarding database. The standard’s default is 2.

Anything beyond that is pruned in the order set by 7.2.7. The ordering is fully deterministic, so that implementations do not diverge.

OrderCriterion
1Adjacency type (End system and reachable address prefix adjacencies are kept first)
2Lower metric sum
3Lower neighbour ID
4Lower circuit ID
5Lower LAN address

IOS XR changes the count with maximum-paths.

Full SPF and partial computation

This part belongs to the implementation. The standard writes the Decision Process as one procedure, but implementations scale the work to the kind of change. IOS XR uses two.

KindWhen it runsWhat it does
FSPF (full SPF)The topology changed: an adjacency, a link, a metric or a node came or wentRebuilds the shortest path tree
PRC (partial route calculation)The topology is unchanged and only the advertised prefixes movedLeaves the tree alone and reattaches prefixes

Loop freedom needs every router to hold the same tree; a change that cannot alter the shape of the tree does not require rebuilding it. Which one ran is recorded in show isis spf-log.

An FSPF also runs periodically, logged as PERIODIC, even with nothing changed.

Verification on real devices

Test environment

R1, R2 and R3 share one broadcast LAN, and R2 and R3 each run a point-to-point link to R4. From R1, R4 sits at cost 20 through either R2 or R3 (10 across the LAN plus 10 across the point-to-point link). All four are level-2-only in area 49.0001.

RouterNETLo0Links
R149.0001.0010.0100.1001.001.1.1.1/32Gi0/0/0/0 10.1.0.1 (LAN)
R249.0001.0020.0200.2002.002.2.2.2/32Gi0/0/0/0 10.1.0.2 (LAN) / Gi0/0/0/1 10.2.4.2 (p2p)
R349.0001.0030.0300.3003.003.3.3.3/32Gi0/0/0/0 10.1.0.3 (LAN) / Gi0/0/0/1 10.3.4.3 (p2p)
R449.0001.0040.0400.4004.004.4.4.4/32Gi0/0/0/0 10.2.4.4 (p2p) / Gi0/0/0/1 10.3.4.4 (p2p)

The STEPs

STEPOperationWhat it confirms
0Defaults, stable stateTwo equal-cost paths from R1 to R4’s Lo0, and a metric of zero out of the pseudonode
1maximum-paths 1 on R1The two equal-cost paths are cut to one, and which one is kept
2Revert, then set the R2 side of R2 - R4 to metric 20Only the path through R3 remains, and spf-log shows FSPF
3Revert, then set the R2 side to metric maximumThe adjacency stays up while that link leaves the computation
4Add Loopback1 (172.16.4.1/32) on R4spf-log shows PRC, with no full SPF
5Revert everything (final state)Matches STEP 0

STEP 0: the pseudonode’s metric is zero

Start with the defaults. R1’s database:

STEP 0 R1: show isis database detail (the R1, R2 and pseudonode entries)
RP/0/RP0/CPU0:R1#show isis database detail
Thu Sep 10 14:12:25.525 UTC

IS-IS 1 (Level-2) Link State Database
LSPID                 LSP Seq Num  LSP Checksum  LSP Holdtime/Rcvd  ATT/P/OL
R1.00-00            * 0x00000009   0x6235        607  /*            0/0/0
  Area Address:   49.0001
  LSP MTU:        1492
  NLPID:          0xcc
  IP Address:     1.1.1.1
  Hostname:       R1
  Metric: 10         IS-Extended R2.01
  Metric: 0          IP-Extended 1.1.1.1/32
  Metric: 10         IP-Extended 10.1.0.0/24
R2.00-00              0x0000000f   0xa79a        886  /1200         0/0/0
  Area Address:   49.0001
  LSP MTU:        1492
  NLPID:          0xcc
  IP Address:     2.2.2.2
  Hostname:       R2
  Metric: 10         IS-Extended R2.01
  Metric: 10         IS-Extended R4.00
  Metric: 0          IP-Extended 2.2.2.2/32
  Metric: 10         IP-Extended 10.1.0.0/24
  Metric: 10         IP-Extended 10.2.4.0/24
R2.01-00              0x00000008   0x4764        618  /1200         0/0/0
  Metric: 0          IS-Extended R3.00
  Metric: 0          IS-Extended R1.00
  Metric: 0          IS-Extended R2.00

For the LAN, both R1 and R2 report a single link, to the pseudonode: Metric: 10 IS-Extended R2.01. Neither reports the other as a direct neighbour. And all three links the pseudonode R2.01-00 reports carry Metric: 0. Crossing the LAN costs only the 10 to get onto it.

The IS-Extended wording says these are advertised in TLV 22, the wide-metric form. The TLVs are covered in The Main IS-IS TLVs.

The result is two paths from R1 to R4.

STEP 0 R1: show isis topology
RP/0/RP0/CPU0:R1#show isis topology
Thu Sep 10 14:12:25.701 UTC

IS-IS 1 paths to IPv4 Unicast (Level-2) routers
System Id          Metric    Next-Hop           Interface       SNPA          
R1                 --      
R2                 10        R2                 Gi0/0/0/0       5254.00bc.1d81
R3                 10        R3                 Gi0/0/0/0       5254.0063.11aa
R4                 20        R2                 Gi0/0/0/0       5254.00bc.1d81
R4                 20        R3                 Gi0/0/0/0       5254.0063.11aa

Through R2 and through R3 both come to metric 20 (10 across the LAN plus 10 across the point-to-point link). R1 pays 10 to enter the LAN, R2 and R3 pay 0 to leave the pseudonode, and the point-to-point hop to R4 is 10. Nothing is counted twice, even with three routers on the LAN.

Both paths reach the routing table.

STEP 0 R1: show route isis
RP/0/RP0/CPU0:R1#show route isis
Thu Sep 10 14:12:24.538 UTC

i L2 2.2.2.2/32 [115/10] via 10.1.0.2, 00:09:40, GigabitEthernet0/0/0/0
i L2 3.3.3.3/32 [115/10] via 10.1.0.3, 00:09:28, GigabitEthernet0/0/0/0
i L2 4.4.4.4/32 [115/20] via 10.1.0.2, 00:05:12, GigabitEthernet0/0/0/0
                [115/20] via 10.1.0.3, 00:05:12, GigabitEthernet0/0/0/0
i L2 10.2.4.0/24 [115/20] via 10.1.0.2, 00:05:12, GigabitEthernet0/0/0/0
i L2 10.3.4.0/24 [115/20] via 10.1.0.3, 00:09:28, GigabitEthernet0/0/0/0

STEP 1: pruning the equal-cost paths

maximum-paths 1 was configured on R1.

STEP 1 R1: show route isis
RP/0/RP0/CPU0:R1#show route isis
Thu Sep 10 14:15:26.805 UTC

i L2 2.2.2.2/32 [115/10] via 10.1.0.2, 00:01:33, GigabitEthernet0/0/0/0
i L2 3.3.3.3/32 [115/10] via 10.1.0.3, 00:01:33, GigabitEthernet0/0/0/0
i L2 4.4.4.4/32 [115/20] via 10.1.0.2, 00:01:33, GigabitEthernet0/0/0/0
i L2 10.2.4.0/24 [115/20] via 10.1.0.2, 00:01:32, GigabitEthernet0/0/0/0
i L2 10.3.4.0/24 [115/20] via 10.1.0.3, 00:01:32, GigabitEthernet0/0/0/0

4.4.4.4/32 drops to one path, and the survivor is 10.1.0.2, the one through R2. Of the criteria in 7.2.7, the adjacency type and the metric sum are identical, so the decision falls to the next one: the lower neighbour ID. R2’s system ID is 0020.0200.2002 against R3’s 0030.0300.3003.

show isis topology still lists both paths at this point. The pruning happens not while building the shortest path tree but while assembling the forwarding database (7.2.9).

STEP 2: changing a metric runs a full SPF

maximum-paths was removed and R2’s Gi0/0/0/1 set to metric 20. R4 is then reached only through R3, at metric 20, because the path through R2 comes to 10+20=30. The path through R2 has not disappeared; it has become expensive.

STEP 3: a link at the maximum metric leaves the computation

The same interface was then set to metric maximum. R2’s LSP becomes:

STEP 3 R1: show isis database detail (the R2 entry)
R2.00-00              0x00000011   0xb2a1        1105 /1200         0/0/0
  Area Address:   49.0001
  LSP MTU:        1492
  NLPID:          0xcc
  IP Address:     2.2.2.2
  Hostname:       R2
  Metric: 10         IS-Extended R2.01
  Metric: 16777215   IS-Extended R4.00
  Metric: 0          IP-Extended 2.2.2.2/32
  Metric: 10         IP-Extended 10.1.0.0/24
  Metric: 16777215   IP-Extended 10.2.4.0/24

16777215 is 2^24 - 1, the ceiling of the wide metric. R2’s adjacency has not gone down:

STEP 3 R2: show isis neighbors
RP/0/RP0/CPU0:R2#show isis neighbors
Thu Sep 10 14:22:08.719 UTC

IS-IS 1 neighbors:
System Id      Interface        SNPA           State Holdtime Type IETF-NSF
R1             Gi0/0/0/0        5254.00a6.5d45 Up    28       L2   Capable 
R3             Gi0/0/0/0        5254.0063.11aa Up    22       L2   Capable 
R4             Gi0/0/0/1        *PtoP*         Up    26       L2   Capable 

Total neighbor count: 3

The adjacency to R4 is still Up. It disappears from R1’s topology all the same.

STEP 3 R1: show isis topology
RP/0/RP0/CPU0:R1#show isis topology
Thu Sep 10 14:21:49.063 UTC

IS-IS 1 paths to IPv4 Unicast (Level-2) routers
System Id          Metric    Next-Hop           Interface       SNPA          
R1                 --      
R2                 10        R2                 Gi0/0/0/0       5254.00bc.1d81
R3                 10        R3                 Gi0/0/0/0       5254.0063.11aa
R4                 20        R3                 Gi0/0/0/0       5254.0063.11aa

Where STEP 2 left a path valued at 30, STEP 3 leaves only one way to reach R4 at all, through R3. The link is not expensive; it is excluded, exactly as RFC 5305 requires. That is what lets traffic be steered off a link without dropping the adjacency.

STEP 4: a prefix-only change does not rebuild the tree

The metric was restored and Loopback1 (172.16.4.1/32) added on R4.

STEP 4 R1: show route isis
RP/0/RP0/CPU0:R1#show route isis
Thu Sep 10 14:26:28.189 UTC

i L2 2.2.2.2/32 [115/10] via 10.1.0.2, 00:09:31, GigabitEthernet0/0/0/0
i L2 3.3.3.3/32 [115/10] via 10.1.0.3, 00:09:31, GigabitEthernet0/0/0/0
i L2 4.4.4.4/32 [115/20] via 10.1.0.2, 00:03:11, GigabitEthernet0/0/0/0
                [115/20] via 10.1.0.3, 00:03:11, GigabitEthernet0/0/0/0
i L2 10.2.4.0/24 [115/20] via 10.1.0.2, 00:03:11, GigabitEthernet0/0/0/0
i L2 10.3.4.0/24 [115/20] via 10.1.0.3, 00:09:31, GigabitEthernet0/0/0/0
i L2 172.16.4.1/32 [115/20] via 10.1.0.2, 00:01:35, GigabitEthernet0/0/0/0
                   [115/20] via 10.1.0.3, 00:01:35, GigabitEthernet0/0/0/0

The new prefix arrives over both equal-cost paths. Now the record of the computations:

STEP 5 R1: show isis spf-log (the whole log since boot)
RP/0/RP0/CPU0:R1#show isis spf-log
Thu Sep 10 14:30:22.230 UTC

  IS-IS 1  Level 2  IPv4 Unicast  Route Calculation Log
                                                   Capacity: 210, Size: 37
                    Time Total Trig.
Timestamp    Type   (ms) Nodes Count First Trigger LSP    Triggers
------------ ----- ----- ----- ----- -------------------- ----------------------
--- Thu Sep 10 2026 ---
13:31:30.214  FSPF     0     1     7             R1.00-00 CONFIG NEWNODE NEWLSP OVLSET PREFIXGOOD AREAADDR IPADDR
13:31:32.409  FSPF     0     1     1             R1.00-00 OVLCLR
13:31:35.608   PRC     0     1     1             R1.00-00 PREFIXGOOD
13:32:45.281  FSPF     0     3     3             R2.01-00 NEWNODE NEWLSP LINKGOOD
13:32:54.163  FSPF     0     3     5             R2.00-00 NEWNODE NEWLSP PREFIXGOOD AREAADDR IPADDR
13:32:55.219  FSPF     0     3     2             R2.01-00 LINKGOOD
13:32:56.226  FSPF     2     3     1             R1.00-00 LINKGOOD
13:33:39.049  FSPF     0     4     6             R3.00-00 NEWNODE NEWLSP LINKGOOD PREFIXGOOD AREAADDR IPADDR
13:33:40.010  FSPF     2     4     1             R2.01-00 LINKGOOD
13:34:41.946  FSPF     0     5     5             R4.00-00 NEWNODE NEWLSP PREFIXGOOD AREAADDR IPADDR
13:34:43.072  FSPF     0     5     1             R4.00-00 LINKGOOD
13:34:44.370  FSPF     2     5     2             R2.00-00 LINKGOOD
13:37:53.124  FSPF     2     5     2             R2.00-00 LINKBAD PREFIXBAD
13:39:03.124  FSPF     1     5     2             R2.00-00 LINKGOOD PREFIXGOOD
13:52:41.752  FSPF     0     5    28             R1.00-00 CONFIG DELNODE LSPEXPIRY LINKBAD PREFIXBAD AREAADDR IPADDR
13:52:41.953  FSPF    57     5    28             R1.00-00 CONFIG NEWNODE NEWLSP LINKGOOD PREFIXGOOD AREAADDR IPADDR
13:55:52.259  FSPF     0     5    28             R1.00-00 CONFIG DELNODE LSPEXPIRY LINKBAD PREFIXBAD AREAADDR IPADDR
13:55:52.460  FSPF    49     5    28             R1.00-00 CONFIG NEWNODE NEWLSP LINKGOOD PREFIXGOOD AREAADDR IPADDR
13:56:03.323  FSPF     2     5     2             R2.00-00 LINKBAD PREFIXBAD
13:59:26.324  FSPF     1     5     2             R2.00-00 LINKBAD PREFIXBAD
14:02:08.623  FSPF     2     5     2             R2.00-00 LINKGOOD PREFIXGOOD
14:02:32.912  FSPF     0     5    28             R1.00-00 CONFIG DELNODE LSPEXPIRY LINKBAD PREFIXBAD AREAADDR IPADDR
14:02:33.113  FSPF     0     5    21             R1.00-00 CONFIG NEWNODE NEWLSP LINKGOOD PREFIXGOOD AREAADDR IPADDR
14:02:44.523  FSPF     1     5     3             R2.00-00 LINKGOOD PREFIXGOOD
14:02:55.957  FSPF     2     5     2             R3.00-00 LINKGOOD PREFIXGOOD
14:03:07.293  FSPF     1     5     2             R4.00-00 LINKGOOD PREFIXGOOD
14:05:26.824  FSPF     2     5     2             R2.00-00 LINKBAD PREFIXBAD
14:07:11.723  FSPF     2     5     2             R2.00-00 LINKGOOD PREFIXGOOD
14:13:53.661  FSPF     0     5    28             R1.00-00 CONFIG DELNODE LSPEXPIRY LINKBAD PREFIXBAD AREAADDR IPADDR
14:13:53.862  FSPF    48     5    28             R1.00-00 CONFIG NEWNODE NEWLSP LINKGOOD PREFIXGOOD AREAADDR IPADDR
14:16:56.122  FSPF     0     5    28             R1.00-00 CONFIG DELNODE LSPEXPIRY LINKBAD PREFIXBAD AREAADDR IPADDR
14:16:56.324  FSPF     2     5    28             R1.00-00 CONFIG NEWNODE NEWLSP LINKGOOD PREFIXGOOD AREAADDR IPADDR
14:17:07.575  FSPF    34     5     2             R2.00-00 LINKBAD PREFIXBAD
14:20:14.723  FSPF     1     5     2             R2.00-00 LINKBAD PREFIXBAD
14:23:17.023  FSPF     1     5     2             R2.00-00 LINKGOOD PREFIXGOOD
14:24:52.509   PRC     1     5     1             R4.00-00 PREFIXGOOD
14:28:04.908   PRC     1     5     1             R4.00-00 PREFIXBAD

Everything from 13:31 to 14:12 is the lab coming up and being prepared (switching to wide metrics and so on); the STEP 0 marker is at 14:12:21. Lining the rest up against the operations:

TimeOperationTypeTriggers
14:13:53maximum-paths 1 (STEP 1)FSPF ×2CONFIG
14:16:56maximum-paths removed (STEP 2)FSPF ×2CONFIG
14:17:07metric 20 (STEP 2)FSPFLINKBAD PREFIXBAD
14:20:14metric maximum (STEP 3)FSPFLINKBAD PREFIXBAD
14:23:17back to metric 10 (setting up STEP 4)FSPFLINKGOOD PREFIXGOOD
14:24:52Loopback1 added (STEP 4)PRCPREFIXGOOD
14:28:04Loopback1 removed (STEP 5)PRCPREFIXBAD

Every operation that touched a link or a metric ran a full SPF, while the two that only added or removed a prefix ran PRC. A change that cannot alter the shape of the shortest path tree does not rebuild it.

Note also that a metric change is logged as LINKBAD PREFIXBAD. IOS XR treats a changed value as the old link going away and a new one appearing.

STEP 5: reverting

Loopback1 was removed from both IS-IS and the interface configuration. All four running-config files match STEP 0.

Verification configs and show output

Each STEP was captured from all four routers as four files per router. The verification config is the ..._run.txt (the final state is the one from the last STEP).

FileContents
..._show.txtshow version, show interface description, show route, and the show isis set (interface, neighbors detail, database detail, topology, adjacency-log, spf-log, lsp-log, statistics)
..._log.txtshow logging narrowed to that STEP. A logmsg marker is placed at the start of each STEP and its timestamp passed to show logging start
..._run.txtshow running-config at that STEP (the verification config for that STEP)
..._trace.txtshow isis trace all filtered to the flooding events (UPD_LSP_ACCEPT, UPD_LSP_SET_SRM, UPD_SNP_ENTRY, UPD_CSNP, UPD_PSNP)

STEP 0: Initial state

Routershowsyslogrunning-configtrace
R1showlogruntrace
R2showlogruntrace
R3showlogruntrace
R4showlogruntrace

STEP 1: maximum-paths 1 on R1

Routershowsyslogrunning-configtrace
R1showlogruntrace
R2showlogruntrace
R3showlogruntrace
R4showlogruntrace

STEP 2: Remove maximum-paths, set the R2 side of R2 - R4 to metric 20

Routershowsyslogrunning-configtrace
R1showlogruntrace
R2showlogruntrace
R3showlogruntrace
R4showlogruntrace

STEP 3: Set the R2 side to metric maximum

Routershowsyslogrunning-configtrace
R1showlogruntrace
R2showlogruntrace
R3showlogruntrace
R4showlogruntrace

STEP 4: Back to metric 10, add Loopback1 on R4

Routershowsyslogrunning-configtrace
R1showlogruntrace
R2showlogruntrace
R3showlogruntrace
R4showlogruntrace

STEP 5: Revert everything (final state)

Routershowsyslogrunning-configtrace
R1showlogruntrace
R2showlogruntrace
R3showlogruntrace
R4showlogruntrace

References

StandardTitleSummary
ISO/IEC 10589:2002 (second edition)Intermediate System to Intermediate System intra-domain routeing information exchange protocolThe IS-IS specification itself. This article draws on 7.2.1 for the inputs and outputs of the Decision Process, 7.2.3 for the zero metric out of a pseudonode, 7.2.4 for reporting links, 7.2.6.1 for the algorithm’s premises and for deciding only the next hop, 7.2.6.2 for the kinds of path, 7.2.6.3 for identifying the adjacency, 7.2.6.4 for per-level and per-metric computation, 7.2.7 for pruning equal-cost paths, 7.2.8.2 for the two-way connectivity check, and 7.2.9 for building the forwarding database. Constants come from Table 2 (MaxPathMetric 1023); the default of 2 for maximumPathSplits comes from the management information definitions.
RFC 1195Use of OSI IS-IS for Routing in TCP/IP and Dual EnvironmentsThe extension that carries IP routes.
RFC 5305IS-IS Extensions for Traffic EngineeringWide metrics (24 bits for Extended IS Reachability, 32 for Extended IP Reachability). States that a link advertised with the maximum link metric (2^24 - 1) must not be considered during normal SPF computation.
RFC 7142Reclassification of RFC 1142 to HistoricStates that the document to cite is ISO/IEC 10589:2002, second edition.

Related articles