Constrained Shortest Path First

Constrained Shortest Path First ( CSPF ) is an extension of algorithms for finding shortest paths. The value calculated by CSPF shortest path satisfies additional constraints. This means that the shortest - path algorithm is calculated after the edges have been removed, which do not satisfy the constraint. Constraints can be for example a connection's bandwidth ( " bandwidth condition " ), the total delay time, the maximum number of visited nodes, or the inclusion and exclusion condition for nodes.

CSPF is different in graph theory and network applications, such as MPLS and Traffic Engineering used. Routing algorithms that use CSPF are also called Constraint - Based Routing (CBR ).

The calculated by CSPF path may be identical to the result of OSPF and IS- IS or completely differ from this, depending on the constraints.

Example with bandwidth condition

To calculate the path from node A to node C of x satisfies the bandwidth condition. The costs were used for each connection is always equal to 1

If x = 50 provides CSPF A → B → C.

If x = 55 provides CSPF A → D → E → C.

If x = 90 provides CSPF A → D → E → F → C.

In the above case, however, the OSPF and IS-IS always supply A → B → C.

Although this topology, the costs of the different paths are different, CSPF provides the appropriate path.

Now let the connection through Costs per 1, except for A → B → C collar with connection costs 4:

If x = 50 provides CSPF A → D → E → C.

Swell

• Mark brick man: Constrained Shortest Paths and Related Problems. Constrained Network Optimization. VDM Verlag Dr. Müller, 2007, ISBN 978-3-8364-4633-4.

• Graph search algorithm
• Optimization algorithm
• Routing