Subject: RE: [IP-Optical] Re: An algorithm for calculating all paths between an s-d pair

From: "Awduche, Daniel" <[email-masked]>
Date: Thu, 16 Aug 2001 11:43:21 -0400

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:[email-masked]]
> Sent: Tuesday, August 14, 2001 1:37 PM
> To: Chrysostomos Tziouvaras
> Cc: [email-masked]; [email-masked]; [email-masked]
> 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
> [email-masked]
> http://lists.bell-labs.com/mailman/listinfo/ip-optical
>

---

From: "Pin-Han Ho" <[email-masked]>
Date: Thu, 16 Aug 2001 15:06:01 -0700

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" <[email-masked]>
To: "Ramesh Bhandari" <[email-masked]>; "Chrysostomos
Tziouvaras" <[email-masked]>
Cc: <[email-masked]>; <[email-masked]>; <[email-masked]>;
"Awduche, Daniel" <[email-masked]>
Sent: Thursday, August 16, 2001 8:43 AM
Subject: RE: [IP-Optical] Re: An algorithm for calculating all paths between
an s-d pair

Cheers,
/Dan

---

From: "Dmitri Krioukov" <[email-masked]>
Date: Wed, 22 Aug 2001 13:58:02 -0400

There is yet another excellent book on the subject:
"Network Optimization: Continuous and Discrete Models"
by Dimitri Bertsekas, but goes well beyond the both
topics.
--
dima.

> From: [email-masked]
> [mailto:[email-masked]]On Behalf Of Awduche,
> Daniel
> Sent: Thursday, August 16, 2001 11:43 AM
> To: Ramesh Bhandari; Chrysostomos Tziouvaras
> Cc: [email-masked]; [email-masked]; [email-masked];
> Awduche, Daniel
> Subject: RE: [IP-Optical] Re: An algorithm for calculating all paths
> between an s-d pair
> 
>