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

From: Durga Gangisetti <[email-masked]>
Date: Thu, 16 Aug 2001 15:36:30 -0400

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" <[email-masked]>
>>To: "Ramesh Bhandari" <[email-masked]>,
>>    "Chrysostomos Tziouvaras" <[email-masked]>
>>Cc: <[email-masked]>, <[email-masked]>, <[email-masked]>,
>>    "Awduche, Daniel" <[email-masked]>
>>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:[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
-------
>The MPLS-OPS Mailing List
>Subscribe/Unsubscribe:  http://www.mplsrc.com/mplsops.shtml
>Archive: http://www.mplsrc.com/mpls-ops_archive.shtml

---

From: Ramesh Bhandari <[email-masked]>
Date: Thu, 16 Aug 2001 17:11:13 -0400

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

---

From: Durga Gangisetti <[email-masked]>
Date: Thu, 16 Aug 2001 23:42:21 -0400

Ramesh,

>book) is optimal and computationally fast.

I agree with you.  

But I think in case of multicommodity flows where non-linear variables like
QoS
and dynamic routing (not fixed routing - i.e; pre-determined) by splitted
traffic
with identical characteristics come in effect, it is at that point :
'  KSP 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 may
    not produce the actual path set. '
it may be valid. Ofcourse above lines are sensitive and arises
architectural and
engieering issues in building an optimal and minimum cost optical network and
differs based on context.

Regards,

Durga,
UUnet Technologies Inc,
A Worldcom Company.