Path Calculation

MPLS TE uses the Constrained Shortest Path First (CSPF) algorithm to calculate the optimal path to a node. CSPF was developed based on shortest path first (SPF).

Elements for CSPF Calculation

CSPF calculation depends on the following factors:

Constraints for LSP setup, including the LSP bandwidth, explicit path, setup/holding priority, and affinity attribute, all of which are configured on the ingress node
Traffic engineering database (TEDB)

A TEDB can be generated only when OSPF TE or IS-IS TE is configured. On an IGP TE-incapable network, CR-LSPs are established based on IGP routes, but not calculated using CSPF.

CSPF Calculation Process

To find the shortest path to the destination, CSPF excludes the links whose attributes do not meet LSP setup constraints in the TEDB and then calculates the metrics of other paths using the SPF algorithm.

If both OSPF TE and IS-IS TE are deployed, CSPF uses the OSPF TEDB to calculate a CR-LSP. If a CR-LSP is calculated using the OSPF TEDB, CSPF does not use the IS-IS TEDB. If no CR-LSP is calculated using the OSPF TEDB, CSPF uses the IS-IS TEDB to calculate a CR-LSP.

Whether OSPF TEDB or IS-IS TEDB is used first in the CSPF calculation is determined by the administrator.

If there are multiple shortest paths with the same metric, CSPF uses a tie-breaking policy to select one of them. The following tie-breaking policies are available:

Most-fill: selects the link with the highest proportion of used bandwidth to the maximum reservable bandwidth. This policy uses the full bandwidth of a link.
Least-fill: selects the link with the lowest proportion of used bandwidth to the maximum reservable bandwidth. This policy uses consistent bandwidth resources on links.
Random: selects a random path among equal-metric paths. This policy sets LSPs consistently over links, regardless of bandwidth distribution.

When several links have the same proportion of used bandwidth to the maximum reservable bandwidth, CSPF selects the link discovered first, irrespective of most-fill or least-fill.

Figure 1 shows an example of CSPF calculation. Figure 1 shows the color and bandwidth of some links. The other links are black and have a bandwidth of 100 Mbit/s. A path to LSRE needs to be set up on the network and must pass through LSRH, with a bandwidth of 80 Mbit/s and an affinity attribute of black. According to the constraints, CSPF excludes the blue links, 50 Mbit/s links, and links not connected to LSRH.

Figure 1 Excluding links

After excluding unqualified links, CSPF uses the SPF algorithm to calculate the path. Figure 2 shows the calculation result.

Figure 2 CSPF calculation result

Differences Between CSPF and SPF

CSPF is specific to MPLS TE path calculation and differs from SPF in the following aspects:

CSPF only calculates the shortest path from an ingress node to an egress node, while SPF calculates the shortest path from a node to all the other nodes on a network.
CSPF uses path constraints such as link bandwidth, link attributes, and affinity attributes as metrics, while SPF simply uses link costs as metrics.
CSPF does not support load balancing and uses tie-breaking policies to determine a path if multiple paths have the same metric.