Subject: RE: CSPF

From: "Abarbanel, Benjamin" <[email-masked]>
Date: Thu, 14 Feb 2002 17:03:49 -0500

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:[email-masked]]
Sent: Thursday, February 14, 2002 4:11 PM
To: Sharma, Prem; 'LE ROUX Jean-Louis FTRD/DAC/LAN'; 'sushantm'
Cc: [email-masked]; [email-masked]
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:[email-masked]]
Sent: Thursday, February 14, 2002 12:57 PM
To: 'LE ROUX Jean-Louis FTRD/DAC/LAN'; 'sushantm'
Cc: [email-masked]; [email-masked]
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:[email-masked]]
Sent: Thursday, February 14, 2002 12:16 AM
To: 'sushantm'
Cc: [email-masked]; [email-masked]
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:[email-masked] <mailto:[email-masked]> ] 
Envoye : jeudi 14 fevrier 2002 05:58 
A : [email-masked]; [email-masked] 
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.