The MPLS WG Archive

["Bora Akyol" <bora@cisco.com>]

They are computationally expensive if you try to do an optimal
implementation, I believe the problem is NP complete.

There are however good heuristics that are pretty efficient.

Bora

-----Original Message-----
From: owner-mpls@UU.NET [mailto:owner-mpls@UU.NET]On Behalf Of Sharma, Prem
Sent: Thursday, February 14, 2002 12:57 PM
To: 'LE ROUX Jean-Louis FTRD/DAC/LAN'; 'sushantm'
Cc: mpls-ops@mplsrc.com; mpls@UU.NET
Subject: RE: CSPF


Just to add further: There is no standard implementation or algorithm for
CSPF. These algorithms are computation very expensive. It has been a good
research topic for quite a while. Though Dijkstra's algorithm is a std. one,
there is nothing of that sort for CSPF. The existing ones that are available
in some routers/solutions are proprietary in nature.

An algorithm MATE (MPLS Adaptive Traffic Engg.) was proposed by some folks
in this regard in Bell labs a long time back. It is available as an internet
draft also. That could be good reference for CSPF.
-Prem
-----Original Message-----
From: LE ROUX Jean-Louis FTRD/DAC/LAN
[mailto:jeanlouis.leroux@rd.francetelecom.com]
Sent: Thursday, February 14, 2002 12:16 AM
To: 'sushantm'
Cc: mpls-ops@mplsrc.com; mpls@UU.NET
Subject: RE: CSPF


Hi Sushanth
CSPF is a modified Dijkstra algorithm.
The input is the Traffic Engineering Database and the LSP constraints.
The output is an Explicit route.
Basically, Dijsktra algorithm builds a shortest path tree from a root node
(source)
Two sets are created during processing:
        PATH set: Contains links that has already been added to the SPF tree
        TENT set: Contains candidates links to be added in PATH set.
The modification for CSPF consists in pruning from TENT set, links that
can't support the constraint.
This admission control is based on the current available bandwidth of the
link (TED) and on the LSP constraints.
Many options can be added to improve the algorithm like tie breaking....
JL
-----Message d'origine-----
De : sushantm [mailto:sushantm@sasken.com]
Envoye : jeudi 14 fevrier 2002 05:58
A : mpls@UU.NET; mpls-ops@mplsrc.com
Objet : CSPF
Importance : Haute


Hi ,
 Can anyone give me information about the CSPF algorithm for finding the
contraint based explicit route. Is the CSPF algorithm available.?
Regards,
Sushanth