The MPLS WG Archive

Cell Relay Retreat>MPLS WG Archive>month:2001-Aug> msg00092



[Date Prev][Date Next][Thread Prev][Thread Next]  
  [Date Index][Thread Index][Author Index][Subject Index]

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

  • From: Antoine Bagula <bagula@cs.sun.ac.za>
  • Date: Tue, 14 Aug 2001 19:15:11 +0200 (SAST)
  • cc: mpls-ops@mplsrc.com, mpls@UU.NET, IP-Optical@lists.bell-labs.com

> I am searching for an algorithm for calculating all paths between an s-d
> 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