Constrained Shortest Path First (CSPF) is an extension of shortest path algorithms. 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 known as bandwidth guaranteed constraint), end-to-end delay, maximum number of links traversed, include/exclude nodes. CSPF is widely used in

MPLS Multiprotocol Label Switching (MPLS) is a routing technique in telecommunications networks that directs data from one node to the next based on labels rather than network addresses. Whereas network addresses identify endpoints the labels identif ...

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 Open Shortest Path First (OSPF) is a routing protocol for Internet Protocol (IP) networks. It uses a link state routing (LSR) algorithm and falls into the group of interior gateway protocols (IGPs), operating within a single autonomous syste ...

and

IS-IS Intermediate System to Intermediate System (IS-IS, also written ISIS) is a routing protocol designed to move information efficiently within a computer network, a group of physically connected computers or similar devices. It accomplishes this b ...

, or it could be completely different depending on the set of constraints to be met.

Example with bandwidth constraint

Consider the network to the right, where a route has to be computed from router-A to the router-C 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 A → B → C. If x = 55 units then CSPF will give path A → D → E → C. If x = 90 units then CSPF will give path A → D → E → F → C. In all of these cases

and

will result in path A → B → C. However, if the link costs in this topology are different, CSPF may accordingly determine a different path. For example, suppose that as before, hop count is used as link cost for all links but A → B and B → C, for which the cost is 4. In this case: If x = 50 units then CSPF will give path A → D → E → C. If x = 55 units then CSPF will give path A → D → E → C. If x = 90 units then CSPF will give path A → D → E → F → C.

References

*{{cite book , first=Mark , last=Ziegelmann , title=Constrained Shortest Path and Related Problems. Constrained Network Optimization , publisher= VDM Verlag Dr. Müller , url=http://d-nb.info/987067745 , year=2007 , isbn=978-3-8364-4633-4 MPLS networking Network protocols Internet protocols Routing protocols