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:42, 30 April 2006. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

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 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 path computed using CSPF could be exactly same as that of OSPF as well as completely different. For example consider the following network.

File:CSPF-Network.JPG
An Example network

A route is 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.