algo/algo-impl/src/main/java/org/opendaylight/algo/impl/ConstrainedShortestPathFirst.java

   1 /*
   2  * Copyright (c) 2016 Orange. All rights reserved.
   3  *
   4  * This program and the accompanying materials are made available under the
   5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   6  * and is available at http://www.eclipse.org/legal/epl-v10.html
   7  */
   8 package org.opendaylight.algo.impl;
   9
  10 import java.util.HashMap;
  11 import java.util.List;
  12
  13 import org.opendaylight.graph.ConnectedEdge;
  14 import org.opendaylight.graph.ConnectedGraph;
  15 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev191125.graph.topology.graph.VertexKey;
  16 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ComputationStatus;
  17 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ConstrainedPath;
  18 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ConstrainedPathBuilder;
  19 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.PathConstraints;
  20 import org.opendaylight.yangtools.yang.common.Uint32;
  21 import org.slf4j.Logger;
  22 import org.slf4j.LoggerFactory;
  23
  24
  25 /**
  26  * This Class implements a simple Constrained Shortest Path First path computation algorithm that take into account
  27  * Bandwidth and TE Metric as constraints.
  28  *
  29  * @author Olivier Dugeon
  30  * @author Philippe Niger
  31  * @author Philippe Cadro
  32  *
  33  */
  34 public class ConstrainedShortestPathFirst extends AbstractPathComputation {
  35
  36     private static final Logger LOG = LoggerFactory.getLogger(ConstrainedShortestPathFirst.class);
  37
  38     private HashMap<Long, CspfPath> visitedVertices;
  39
  40     public ConstrainedShortestPathFirst(ConnectedGraph graph) {
  41         super(graph);
  42         visitedVertices = new HashMap<Long, CspfPath>();
  43     }
  44
  45     public ConstrainedPath computeP2pPath(VertexKey src, VertexKey dst, PathConstraints cts) {
  46         ConstrainedPathBuilder cpathBuilder;
  47         List<ConnectedEdge> edges;
  48         CspfPath currentPath;
  49         int currentCost = Integer.MAX_VALUE;
  50
  51         LOG.info("Start CSPF Path Computation from {} to {} with constraints {}", src, dst, cts);
  52
  53         /* Initialize algorithm */
  54         this.constraints = cts;
  55         cpathBuilder = initializePathComputation(src, dst);
  56         if (cpathBuilder.getStatus() == ComputationStatus.Failed) {
  57             return cpathBuilder.build();
  58         }
  59
  60         cpathBuilder.setBandwidth(cts.getBandwidth()).setClassType(cts.getClassType());
  61
  62         visitedVertices.clear();
  63
  64         /* Process all Connected Vertex until priority queue becomes empty. Connected Vertices are added into the
  65          * priority queue when processing the next Connected Vertex: see relaxMC() method */
  66         while (priorityQueue.size() != 0) {
  67             currentPath = priorityQueue.poll();
  68             visitedVertices.put(currentPath.getVertexKey(), currentPath);
  69             LOG.debug("Got path to Vertex {} from Priority Queue", currentPath.getVertex().toString());
  70             edges = currentPath.getVertex().getOutputConnectedEdges();
  71
  72             for (ConnectedEdge edge : edges) {
  73                 /* Skip Connected Edges that must be prune i.e. Edges that not satisfy the given constraints,
  74                  * in particular the Bandwidth, TE Metric and Delay. */
  75                 if (pruneEdge(edge, currentPath)) {
  76                     LOG.trace("  Prune Edge {}", edge.toString());
  77                     continue;
  78                 }
  79                 if ((relaxMultiConstraints(edge, currentPath)) && (pathDestination.getCost() < currentCost)) {
  80                     currentCost = pathDestination.getCost();
  81                     cpathBuilder.setPathDescription(getPathDescription(pathDestination.getPath()))
  82                             .setMetric(Uint32.valueOf(pathDestination.getCost()))
  83                             .setStatus(ComputationStatus.Active);
  84                     LOG.debug("  Found a valid path up to destination {}", cpathBuilder.getPathDescription());
  85                 }
  86             }
  87         }
  88         /* The priority queue is empty => all the possible (vertex, path) elements have been explored
  89          * The "ConstrainedPathBuilder" object contains the optimal path if it exists
  90          * Otherwise an empty path with status failed is returned
  91          */
  92         if ((cpathBuilder.getStatus() == ComputationStatus.InProgress)
  93                 || (cpathBuilder.getPathDescription().size() == 0)) {
  94             cpathBuilder.setStatus(ComputationStatus.Failed);
  95         } else {
  96             cpathBuilder.setStatus(ComputationStatus.Completed);
  97         }
  98         return cpathBuilder.build();
  99     }
 100
 101     private boolean relaxMultiConstraints(ConnectedEdge edge, CspfPath currentPath) {
 102         LOG.debug("    Start relaxing Multi Constraints on Edge {} to Vertex {}",
 103                 edge.toString(), edge.getDestination().toString());
 104         final Long nextVertexKey = edge.getDestination().getKey();
 105
 106         /* Verify if we have not visited this Vertex to avoid loop */
 107         if (visitedVertices.containsKey(nextVertexKey)) {
 108             return false;
 109         }
 110
 111         /* Get Next Vertex from processedPath or create a new one if it has not yet processed */
 112         CspfPath nextPath = processedPath.get(nextVertexKey);
 113         if (nextPath == null) {
 114             nextPath = new CspfPath(edge.getDestination());
 115             processedPath.put(nextPath.getVertexKey(), nextPath);
 116         }
 117
 118         /* Add or update the CspfPath in the Priority Queue if total path Cost is lower than cost associated
 119          * to this next Vertex. This could occurs if we process a Vertex that as not yet been visited in the Graph
 120          * or if we found a shortest path up to this Vertex. */
 121         int totalCost = edge.getEdge().getEdgeAttributes().getTeMetric().intValue() + currentPath.getCost();
 122         if (totalCost < nextPath.getCost()) {
 123             nextPath.setCost(totalCost)
 124                     .replacePath(currentPath.getPath())
 125                     .addConnectedEdge(edge);
 126             /* It is not possible to directly update the CspfPath in the Priority Queue. Indeed, if we modify the path
 127              * weight, the Priority Queue must be re-ordered. So, we need fist to remove the CspfPath if it is present
 128              * in the Priority Queue, then, update the Path Weight, and finally (re-)insert it in the Priority Queue.
 129              */
 130             priorityQueue.removeIf((path) -> path.getVertexKey().equals(nextVertexKey));
 131             nextPath.setKey(totalCost);
 132             priorityQueue.add(nextPath);
 133             LOG.debug("    Added path to Vertex {} in the Priority Queue", nextPath.getVertex().toString());
 134         }
 135         /* Return True if we reach the destination, false otherwise */
 136         return pathDestination.equals(nextPath);
 137     }
 138 }