Subject: An algorithm for calculating all paths between an s-d pair

From: Chrysostomos Tziouvaras <[email-masked]>
Date: Tue, 14 Aug 2001 12:58:57 +0300 (EET DST)

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

---

From: "Pin-Han Ho" <[email-masked]>
Date: Tue, 14 Aug 2001 12:50:32 -0700

What kind of paths do you need? Shortest ones?
----- Original Message -----
From: "Chrysostomos Tziouvaras" <[email-masked]>
To: <[email-masked]>; <[email-masked]>; <[email-masked]>
Sent: Tuesday, August 14, 2001 2:58 AM
Subject: [IP-Optical] An algorithm for calculating all paths between an s-d
pair

Hi,

Thanks
Chrysostomos

---

From: Ramesh Bhandari <[email-masked]>
Date: Tue, 14 Aug 2001 13:36:30 -0400

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

---

From: Antoine Bagula <[email-masked]>
Date: Tue, 14 Aug 2001 19:15:11 +0200 (SAST)

> pair. Can you provide me pointers to books or URLs?
It depends on the routing model you want to implement. Is it an off-line
or an on-line model. If it is an off-line model, you can use either the
"flow deviation" algorithm by Kleinrock which allows you to calculate not
only the paths but also their assigned bandwidth. If you just want to
calculate the paths, you can use the "KSP" (k-shortest paths) method which
calculates link-disjoint paths. There are some research work done on that
topic (path selection and bandwidth allocation in MPLS networks) and two
papers submitted at MASCOTS2001 and ITCOM2001 will be available at
http://www.cs.sun.ac.za/COE early september.

Hope that i am not out of track

Antoine

---

From: "John Strand" <[email-masked]>
Date: Tue, 14 Aug 2001 13:38:00 -0700

I think you need to define your problem better. I assume you dont want
loops,
for example. For most apps there are lots of paths that dont make any
sense - for example hopping repeatedly from one side of the network to the
other. Also, unless you are working in quite a small network a complete
path list will be HUGE.

John

-----Original Message-----
From: [email-masked]
[mailto:[email-masked]]On Behalf Of Pin-Han Ho
Sent: Tuesday, August 14, 2001 12:51 PM
To: Chrysostomos Tziouvaras; [email-masked]; [email-masked];
[email-masked]
Subject: Re: [IP-Optical] An algorithm for calculating all paths between
an s-d pair

----- Original Message -----
From: "Chrysostomos Tziouvaras" <[email-masked]>
To: <[email-masked]>; <[email-masked]>; <[email-masked]>
Sent: Tuesday, August 14, 2001 2:58 AM
Subject: [IP-Optical] An algorithm for calculating all paths between an s-d
pair

Hi,

Thanks
Chrysostomos

_______________________________________________
IP-Optical mailing list
[email-masked]
http://lists.bell-labs.com/mailman/listinfo/ip-optical