Initial commit of Path Computation Algorithms implementation.
This is the 2/3 Patch Set to implement a full featured PCE server
in conformity to RFC5440. It provides three different algorithms
able to compute paths between end points by taking into account
different constraints:
- A simple Shortest Path First that takes into account only
standard IGP metric
- A Constrained Shortest Path First (CSPF) that takes into
account the TE Metric and Bandwidth for constraints
- SAMCRA algorithm that takes into account TE Metric, Delay,
Loss and Bandwidth for constraints
Details information about how the various algorithms are implemented
and how to use them will be provided in docs/algo directory.
JIRA: BGPCEP-858
Signed-off-by: Olivier Dugeon <olivier.dugeon@orange.com>
Co-authored-by: Philippe Niger <philippe.niger@orange.com>
Co-authored-by: Philippe Cadro <philippe.cadro@orange.com>
Change-Id: Ifbcf2a65aef08c3fa95a2be54eb53ffdf55dd417
--- /dev/null
+<?xml version="1.0" encoding="UTF-8"?>
+<!-- vi: set et smarttab sw=4 tabstop=4: -->
+<!--
+ Copyright (c) 2019 Orange Labs. All rights reserved.
+
+ This program and the accompanying materials are made available under the
+ terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ and is available at http://www.eclipse.org/legal/epl-v10.html
+-->
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+ xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+
+ <modelVersion>4.0.0</modelVersion>
+ <parent>
+ <groupId>org.opendaylight.bgpcep</groupId>
+ <artifactId>binding-parent</artifactId>
+ <version>0.14.0-SNAPSHOT</version>
+ <relativePath>../../binding-parent</relativePath>
+ </parent>
+
+ <artifactId>algo-api</artifactId>
+ <description>Path Computation Algorithms API</description>
+ <packaging>bundle</packaging>
+ <name>${project.artifactId}</name>
+
+ <dependencies>
+ <dependency>
+ <groupId>${project.groupId}</groupId>
+ <artifactId>graph-api</artifactId>
+ </dependency>
+ <dependency>
+ <groupId>${project.groupId}</groupId>
+ <artifactId>concepts</artifactId>
+ </dependency>
+ <dependency>
+ <groupId>org.opendaylight.yangtools</groupId>
+ <artifactId>yang-common</artifactId>
+ </dependency>
+ <dependency>
+ <groupId>org.opendaylight.yangtools</groupId>
+ <artifactId>concepts</artifactId>
+ </dependency>
+ <dependency>
+ <groupId>org.opendaylight.mdsal.binding.model.ietf</groupId>
+ <artifactId>rfc6991-ietf-inet-types</artifactId>
+ </dependency>
+ <dependency>
+ <groupId>com.google.guava</groupId>
+ <artifactId>guava</artifactId>
+ </dependency>
+ </dependencies>
+</project>
--- /dev/null
+/*
+ * Copyright (c) 2020 Orange. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+
+package org.opendaylight.algo;
+
+import org.eclipse.jdt.annotation.NonNull;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev191125.graph.topology.graph.VertexKey;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ConstrainedPath;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.PathConstraints;
+
+/**
+ * This class provides entry for various Path Computation Algorithms.
+ *
+ * @author Olivier Dugeon
+ *
+ */
+public interface PathComputationAlgorithm {
+
+ /**
+ * Compute Point to Point Path from source to destination taking into account constraints.
+ *
+ * @param source Source Vertex Key
+ * @param destination Destination Vertex Key
+ * @param constraints Constraints (Metric, TE Metric, Delay, Jitter, Loss, Bandwidth)
+ *
+ * @return A Path that meet constraints or empty path otherwise. ConstrainedPath.Status indicates the result of
+ * the path computation (Completed or Failed)
+ */
+ @NonNull ConstrainedPath computeP2pPath(VertexKey source, VertexKey destination, PathConstraints constraints);
+}
--- /dev/null
+/*
+ * Copyright (c) 2020 Orange. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+
+package org.opendaylight.algo;
+
+import org.opendaylight.graph.ConnectedGraph;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.AlgorithmType;
+
+/**
+ * This class provides access to Path Computation Algorithms.
+ *
+ * @author Olivier Dugeon
+ *
+ */
+public interface PathComputationProvider {
+
+ /**
+ * Return Path Computation Algorithm object that corresponds to the requested type.
+ *
+ * @param cgraph Connected Graph on which path computation will run
+ * @param algorithmType Algorithm supported types are: 'SPF', 'CSPF' and 'SAMCRA'
+ *
+ * @return PathComputationAlgorithm
+ */
+ PathComputationAlgorithm getPathComputationAlgorithm(ConnectedGraph cgraph, AlgorithmType algorithmType);
+
+}
--- /dev/null
+module path-computation {
+ yang-version 1;
+ namespace "urn:opendaylight:params:xml:ns:yang:path:computation";
+ prefix "algo";
+
+ import network-concepts { prefix netc; revision-date 2013-11-25; }
+ import ietf-inet-types { prefix inet; revision-date 2013-07-15; }
+ import graph { prefix gr; revision-date 2019-11-25; }
+
+ organization "Orange";
+ contact "Olivier Dugeon <olivier.dugeon@orange.com>";
+
+ description
+ "This module contains the model of Computed Path
+ used in various Path Computation algorithms.
+
+ Copyright (c)2020 Orange. All rights reserved.
+
+ This program and the accompanying materials are made available
+ under the terms of the Eclipse Public License v1.0 which
+ accompanies this distribution, and is available at
+ http://www.eclipse.org/legal/epl-v10.html";
+
+ revision "2020-01-20" {
+ description
+ "Initial revision.";
+ reference "";
+ }
+
+ typedef computation-status {
+ description
+ "Status of the Path Computation Algorithm regaring current
+ computed path";
+ type enumeration {
+ enum idle {
+ description "Path Computeation Algorithm has not yet started";
+ value 0;
+ }
+ enum in-progress {
+ description
+ "Path Computation has started but no path has been found";
+ value 1;
+ }
+ enum active {
+ description
+ "A valid path has been found,
+ but it is perhaps not the best one";
+ value 2;
+ }
+ enum completed {
+ description
+ "Path Computation Algorithm has completed
+ and a valid computed path found";
+ value 3;
+ }
+ enum failed {
+ value 4;
+ }
+ }
+ }
+
+ typedef algorithm-type {
+ description "Various type of Path Computation Algorithms";
+ type enumeration {
+ enum spf {
+ value 0;
+ }
+ enum cspf {
+ value 1;
+ }
+ enum samcra {
+ value 2;
+ }
+ }
+ default "spf";
+ }
+
+ grouping path-constraints {
+ description "Set of Constraints for Path Computation";
+ leaf metric {
+ description "Maximum end to end IGP metric";
+ type uint32;
+ }
+ leaf te-metric {
+ description "Maximum end to end Traffic Engineering metric";
+ type uint32;
+ }
+ leaf delay {
+ description "Maximum end to end delay";
+ units "micro-seconds";
+ type gr:delay;
+ }
+ leaf jitter {
+ description "Maximum delay variation for selected edges";
+ units "micro-seconds";
+ type gr:delay;
+ }
+ leaf loss {
+ description "Maximum loss for selected edges";
+ units "0.000003%";
+ type gr:loss;
+ }
+ leaf admin-group {
+ description "Admin group to select edges";
+ type uint32;
+ }
+ leaf address-family {
+ description "Address family of the computed path";
+ type enumeration {
+ enum ipv4 {
+ value 0;
+ }
+ enum ipv6 {
+ value 1;
+ }
+ enum sr-ipv4 {
+ value 2;
+ }
+ enum sr-ipv6 {
+ value 3;
+ }
+ }
+ default "ipv4";
+ }
+ leaf class-type {
+ description "Class Type for bandwidth constraints";
+ type uint8 {
+ range "0..7";
+ }
+ }
+ leaf bandwidth {
+ description "Requested bandwidth for the computed path";
+ units "bytes/second";
+ type gr:decimal-bandwidth;
+ }
+ }
+
+ grouping path-descriptions {
+ description
+ "Computed Path description as a list of IPv4, IPv6 or MPLS Label";
+ list path-description {
+ leaf ipv4 {
+ when "path-constraints/address-family = 0";
+ type inet:ipv4-address;
+ }
+ leaf ipv6 {
+ when "path-constraints/address-family = 1";
+ type inet:ipv6-address;
+ }
+ leaf label {
+ when "path-constraints/address-family = 2 or path-constraints/address-family = 3";
+ type netc:mpls-label;
+ }
+ }
+ }
+
+ container constrained-path {
+ description "Computed Path as result of Path Computation Algorithms";
+ uses path-constraints;
+ leaf source {
+ type uint64;
+ }
+ leaf destination {
+ type uint64;
+ }
+ uses path-descriptions;
+ leaf status {
+ type computation-status;
+ }
+ }
+
+ rpc get-constrained-path {
+ input {
+ leaf graph-name {
+ type string;
+ mandatory true;
+ }
+ leaf source {
+ type uint64;
+ }
+ leaf destination {
+ type uint64;
+ }
+ container constraints {
+ uses path-constraints;
+ }
+ leaf algorithm {
+ type algorithm-type;
+ }
+ }
+ output {
+ uses path-descriptions;
+ leaf status {
+ type computation-status;
+ }
+ leaf computed-metric {
+ type uint32;
+ }
+ leaf computed-te-metric {
+ type uint32;
+ }
+ leaf computed-delay {
+ type gr:delay;
+ }
+ }
+ }
+}
+
--- /dev/null
+<?xml version="1.0" encoding="UTF-8"?>
+<!--
+ Copyright (c) 2019 Orange Labs. All rights reserved.
+
+ This program and the accompanying materials are made available under the
+ terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ and is available at http://www.eclipse.org/legal/epl-v10.html
+-->
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+
+ <modelVersion>4.0.0</modelVersion>
+
+ <parent>
+ <groupId>org.opendaylight.odlparent</groupId>
+ <artifactId>odlparent-lite</artifactId>
+ <version>6.0.4</version>
+ <relativePath/>
+ </parent>
+
+ <groupId>org.opendaylight.bgpcep</groupId>
+ <artifactId>algo-artifacts</artifactId>
+ <version>0.14.0-SNAPSHOT</version>
+ <packaging>pom</packaging>
+
+ <dependencyManagement>
+ <dependencies>
+ <dependency>
+ <groupId>${project.groupId}</groupId>
+ <artifactId>algo-api</artifactId>
+ <version>${project.version}</version>
+ </dependency>
+ <dependency>
+ <groupId>${project.groupId}</groupId>
+ <artifactId>algo-impl</artifactId>
+ <version>${project.version}</version>
+ </dependency>
+ <!-- Algorithms Features artifacts -->
+ <dependency>
+ <groupId>org.opendaylight.bgpcep</groupId>
+ <artifactId>features-algo</artifactId>
+ <classifier>features</classifier>
+ <type>xml</type>
+ <version>${project.version}</version>
+ </dependency>
+ <dependency>
+ <groupId>org.opendaylight.bgpcep</groupId>
+ <artifactId>odl-bgpcep-algo</artifactId>
+ <classifier>features</classifier>
+ <type>xml</type>
+ <version>${project.version}</version>
+ </dependency>
+ <dependency>
+ <groupId>org.opendaylight.bgpcep</groupId>
+ <artifactId>odl-bgpcep-algo-api</artifactId>
+ <classifier>features</classifier>
+ <type>xml</type>
+ <version>${project.version}</version>
+ </dependency>
+ </dependencies>
+ </dependencyManagement>
+</project>
--- /dev/null
+<?xml version="1.0" encoding="UTF-8"?>
+<!-- vi: set et smarttab sw=4 tabstop=4: -->
+<!--
+ Copyright (c) 2019 Orange Labs and others. All rights reserved.
+
+ This program and the accompanying materials are made available under the
+ terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ and is available at http://www.eclipse.org/legal/epl-v10.html
+-->
+
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+ xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+
+ <modelVersion>4.0.0</modelVersion>
+ <parent>
+ <groupId>org.opendaylight.bgpcep</groupId>
+ <artifactId>bgpcep-parent</artifactId>
+ <version>0.14.0-SNAPSHOT</version>
+ <relativePath>../../parent</relativePath>
+ </parent>
+
+ <artifactId>algo-impl</artifactId>
+ <description>Path Computation Algorithms Implementation</description>
+ <packaging>bundle</packaging>
+ <name>${project.artifactId}</name>
+
+ <dependencies>
+ <dependency>
+ <groupId>${project.groupId}</groupId>
+ <artifactId>algo-api</artifactId>
+ </dependency>
+ <dependency>
+ <groupId>${project.groupId}</groupId>
+ <artifactId>graph-api</artifactId>
+ </dependency>
+ <dependency>
+ <groupId>${project.groupId}</groupId>
+ <artifactId>concepts</artifactId>
+ </dependency>
+ <dependency>
+ <groupId>org.opendaylight.mdsal</groupId>
+ <artifactId>mdsal-binding-api</artifactId>
+ </dependency>
+ <dependency>
+ <groupId>org.opendaylight.mdsal.binding.model.ietf</groupId>
+ <artifactId>rfc6991-ietf-inet-types</artifactId>
+ </dependency>
+ <dependency>
+ <groupId>com.google.guava</groupId>
+ <artifactId>guava</artifactId>
+ </dependency>
+ <dependency>
+ <groupId>org.opendaylight.yangtools</groupId>
+ <artifactId>concepts</artifactId>
+ </dependency>
+ <dependency>
+ <groupId>org.opendaylight.yangtools</groupId>
+ <artifactId>yang-common</artifactId>
+ </dependency>
+ </dependencies>
+</project>
--- /dev/null
+/*
+ * Copyright (c) 2020 Orange. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.algo.impl;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.PriorityQueue;
+import org.eclipse.jdt.annotation.Nullable;
+import org.opendaylight.algo.PathComputationAlgorithm;
+import org.opendaylight.graph.ConnectedEdge;
+import org.opendaylight.graph.ConnectedGraph;
+import org.opendaylight.graph.ConnectedVertex;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev191125.edge.EdgeAttributes;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev191125.graph.topology.graph.Prefix;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev191125.graph.topology.graph.VertexKey;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.network.concepts.rev131125.MplsLabel;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ComputationStatus;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ConstrainedPath;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ConstrainedPathBuilder;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.PathConstraints;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.path.descriptions.PathDescription;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.path.descriptions.PathDescriptionBuilder;
+import org.opendaylight.yangtools.yang.common.Uint32;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+public abstract class AbstractPathComputation implements PathComputationAlgorithm {
+
+ private static final Logger LOG = LoggerFactory.getLogger(AbstractPathComputation.class);
+
+ protected final ConnectedGraph graph;
+
+ /* Source and Destination of the path */
+ protected CspfPath pathSource = null;
+ protected CspfPath pathDestination = null;
+
+ /* Constraints that the path must respect */
+ protected PathConstraints constraints = null;
+
+ /* Priority Queue and HashMap to manage path computation */
+ protected PriorityQueue<CspfPath> priorityQueue;
+ protected HashMap<Long, CspfPath> processedPath;
+
+ protected AbstractPathComputation(ConnectedGraph graph) {
+ this.graph = graph;
+ priorityQueue = new PriorityQueue<CspfPath>();
+ processedPath = new HashMap<Long, CspfPath>();
+ }
+
+ /**
+ * Initialize the various parameters for Path Computation, in particular the
+ * Source and Destination CspfPath.
+ *
+ * @param src
+ * Source Vertex Identifier in the Connected Graph
+ * @param dst
+ * Destination Vertex Identifier in the Connected Graph
+ *
+ * @return Constrained Path Builder with status set to 'OnGoing' if
+ * initialization success, 'Failed' otherwise
+ */
+ protected ConstrainedPathBuilder initializePathComputation(VertexKey src, VertexKey dst) {
+ ConstrainedPathBuilder cpathBuilder = new ConstrainedPathBuilder().setStatus(ComputationStatus.InProgress);
+
+ /* Check that source and destination vertexKey are not identical */
+ if (src.equals(dst)) {
+ LOG.warn("Source and Destination are equal: Abort!");
+ cpathBuilder.setStatus(ComputationStatus.Failed);
+ return cpathBuilder;
+ }
+
+ /*
+ * Get the Connected Vertex from the Graph to initialize the source of
+ * the Cspf Path
+ */
+ ConnectedVertex vertex = null;
+ vertex = graph.getConnectedVertex(src.getVertexId().longValue());
+ if (vertex == null) {
+ LOG.warn("Found no source for Vertex Key {}", src);
+ cpathBuilder.setStatus(ComputationStatus.Failed);
+ return cpathBuilder;
+ }
+ LOG.debug("Create Path Source with Vertex {}", vertex.toString());
+ pathSource = new CspfPath(vertex).setCost(0).setDelay(0);
+ cpathBuilder.setSource(vertex.getVertex().getVertexId());
+
+ /*
+ * Get the Connected Vertex from the Graph to initialize the destination
+ * of the Cspf Path
+ */
+ vertex = graph.getConnectedVertex(dst.getVertexId().longValue());
+ if (vertex == null) {
+ LOG.warn("Found no destination for Vertex Key {}", src);
+ cpathBuilder.setStatus(ComputationStatus.Failed);
+ return cpathBuilder;
+ }
+ LOG.debug("Create Path Destination with Vertex {}", vertex.toString());
+ pathDestination = new CspfPath(vertex);
+ cpathBuilder.setDestination(vertex.getVertex().getVertexId());
+
+ /* Initialize the Priority Queue, HashMap */
+ priorityQueue.clear();
+ priorityQueue.add(pathSource);
+ processedPath.clear();
+ processedPath.put(pathSource.getVertexKey(), pathSource);
+ processedPath.put(pathDestination.getVertexKey(), pathDestination);
+
+ return cpathBuilder;
+ }
+
+ /**
+ * Check if Edge need to be prune regarding all constraints including
+ * address family.
+ *
+ * @return True if Edge must be prune, False if Edge must be keep
+ */
+ protected boolean pruneEdge(ConnectedEdge edge, CspfPath path) {
+ /* Check that Constraints are initialized */
+ if (constraints == null) {
+ LOG.warn("Constraints not set");
+ return true;
+ }
+
+ /* Edge could point to an unknown Vertex e.g. with inter-domain link */
+ if ((edge.getDestination() == null) || (edge.getDestination().getVertex() == null)) {
+ LOG.debug("No Destination");
+ return true;
+ }
+
+ /* Check that Edge have attributes */
+ EdgeAttributes attributes = edge.getEdge() != null ? edge.getEdge().getEdgeAttributes() : null;
+ if (attributes == null) {
+ LOG.debug("No attributes");
+ return true;
+ }
+
+ /* Check that Edge belongs to the requested address family */
+ switch (constraints.getAddressFamily()) {
+ case Ipv4:
+ if ((attributes.getRemoteAddress() == null)
+ || (attributes.getRemoteAddress().getIpv4Address() == null)) {
+ LOG.debug("No Ipv4 address");
+ return true;
+ }
+ break;
+ case Ipv6:
+ if ((attributes.getRemoteAddress() == null)
+ || (attributes.getRemoteAddress().getIpv6Address() == null)) {
+ LOG.debug("No Ipv6 address");
+ return true;
+ }
+ break;
+ case SrIpv4:
+ if (getIpv4NodeSid(edge.getDestination()) == null) {
+ LOG.debug("No SR-Ipv4 SID");
+ return true;
+ }
+ break;
+ case SrIpv6:
+ if (getIpv6NodeSid(edge.getDestination()) == null) {
+ LOG.debug("No SR-Ipv6 SID");
+ return true;
+ }
+ break;
+ default:
+ return true;
+ }
+
+ /* Skip checking other Constraints for simple SPF algorithm */
+ if (this instanceof ShortestPathFirst) {
+ LOG.trace("Edge {} is valid for Simple Path Computation", edge.toString());
+ return false;
+ }
+
+ /*
+ * If specified, check that total TE Metric up to this edge respects the
+ * initial constraints
+ */
+ if (constraints.getTeMetric() != null) {
+ if (attributes.getTeMetric() == null) {
+ return true;
+ } else {
+ int totalCost = attributes.getTeMetric().intValue() + path.getCost();
+ if (totalCost > constraints.getTeMetric().intValue()) {
+ LOG.debug("TeMetric {} exceed constraint {}", totalCost, constraints.getTeMetric().intValue());
+ return true;
+ }
+ }
+ }
+
+ /*
+ * If specified, check that total Delay up to this edge respects the
+ * initial constraints
+ */
+ if (constraints.getDelay() != null) {
+ if (attributes.getDelay() == null) {
+ return true;
+ } else {
+ int totalDelay = attributes.getDelay().getValue().intValue() + path.getDelay();
+ if (totalDelay > constraints.getDelay().getValue().intValue()) {
+ LOG.debug("Delay {} exceed constraint {}", totalDelay,
+ constraints.getDelay().getValue().intValue());
+ return true;
+ }
+ }
+ }
+
+ /* Check that Edge respect Loss constraint */
+ if (constraints.getLoss() != null) {
+ if ((attributes.getLoss() == null)
+ || (attributes.getLoss().getValue().intValue() > constraints.getLoss().getValue().intValue())) {
+ return true;
+ }
+ }
+
+ /* Check that Edge meet Bandwidth constraint */
+ if (constraints.getBandwidth() != null) {
+ if ((attributes.getMaxLinkBandwidth() == null) || (attributes.getMaxResvLinkBandwidth() == null)
+ || (attributes.getUnreservedBandwidth() == null)
+ || (attributes.getUnreservedBandwidth().get(constraints.getClassType().intValue()) == null)) {
+ return true;
+ } else {
+ Long bandwidth = constraints.getBandwidth().getValue().longValue();
+ if (attributes.getUnreservedBandwidth().get(constraints.getClassType().intValue()).getBandwidth()
+ .getValue().longValue() < bandwidth
+ || attributes.getMaxLinkBandwidth().getValue().longValue() < bandwidth
+ || attributes.getMaxResvLinkBandwidth().getValue().longValue() < bandwidth) {
+ LOG.debug("Bandwidth constraint is not met");
+ return true;
+ }
+ }
+ }
+
+ /* Check that Edge belongs to admin group */
+ if ((constraints.getAdminGroup() != null)
+ && !(constraints.getAdminGroup().equals(attributes.getAdminGroup()))) {
+ LOG.debug("Not in the requested admin-group");
+ return true;
+ }
+
+ /*
+ * OK. All is fine. We can consider this Edge valid, so not to be prune
+ */
+ LOG.trace("Edge {} is valid for Constrained Path Computation", edge.toString());
+ return false;
+ }
+
+ /**
+ * Return the MPLS Label corresponding to the Node SID for IPv4 when the
+ * Connected Vertex is Segment Routing aware.
+ *
+ * @return MPLS Label if Connected Vertex is Segment Routing aware, Null
+ * otherwise
+ */
+ protected @Nullable MplsLabel getIpv4NodeSid(ConnectedVertex cvertex) {
+ /*
+ * Check that Vertex is Segment Routing aware
+ */
+ if ((cvertex.getVertex() == null) || (cvertex.getVertex().getSrgb() == null)) {
+ return null;
+ }
+ /*
+ * Find in Prefix List Node SID attached to the IPv4 of the next Vertex
+ * and return the MPLS Label that corresponds to the index in the SRGB
+ */
+ if (cvertex.getPrefixes() == null) {
+ return null;
+ }
+ for (Prefix prefix : cvertex.getPrefixes()) {
+ if ((prefix.getPrefixSid() == null) || (prefix.isNodeSid() == null)) {
+ continue;
+ }
+ if (prefix.isNodeSid() && prefix.getPrefix().getIpv4Prefix() != null) {
+ return new MplsLabel(Uint32.valueOf(prefix.getPrefixSid().intValue()));
+ }
+ }
+ return null;
+ }
+
+ /**
+ * Return the MPLS Label corresponding to the Node SID for IPv6 when the
+ * Connected Vertex is Segment Routing aware.
+ *
+ * @return MPLS Label if Connected Vertex is Segment Routing aware, Null
+ * otherwise
+ */
+ protected @Nullable MplsLabel getIpv6NodeSid(ConnectedVertex cvertex) {
+ /*
+ * Check that Vertex is Segment Routing aware
+ */
+ if ((cvertex.getVertex() == null) || (cvertex.getVertex().getSrgb() == null)) {
+ return null;
+ }
+ /*
+ * Find in Prefix List Node SID attached to the IPv6 of the next Vertex
+ * and return the MPLS Label that corresponds to the index in the SRGB
+ */
+ if (cvertex.getPrefixes() == null) {
+ return null;
+ }
+ for (Prefix prefix : cvertex.getPrefixes()) {
+ if ((prefix.getPrefixSid() == null) || (prefix.isNodeSid() == null)) {
+ continue;
+ }
+ if (prefix.isNodeSid() && prefix.getPrefix().getIpv6Prefix() != null) {
+ return new MplsLabel(Uint32.valueOf(prefix.getPrefixSid().intValue()));
+ }
+ }
+ return null;
+ }
+
+ /**
+ * Convert List of Connected Edges into a Path Description as a List of
+ * IPv4, IPv6 or MPLS Label depending of the requested Address Family.
+ *
+ * @param edges
+ * List of Connected Edges
+ *
+ * @return Path Description
+ */
+ protected List<PathDescription> getPathDescription(List<ConnectedEdge> edges) {
+ ArrayList<PathDescription> list = new ArrayList<PathDescription>();
+
+ for (ConnectedEdge edge : edges) {
+ PathDescription pathDesc = null;
+ switch (constraints.getAddressFamily()) {
+ case Ipv4:
+ pathDesc = new PathDescriptionBuilder()
+ .setIpv4(edge.getEdge().getEdgeAttributes().getRemoteAddress().getIpv4Address()).build();
+ break;
+ case Ipv6:
+ pathDesc = new PathDescriptionBuilder()
+ .setIpv6(edge.getEdge().getEdgeAttributes().getRemoteAddress().getIpv6Address()).build();
+ break;
+ case SrIpv4:
+ pathDesc = new PathDescriptionBuilder()
+ .setIpv4(edge.getDestination().getVertex().getRouterId().getIpv4Address())
+ .setLabel(getIpv4NodeSid(edge.getDestination()))
+ .build();
+ break;
+ case SrIpv6:
+ pathDesc = new PathDescriptionBuilder()
+ .setIpv6(edge.getDestination().getVertex().getRouterId().getIpv6Address())
+ .setLabel(getIpv6NodeSid(edge.getDestination()))
+ .build();
+ break;
+ default:
+ break;
+ }
+ list.add(pathDesc);
+ }
+ return list;
+ }
+
+ @Override
+ public abstract ConstrainedPath computeP2pPath(VertexKey source, VertexKey destination,
+ PathConstraints constraints);
+
+}
--- /dev/null
+/*
+ * Copyright (c) 2016 Orange. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.algo.impl;
+
+import java.util.HashMap;
+import java.util.List;
+
+import org.opendaylight.graph.ConnectedEdge;
+import org.opendaylight.graph.ConnectedGraph;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev191125.graph.topology.graph.VertexKey;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ComputationStatus;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ConstrainedPath;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ConstrainedPathBuilder;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.PathConstraints;
+import org.opendaylight.yangtools.yang.common.Uint32;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+
+/**
+ * This Class implements a simple Constrained Shortest Path First path computation algorithm that take into account
+ * Bandwidth and TE Metric as constraints.
+ *
+ * @author Olivier Dugeon
+ * @author Philippe Niger
+ * @author Philippe Cadro
+ *
+ */
+public class ConstrainedShortestPathFirst extends AbstractPathComputation {
+
+ private static final Logger LOG = LoggerFactory.getLogger(ConstrainedShortestPathFirst.class);
+
+ private HashMap<Long, CspfPath> visitedVertices;
+
+ public ConstrainedShortestPathFirst(ConnectedGraph graph) {
+ super(graph);
+ visitedVertices = new HashMap<Long, CspfPath>();
+ }
+
+ public ConstrainedPath computeP2pPath(VertexKey src, VertexKey dst, PathConstraints cts) {
+ ConstrainedPathBuilder cpathBuilder;
+ List<ConnectedEdge> edges;
+ CspfPath currentPath;
+ int currentCost = Integer.MAX_VALUE;
+
+ LOG.info("Start CSPF Path Computation from {} to {} with constraints {}", src, dst, cts);
+
+ /* Initialize algorithm */
+ this.constraints = cts;
+ cpathBuilder = initializePathComputation(src, dst);
+ if (cpathBuilder.getStatus() == ComputationStatus.Failed) {
+ return cpathBuilder.build();
+ }
+
+ cpathBuilder.setBandwidth(cts.getBandwidth()).setClassType(cts.getClassType());
+
+ visitedVertices.clear();
+
+ /* Process all Connected Vertex until priority queue becomes empty. Connected Vertices are added into the
+ * priority queue when processing the next Connected Vertex: see relaxMC() method */
+ while (priorityQueue.size() != 0) {
+ currentPath = priorityQueue.poll();
+ visitedVertices.put(currentPath.getVertexKey(), currentPath);
+ LOG.debug("Got path to Vertex {} from Priority Queue", currentPath.getVertex().toString());
+ edges = currentPath.getVertex().getOutputConnectedEdges();
+
+ for (ConnectedEdge edge : edges) {
+ /* Skip Connected Edges that must be prune i.e. Edges that not satisfy the given constraints,
+ * in particular the Bandwidth, TE Metric and Delay. */
+ if (pruneEdge(edge, currentPath)) {
+ LOG.trace(" Prune Edge {}", edge.toString());
+ continue;
+ }
+ if ((relaxMultiConstraints(edge, currentPath)) && (pathDestination.getCost() < currentCost)) {
+ currentCost = pathDestination.getCost();
+ cpathBuilder.setPathDescription(getPathDescription(pathDestination.getPath()))
+ .setMetric(Uint32.valueOf(pathDestination.getCost()))
+ .setStatus(ComputationStatus.Active);
+ LOG.debug(" Found a valid path up to destination {}", cpathBuilder.getPathDescription());
+ }
+ }
+ }
+ /* The priority queue is empty => all the possible (vertex, path) elements have been explored
+ * The "ConstrainedPathBuilder" object contains the optimal path if it exists
+ * Otherwise an empty path with status failed is returned
+ */
+ if ((cpathBuilder.getStatus() == ComputationStatus.InProgress)
+ || (cpathBuilder.getPathDescription().size() == 0)) {
+ cpathBuilder.setStatus(ComputationStatus.Failed);
+ } else {
+ cpathBuilder.setStatus(ComputationStatus.Completed);
+ }
+ return cpathBuilder.build();
+ }
+
+ private boolean relaxMultiConstraints(ConnectedEdge edge, CspfPath currentPath) {
+ LOG.debug(" Start relaxing Multi Constraints on Edge {} to Vertex {}",
+ edge.toString(), edge.getDestination().toString());
+ final Long nextVertexKey = edge.getDestination().getKey();
+
+ /* Verify if we have not visited this Vertex to avoid loop */
+ if (visitedVertices.containsKey(nextVertexKey)) {
+ return false;
+ }
+
+ /* Get Next Vertex from processedPath or create a new one if it has not yet processed */
+ CspfPath nextPath = processedPath.get(nextVertexKey);
+ if (nextPath == null) {
+ nextPath = new CspfPath(edge.getDestination());
+ processedPath.put(nextPath.getVertexKey(), nextPath);
+ }
+
+ /* Add or update the CspfPath in the Priority Queue if total path Cost is lower than cost associated
+ * to this next Vertex. This could occurs if we process a Vertex that as not yet been visited in the Graph
+ * or if we found a shortest path up to this Vertex. */
+ int totalCost = edge.getEdge().getEdgeAttributes().getTeMetric().intValue() + currentPath.getCost();
+ if (totalCost < nextPath.getCost()) {
+ nextPath.setCost(totalCost)
+ .replacePath(currentPath.getPath())
+ .addConnectedEdge(edge);
+ /* It is not possible to directly update the CspfPath in the Priority Queue. Indeed, if we modify the path
+ * weight, the Priority Queue must be re-ordered. So, we need fist to remove the CspfPath if it is present
+ * in the Priority Queue, then, update the Path Weight, and finally (re-)insert it in the Priority Queue.
+ */
+ priorityQueue.removeIf((path) -> path.getVertexKey().equals(nextVertexKey));
+ nextPath.setKey(totalCost);
+ priorityQueue.add(nextPath);
+ LOG.debug(" Added path to Vertex {} in the Priority Queue", nextPath.getVertex().toString());
+ }
+ /* Return True if we reach the destination, false otherwise */
+ return pathDestination.equals(nextPath);
+ }
+}
--- /dev/null
+/*
+ * Copyright (c) 2020 Orange. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+
+package org.opendaylight.algo.impl;
+
+import java.util.ArrayList;
+import java.util.List;
+import org.opendaylight.graph.ConnectedEdge;
+import org.opendaylight.graph.ConnectedVertex;
+
+/**
+ * This Class implements the Constrained Shortest Path First (CSPF) Path stored in the Priority Queue used by various
+ * Path Computation Algorithms.
+ *
+ * <p>The path corresponds to the computed path between the Source Vertex and the Current Vertex. Cost (based
+ * on TE Metric) and Delay are accumulated values from the source to the current vertex.
+ *
+ * <p>The class uses standard java "Comparable" interface to support "natural ordering" and thus implements
+ * the compareTo() method based on the "key" value. However, the equals() method uses Vertex Key for comparison.
+ * HashCode() method is also overridden by the Connected Vertex hashCode() method.
+ *
+ * @author Olivier Dugeon
+ *
+ */
+
+public class CspfPath implements Comparable<CspfPath> {
+
+ /* Associated Connected Vertex: i.e. the current vertex in the Path */
+ private ConnectedVertex cvertex;
+
+ /* Path Length and associated cost and delay */
+ private float pathLength = 0;
+ private int cost = Integer.MAX_VALUE;
+ private int delay = Integer.MAX_VALUE;
+
+ /* Path as Connected Edge list from the source up to the Connected Vertex */
+ private ArrayList<ConnectedEdge> currentPath = new ArrayList<ConnectedEdge>();
+
+ /* Penultimate Connected Vertex in the current Path */
+ private Long predecessor;
+
+ public static final byte UNKNOWN = 0x00;
+ public static final byte ACTIVE = 0x01;
+ public static final byte SELECTED = 0x02;
+ public static final byte DOMINATED = 0x03;
+ public static final byte PROCESSED = 0x04;
+ private byte pathStatus;
+ /* Key used by the Priority Queue to sort the paths */
+ private Integer key = Integer.MAX_VALUE;
+
+ public CspfPath(ConnectedVertex vertex) {
+ this.cvertex = vertex;
+ }
+
+ public ConnectedVertex getVertex() {
+ return this.cvertex;
+ }
+
+ public Long getVertexKey() {
+ return this.cvertex.getKey();
+ }
+
+ public CspfPath setCost(int cost) {
+ this.cost = cost;
+ return this;
+ }
+
+ public int getCost() {
+ return this.cost;
+ }
+
+ public CspfPath setDelay(int delay) {
+ this.delay = delay;
+ return this;
+ }
+
+ public int getDelay() {
+ return this.delay;
+ }
+
+ public CspfPath addConnectedEdge(ConnectedEdge edge) {
+ this.currentPath.add(edge);
+ return this;
+ }
+
+ public CspfPath replacePath(List<ConnectedEdge> list) {
+ if ((list != null) && (list.size() != 0)) {
+ this.currentPath.clear();
+ }
+ this.currentPath.addAll(list);
+ return this;
+ }
+
+ public List<ConnectedEdge> getPath() {
+ return this.currentPath;
+ }
+
+ public int getPathCount() {
+ return this.currentPath.size();
+ }
+
+ public CspfPath setPathStatus(byte status) {
+ this.pathStatus = status;
+ return this;
+ }
+
+ public byte getPathStatus() {
+ return this.pathStatus;
+ }
+
+ public CspfPath setPredecessor(Long vertexId) {
+ this.predecessor = vertexId;
+ return this;
+ }
+
+ public Long getPredecessor() {
+ return this.predecessor;
+ }
+
+ public CspfPath setPathLength(float length) {
+ this.pathLength = length;
+ return this;
+ }
+
+ public float getPathLength() {
+ return this.pathLength;
+ }
+
+ public void clearPath() {
+ this.currentPath.clear();
+ }
+
+ /*
+ * Definition of the comparator method to be used by the java Priority Queue:
+ * "In the PQ the elements are classified relying on the "key" attribute. The "compareTo" method return a negative,
+ * zero or positive integer as this object is less than, equal to or greater than the specified object"
+ *
+ * The "key" attribute is here represented by the weight of the associated Vertex in the Path. For example in
+ * Shortest Path First algorithm, the key represent the cost between the source and the Vertex.
+ *
+ * The "equals" method performs the comparison on the Vertex Key. The "equals" method is used by the "remove"
+ * method of the priority queue
+ *
+ */
+
+ public CspfPath setKey(Integer key) {
+ this.key = key;
+ return this;
+ }
+
+ public Integer getKey() {
+ return this.key;
+ }
+
+ @Override
+ public int compareTo(CspfPath other) {
+ return this.key.compareTo(other.getKey());
+ }
+
+ @Override
+ public boolean equals(Object object) {
+ if (!(object instanceof CspfPath)) {
+ return false;
+ }
+
+ CspfPath cspfPath = (CspfPath) object;
+ return this.getVertexKey().equals(cspfPath.getVertexKey());
+ }
+
+ @Override
+ public int hashCode() {
+ return this.cvertex.getKey().hashCode();
+ }
+
+}
--- /dev/null
+/*
+ * Copyright (c) 2020 Orange. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.algo.impl;
+
+import static com.google.common.base.Preconditions.checkArgument;
+
+import com.google.common.util.concurrent.ListenableFuture;
+import org.opendaylight.algo.PathComputationAlgorithm;
+import org.opendaylight.algo.PathComputationProvider;
+import org.opendaylight.graph.ConnectedGraph;
+import org.opendaylight.graph.ConnectedGraphProvider;
+import org.opendaylight.mdsal.binding.api.RpcProviderService;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev191125.graph.topology.graph.VertexKey;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.AlgorithmType;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ComputationStatus;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ConstrainedPath;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.GetConstrainedPathInput;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.GetConstrainedPathOutput;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.GetConstrainedPathOutputBuilder;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.PathComputationService;
+import org.opendaylight.yangtools.concepts.ObjectRegistration;
+import org.opendaylight.yangtools.yang.common.RpcError;
+import org.opendaylight.yangtools.yang.common.RpcResult;
+import org.opendaylight.yangtools.yang.common.RpcResultBuilder;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+/**
+ * Path Computation Algorithms provider.
+ *
+ * @author Olivier Dugeon
+ */
+public class PathComputationServer implements AutoCloseable, PathComputationService, PathComputationProvider {
+
+ private static final Logger LOG = LoggerFactory.getLogger(PathComputationServer.class);
+
+ private ObjectRegistration<PathComputationService> pathService;
+ private RpcProviderService rpcProviderRegistry;
+ private ConnectedGraphProvider graphProvider;
+
+ private ConnectedGraph cgraph;
+
+ public PathComputationServer(final RpcProviderService rpcService, final ConnectedGraphProvider graphProvider) {
+ checkArgument(rpcService != null);
+ checkArgument(graphProvider != null);
+ this.rpcProviderRegistry = rpcService;
+ this.graphProvider = graphProvider;
+ }
+
+ public void init() {
+ pathService = this.rpcProviderRegistry.registerRpcImplementation(PathComputationService.class, this);
+ }
+
+ @Override
+ public ListenableFuture<RpcResult<GetConstrainedPathOutput>> getConstrainedPath(
+ final GetConstrainedPathInput input) {
+ final GetConstrainedPathOutputBuilder output = new GetConstrainedPathOutputBuilder();
+
+ LOG.info("Got Path Computation Service request");
+
+ /* First, get graph */
+ this.cgraph = graphProvider.getConnectedGraph(input.getGraphName());
+ if (this.cgraph == null) {
+ output.setStatus(ComputationStatus.Failed);
+ return RpcResultBuilder.<GetConstrainedPathOutput>failed()
+ .withError(RpcError.ErrorType.RPC, "Unknown Graph Name").buildFuture();
+ }
+
+ /* get a new Path Computation Algorithm according to Input choice */
+ PathComputationAlgorithm algo = getPathComputationAlgorithm(this.cgraph, input.getAlgorithm());
+ if (algo == null) {
+ output.setStatus(ComputationStatus.Failed);
+ return RpcResultBuilder.<GetConstrainedPathOutput>failed()
+ .withError(RpcError.ErrorType.RPC, "Unknown Path Computation Algorithm").buildFuture();
+ }
+
+ /*
+ * Request Path Computation for given source, destination and
+ * constraints
+ */
+ final VertexKey source = new VertexKey(input.getSource());
+ final VertexKey destination = new VertexKey(input.getDestination());
+ LOG.info("Call Path Computation {} algorithm for path from {} to {} with contraints {}",
+ input.getAlgorithm().getName(), source, destination, input.getConstraints());
+ final ConstrainedPath cpath = algo.computeP2pPath(source, destination, input.getConstraints());
+
+ /* Send back the Computed Path */
+ output.setPathDescription(cpath.getPathDescription()).setStatus(cpath.getStatus())
+ .setComputedMetric(cpath.getMetric()).setComputedTeMetric(cpath.getTeMetric())
+ .setComputedDelay(cpath.getDelay());
+
+ return RpcResultBuilder.success(output.build()).buildFuture();
+ }
+
+ @Override
+ public void close() throws Exception {
+ pathService.close();
+ }
+
+ @Override
+ public PathComputationAlgorithm getPathComputationAlgorithm(ConnectedGraph runningGraph,
+ AlgorithmType algorithmType) {
+ PathComputationAlgorithm algo = null;
+ switch (algorithmType) {
+ case Spf:
+ algo = new ShortestPathFirst(runningGraph);
+ break;
+ case Cspf:
+ algo = new ConstrainedShortestPathFirst(runningGraph);
+ break;
+ case Samcra:
+ algo = new Samcra(runningGraph);
+ break;
+ default:
+ break;
+ }
+ return algo;
+ }
+}
--- /dev/null
+/*
+ * Copyright (c) 2020 Orange. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.algo.impl;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+
+import org.opendaylight.graph.ConnectedEdge;
+import org.opendaylight.graph.ConnectedGraph;
+import org.opendaylight.graph.ConnectedVertex;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev191125.Delay;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev191125.graph.topology.graph.VertexKey;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ComputationStatus;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ConstrainedPath;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ConstrainedPathBuilder;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.PathConstraints;
+import org.opendaylight.yangtools.yang.common.Uint32;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+/**
+ * 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
+ * @author Olivier Dugeon
+ * @author Philippe Cadro
+ *
+ */
+
+public class Samcra extends AbstractPathComputation {
+
+ /*
+ * This class stores the set of paths which has been computed for a given Connected Vertex:
+ * - pathCount number of active paths
+ * - pathCurrent node path currently in the priority queue (path with minimal length)
+ * - pathList list of computed paths
+ *
+ * Each path is represented by a "CspfPath" class to encompass path predecessor, path status
+ * and path length information
+ */
+
+ private static class SamcraPath {
+
+ private ConnectedVertex cvertex;
+ private int pathCount;
+ private CspfPath currentPath = null;
+ private ArrayList<CspfPath> pathList;
+
+ SamcraPath(ConnectedVertex vertex) {
+ this.cvertex = vertex;
+ this.pathCount = 0;
+ pathList = new ArrayList<CspfPath>();
+ }
+
+ public ConnectedVertex getVertex() {
+ return this.cvertex;
+ }
+
+ public void decrementPathCount() {
+ this.pathCount--;
+ }
+
+ public void incrementPathCount() {
+ this.pathCount++;
+ }
+
+ public int getPathCount() {
+ return this.pathCount;
+ }
+
+ public void setCurrentPath(CspfPath path) {
+ this.currentPath = path;
+ }
+
+ public CspfPath getCurrentPath() {
+ return this.currentPath;
+ }
+
+ public void addPath(CspfPath path) {
+ this.pathList.add(path);
+ }
+
+ public ArrayList<CspfPath> getPathList() {
+ return this.pathList;
+ }
+ }
+
+ private static final Logger LOG = LoggerFactory.getLogger(Samcra.class);
+
+ /* List of potential Samcra Path that satisfy given constraints */
+ private HashMap<Long, SamcraPath> samcraPaths;
+
+ /* TE Metric cost and Delay cost for the current selected Path */
+ int teCost = Integer.MAX_VALUE;
+ int delayCost = Integer.MAX_VALUE;
+
+ public Samcra(ConnectedGraph graph) {
+ super(graph);
+ samcraPaths = new HashMap<Long, SamcraPath>();
+ }
+
+ /* Samcra Algo:
+ *
+ * To limit the modification outside the Samcra method the same set of parameters as
+ * the CSPF method is used (related to pseudo code, the path length is computed inside
+ * the method based on the individual constraint parameters).
+ *
+ * On contrast to a simple CSPF algo, with Samcra a connected vertex might be associated to several
+ * metric vectors from which different path lengths are computed. However a connected vertex is only
+ * present once in the priority queue, associated to the minimal path weight, which is used as key
+ * to address the priority queue.
+ *
+ * For a given metric the path weight is an integer value computed as the entire part of
+ * the quantity:
+ * 100 * (vector_path_metric/target_metric)
+ * The path weight correspond to the maximum length computed from either the delay or TE metric.
+ *
+ * To maintain the priority queue behavior unchanged, a "SamcraPath" classes is created to manage
+ * the set of possible paths associated to a given vertex (see above).
+ *
+ */
+
+ @Override
+ public ConstrainedPath computeP2pPath(VertexKey src, VertexKey dst, PathConstraints cts) {
+ ConstrainedPathBuilder cpathBuilder;
+ List<ConnectedEdge> edges;
+ CspfPath currentPath;
+
+ LOG.info("Start SAMCRA Path Computation from {} to {} with constraints {}", src, dst, cts);
+
+ /* Initialize SAMCRA variables */
+ this.constraints = cts;
+ cpathBuilder = initializePathComputation(src, dst);
+ if (cpathBuilder.getStatus() == ComputationStatus.Failed) {
+ return cpathBuilder.build();
+ }
+ cpathBuilder.setBandwidth(cts.getBandwidth()).setClassType(cts.getClassType());
+
+ samcraPaths.clear();
+ samcraPaths.put(pathSource.getVertexKey(), new SamcraPath(pathSource.getVertex()));
+ samcraPaths.put(pathDestination.getVertexKey(), new SamcraPath(pathDestination.getVertex()));
+
+ /* Exploration of the priority queue:
+ * Each connected vertex is represented only once in the priority queue associated to the path
+ * with the minimal length (other path are stored in the SamcraPath object).
+ * The top of the queue, i.e. the element with the minimal key( path weight), is processed at each loop
+ */
+ while (priorityQueue.size() != 0) {
+ currentPath = priorityQueue.poll();
+ LOG.debug("Process path to Vertex {} from Priority Queue", currentPath.getVertex().toString());
+
+ /* Prepare Samcra Path from current CSP Path except for the source */
+ if (!(currentPath.equals(pathSource))) {
+ SamcraPath currentSamcraPath = samcraPaths.get(currentPath.getVertexKey());
+ CspfPath currentCspfPath = currentSamcraPath.getCurrentPath();
+ float queuePathLength = currentCspfPath.getPathLength();
+ LOG.trace("Samcra: priority Queue output SamcraPaths: {} CurrentPath: {} PathLength: {}",
+ currentSamcraPath.currentPath.getPath(), currentCspfPath.getPath(), queuePathLength);
+ }
+
+ edges = currentPath.getVertex().getOutputConnectedEdges();
+ float currentPathLength = 1.0F;
+ for (ConnectedEdge edge : edges) {
+ /* Connected Vertex's edges processing:
+ * Prune the connected edges that do not satisfy the constraints (Bandwidth, TE Metric, Delay, Loss)
+ * For each remaining edge process the path to the remote vertex using the "relaxSamcra" procedure
+ *
+ * If the return path length is positive, the destination is reached and the
+ * obtained route satisfies the requested constraints.
+ * The path length is checked to record only the optimal route (i.e. the route with
+ * the minimal path length) info obtained from the destination vertex
+ */
+ if (pruneEdge(edge, currentPath)) {
+ LOG.trace(" Prune Edge {}", edge.toString());
+ continue;
+ }
+ float pathLength = relaxSamcra(edge, currentPath, pathSource);
+
+ /* Check if we found a valid and better path */
+ if ((pathLength > 0F) && (pathLength <= currentPathLength)) {
+ final SamcraPath finalPath = samcraPaths.get(pathDestination.getVertexKey());
+ cpathBuilder.setPathDescription(getPathDescription(finalPath.getCurrentPath().getPath()))
+ .setMetric(Uint32.valueOf(pathDestination.getCost()))
+ .setDelay(new Delay(Uint32.valueOf(pathDestination.getDelay())))
+ .setStatus(ComputationStatus.Active);
+ LOG.debug("Samcra: path to destination found and registered: {}",
+ cpathBuilder.getPathDescription());
+ currentPathLength = pathLength;
+ }
+ }
+
+ /* The connected vertex that has been removed from the priority queue may have to be re-inserted with
+ * the minimal length non-dominated path associated to the connected vertex if it exists (to be done
+ * except for the source). Otherwise, the current path associated to the connected vertex is reset to
+ * null to allow the connected vertex addition to the priority queue later on with a new path
+ * (refer to "relaxSamcra" for addition of a connected vertex to the priority queue).
+ */
+ float previousLength = 1.0F;
+ CspfPath selectedPath = null;
+
+ if (!(currentPath.equals(pathSource))) {
+ LOG.debug("Samcra: priority queue output processing for connected vertex: {}",
+ currentPath.getVertexKey());
+ SamcraPath currentSamcraPath = samcraPaths.get(currentPath.getVertexKey());
+ currentSamcraPath.decrementPathCount();
+ /*
+ * The list of paths associated to the connected vertex is retrieved
+ * The path used to represent the connected vertex in the Priority Queue is marked from "selected"
+ * to "processed". The list of paths is analyzed to check if other "active" path(s) exist(s).
+ * If it is the case the shortest length is used to re-inject the connected vertex in the Priority Queue
+ */
+ for (CspfPath testedPath : currentSamcraPath.getPathList()) {
+ LOG.debug("Samcra: priority queue output: testedPath: {} status: {} ", testedPath,
+ testedPath.getPathStatus());
+ if (testedPath.getPathStatus() == CspfPath.SELECTED) {
+ testedPath.setPathStatus(CspfPath.PROCESSED);
+ } else if ((testedPath.getPathStatus() == CspfPath.ACTIVE)
+ && (testedPath.getPathLength() < previousLength)) {
+ selectedPath = testedPath;
+ previousLength = testedPath.getPathLength();
+ }
+ }
+ /* If a path is found it is marked as "selected", used as "current path" for the connected vertex
+ * and added to the priority queue
+ */
+ if (selectedPath != null) {
+ selectedPath.setPathStatus(CspfPath.SELECTED);
+ currentSamcraPath.setCurrentPath(selectedPath);
+ priorityQueue.add(selectedPath);
+ LOG.debug("Samcra priority queue output: add path to the priority queue: {} path count: {} ",
+ selectedPath.getPath(), currentSamcraPath.getPathCount());
+ } else {
+ currentSamcraPath.setCurrentPath(null);
+ }
+ }
+ }
+ /* The priority queue is empty => all the possible (vertex, path) elements have been explored
+ * The "ConstrainedPathBuilder" object contains the optimal path if it exists
+ * Otherwise an empty path with status failed is returned
+ */
+ if ((cpathBuilder.getStatus() == ComputationStatus.InProgress)
+ || (cpathBuilder.getPathDescription().size() == 0)) {
+ cpathBuilder.setStatus(ComputationStatus.Failed);
+ } else {
+ cpathBuilder.setStatus(ComputationStatus.Completed);
+ }
+ return cpathBuilder.build();
+ }
+
+ /* Connected Edge to remote connected vertex processing (on contrast to CSPF algorithm, the already processed
+ * connected vertex are not zapped as a connected vertex may be associated to multiple paths). This method
+ * computes the TE metric and Delay costs up to the remote end-point connected vertex and checks if the computed
+ * values are acceptable according to the end-to-end constraints.
+ * If relevant, update the computed path on the remote end-point connected vertex.
+ * If the connected vertex has not already been processed, the corresponding CspfPath object is created.
+ */
+ private float relaxSamcra(ConnectedEdge edge, CspfPath currentPath, CspfPath source) {
+ LOG.debug(" Start SAMCRA relaxing Edge {} to Vertex {}", edge.toString(), edge.getDestination().toString());
+
+ /* Process CspfPath including the next Vertex */
+ CspfPath nextVertexPath = processedPath.get(edge.getDestination().getKey());
+ if (nextVertexPath == null) {
+ nextVertexPath = new CspfPath(edge.getDestination());
+ processedPath.put(nextVertexPath.getVertexKey(), nextVertexPath);
+ SamcraPath nextSamcraPath = new SamcraPath(edge.getDestination());
+ samcraPaths.put(nextVertexPath.getVertexKey(), nextSamcraPath);
+ LOG.debug("relaxSamcra: next connected vertex does not exists, create it: {} with new Samcra Path: {}",
+ nextVertexPath.toString(), nextSamcraPath);
+ }
+
+ /* Connected Vertex's paths management using SamcraPath object.
+ * The predecessor connected vertex is checked to avoid unnecessary processing.
+ */
+ Long predecessorId = 0L;
+ if (!(currentPath.equals(source))) {
+ LOG.debug("relaxSamcra: check predecessor");
+ SamcraPath currentSamcraPath = samcraPaths.get(currentPath.getVertexKey());
+ CspfPath currentVertexPath = currentSamcraPath.getCurrentPath();
+ predecessorId = currentVertexPath.getPredecessor();
+ }
+ if (predecessorId.equals(nextVertexPath.getVertexKey())) {
+ LOG.debug("relaxSamcra: Skip Edge because next vertex: {} is predecessor of: {}",
+ nextVertexPath.getVertexKey(), predecessorId);
+ return 0F;
+ }
+
+ /* Connected Vertex's paths management using CspfPath object.
+ * The paths list is explored and the paths dominated by the new path are marked as dominated.
+ * The new path is also check and if it is dominated by an existing path it is omitted.
+ */
+ if (edge.getEdge().getEdgeAttributes().getTeMetric() != null) {
+ teCost = edge.getEdge().getEdgeAttributes().getTeMetric().intValue() + currentPath.getCost();
+ } else {
+ teCost = currentPath.getCost();
+ }
+ if (edge.getEdge().getEdgeAttributes().getDelay() != null) {
+ delayCost = edge.getEdge().getEdgeAttributes().getDelay().getValue().intValue() + currentPath.getDelay();
+ } else {
+ delayCost = currentPath.getDelay();
+ }
+
+ SamcraPath samcraPath = samcraPaths.get(nextVertexPath.getVertexKey());
+ if (isPathDominated(samcraPath)) {
+ LOG.debug("relaxSamcra: Skip Edge because new path is dominated");
+ return 0F;
+ }
+
+ /* If the new path is not dominated by an already existing path, a new "CspfPath" object
+ * is created with predecessor set to connected vertex, path length and path status information,
+ * marked as "active" and added to the connected vertex's path list.
+ * The weight attribute, used as classification key by the priority queue, is an integer value computed
+ * from the TE and delay length.
+ */
+ CspfPath newPath = createNonDominatedPath(edge, nextVertexPath.getVertex(), currentPath);
+
+ /* The new path is check versus the path currently representing the connected vertex in the priority
+ * queue. If there is not yet a path for the connected vertex or if the new path length is shorter
+ * than the length of the path currently selected, the new path is used as current path, marked as
+ * "selected" and is added to the priority queue.
+ * The previously current path status is changed from "selected" to "active" and can be re-selected
+ * later on. If the new path is associated to the destination connected vertex it is not added to
+ * the priority queue.
+ */
+ CspfPath currentSamcraPath = samcraPath.getCurrentPath();
+ if (currentSamcraPath == null) {
+ LOG.debug("relaxSamcra: add new Path: {}", newPath);
+ if (!(newPath.equals(pathDestination))) {
+ priorityQueue.add(newPath);
+ }
+ newPath.setPathStatus(CspfPath.SELECTED);
+ samcraPath.setCurrentPath(newPath);
+ } else if (newPath.getPathLength() < currentSamcraPath.getPathLength()) {
+ LOG.debug("relaxSamcra: update current Path: {} with new Path: {}", currentSamcraPath, newPath);
+ samcraPath.getPathList()
+ .stream()
+ .filter(path -> path.getPathStatus() == CspfPath.SELECTED)
+ .forEach(path -> path.setPathStatus(CspfPath.ACTIVE));
+
+ /* It is not possible to directly update the CspfPath in the Priority Queue. Indeed, if we
+ * modify the path weight, the Priority Queue must be re-ordered. So, we need fist to remove
+ * the CspfPath if it is present in the Priority Queue, then, update the Path Weight,
+ * and finally (re-)insert it in the Priority Queue.
+ */
+ if (!(newPath.equals(pathDestination))) {
+ priorityQueue.removeIf((path) -> path.getVertexKey().equals(newPath.getVertexKey()));
+ priorityQueue.add(newPath);
+ }
+ newPath.setPathStatus(CspfPath.SELECTED);
+ samcraPath.setCurrentPath(newPath);
+ }
+
+ /* In all cases the new path is added to the list of paths associated to the vertex */
+ samcraPath.addPath(newPath);
+ samcraPath.incrementPathCount();
+
+ LOG.debug("relaxSamcra: number of paths {} ", samcraPath.getPathCount());
+ LOG.debug("relaxSamcra: add vertex Paths to samcraPath {} with index {}", samcraPath,
+ samcraPath.getVertex().getKey());
+ LOG.debug("relaxSamcra: current Path {} predecessor {}", samcraPath.getCurrentPath(),
+ samcraPath.getCurrentPath().getPredecessor());
+ samcraPaths.put(samcraPath.getVertex().getKey(), samcraPath);
+
+ /* If the destination is reached, return the computed path length 0 otherwise */
+ if ((samcraPath.getVertex().getKey()).equals(pathDestination.getVertexKey())) {
+ return samcraPath.getCurrentPath().getPathLength();
+ } else {
+ return 0F;
+ }
+ }
+
+ /**
+ * Evaluate if the current path is dominated by an all one or dominates all previous computed path.
+ *
+ * @param samcraPath Current Samcra Path
+ *
+ * @return true if path is dominated false otherwise
+ */
+ private boolean isPathDominated(SamcraPath samcraPath) {
+ /* Evaluate Path Domination */
+ LOG.debug("Check path domination");
+ Uint32 teMetric = constraints.getTeMetric();
+ Uint32 delay = (constraints.getDelay() != null) ? constraints.getDelay().getValue() : null;
+
+ for (CspfPath testedPath : samcraPath.getPathList()) {
+ boolean pathCostDominated = false;
+ boolean pathDelayDominated = false;
+ boolean testedPathCostDominated = false;
+ boolean testedPathDelayDominated = false;
+
+ LOG.debug("Check if path {} is dominated or dominates", testedPath);
+ if (testedPath.getPathStatus() != CspfPath.DOMINATED) {
+ if (teMetric != null) {
+ if (teCost >= testedPath.getCost()) {
+ pathCostDominated = true;
+ } else {
+ testedPathCostDominated = true;
+ }
+ }
+ if (delay != null) {
+ if (delayCost >= testedPath.getDelay()) {
+ pathDelayDominated = true;
+ } else {
+ testedPathDelayDominated = true;
+ }
+ }
+
+ if ((((teMetric != null) && (pathCostDominated)) && ((pathDelayDominated) || (delay == null)))
+ || ((teMetric == null) && ((delay != null) && (pathDelayDominated)))) {
+ LOG.debug("New path is dominated with teCost: {} delayCost: {}", teCost, delayCost);
+ /* A path that dominates the current path has been found */
+ return true;
+ } else if ((((teMetric != null) && (testedPathCostDominated))
+ && ((testedPathDelayDominated) || (delay == null)))
+ || ((teMetric == null) && ((delay != null) && (testedPathDelayDominated)))) {
+ /* Old Path is dominated by the new path. Mark it as Dominated and decrement number of valid Path */
+ testedPath.setPathStatus(CspfPath.DOMINATED);
+ samcraPath.decrementPathCount();
+ LOG.debug("New path dominates existing path: {} teCost: {} delayCost: {}", testedPath,
+ testedPath.getCost(), testedPath.getDelay());
+ }
+ }
+ }
+ return false;
+ }
+
+ private CspfPath createNonDominatedPath(ConnectedEdge edge, ConnectedVertex vertex, CspfPath cspfPath) {
+ float pathLength = 1.0F;
+ Uint32 metric = constraints.getTeMetric();
+ Uint32 delay = (constraints.getDelay() != null) ? constraints.getDelay().getValue() : null;
+
+ LOG.debug("Create new non dominated path");
+
+ /* Compute Path length as key for the path Weight */
+ float teLength = 0.0F;
+ if ((metric != null) && (metric.intValue() > 0)) {
+ teLength = (float) teCost / metric.intValue();
+ pathLength = teLength;
+ }
+ float delayLength = 0.0F;
+ if ((delay != null) && (delay.intValue() > 0)) {
+ delayLength = (float) delayCost / delay.intValue();
+ if (delayLength > teLength) {
+ pathLength = delayLength;
+ }
+ }
+
+ /* Create new Path with computed TE Metric, Delay and Path Length */
+ CspfPath newPath = new CspfPath(vertex)
+ .setCost(teCost)
+ .setDelay(delayCost)
+ .setKey((int) (100 * pathLength))
+ .setPathStatus(CspfPath.ACTIVE)
+ .setPathLength(pathLength)
+ .setPredecessor(cspfPath.getVertexKey())
+ .replacePath(cspfPath.getPath())
+ .addConnectedEdge(edge);
+
+ LOG.debug("Creation of a new Path: {} path length: {} predecessor connected vertex {}",
+ newPath, pathLength, newPath.getPredecessor());
+
+ return cspfPath;
+ }
+}
--- /dev/null
+/*
+ * Copyright (c) 2016 Orange. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.algo.impl;
+
+import java.util.HashMap;
+import java.util.List;
+
+import org.opendaylight.graph.ConnectedEdge;
+import org.opendaylight.graph.ConnectedGraph;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev191125.graph.topology.graph.VertexKey;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ComputationStatus;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ConstrainedPath;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ConstrainedPathBuilder;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.PathConstraints;
+import org.opendaylight.yangtools.yang.common.Uint32;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+
+/**
+ * This Class implements a simple Shortest Path First path computation algorithm based on standard IGP Metric.
+ *
+ * @author Olivier Dugeon
+ * @author Philippe Niger
+ * @author Philippe Cadro
+ *
+ */
+public class ShortestPathFirst extends AbstractPathComputation {
+
+ private static final Logger LOG = LoggerFactory.getLogger(ShortestPathFirst.class);
+
+ private HashMap<Long, CspfPath> visitedVertices;
+
+ public ShortestPathFirst(ConnectedGraph graph) {
+ super(graph);
+ visitedVertices = new HashMap<Long, CspfPath>();
+ }
+
+ public ConstrainedPath computeP2pPath(VertexKey src, VertexKey dst, PathConstraints cts) {
+ ConstrainedPathBuilder cpathBuilder;
+ List<ConnectedEdge> edges;
+ CspfPath currentPath;
+ int currentCost = Integer.MAX_VALUE;
+
+ LOG.info("Start SPF Path Computation from {} to {} with constraints {}", src, dst, cts);
+
+ /* Initialize algorithm */
+ this.constraints = cts;
+ cpathBuilder = initializePathComputation(src, dst);
+ if (cpathBuilder.getStatus() == ComputationStatus.Failed) {
+ LOG.warn("Initial configurations are not met. Abort!");
+ return cpathBuilder.build();
+ }
+
+ visitedVertices.clear();
+
+ while (priorityQueue.size() != 0) {
+ currentPath = priorityQueue.poll();
+ visitedVertices.put(currentPath.getVertexKey(), currentPath);
+ LOG.debug("Process path to Vertex {} from Priority Queue", currentPath.getVertex().toString());
+ edges = currentPath.getVertex().getOutputConnectedEdges();
+
+ for (ConnectedEdge edge : edges) {
+ /* Check that Edge point to a valid Vertex and is suitable for the Constraint Address Family */
+ if (pruneEdge(edge, currentPath)) {
+ LOG.trace(" Prune Edge {}", edge.toString());
+ continue;
+ }
+ if ((relax(edge, currentPath)) && (pathDestination.getCost() < currentCost)) {
+ currentCost = pathDestination.getCost();
+ cpathBuilder.setPathDescription(getPathDescription(pathDestination.getPath()))
+ .setMetric(Uint32.valueOf(pathDestination.getCost()))
+ .setStatus(ComputationStatus.Active);
+ LOG.debug(" Found a valid path up to destination {}", cpathBuilder.getPathDescription());
+ }
+ }
+ }
+ /* The priority queue is empty => all the possible (vertex, path) elements have been explored
+ * The "ConstrainedPathBuilder" object contains the optimal path if it exists
+ * Otherwise an empty path with status failed is returned
+ */
+ if ((cpathBuilder.getStatus() == ComputationStatus.InProgress)
+ || (cpathBuilder.getPathDescription().size() == 0)) {
+ cpathBuilder.setStatus(ComputationStatus.Failed);
+ } else {
+ cpathBuilder.setStatus(ComputationStatus.Completed);
+ }
+ return cpathBuilder.build();
+ }
+
+ private boolean relax(ConnectedEdge edge, CspfPath currentPath) {
+ LOG.debug(" Start relaxing Edge {} to Vertex {}", edge.toString(), edge.getDestination().toString());
+ final Long nextVertexKey = edge.getDestination().getKey();
+
+ /* Verify if we have not visited this Vertex to avoid loop */
+ if (visitedVertices.containsKey(nextVertexKey)) {
+ return false;
+ }
+
+ /* Get Next Vertex from processedPath or create a new one if it has not yet processed */
+ CspfPath nextPath = processedPath.get(nextVertexKey);
+ if (nextPath == null) {
+ nextPath = new CspfPath(edge.getDestination());
+ processedPath.put(nextPath.getVertexKey(), nextPath);
+ }
+
+ /* Compute Cost from source to this next Vertex and add or update it in the Priority Queue
+ * if total path Cost is lower than cost associated to this next Vertex.
+ * This could occurs if we process a Vertex that as not yet been visited in the Graph
+ * or if we found a shortest path up to this Vertex. */
+ int totalCost = edge.getEdge().getEdgeAttributes().getMetric().intValue() + currentPath.getCost();
+ if (nextPath.getCost() > totalCost) {
+ nextPath.setCost(totalCost)
+ .replacePath(currentPath.getPath())
+ .addConnectedEdge(edge);
+ /* It is not possible to directly update the CspfPath in the Priority Queue. Indeed, if we modify the path
+ * weight, the Priority Queue must be re-ordered. So, we need fist to remove the CspfPath if it is present
+ * in the Priority Queue, then, update the Path Weight, and finally (re-)insert it in the Priority Queue.
+ */
+ priorityQueue.removeIf((path) -> path.getVertexKey().equals(nextVertexKey));
+ nextPath.setKey(totalCost);
+ priorityQueue.add(nextPath);
+ LOG.debug(" Added path to Vertex {} in the Priority Queue with weight {}",
+ nextPath.getVertex().toString(), nextPath.getKey());
+ }
+ /* Return True if we reach the destination, false otherwise */
+ return pathDestination.equals(nextPath);
+ }
+}
--- /dev/null
+<?xml version="1.0" encoding="UTF-8"?>
+<!--
+ Copyright (c) 2020 Orange. All rights reserved.
+
+ This program and the accompanying materials are made available under the
+ terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ and is available at http://www.eclipse.org/legal/epl-v10.html
+-->
+<blueprint xmlns="http://www.osgi.org/xmlns/blueprint/v1.0.0"
+ xmlns:odl="http://opendaylight.org/xmlns/blueprint/v1.0.0">
+
+ <reference id="connectedGraphProvider" interface="org.opendaylight.graph.ConnectedGraphProvider"/>
+ <reference id="rpcRegistry" interface="org.opendaylight.mdsal.binding.api.RpcProviderService"/>
+
+ <bean id="pathComputationProvider"
+ class="org.opendaylight.algo.impl.PathComputationServer"
+ destroy-method="close"
+ init-method="init">
+ <argument ref="rpcRegistry"/>
+ <argument ref="connectedGraphProvider"/>
+ </bean>
+
+ <service ref="pathComputationProvider" interface="org.opendaylight.algo.PathComputationProvider" />
+
+</blueprint>
--- /dev/null
+<?xml version="1.0" encoding="UTF-8"?>
+<!--
+ Copyright (c) 2018 Orange Labs. All rights reserved.
+
+ This program and the accompanying materials are made available under the
+ terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ and is available at http://www.eclipse.org/legal/epl-v10.html
+-->
+<blueprint xmlns="http://www.osgi.org/xmlns/blueprint/v1.0.0"
+ xmlns:odl="http://opendaylight.org/xmlns/blueprint/v1.0.0">
+
+ <reference id="tedProvider" interface="org.opendaylight.bgpcep.bgp.topology.provider.spi.TEDProvider"/>
+
+ <bean id="pathComputationProvider"
+ class="org.opendaylight.bgpcep.pcep.server.algo.PathComputationFactory"
+ destroy-method="close"
+ init-method="init">
+ <argument ref="tedProvider"/>
+ </bean>
+
+ <service ref="pathComputationProvider" interface="org.opendaylight.bgpcep.pcep.server.algo.PathComputationProvider"/>
+
+</blueprint>
--- /dev/null
+<?xml version="1.0" encoding="UTF-8"?>
+<!--
+ Copyright (c) 2019 Orange Labs. All rights reserved.
+
+ This program and the accompanying materials are made available under the
+ terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ and is available at http://www.eclipse.org/legal/epl-v10.html
+-->
+<project xmlns="http://maven.apache.org/POM/4.0.0"
+ xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+ xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+ <modelVersion>4.0.0</modelVersion>
+ <parent>
+ <groupId>org.opendaylight.odlparent</groupId>
+ <artifactId>odlparent-lite</artifactId>
+ <version>6.0.4</version>
+ <relativePath/>
+ </parent>
+
+ <groupId>org.opendaylight.bgpcep</groupId>
+ <artifactId>algo-parent</artifactId>
+ <version>0.14.0-SNAPSHOT</version>
+ <packaging>pom</packaging>
+ <description>Path Computation Algorithms components</description>
+ <name>${project.artifactId}</name>
+
+ <modules>
+ <module>algo-artifacts</module>
+ <module>algo-api</module>
+ <module>algo-impl</module>
+ </modules>
+
+ <properties>
+ <maven.deploy.skip>true</maven.deploy.skip>
+ <maven.install.skip>true</maven.install.skip>
+ </properties>
+</project>
<scope>import</scope>
<type>pom</type>
</dependency>
+ <dependency>
+ <groupId>${project.groupId}</groupId>
+ <artifactId>algo-artifacts</artifactId>
+ <version>${project.version}</version>
+ <scope>import</scope>
+ <type>pom</type>
+ </dependency>
<dependency>
<groupId>${project.groupId}</groupId>
<artifactId>topology-artifacts</artifactId>
<type>xml</type>
<scope>runtime</scope>
</dependency>
+ <dependency>
+ <groupId>org.opendaylight.bgpcep</groupId>
+ <artifactId>features-algo</artifactId>
+ <classifier>features</classifier>
+ <type>xml</type>
+ <scope>runtime</scope>
+ </dependency>
<dependency>
<groupId>org.opendaylight.bgpcep</groupId>
<artifactId>features-rsvp</artifactId>
--- /dev/null
+<?xml version="1.0" encoding="UTF-8"?>
+<!--
+ Copyright (c) 2019 Orange Labs and others. All rights reserved.
+
+ This program and the accompanying materials are made available under the
+ terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ and is available at http://www.eclipse.org/legal/epl-v10.html
+-->
+<project xmlns="http://maven.apache.org/POM/4.0.0"
+ xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+ xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+ <modelVersion>4.0.0</modelVersion>
+ <parent>
+ <groupId>org.opendaylight.bgpcep</groupId>
+ <artifactId>feature-repo-parent</artifactId>
+ <version>0.14.0-SNAPSHOT</version>
+ <relativePath>../../../feature-repo-parent</relativePath>
+ </parent>
+
+ <artifactId>features-algo</artifactId>
+ <packaging>feature</packaging>
+
+ <dependencies>
+ <dependency>
+ <groupId>${project.groupId}</groupId>
+ <artifactId>odl-bgpcep-algo</artifactId>
+ <type>xml</type>
+ <classifier>features</classifier>
+ </dependency>
+ <dependency>
+ <groupId>${project.groupId}</groupId>
+ <artifactId>odl-bgpcep-algo-api</artifactId>
+ <type>xml</type>
+ <classifier>features</classifier>
+ </dependency>
+ <dependency>
+ <groupId>${project.groupId}</groupId>
+ <artifactId>odl-bgpcep-graph-api</artifactId>
+ <type>xml</type>
+ <classifier>features</classifier>
+ </dependency>
+ <dependency>
+ <groupId>${project.groupId}</groupId>
+ <artifactId>odl-bgpcep-graph</artifactId>
+ <type>xml</type>
+ <classifier>features</classifier>
+ </dependency>
+ </dependencies>
+</project>
--- /dev/null
+<?xml version="1.0" encoding="UTF-8"?>
+<!--
+ Copyright (c) 2019 Orange Labs and others. All rights reserved.
+
+ This program and the accompanying materials are made available under the
+ terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ and is available at http://www.eclipse.org/legal/epl-v10.html
+-->
+<project xmlns="http://maven.apache.org/POM/4.0.0"
+ xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+ xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+ <modelVersion>4.0.0</modelVersion>
+ <parent>
+ <groupId>org.opendaylight.bgpcep</groupId>
+ <artifactId>single-feature-parent</artifactId>
+ <version>0.14.0-SNAPSHOT</version>
+ <relativePath>../../../single-feature-parent</relativePath>
+ </parent>
+
+ <artifactId>odl-bgpcep-algo-api</artifactId>
+ <packaging>feature</packaging>
+ <name>OpenDaylight :: Path Computation Algorithms :: API</name>
+
+ <dependencies>
+ <dependency>
+ <groupId>${project.groupId}</groupId>
+ <artifactId>algo-api</artifactId>
+ </dependency>
+ <dependency>
+ <groupId>org.opendaylight.mdsal.model</groupId>
+ <artifactId>odl-mdsal-model-rfc6991</artifactId>
+ <type>xml</type>
+ <classifier>features</classifier>
+ </dependency>
+ <dependency>
+ <groupId>org.opendaylight.mdsal.model</groupId>
+ <artifactId>odl-mdsal-model-odl-uint24</artifactId>
+ <type>xml</type>
+ <classifier>features</classifier>
+ </dependency>
+ </dependencies>
+</project>
--- /dev/null
+<?xml version="1.0" encoding="UTF-8"?>
+<!--
+ Copyright (c) 2019 Orange Labs and others. All rights reserved.
+
+ This program and the accompanying materials are made available under the
+ terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ and is available at http://www.eclipse.org/legal/epl-v10.html
+-->
+<project xmlns="http://maven.apache.org/POM/4.0.0"
+ xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+ xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+ <modelVersion>4.0.0</modelVersion>
+ <parent>
+ <groupId>org.opendaylight.bgpcep</groupId>
+ <artifactId>single-feature-parent</artifactId>
+ <version>0.14.0-SNAPSHOT</version>
+ <relativePath>../../../single-feature-parent</relativePath>
+ </parent>
+
+ <artifactId>odl-bgpcep-algo</artifactId>
+ <packaging>feature</packaging>
+ <name>OpenDaylight :: Path Computation Algorithms</name>
+
+ <dependencies>
+ <dependency>
+ <groupId>${project.groupId}</groupId>
+ <artifactId>algo-impl</artifactId>
+ </dependency>
+ <dependency>
+ <groupId>${project.groupId}</groupId>
+ <artifactId>odl-bgpcep-algo-api</artifactId>
+ <type>xml</type>
+ <classifier>features</classifier>
+ </dependency>
+ <dependency>
+ <groupId>${project.groupId}</groupId>
+ <artifactId>odl-bgpcep-graph</artifactId>
+ <type>xml</type>
+ <classifier>features</classifier>
+ </dependency>
+ </dependencies>
+</project>
--- /dev/null
+<?xml version="1.0" encoding="UTF-8"?>
+<!--
+ Copyright (c) 2019 Orange Labs and others. All rights reserved.
+
+ This program and the accompanying materials are made available under the
+ terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ and is available at http://www.eclipse.org/legal/epl-v10.html
+-->
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+ <modelVersion>4.0.0</modelVersion>
+ <parent>
+ <groupId>org.opendaylight.odlparent</groupId>
+ <artifactId>odlparent-lite</artifactId>
+ <version>6.0.4</version>
+ <relativePath/>
+ </parent>
+
+ <artifactId>features-aggregator-algo</artifactId>
+ <groupId>org.opendaylight.bgpcep</groupId>
+ <version>0.14.0-SNAPSHOT</version>
+ <packaging>pom</packaging>
+
+ <modules>
+ <module>features-algo</module>
+ <module>odl-bgpcep-algo-api</module>
+ <module>odl-bgpcep-algo</module>
+ </modules>
+
+ <properties>
+ <maven.deploy.skip>true</maven.deploy.skip>
+ <maven.install.skip>true</maven.install.skip>
+ </properties>
+</project>
<module>bgp</module>
<module>pcep</module>
<module>graph</module>
+ <module>algo</module>
<module>bgpcep-extras</module>
<module>bmp</module>
<module>rsvp</module>
<module>bgp</module>
<module>bmp</module>
<module>graph</module>
+ <module>algo</module>
<module>pcep</module>
<module>programming</module>
<module>rsvp</module>
Code Review / bgpcep.git / commitdiff