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 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 know as bandwidth guaranteed constraint), end-to-end delay, maximum number of link 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.

[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