The MPLS WG Archive

["Gang Luo" <gluo@nortelnetworks.com>]

Title: RE: Constraint-based Shortest path algorithm

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 <wswen@ece.ucdavis.edu>
     Date: Fri, 20 Apr 2001 09:58:46 -0700
     X-Apparently-From: Wswen99@aol.com
     X-Sender: wswen@ash.ece.ucdavis.edu

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