Constrained Shortest Path First
{{multiple issues|
{{No footnotes|date=December 2022}}
{{More references|date=December 2022}}
}}
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|date=June 2008}}. 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 network to the right, where a route has to be computed from router-A to the router-C 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 A → B → C.
If x = 55 units then CSPF will give path A → D → E → C.
If x = 90 units then CSPF will give path A → D → E → F → C.
In all of these cases OSPF and IS-IS will result in path A → B → C.
However, if the link costs in this topology are different, CSPF may accordingly determine a different path. For example, suppose that as before, hop count is used as link cost for all links but A → B and B → C, for which the cost is 4. In this case:
If x = 50 units then CSPF will give path A → D → E → C.
If x = 55 units then CSPF will give path A → D → E → C.
If x = 90 units then CSPF will give path A → D → E → F → C.
References
{{Reflist}}
- {{cite book
|first=Mark
|last=Ziegelmann
|title=Constrained Shortest Path and Related Problems. Constrained Network Optimization
|publisher=VDM Verlag Dr. Müller
|url=http://d-nb.info/987067745
|year=2007
|isbn=978-3-8364-4633-4
}}