Using Labeled-Switched Paths to Augment SPF to Compute IGP Shortcuts
Link-state protocols, such as OSPF and IS-IS, use the shortest-path-first (SPF) algorithm to compute the shortest-path tree to all nodes in the network. The results of such computations can be represented by the destination node, next-hop address, and output interface, where the output interface is a physical interface. Label-switched paths (LSPs) can be used to augment the SPF algorithm.
IGP typically performs two independent computations. The first is performed without considering any LSP. The result of the computation is stored in the inet.0 table. This step is no different from traditional SPF computations and is always performed even if IGP shortcut is disabled.
The second computation is performed considering only LSPs as a logical interface. Each LSP’s egress router is considered. The list of destinations whose shortest path traverses the egress router (established during the first computation) is placed in the inet.3 routing table. These destinations are given the egress router of the LSP as a next hop, enabling BGP on the local router to use these LSPs to access BGP next hops beyond the egress router. Normally, BGP can use only LSPs that terminate at the BGP next hop.
As an illustration, begin with a typical SPF tree (see Figure 1).
If an LSP connects Router A to Router D and if IGP shortcuts are enabled on Router A, you might have the SPF tree shown in Figure 2.
Note that Router D is now reachable through LSP A–D.
When computing the shortest path to reach Router D, Router A has two choices:
Use IGP path A–B–D.
Use LSP A–D.
Router A decides between the two choices by comparing the IGP metrics for path A–B–D with the LSP metrics for LSP A–D. If the IGP metric is lower, path A–B–D is chosen (Figure 1). This path A–B–D is valid only when node D is not the tail-end of the LSP. If node D is the tail end of the LSP, even if the LSP metric is lower or both IGP and LSP metrics are equal, LSP A–D is used (Figure 2).
Note that Router E is reachable through LSP A–D and Router F will take the IGP path.