The MPLS WG Archive

["Dmitri Krioukov" <dima@krioukov.net>]

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.

> -----Original Message-----
> From: ip-optical-admin@lists.bell-labs.com
> [mailto:ip-optical-admin@lists.bell-labs.com]On Behalf Of Awduche,
> Daniel
> Sent: Thursday, August 16, 2001 11:43 AM
> To: Ramesh Bhandari; Chrysostomos Tziouvaras
> Cc: mpls-ops@mplsrc.com; mpls@UU.NET; IP-Optical@lists.bell-labs.com;
> Awduche, Daniel
> 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
> > 
> 
> _______________________________________________
> IP-Optical mailing list
> IP-Optical@lists.bell-labs.com
> http://lists.bell-labs.com/mailman/listinfo/ip-optical