The MPLS WG Archive

[Ramesh Bhandari <bhandari1@lucent.com>]

Durga,

If by KSP you mean K-disjoint shortest paths as discussed in my book,
then I disagree with your statement " ....KSP is simpler computationally
than MF, but doesnot may always generate the optimal disjoint path
set....". We did once a numerical comparison of the results based on the
algorithms in my book and the one based on the maximum flow (MF). While
the numerical results obtained were exactly identical, the MF method
took much longer to compute, which is not surprising, since the former
is simpler, being based on repeated application of a suitable shortest
path algorithm (e.g., a modified Dijkstra algorithm) in a properly
transformed graph.

Summary: KSP (not the naive algorithm, but the algorithm as given in my
book) is optimal and computationally fast.

Ramesh 

Durga Gangisetti wrote:
> 
> Chrysostomos,
> 
> My two cents suuggestion: -)
> 
> KSP and maximum flow (MF) can be considered as the two widely used
> routing criteria in survivable networks. Both of them shoot to find the
> max disjoint paths between given/any node-pairs in the network. It can
> be said that KSP is simpler computationally than MF, but doesnot may
> always generate the optimal disjoint path set. Whereas MF is kind of
> guaranted to produce the max no:of possible disjoint paths and maynot
> produce the actual path set.
> 
> It is found that the difference in their effectiveness in practical network
> topologies is ver small...les than 0.27% ( I guess)according to an extensive
> study reported by Dunn & Grover " Cmp of KSPs and MF routing",IEEE
> Jan'94.
> 
> Since the difference is so small and the computational complexity between
> them is  substantial  [ O (n log (n) ) ) vs O(n*n*n ) + path-set calculation ]
> most researchers may argue  that KSP can be used in practice instead of
> MF with "no" penalty.
> 
> Helpful reference books ( incl what  Ramesh and Dan suggested),
> 1.Network Flows by Ravindra,Orlin,Magnanti  and
> 2.Network programming, K G Murthy
> 
> Regards,
> Durga,
> UUnet Technologies Inc,
> A Worldcom Company.
> 
> At 12:07 PM 8/16/01 -0400, Irwin Lazar wrote:
> >Forwarded:
> >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>
> >>X-MIME-Autoconverted: from quoted-printable to 8bit by
> >>host.secure4-hosting.net id f7GFhR522007
> >>X-Diagnostic: Not on the accept list
> >>X-Envelope-To: mpls-ops
> >>
> >>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
> -------
> >The MPLS-OPS Mailing List
> >Subscribe/Unsubscribe:  http://www.mplsrc.com/mplsops.shtml
> >Archive: http://www.mplsrc.com/mpls-ops_archive.shtml