The MPLS WG Archive

["Abarbanel, Benjamin" <Benjamin.Abarbanel@Marconi.com>]

Title: RE: CSPF

There are a number of ways to compute the CSPF algorithm. Some are more efficient than others. I am curious to know if

there has been any performance measurements done on various algorithms for a given set of constraint and given size

topology?

 

Ben

-----Original Message-----
From: Gary Tam [mailto:gtam@lanterncom.com]
Sent: Thursday, February 14, 2002 4:11 PM
To: Sharma, Prem; 'LE ROUX Jean-Louis FTRD/DAC/LAN'; 'sushantm'
Cc: mpls-ops@mplsrc.com; mpls@UU.NET
Subject: RE: CSPF

If you only do pruning on existing IGP TE-LSDB, but not re-calculating

your TE-LSDB. It should not be computational intense. 

-----Original Message-----
From: Sharma, Prem [mailto:p_sharma@trillium.com]
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

This e-mail and any attachments are confidential. If you are not the intended recipient, please notify us immediately by reply e-mail and then delete this message from your system. Do not copy this e-mail or any attachment, use the contents for any purposes, or disclose the contents to any other person: to do so could be a breach of confidence.