The MPLS WG Archive

["Pin-Han Ho" <8ph5@qlink.queensu.ca>]

For performing shared protection in which working and protection paths are
selected based on different link metrics, is there any feasible diverse
routing algorithm?

Thanks.

Pin-Han

----- Original Message -----
From: "Awduche, Daniel" <awduche@movaz.com>
To: "Ramesh Bhandari" <bhandari@hotair.hobl.lucent.com>; "Chrysostomos
Tziouvaras" <tziou@ics.forth.gr>
Cc: <mpls-ops@mplsrc.com>; <mpls@UU.NET>; <IP-Optical@lists.bell-labs.com>;
"Awduche, Daniel" <awduche@movaz.com>
Sent: Thursday, August 16, 2001 8:43 AM
Subject: RE: [IP-Optical] Re: An algorithm for calculating all paths between
an s-d pair


The 'K-Shortest Path' problem is well known and
well studied (dating back to the late 1950's).
Many different versions of this problem exist,
subject to various types of restrictions.

There are solution techniques based on improvements
to Dijkstra's algorithm, and many others based
on network flows and dynamic programming methods.
Some approaches involve elegant graph transformations
(as was the case, for example, in Ramesh's book on
diverse routing).

In addition to the references mentioned by Ramesh,
the works of David Eppstein (and the references
therein) may be of interest:
<http://www.ics.uci.edu/~eppstein/pubs/all.html>.

CAVEAT:-- Many theoretical versions of the K-Shortest
Path problem do not require the paths to be simple
(i.e. loop-free).

Yes, the K-Shortest Path problem may have relevance in
optical connection routing, especially when considering
wavelength assignment, optical impairments, and other
constraints.

Cheers,
/Dan


> -----Original Message-----
> From: Ramesh Bhandari [mailto:bhandari@hotair.hobl.lucent.com]
> Sent: Tuesday, August 14, 2001 1:37 PM
> To: Chrysostomos Tziouvaras
> Cc: mpls-ops@mplsrc.com; mpls@UU.NET; IP-Optical@lists.bell-labs.com
> Subject: [IP-Optical] Re: An algorithm for calculating all
> paths between
> an s-d pair
>
>
> Hi Chrysostomos,
>
> I believe you are searching for the K-shortest path algorithm, which
> provides paths for a given pair of nodes in ascending order of their
> lengths. An example website for information on this is
> http://www.mat.uc.pt/~eqvm/cientificos/investigacao/r_papers.html#mps.
>
> But, if you are looking for algorithms for K-disjoint paths, these can
> be found in my book: "Survivable Networks: Algorithms for Diverse
> Routing", Kluwer Academic Publishers (1999).
>
> Regards,
>
> Ramesh
>
> Chrysostomos Tziouvaras wrote:
> >
> > Hi,
> > I am searching for an algorithm for calculating all paths
> between an s-d
> > pair. Can you provide me pointers to books or URLs?
> >
> > Thanks
> > Chrysostomos
>
> _______________________________________________
> IP-Optical mailing list
> IP-Optical@lists.bell-labs.com
> http://lists.bell-labs.com/mailman/listinfo/ip-optical
>