Jump to content

Constrained Shortest Path First

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by ALM scientist (talk | contribs) at 16:48, 1 May 2006. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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, and it could be completely different. For example consider the following network.

File:CSPF-Network.JPG
An Example network

Let say, a route has to be computed from router-1 to the router-3 satisfying bandwidth constrained of x- units.

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 (assuming each links has unity cost).