The MPLS WG Archive[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index][Thread Index][Author Index][Subject Index] Fwd: RE: [IP-Optical] Re: An algorithm for calculating all paths between an s-d pair
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
|
|