Package org.opendaylight.algo.impl

Class Samcra

java.lang.Object

org.opendaylight.algo.impl.AbstractPathComputation

org.opendaylight.algo.impl.Samcra

All Implemented Interfaces:

PathComputationAlgorithm

public class Samcra
extends AbstractPathComputation

This Class implements the Self Adaptive Multiple Constraints Routing Algorithm (SAMCRA) a Path Computation Algorithm. The SAMCRA algorithm take into account the Bandwidth, TE Metric and Delay as composite constraints. Details of SAMCRA algorithm could be found in the article "Concepts of Exact QoS Routing Algorithms", Piet Van Mieghem and Fernando A. Kuipers, IEEE/ACM Transactions on Networking, Volume 12, Number 5, October 2004.

Author:

Philippe Niger, Olivier Dugeon, Philippe Cadro

Field Summary

Fields inherited from class org.opendaylight.algo.impl.AbstractPathComputation

constraints, graph, pathDestination, pathSource, priorityQueue, processedPath, status

Constructor Summary

Constructors

Constructor	Description
Samcra(ConnectedGraph graph)

Method Summary

Modifier and Type	Method	Description
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.
protected CspfPath	computeSimplePath(VertexKey src, VertexKey dst)

Methods inherited from class org.opendaylight.algo.impl.AbstractPathComputation

combineDivertPaths, computeP2pPath, getComputedDelay, getComputedMetric, getComputedTeMetric, getIpv4NodeSid, getIpv6NodeSid, getPathDescription, initializePathComputation, pruneEdge, resetEdgesDiversity, resetVerticesDiversity, setEdgesDiversity, setVerticesDiversity, toConstrainedPath, toConstrainedPath, verifySrlgs

Methods inherited from class java.lang.Object

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

Constructor Details

Samcra

public Samcra(ConnectedGraph graph)

Method Details

computeSimplePath

protected CspfPath computeSimplePath(VertexKey src,
 VertexKey dst)

Specified by:

computeSimplePath in class AbstractPathComputation

computeDivertPaths

public ConstrainedPath computeDivertPaths(VertexKey source,
 VertexKey destination,
 Constraints cts)

Description copied from class: AbstractPathComputation

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

Overrides:

computeDivertPaths in class AbstractPathComputation

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.