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

   1 /*
   2  * Copyright (c) 2020 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.ArrayList;
  11 import java.util.HashMap;
  12 import java.util.List;
  13 import org.opendaylight.graph.ConnectedEdge;
  14 import org.opendaylight.graph.ConnectedGraph;
  15 import org.opendaylight.graph.ConnectedVertex;
  16 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev191125.Delay;
  17 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev191125.graph.topology.graph.VertexKey;
  18 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ComputationStatus;
  19 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ConstrainedPath;
  20 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ConstrainedPathBuilder;
  21 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.PathConstraints;
  22 import org.opendaylight.yangtools.yang.common.Uint32;
  23 import org.slf4j.Logger;
  24 import org.slf4j.LoggerFactory;
  25
  26 /**
  27  * This Class implements the Self Adaptive Multiple Constraints Routing Algorithm (SAMCRA) a Path Computation Algorithm.
  28  * The SAMCRA algorithm take into account the Bandwidth, TE Metric and Delay as composite constraints.
  29  * Details of SAMCRA algorithm could be found in the article "Concepts of Exact QoS Routing Algorithms",
  30  * Piet Van Mieghem and Fernando A. Kuipers, IEEE/ACM Transactions on Networking, Volume 12, Number 5, October 2004.
  31  *
  32  * @author Philippe Niger
  33  * @author Olivier Dugeon
  34  * @author Philippe Cadro
  35  */
  36 public class Samcra extends AbstractPathComputation {
  37     /*
  38      * This class stores the set of paths which has been computed for a given Connected Vertex:
  39      *     - pathCount        number of active paths
  40      *     - pathCurrent      node path currently in the priority queue (path with minimal length)
  41      *     - pathList         list of computed paths
  42      *
  43      * Each path is represented by a "CspfPath" class to encompass path predecessor, path status
  44      * and path length information
  45      */
  46     private static class SamcraPath {
  47
  48         private ConnectedVertex cvertex;
  49         private int pathCount;
  50         private CspfPath currentPath = null;
  51         private ArrayList<CspfPath> pathList;
  52
  53         SamcraPath(ConnectedVertex vertex) {
  54             this.cvertex = vertex;
  55             this.pathCount = 0;
  56             pathList = new ArrayList<CspfPath>();
  57         }
  58
  59         public ConnectedVertex getVertex() {
  60             return this.cvertex;
  61         }
  62
  63         public void decrementPathCount() {
  64             this.pathCount--;
  65         }
  66
  67         public void incrementPathCount() {
  68             this.pathCount++;
  69         }
  70
  71         public int getPathCount() {
  72             return this.pathCount;
  73         }
  74
  75         public void setCurrentPath(CspfPath path) {
  76             this.currentPath = path;
  77         }
  78
  79         public CspfPath getCurrentPath() {
  80             return this.currentPath;
  81         }
  82
  83         public void addPath(CspfPath path) {
  84             this.pathList.add(path);
  85         }
  86
  87         public ArrayList<CspfPath> getPathList() {
  88             return this.pathList;
  89         }
  90     }
  91
  92     private static final Logger LOG = LoggerFactory.getLogger(Samcra.class);
  93
  94     /* List of potential Samcra Path that satisfy given constraints */
  95     private HashMap<Long, SamcraPath> samcraPaths;
  96
  97     /* TE Metric cost and Delay cost for the current selected Path */
  98     int teCost = Integer.MAX_VALUE;
  99     /* Uint24 Max value */
 100     int delayCost = 16777215;
 101
 102     public Samcra(ConnectedGraph graph) {
 103         super(graph);
 104         samcraPaths = new HashMap<Long, SamcraPath>();
 105     }
 106
 107     /* Samcra Algo:
 108      *
 109      * To limit the modification outside the Samcra method the same set of parameters as
 110      * the CSPF method is used (related to pseudo code, the path length is computed inside
 111      * the method based on the individual constraint parameters).
 112      *
 113      * On contrast to a simple CSPF algo, with Samcra a connected vertex might be associated to several
 114      * metric vectors from which different path lengths are computed. However a connected vertex is only
 115      * present once in the priority queue, associated to the minimal path weight, which is used as key
 116      * to address the priority queue.
 117      *
 118      * For a given metric the path weight is an integer value computed as the entire part of
 119      * the quantity:
 120      *      100 * (vector_path_metric/target_metric)
 121      * The path weight correspond to the maximum length computed from either the delay or TE metric.
 122      *
 123      * To maintain the priority queue behavior unchanged, a "SamcraPath" classes is created to manage
 124      * the set of possible paths associated to a given vertex (see above).
 125      *
 126      */
 127
 128     @Override
 129     public ConstrainedPath computeP2pPath(VertexKey src, VertexKey dst, PathConstraints cts) {
 130         ConstrainedPathBuilder cpathBuilder;
 131         List<ConnectedEdge> edges;
 132         CspfPath currentPath;
 133
 134         LOG.info("Start SAMCRA Path Computation from {} to {} with constraints {}", src, dst, cts);
 135
 136         /* Initialize SAMCRA variables */
 137         this.constraints = cts;
 138         cpathBuilder = initializePathComputation(src, dst);
 139         if (cpathBuilder.getStatus() == ComputationStatus.Failed) {
 140             return cpathBuilder.build();
 141         }
 142         cpathBuilder.setBandwidth(cts.getBandwidth()).setClassType(cts.getClassType());
 143
 144         samcraPaths.clear();
 145         samcraPaths.put(pathSource.getVertexKey(), new SamcraPath(pathSource.getVertex()));
 146         samcraPaths.put(pathDestination.getVertexKey(), new SamcraPath(pathDestination.getVertex()));
 147
 148         /* Exploration of the priority queue:
 149          * Each connected vertex is represented only once in the priority queue associated to the path
 150          * with the minimal length (other path are stored in the SamcraPath object).
 151          * The top of the queue, i.e. the element with the minimal key( path weight), is processed at each loop
 152          */
 153         while (priorityQueue.size() != 0) {
 154             currentPath = priorityQueue.poll();
 155             LOG.debug(" - Process path up to Vertex {} from Priority Queue", currentPath.getVertex().toString());
 156
 157             /* Prepare Samcra Path from current CSP Path except for the source */
 158             if (!(currentPath.equals(pathSource))) {
 159                 SamcraPath currentSamcraPath = samcraPaths.get(currentPath.getVertexKey());
 160                 CspfPath currentCspfPath = currentSamcraPath.getCurrentPath();
 161                 float queuePathLength = currentCspfPath.getPathLength();
 162                 LOG.trace(" - Priority Queue output SamcraPaths {} CurrentPath {} with PathLength {}",
 163                         currentSamcraPath.currentPath.toString(), currentCspfPath.toString(), queuePathLength);
 164             }
 165
 166             edges = currentPath.getVertex().getOutputConnectedEdges();
 167             float currentPathLength = 1.0F;
 168             for (ConnectedEdge edge : edges) {
 169                 /* Connected Vertex's edges processing:
 170                  * Prune the connected edges that do not satisfy the constraints (Bandwidth, TE Metric, Delay, Loss)
 171                  * For each remaining edge process the path to the remote vertex using the "relaxSamcra" procedure
 172                  *
 173                  * If the return path length is positive, the destination is reached and the
 174                  * obtained route satisfies the requested constraints.
 175                  * The path length is checked to record only the optimal route (i.e. the route with
 176                  * the minimal path length) info obtained from the destination vertex
 177                  */
 178                 if (pruneEdge(edge, currentPath)) {
 179                     LOG.trace(" - Prune Edge {}", edge.toString());
 180                     continue;
 181                 }
 182                 float pathLength = relaxSamcra(edge, currentPath, pathSource);
 183
 184                 /* Check if we found a valid and better path */
 185                 if ((pathLength > 0F) && (pathLength <= currentPathLength)) {
 186                     final SamcraPath finalPath = samcraPaths.get(pathDestination.getVertexKey());
 187                     cpathBuilder.setPathDescription(getPathDescription(finalPath.getCurrentPath().getPath()))
 188                             .setMetric(Uint32.valueOf(finalPath.getCurrentPath().getCost()))
 189                             .setDelay(new Delay(Uint32.valueOf(finalPath.getCurrentPath().getDelay())))
 190                             .setStatus(ComputationStatus.Active);
 191                     LOG.debug(" - Path to destination found and registered {}",
 192                             cpathBuilder.getPathDescription());
 193                     currentPathLength = pathLength;
 194                 }
 195             }
 196
 197             /* The connected vertex that has been removed from the priority queue may have to be re-inserted with
 198              * the minimal length non-dominated path associated to the connected vertex if it exists (to be done
 199              * except for the source). Otherwise, the current path associated to the connected vertex is reset to
 200              * null to allow the connected vertex addition to the priority queue later on with a new path
 201              * (refer to "relaxSamcra" for addition of a connected vertex to the priority queue).
 202              */
 203             float previousLength = 1.0F;
 204             CspfPath selectedPath = null;
 205
 206             if (!(currentPath.equals(pathSource))) {
 207                 LOG.debug(" - Processing current path {} up to {} from Priority Queue", currentPath.toString(),
 208                         currentPath.getVertex().toString());
 209                 SamcraPath currentSamcraPath = samcraPaths.get(currentPath.getVertexKey());
 210                 currentSamcraPath.decrementPathCount();
 211                 /*
 212                  * The list of paths associated to the connected vertex is retrieved
 213                  * The path used to represent the connected vertex in the Priority Queue is marked from "selected"
 214                  * to "processed". The list of paths is analyzed to check if other "active" path(s) exist(s).
 215                  * If it is the case the shortest length is used to re-inject the connected vertex in the Priority Queue
 216                  */
 217                 for (CspfPath testedPath : currentSamcraPath.getPathList()) {
 218                     LOG.debug(" - Testing path {} with status {} ",
 219                             testedPath.toString(), testedPath.getPathStatus());
 220                     if (testedPath.getPathStatus() == CspfPath.SELECTED) {
 221                         testedPath.setPathStatus(CspfPath.PROCESSED);
 222                     } else if ((testedPath.getPathStatus() == CspfPath.ACTIVE)
 223                             && (testedPath.getPathLength() < previousLength)) {
 224                         selectedPath = testedPath;
 225                         previousLength = testedPath.getPathLength();
 226                     }
 227                 }
 228                 /* If a path is found it is marked as "selected", used as "current path" for the connected vertex
 229                  * and added to the priority queue
 230                  */
 231                 if (selectedPath != null) {
 232                     selectedPath.setPathStatus(CspfPath.SELECTED);
 233                     currentSamcraPath.setCurrentPath(selectedPath);
 234                     priorityQueue.add(selectedPath);
 235                     LOG.debug(" - Add path {} to Priority Queue. New path count {} ",
 236                             selectedPath.toString(), currentSamcraPath.getPathCount());
 237                 } else {
 238                     currentSamcraPath.setCurrentPath(null);
 239                 }
 240             }
 241         }
 242         /* The priority queue is empty => all the possible (vertex, path) elements have been explored
 243          * The "ConstrainedPathBuilder" object contains the optimal path if it exists
 244          * Otherwise an empty path with status failed is returned
 245          */
 246         if ((cpathBuilder.getStatus() == ComputationStatus.InProgress)
 247                 || (cpathBuilder.getPathDescription().size() == 0)) {
 248             cpathBuilder.setStatus(ComputationStatus.Failed);
 249         } else {
 250             cpathBuilder.setStatus(ComputationStatus.Completed);
 251         }
 252         return cpathBuilder.build();
 253     }
 254
 255     /* Connected Edge to remote connected vertex processing (on contrast to CSPF algorithm, the already processed
 256      * connected vertex are not zapped as a connected vertex may be associated to multiple paths). This method
 257      * computes the TE metric and Delay costs up to the remote end-point connected vertex and checks if the computed
 258      * values are acceptable according to the end-to-end constraints.
 259      * If relevant, update the computed path on the remote end-point connected vertex.
 260      * If the connected vertex has not already been processed, the corresponding CspfPath object is created.
 261      */
 262     private float relaxSamcra(ConnectedEdge edge, CspfPath currentPath, CspfPath source) {
 263         LOG.debug("   - Start SAMCRA relaxing Edge {} to Vertex {}", edge.toString(), edge.getDestination().toString());
 264
 265         /* Process CspfPath including the next Vertex */
 266         CspfPath nextVertexPath = processedPath.get(edge.getDestination().getKey());
 267         if (nextVertexPath == null) {
 268             nextVertexPath = new CspfPath(edge.getDestination());
 269             processedPath.put(nextVertexPath.getVertexKey(), nextVertexPath);
 270             SamcraPath nextSamcraPath = new SamcraPath(edge.getDestination());
 271             samcraPaths.put(nextVertexPath.getVertexKey(), nextSamcraPath);
 272             LOG.debug("     - Next connected vertex {} does not exist, create it with new Samcra Path {}",
 273                     nextSamcraPath.getVertex().toString(), nextVertexPath.toString());
 274         }
 275
 276         /* Connected Vertex's paths management using SamcraPath object.
 277          * The predecessor connected vertex is checked to avoid unnecessary processing.
 278          */
 279         Long predecessorId = 0L;
 280         if (!(currentPath.equals(source))) {
 281             LOG.debug("     - Check predecessor");
 282             SamcraPath currentSamcraPath = samcraPaths.get(currentPath.getVertexKey());
 283             CspfPath currentVertexPath = currentSamcraPath.getCurrentPath();
 284             predecessorId = currentVertexPath.getPredecessor();
 285         }
 286         if (predecessorId.equals(nextVertexPath.getVertexKey())) {
 287             LOG.debug("     - Skip Edge because next vertex {} is predecessor of {}",
 288                     nextVertexPath.getVertexKey(), predecessorId);
 289             return 0F;
 290         }
 291
 292         /* Connected Vertex's paths management using CspfPath object.
 293          * The paths list is explored and the paths dominated by the new path are marked as dominated.
 294          * The new path is also check and if it is dominated by an existing path it is omitted.
 295          * Even if call to pruneEdge() method has removed edges that do not meet constraints, the method keep edges
 296          * that have no Delay or TE Metric if the Delay, respectively the TE Metric are not specified in constraints.
 297          * So, Delay and TE Metric presence in edge attributes must be checked again.
 298          */
 299         if (edge.getEdge().getEdgeAttributes().getTeMetric() != null) {
 300             teCost = edge.getEdge().getEdgeAttributes().getTeMetric().intValue() + currentPath.getCost();
 301         } else {
 302             teCost = currentPath.getCost();
 303         }
 304         if (edge.getEdge().getEdgeAttributes().getDelay() != null) {
 305             delayCost = edge.getEdge().getEdgeAttributes().getDelay().getValue().intValue() + currentPath.getDelay();
 306         } else {
 307             delayCost = currentPath.getDelay();
 308         }
 309
 310         SamcraPath samcraPath = samcraPaths.get(nextVertexPath.getVertexKey());
 311         if (isPathDominated(samcraPath)) {
 312             LOG.debug("     - Skip Edge because new path is dominated");
 313             return 0F;
 314         }
 315
 316         /* If the new path is not dominated by an already existing path, a new "CspfPath" object
 317          * is created with predecessor set to connected vertex, path length and path status information,
 318          * marked as "active" and added to the connected vertex's path list.
 319          * The weight attribute, used as classification key by the priority queue, is an integer value computed
 320          * from the TE Metric and Delay length.
 321          */
 322         CspfPath newPath = createNonDominatedPath(edge, nextVertexPath.getVertex(), currentPath);
 323
 324         /* The new path is check versus the path currently representing the connected vertex in the priority
 325          * queue. If there is not yet a path for the connected vertex or if the new path length is shorter
 326          * than the length of the path currently selected, the new path is used as current path, marked as
 327          * "selected" and is added to the priority queue.
 328          * The previously current path status is changed from "selected" to "active" and can be re-selected
 329          * later on. If the new path is associated to the destination connected vertex it is not added to
 330          * the priority queue.
 331          */
 332         CspfPath currentSamcraPath = samcraPath.getCurrentPath();
 333         if (currentSamcraPath == null) {
 334             LOG.debug("     - Add new Path {}", newPath.toString());
 335             if (!(newPath.equals(pathDestination))) {
 336                 priorityQueue.add(newPath);
 337             }
 338             newPath.setPathStatus(CspfPath.SELECTED);
 339             samcraPath.setCurrentPath(newPath);
 340         } else if (newPath.getPathLength() < currentSamcraPath.getPathLength()) {
 341             LOG.debug("     - Update current path up to {} with new path {}",
 342                     currentSamcraPath.getVertex().toString(), newPath.toString());
 343             samcraPath.getPathList()
 344                 .stream()
 345                 .filter(path -> path.getPathStatus() == CspfPath.SELECTED)
 346                 .forEach(path -> path.setPathStatus(CspfPath.ACTIVE));
 347
 348             /* It is not possible to directly update the CspfPath in the Priority Queue. Indeed, if we
 349              * modify the path weight, the Priority Queue must be re-ordered. So, we need fist to remove
 350              * the CspfPath if it is present in the Priority Queue, then, update the Path Weight,
 351              * and finally (re-)insert it in the Priority Queue.
 352              */
 353             if (!(newPath.equals(pathDestination))) {
 354                 priorityQueue.removeIf((path) -> path.getVertexKey().equals(newPath.getVertexKey()));
 355                 priorityQueue.add(newPath);
 356             }
 357             newPath.setPathStatus(CspfPath.SELECTED);
 358             samcraPath.setCurrentPath(newPath);
 359         }
 360
 361         /* In all cases the new path is added to the list of paths associated to the vertex */
 362         samcraPath.addPath(newPath);
 363         samcraPath.incrementPathCount();
 364
 365         LOG.debug("     - Add path {} to {} with index {}/{}", samcraPath.getCurrentPath().toString(),
 366                 samcraPath.getCurrentPath().getVertex().toString(), samcraPath.getVertex().getKey(),
 367                 samcraPath.getPathCount());
 368         samcraPaths.put(samcraPath.getVertex().getKey(), samcraPath);
 369
 370         /* If the destination is reached, return the computed path length 0 otherwise */
 371         if ((samcraPath.getVertex().getKey()).equals(pathDestination.getVertexKey())) {
 372             return samcraPath.getCurrentPath().getPathLength();
 373         } else {
 374             return 0F;
 375         }
 376     }
 377
 378     /**
 379      * Evaluate if the current path is dominated by an all one or dominates all previous computed path.
 380      *
 381      * @param samcraPath Current Samcra Path
 382      *
 383      * @return true if path is dominated false otherwise
 384      */
 385     private boolean isPathDominated(SamcraPath samcraPath) {
 386         /* Evaluate Path Domination */
 387         LOG.debug("       - Check path domination");
 388         Uint32 teMetric = constraints.getTeMetric();
 389         Uint32 delay = (constraints.getDelay() != null) ? constraints.getDelay().getValue() : null;
 390
 391         for (CspfPath testedPath : samcraPath.getPathList()) {
 392             boolean pathCostDominated = false;
 393             boolean pathDelayDominated = false;
 394             boolean testedPathCostDominated = false;
 395             boolean testedPathDelayDominated = false;
 396
 397             LOG.debug("       - Check if path {} is dominated or dominates", testedPath.toString());
 398             if (testedPath.getPathStatus() != CspfPath.DOMINATED) {
 399                 if (teMetric != null) {
 400                     if (teCost >= testedPath.getCost()) {
 401                         pathCostDominated = true;
 402                     } else {
 403                         testedPathCostDominated = true;
 404                     }
 405                 }
 406                 if (delay != null) {
 407                     if (delayCost >= testedPath.getDelay()) {
 408                         pathDelayDominated = true;
 409                     } else {
 410                         testedPathDelayDominated = true;
 411                     }
 412                 }
 413
 414                 if ((((teMetric != null) && (pathCostDominated)) && ((pathDelayDominated) || (delay == null)))
 415                         || ((teMetric == null) && ((delay != null) && (pathDelayDominated)))) {
 416                     LOG.debug("       - New path is dominated by teCost {} and/or delayCost {}", teCost, delayCost);
 417                     /* A path that dominates the current path has been found */
 418                     return true;
 419                 } else if ((((teMetric != null) && (testedPathCostDominated))
 420                         && ((testedPathDelayDominated) || (delay == null)))
 421                         || ((teMetric == null) && ((delay != null) && (testedPathDelayDominated)))) {
 422                     /* Old Path is dominated by the new path. Mark it as Dominated and decrement
 423                      * the number of valid Paths */
 424                     testedPath.setPathStatus(CspfPath.DOMINATED);
 425                     samcraPath.decrementPathCount();
 426                     LOG.debug("       - New path dominates existing path with teCost {} and/or delayCost {}",
 427                             testedPath.getCost(), testedPath.getDelay());
 428                 }
 429             }
 430         }
 431         return false;
 432     }
 433
 434     private CspfPath createNonDominatedPath(ConnectedEdge edge, ConnectedVertex vertex, CspfPath cspfPath) {
 435         float pathLength = 1.0F;
 436         Uint32 metric = constraints.getTeMetric();
 437         Uint32 delay = (constraints.getDelay() != null) ? constraints.getDelay().getValue() : null;
 438
 439         LOG.debug("       - Create new non dominated path");
 440
 441         /* Compute Path length as key for the path Weight */
 442         float teLength = 0.0F;
 443         if ((metric != null) && (metric.intValue() > 0)) {
 444             teLength = (float) teCost / metric.intValue();
 445             pathLength = teLength;
 446         }
 447         float delayLength = 0.0F;
 448         if ((delay != null) && (delay.intValue() > 0)) {
 449             delayLength = (float) delayCost / delay.intValue();
 450             if (delayLength > teLength) {
 451                 pathLength = delayLength;
 452             }
 453         }
 454
 455         /* Create new Path with computed TE Metric, Delay and Path Length */
 456         CspfPath newPath = new CspfPath(vertex)
 457                 .setCost(teCost)
 458                 .setDelay(delayCost)
 459                 .setKey((int) (100 * pathLength))
 460                 .setPathStatus(CspfPath.ACTIVE)
 461                 .setPathLength(pathLength)
 462                 .setPredecessor(cspfPath.getVertexKey())
 463                 .replacePath(cspfPath.getPath())
 464                 .addConnectedEdge(edge);
 465
 466         LOG.debug("       - Created new Path {} with length {}, cost {} and delay {}",
 467                 newPath.toString(), pathLength, teCost, delayCost);
 468
 469         return newPath;
 470     }
 471 }