Navigation
Supported Platforms
Constrained-Path 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:
