Constrained Shortest Path First

From Wikipedia, the free encyclopedia

Constrained Shortest Path First (CSPF) is an extension of shortest path algorithms like OSPF and IS-IS. The path computed using CSPF is a shortest path fulfilling set of constrains. 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 know as bandwidth guaranteed constraint), end-to-end delay, maximum number of link traversed etc. CSPF is widely used in MPLS Traffic Engineering. 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.

[edit] An Example With Bandwidth Constraint

For example 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

Note that in all of the above cases OSPF and IS-IS will always give path 1-->2-->3.

If however the link cost in this topology is different, CSPF will accordingly pick a different path. Suppose we still assume hop count as link cost between all nodes, except for link 1-->2 and 2-->3, the link cost is assumed to be 4 each. This time, CSPF will pick the first one (x = 50) as follows:

If x = 50 units then CSPF will give path 1-->4-->5-->3