be.ac.ulg.montefiore.run.totem.repository.CSPF
Class BhandariKDisjointPath

java.lang.Object
  be.ac.ulg.montefiore.run.totem.repository.CSPF.BhandariKDisjointPath

public class BhandariKDisjointPath
extends java.lang.Object

Implementation of the Bhandari K Disjoint Shortest Path aglorithm. This algorithm can be used to compute disjoint paths between pair of nodes. This implementation works on the SimplifiedDomain and supports only link disjoint paths although Bhandari supports also node disjoint path. This implementation does not support multiple links between nodes. For more information about the algorithms see R. Bhandari, "Survivable Networks: Algorithms for Diverse Routing", Kluwer Academic.

Creation date: 18-May-2005

Author:

Fabian Skivee (skivee@run.montefiore.ulg.ac.be)

Constructor Summary

BhandariKDisjointPath(SimplifiedDomain topo)
Init the topology as a SimplifiedDomain

Method Summary

SimplifiedPath[]

computeLinkDisjointPath(int src, int dst, int k) Compute K disjoint shortest path between src to dst.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BhandariKDisjointPath

public BhandariKDisjointPath(SimplifiedDomain topo)

Init the topology as a SimplifiedDomain

Parameters:

topo -

Method Detail

computeLinkDisjointPath

public SimplifiedPath[] computeLinkDisjointPath(int src,
                                                int dst,
                                                int k)
                                         throws NoRouteToHostException,
                                                RoutingException,
                                                java.lang.CloneNotSupportedException,
                                                CreatePathException,
                                                LinkNotFoundException,
                                                NodeNotFoundException

Compute K disjoint shortest path between src to dst. The algorithm first computes a shortest path using the Bhandari shortest path. Then the path's links are removed and the metric of the opposite links are negativate. A second shortest path is computed using the Bhandari algorithm that manages the negative metric. This process is done K times. At the end with the K path, the algorithm removes the interlacing links and reassembles the segments to produces the K disjoint paths.

Parameters:

src -

dst -

k -

Returns:

Throws:

NoRouteToHostException

RoutingException

java.lang.CloneNotSupportedException

CreatePathException

LinkNotFoundException

NodeNotFoundException

See Also:

Bhandari