Theoretical foundations and architecture
CSPF (Constrained Shortest Path First) is an advanced variant of Dijkstra's algorithm executed over the local TED topology graph. Unlike standard SPF, which evaluates exclusively metric sums, CSPF prunes non-compliant links before computing shortest-path trees: 1. Bandwidth Constraints: any link lacking sufficient unreserved bandwidth across the requested priority level is immediately pruned from the calculation. 2. Administrative Groups (Link Affinity / Coloring): every physical core link is tagged with a 32-bit administrative bitmask (e.g., bit 0 = Low-Latency terrestrial fiber, bit 1 = High-Latency satellite). A tunnel specifies its affinity and mask properties, mandating strict link inclusion (include-any / include-all) or absolute link avoidance (exclude-any). 3. Explicit Paths: operators can deterministically pin the LSP to transit specific IP hops via Strict Hops (must be directly adjacent) or Loose Hops (IGP computes intermediate transit).
What CSPF does
CSPF (Constrained SPF) runs on the LSP head-end over the TED and returns the ERO for signaling. The algorithm: take the TED graph, throw away everything that violates the constraints, and run Dijkstra on what remains. The pruning order:
- Links without TE attributes and links without free bandwidth at the required priority (unreserved bandwidth[setup priority] is lower than requested).
- Links that fail the administrative group (affinity) check.
- Nodes and links named in exclude-address / the exclude list of an explicit path.
- Links in SRLGs that must not be used (for protection paths).
- Dijkstra by TE metric (or IGP metric, if selected) on the remaining graph.
If no path to the tail is left after pruning, the tunnel stays in the Path: not valid state and RSVP is not started at all: no Path is sent. CSPF knows nothing that is not reflected in the TED, so a race with stale information is possible: the path is computed, but a transit node answers with PathErr.
If several equal-cost paths remain, the choice depends on the platform. Cisco takes the path with the largest minimum available bandwidth, then the one with fewer hops, then a random one. Junos selects randomly by default (random), or by configuration least-fill (the less filled one) or most-fill. Different rules are a frequent reason why the same configuration on different platforms yields a different path.
Metric: TE metric or IGP metric
The TE metric is a separate number in sub-TLV 5 (OSPF) / sub-TLV 18 (IS-IS) that by default equals the IGP metric. Its independence makes it possible to compute the TE path with different weights, for example by delay: the IGP metric is left for capacity and the TE metric is set proportional to the link delay. On Cisco the metric for a tunnel is selected with tunnel mpls traffic-eng path-selection metric te|igp, and the TE metric is used by default. Junos uses the TE metric if ospf traffic-engineering is enabled and te-metric is set, otherwise the IGP metric. In the lab configuration the TE metric of the link through P2 (5) is lower than that of the link through P1 (10): without constraints CSPF would choose P2, and the affinity constraint forces the more expensive path.
Administrative groups (affinity)
A link administrative group is a 32-bit mask (OSPF sub-TLV 9, IS-IS sub-TLV 3). Each bit is an arbitrary "color": bit 0 - GOLD, bit 1 - SAT. Cisco sets it as a number, mpls traffic-eng attribute-flags 0x1; Junos uses names, admin-groups GOLD 0 (the name is bound to a bit number), and binds them to an interface. The administrator defines the meaning of a bit; it is not standardized.
On the tunnel side, SESSION_ATTRIBUTE (C-Type 1, RFC 3209) carries three 32-bit masks: exclude-any, include-any, include-all. A link is allowed if:
- (link & exclude-any) == 0: there is no forbidden color;
- include-any == 0 or (link & include-any) != 0: at least one of the required colors is present;
- (link & include-all) == include-all: all mandatory colors are present.
Cisco configures this with the pair affinity VALUE mask MASK: for each bit in the mask, the link bit must match the affinity bit. So affinity 0x1 mask 0x3 means "bit 0 must be 1, bit 1 must be 0, the rest do not matter" - a combination of include-all (0x1) and exclude-any (0x2). Junos expresses the same with the keywords admin-group include-any, include-all and exclude.
A trap known to everyone who has worked with Cisco: the default is affinity 0x0 mask 0xFFFF. This means that a tunnel without explicit settings avoids any link that has at least one bit set in the low 16 bits. It is enough to put attribute-flags 0x4 on a link "for monitoring" and all tunnels with default settings stop using that link. Another trap: changing constraints does not re-route a running LSP instantly. The new path is computed during re-optimization: on a timer (on Cisco 3600 s by default), on an event, or manually.
Explicit and dynamic paths
A path-option describes how to obtain the ERO.
| Variant | What CSPF does | When to use |
|---|---|---|
| dynamic | computes the whole path under the constraints | the main mode, adapts to failures |
| explicit, strict hops | verifies the path against the TED but does not choose it | rigid pinning, for example because of a contract on a circuit |
| explicit, loose hops | computes the segments between the listed nodes | "go through P1, find the rest yourself" |
| explicit, exclude | removes addresses from the graph and computes the rest | bypassing a problem node or link |
An ERO subobject is strict (the next node must be a neighbor) or loose (the path to it is computed by the previous node in the ERO from its own TED, so a loose path can change without the head-end taking part). Cisco supports prioritized options (path-option 10, path-option 20 dynamic): if the first is impossible, the head-end tries the next. The verbatim (Cisco) and no-cspf (Junos) parameters turn off the TED check and allow signaling a path that the head-end cannot see, for example in another area: responsibility for correctness lies entirely with the operator.
An explicit path lists interface addresses or router-ids. If an address has changed but the path stayed in the configuration, the tunnel receives PathErr 24/2 (Bad strict node) or fails the TED check. It is convenient to keep named paths separately from tunnels and change them in one place.
