Constrained Shortest Path First
Constrained Shortest Path First (CSPF) is an extension for algorithms for determining shortest paths . The shortest path calculated by CSPF fulfills additional constraints . This means that the shortest path algorithm is calculated after removing the edges that do not meet the constraint. Constraints can be, for example, the bandwidth of a connection (“bandwidth condition”), the total delay time, the maximum number of visited nodes or the inclusion and exclusion conditions for nodes.
CSPF is used in various graph theory and network applications such as MPLS and traffic engineering . Routing algorithms that use CSPF are also known as Constraint-Based Routing (CBR).
The path calculated by CSPF can be identical to the result of OSPF and IS-IS or deviate from this completely, depending on the constraints.
Example with bandwidth requirement
The path from node A to node C which fulfills the bandwidth condition x must be calculated. The costs are always equal to 1 for each connection used.
If x = 50, CSPF yields A → B → C.
If x = 55, CSPF yields A → D → E → C.
If x = 90, CSPF yields A → D → E → F → C.
In the above case, however, OSPF and IS-IS always return A → B → C.
Although the costs of the different paths are different in this topology, CSPF provides the corresponding path.
Now let the connection costs each be 1, except for A → B and B → C with connection costs 4:
If x = 50, CSPF yields A → D → E → C.
swell
- Mark Ziegelmann: Constrained Shortest Paths and Related Problems. Constrained Network Optimization . VDM Verlag Dr. Müller, 2007, ISBN 978-3-8364-4633-4 .