LSP Computation

The Constrained Shortest Path First (CSPF) algorithm is an advanced form of the shortest-path-first (SPF) algorithm used in OSPF and IS-IS route computations. CSPF is used in computing paths for LSPs that are subject to multiple constraints. When computing paths for LSPs, CSPF considers not only the topology of the network, but also the attributes of the LSP and the links, and it attempts to minimize congestion by intelligently balancing the network load.

The constraints that CSPF considers include:

• LSP attributes

  • Administrative groups (that is, link color requirements)

  • Bandwidth requirements

  • Explicit route (strict or loose)

  • Hop limitations

  • Priority (setup and hold)

• Link attributes

  • Administrative groups (that is, link colors assigned to the link)

  • Reservable bandwidth of the links (static bandwidth minus the currently reserved bandwidth)

The data that CSPF considers comes from the following sources:

• Traffic engineering database—Provides CSPF with up-to-date topology information, the current reservable bandwidth of links, and the link colors. For the CSPF algorithm to perform its computations, a link-state IGP (such as OSPF or IS-IS) with special extensions is needed. For CSPF to be effective, the link-state IGP on all routers must support the special extensions. While building the topology database, the extended IGP must take into consideration the current LSPs and must flood the route information everywhere. Because changes in the reserved link bandwidth and link color cause database updates, an extended IGP tends to flood more frequently than a normal IGP. See Figure 1 for a diagram of the relationships between these components.

• Currently active LSPs—Includes all the LSPs that should originate from the router and their current operational status (up, down, or timeout).

Figure 1: CSPF Computation Process

This section discusses the following topics:

• How CSPF Selects a Path

• CSPF Path Selection Tie-Breaking

• Computing CSPF Paths Offline

To select a path, CSPF follows certain rules. The rules are as follows:

1. Computes LSPs one at a time, beginning with the highest priority LSP (the one with the lowest setup priority value). Among LSPs of equal priority, CSPF services the LSPs in alphabetical order of the LSP names.

2. Prunes the traffic engineering database of all the links that are not full duplex and do not have sufficient reservable bandwidth.

3. If the LSP configuration includes the include statement, prunes all links that do not share any included colors.

4. If the LSP configuration includes the exclude statement, prunes all links that contain excluded colors. If the link does not have a color, it is accepted.

5. If several paths have equal cost, chooses the one whose last-hop address is the same as the LSP’s destination.

6. If several equal cost paths remain, selects the one with the fewest number of hops.

7. If several equal-cost paths remain, applies the CSPF load-balancing rule configured on the LSP (least fill, most fill, or random).

CSPF finds the shortest path toward the LSP’s egress router, taking into account explicit-path constraints. For example, if the path must pass through Router A, two separate SPFs are computed, one from the ingress router to Router A, the other from Router A to the egress router. All CSPF rules are applied to both computations.

If more than one path is still available after the CSPF rules (How CSPF Selects a Path) have been applied, a tie-breaking rule is applied to choose the path for the LSP. The rule used depends on the configuration. There are three tie-breaking rules:

• Random—One of the remaining paths is picked at random. This rule tends to place an equal number of LSPs on each link, regardless of the available bandwidth ratio. This is the default behavior.

• Least fill—The path with the largest minimum available bandwidth ratio is preferred. This rule tries to equalize the reservation on each link.

• Most fill—The path with the smallest minimum available bandwidth ratio is preferred. This rule tries to fill a link before moving on to alternative links.

The following definitions describe how a figure for minimum available bandwidth ratio is derived for the least fill and most fill rules:

• Reservable bandwidth = bandwidth of link x subscription factor of link

• Available bandwidth = reservable bandwidth – (sum of the bandwidths of the LSPs traversing the link)

• Available bandwidth ratio = available bandwidth/reservable bandwidth

• Minimum available bandwidth ratio (for a path) = the smallest available bandwidth ratio of the links in a path

The Junos OS provides online, real-time CSPF computation only; each router performs CSPF calculations independent of the other routers in the network. These calculations are based on currently available topology information—information that is usually recent, but not completely accurate. LSP placements are locally optimized, based on current network status.

To optimize links globally across the network, you can use an offline tool to perform the CSPF calculations and determine the paths for the LSPs. You can create such a tool yourself, or you can modify an existing network design tool to perform these calculations. You should run the tool periodically (daily or weekly) and download the results into the router. An offline tool should take the following into account when performing the optimized calculations:

• All the LSP’s requirements

• All link attributes

• Complete network topology

When selecting a path for an LSP, CSPF uses a tie-breaking process if there are several equal-cost paths. For information about how CSPF selects a path, see How CSPF Selects a Path.

You can configure one of the following statements (you can only configure one of these statements at a time) to alter the behavior of CSPF tie-breaking:

• By default, a random tie-breaking rule for CSPF is used to select a path from the set of equal-cost paths. However, you can also explicitly configure this behvior using the random statement:

• To prefer the path with the least-utilized links, include the least-fill statement:

• To prefer the path with the most-utilized links, include the most-fill statement:

You can include each of these statements at the following hierarchy levels:

• [edit protocols mpls label-switched-path lsp-name]

• [edit logical-systems logical-system-name protocols mpls label-switched-path lsp-name]

If the IGP is a link-state protocol (such as IS-IS or OSPF) and supports extensions that allow the current bandwidth reservation on each router’s link to be reported, constrained-path LSPs are computed by default.

The Junos implementations of IS-IS and OSPF include the extensions that support constrained-path LSP computation.

• IS-IS—These extensions are enabled by default. To disable this support, include the disable statement at the [edit protocols isis traffic-engineering] hierarchy level, as discussed in the Junos OS Routing Protocols Library for Routing Devices.

• OSPF—These extensions are disabled by default. To enable this support, include the traffic-engineering statement in the configurations of all routers running OSPF, as described in the Junos OS Routing Protocols Library for Routing Devices.

If IS-IS is enabled on a router or you enable OSPF traffic engineering extensions, MPLS performs the constrained-path LSP computation by default. For information about how constrained-path LSP computation works, see Constrained-Path LSP Computation.

Constrained-path LSPs have a greater chance of being established quickly and successfully for the following reasons:

• The LSP computation takes into account the current bandwidth reservation.

• Constrained-path LSPs reroute themselves away from node failures and congestion.

When constrained-path LSP computation is enabled, you can configure the LSP so that it is periodically reoptimized, as described in Optimizing Signaled LSPs.

When an LSP is being established or when an existing LSP fails, the constrained-path LSP computation is repeated periodically at the interval specified by the retry timer until the LSP is set up successfully. Once the LSP is set up, no recomputation is done. For more information about the retry timer, see Configuring the Connection Between Ingress and Egress Routers.

By default, constrained-path LSP computation is enabled. You might want to disable constrained-path LSP computation when all nodes do not support the necessary traffic engineering extensions. To disable constrained-path LSP computation, include the no-cspf statement:

For a list of hierarchy levels at which you can include this statement, see the statement summary section for this statement.

If you disable constrained-path LSP computation on LSPs by configuring the no-cspf statement and then attempt to advertise other LSPs with lower metrics than the IGPs from this router in either IS-IS or OSPF, new LSPs cannot be established.