Subject: RE: Constraint-based Shortest path algorithm

From: "Gang Luo" <[email-masked]>
Date: Wed, 25 Apr 2001 22:08:41 -0400

Hi Wushao,

You may find our paper that proposed such an algorithm that does not try to
find the path with minimum cost , but nearly minimun path (to avoid solving
the NP-hard problem).

http://members.home.net/gluo1/qospathcomp.pdf

Therefore, the complexity of our algorihtm is n square, at the cost of
missing the minimum cost path. For practical use, it looks ok to miss the
minimum path
if the nearly minimum path can be found.
Best regards.
Gang Luo.

======================================================
     From: wushao wen <[email-masked]> 
     Date: Fri, 20 Apr 2001 09:58:46 -0700 
     X-Apparently-From: [email-masked] 
     X-Sender: [email-masked] 

Hello,
        In the traffic engineering, we need to calculate the 
constraint-based shortest path for a FEC. Is there any mature and efficient 
algorithm to do the calculation? Let's said that we have two parameter for 
each link (cost, and delay), how can we calculate the shortest path under 
end-to-end delay constraint (As I know, this is NP hard problem, right)?
       If anybody have implemented some  algorithms on this, please let me 
know.
       Thanks!

Wushao

     Prev by Date: LSP Failure Notification 
     Next by Date: ATM-LSR do they use OSPF/IS-IS or PNNI?? 
     Prev by thread: VoMPLS 
     Next by thread: Question about Label allocation in RSVP-TE 
     Index(es): 
          Date 
          Thread