Package org.opendaylight.algo.impl

Class AbstractPathComputation

java.lang.Object
org.opendaylight.algo.impl.AbstractPathComputation
All Implemented Interfaces:
PathComputationAlgorithm
Direct Known Subclasses:
ConstrainedShortestPathFirst, Samcra, ShortestPathFirst
public abstract class AbstractPathComputation extends Object implements PathComputationAlgorithm

  • Field Details

  • Constructor Details

    • AbstractPathComputation

      protected AbstractPathComputation(ConnectedGraph graph)

  • Method Details

    • initializePathComputation

      protected ComputationStatus initializePathComputation(VertexKey src, VertexKey dst)
      Initialize the various parameters for Path Computation, in particular the Source and Destination CspfPath.
      Parameters:
      src - Source Vertex Identifier in the Connected Graph
      dst - Destination Vertex Identifier in the Connected Graph
      Returns:
      Computation Status

    • verifySrlgs

      protected boolean verifySrlgs(ConnectedEdge edge, CspfPath path)
      Verify if Edge share SRLG with current path during Path Diversity computation.
      Parameters:
      edge - Connected Edge to be verified
      path - Current CSPF Path
      Returns:
      True if Edge share SRLG with current path, False otherwise

    • pruneEdge

      protected boolean pruneEdge(ConnectedEdge edge, CspfPath path)
      Check if Edge need to be prune regarding all constraints including address family.
      Parameters:
      edge - Connected Edge to be verified
      path - Current Cspf Path
      Returns:
      True if Edge must be prune, False if Edge must be keep

    • getIpv4NodeSid

      protected @Nullable MplsLabel getIpv4NodeSid(ConnectedVertex cvertex)
      Return the MPLS Label corresponding to the Node SID for IPv4 when the Connected Vertex is Segment Routing aware.
      Parameters:
      cvertex - Connected Vertex
      Returns:
      MPLS Label if Connected Vertex is Segment Routing aware, Null otherwise

    • getIpv6NodeSid

      protected @Nullable MplsLabel getIpv6NodeSid(ConnectedVertex cvertex)
      Return the MPLS Label corresponding to the Node SID for IPv6 when the Connected Vertex is Segment Routing aware.
      Parameters:
      cvertex - Connected Vertex
      Returns:
      MPLS Label if Connected Vertex is Segment Routing aware, Null otherwise

    • getPathDescription

      protected List<PathDescription> getPathDescription(List<ConnectedEdge> edges)
      Convert List of Connected Edges into a Path Description as a List of IPv4, IPv6 or MPLS Label depending of the requested Address Family.
      Parameters:
      edges - List of Connected Edges
      Returns:
      Path Description

    • toConstrainedPath

      protected ConstrainedPath toConstrainedPath(CspfPath path)

    • toConstrainedPath

      protected ConstrainedPath toConstrainedPath(CspfPath primary, CspfPath secondary)

    • computeP2pPath

      public ConstrainedPath computeP2pPath(VertexKey source, VertexKey destination, Constraints cts)
      Description copied from interface: PathComputationAlgorithm
      Compute Point to Point Path from source to destination taking into account constraints.
      Specified by:
      computeP2pPath in interface PathComputationAlgorithm
      Parameters:
      source - Source Vertex Key
      destination - Destination Vertex Key
      cts - Constraints (Metric, TE Metric, Delay, Jitter, Loss, Bandwidth)
      Returns:
      A Path that meet constraints or empty path otherwise. ConstrainedPath.Status indicates the result of the path computation (Completed or Failed)

    • setEdgesDiversity

      protected void setEdgesDiversity(List<ConnectedEdge> edges)

    • resetEdgesDiversity

      protected void resetEdgesDiversity(List<ConnectedEdge> edges)

    • setVerticesDiversity

      protected void setVerticesDiversity(List<ConnectedEdge> edges)

    • resetVerticesDiversity

      protected void resetVerticesDiversity(List<ConnectedEdge> edges)

    • getComputedMetric

      protected int getComputedMetric(List<ConnectedEdge> path)

    • getComputedTeMetric

      protected int getComputedTeMetric(List<ConnectedEdge> path)

    • getComputedDelay

      protected int getComputedDelay(List<ConnectedEdge> path)

    • combineDivertPaths

      protected ConstrainedPath combineDivertPaths(CspfPath pcp, CspfPath scp)

    • computeDivertPaths

      public ConstrainedPath computeDivertPaths(VertexKey source, VertexKey destination, Constraints cts)
      Compute Divert path algorithms could be simple as: 1) compute first path, 2) remove edges and nodes in graph and 3) compute the second path. Named Remove and Find this simple solution is not optimal and frequently failed. Thus, we use here another approach based on Suurballe's algorithm: - Step1: Compute the first path P1 from graph G(V,E) - Step2: Replace P1 by -P1 in G(V,E) to form a new graph G'(V',E') - Step3: Compute the second path P2 from graph G'(V',E') - Step4: Take the union of P1 and P2, remove from the union the set of links consisting of those P1 links whose reversed links appear on P2, and vice versa; then group the remaining links into two paths P1' and P2' In our case, step2 will consist to mark P1 edge's and/or vertice's as "diverted" in Connected Graph as all edges are bi-directionnal and unmark them after step 3.
      Specified by:
      computeDivertPaths in interface PathComputationAlgorithm
      Parameters:
      source - Source Vertex Key
      destination - Destination Vertex Key
      cts - Constraints including diversity (link, node, srlg and endpoints if different)
      Returns:
      Two diverted paths that meet constraints or empty paths otherwise. ConstrainedPath.Status indicates the result of the path computation (Completed or Failed). SecondaryPath contains the path description of the diverted path.

    • computeSimplePath

      protected abstract CspfPath computeSimplePath(VertexKey source, VertexKey destination)