Constrained Shortest Path First
Constrained Shortest Path First (CSPF) is an extension of shortest path algorithms. The path computed using CSPF is a shortest path fulfilling a set of constraints. It simply means that it runs shortest path algorithm after pruning those links that violate a given set of constraints. A constraint could be minimum bandwidth required per link (also known as bandwidth guaranteed constraint), end-to-end delay, maximum number of links traversed, include/exclude nodes. CSPF is widely used in MPLS Traffic Engineering[citation needed]. The routing using CSPF is known as Constraint Based Routing (CBR).
The path computed using CSPF could be exactly same as that of computed from OSPF and IS-IS, or it could be completely different depending on the set of constraints to be met.
Example with bandwidth constraint
Consider the following network:
Say a route has to be computed from router-1 to the router-3 satisfying bandwidth constrained of x- units, and link cost for each link is based on hop-count (i.e., 1).
If x = 50 units then CSPF will give path 1 → 2 → 3.
If x = 55 units then CSPF will give path 1 → 4 → 5 → 3.
If x = 90 units then CSPF will give path 1 → 4 → 5 → 6 → 3.
In all of these cases OSPF and IS-IS will result in path 1 → 2 → 3.
However, if the link cost in this topology is different, CSPF will accordingly determine a different path. If hop count is used as link cost between all nodes, except for link 1 → 2 and 2 → 3, the link cost is assumed to be 4 in each case. This time, CSPF will determine the first case (x = 50) as follows:
If x = 50 units then CSPF will give path 1 → 4 → 5 → 3.
References
- Ziegelmann, Mark (2007). Constrained Shortest Path and Related Problems. Constrained Network Optimization. VDM Verlag Dr. Mueller. ISBN 978-3-8364-4633-4.