algo/algo-impl/src/main/java/org/opendaylight/algo/impl/AbstractPathComputation.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 java.util.PriorityQueue;
  14 import org.eclipse.jdt.annotation.Nullable;
  15 import org.opendaylight.algo.PathComputationAlgorithm;
  16 import org.opendaylight.graph.ConnectedEdge;
  17 import org.opendaylight.graph.ConnectedGraph;
  18 import org.opendaylight.graph.ConnectedVertex;
  19 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev191125.edge.EdgeAttributes;
  20 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev191125.edge.attributes.UnreservedBandwidth;
  21 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev191125.graph.topology.graph.Prefix;
  22 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev191125.graph.topology.graph.VertexKey;
  23 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.network.concepts.rev131125.MplsLabel;
  24 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ComputationStatus;
  25 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ConstrainedPath;
  26 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ConstrainedPathBuilder;
  27 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.PathConstraints;
  28 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.path.descriptions.PathDescription;
  29 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.path.descriptions.PathDescriptionBuilder;
  30 import org.opendaylight.yangtools.yang.common.Uint32;
  31 import org.slf4j.Logger;
  32 import org.slf4j.LoggerFactory;
  33
  34 public abstract class AbstractPathComputation implements PathComputationAlgorithm {
  35
  36     private static final Logger LOG = LoggerFactory.getLogger(AbstractPathComputation.class);
  37
  38     protected final ConnectedGraph graph;
  39
  40     /* Source and Destination of the path */
  41     protected CspfPath pathSource = null;
  42     protected CspfPath pathDestination = null;
  43
  44     /* Constraints that the path must respect */
  45     protected PathConstraints constraints = null;
  46
  47     /* Priority Queue and HashMap to manage path computation */
  48     protected PriorityQueue<CspfPath> priorityQueue;
  49     protected HashMap<Long, CspfPath> processedPath;
  50
  51     protected AbstractPathComputation(ConnectedGraph graph) {
  52         this.graph = graph;
  53         priorityQueue = new PriorityQueue<CspfPath>();
  54         processedPath = new HashMap<Long, CspfPath>();
  55     }
  56
  57     /**
  58      * Initialize the various parameters for Path Computation, in particular the
  59      * Source and Destination CspfPath.
  60      *
  61      * @param src
  62      *            Source Vertex Identifier in the Connected Graph
  63      * @param dst
  64      *            Destination Vertex Identifier in the Connected Graph
  65      *
  66      * @return Constrained Path Builder with status set to 'OnGoing' if
  67      *         initialization success, 'Failed' otherwise
  68      */
  69     protected ConstrainedPathBuilder initializePathComputation(VertexKey src, VertexKey dst) {
  70         ConstrainedPathBuilder cpathBuilder = new ConstrainedPathBuilder().setStatus(ComputationStatus.InProgress);
  71
  72         /* Check that source and destination vertexKey are not identical */
  73         if (src.equals(dst)) {
  74             LOG.warn("Source and Destination are equal: Abort!");
  75             cpathBuilder.setStatus(ComputationStatus.Failed);
  76             return cpathBuilder;
  77         }
  78
  79         /*
  80          * Get the Connected Vertex from the Graph to initialize the source of
  81          * the Cspf Path
  82          */
  83         ConnectedVertex vertex = null;
  84         vertex = graph.getConnectedVertex(src.getVertexId().longValue());
  85         if (vertex == null) {
  86             LOG.warn("Found no source for Vertex Key {}", src);
  87             cpathBuilder.setStatus(ComputationStatus.Failed);
  88             return cpathBuilder;
  89         }
  90         LOG.debug("Create Path Source with Vertex {}", vertex.toString());
  91         pathSource = new CspfPath(vertex).setCost(0).setDelay(0);
  92         cpathBuilder.setSource(vertex.getVertex().getVertexId());
  93
  94         /*
  95          * Get the Connected Vertex from the Graph to initialize the destination
  96          * of the Cspf Path
  97          */
  98         vertex = graph.getConnectedVertex(dst.getVertexId().longValue());
  99         if (vertex == null) {
 100             LOG.warn("Found no destination for Vertex Key {}", src);
 101             cpathBuilder.setStatus(ComputationStatus.Failed);
 102             return cpathBuilder;
 103         }
 104         LOG.debug("Create Path Destination with Vertex {}", vertex.toString());
 105         pathDestination = new CspfPath(vertex);
 106         cpathBuilder.setDestination(vertex.getVertex().getVertexId());
 107
 108         /* Initialize the Priority Queue, HashMap */
 109         priorityQueue.clear();
 110         priorityQueue.add(pathSource);
 111         processedPath.clear();
 112         processedPath.put(pathSource.getVertexKey(), pathSource);
 113         processedPath.put(pathDestination.getVertexKey(), pathDestination);
 114
 115         return cpathBuilder;
 116     }
 117
 118     /**
 119      * Check if Edge need to be prune regarding all constraints including
 120      * address family.
 121      *
 122      * @return True if Edge must be prune, False if Edge must be keep
 123      */
 124     protected boolean pruneEdge(ConnectedEdge edge, CspfPath path) {
 125         /* Check that Constraints are initialized */
 126         if (constraints == null) {
 127             LOG.warn("Constraints not set");
 128             return true;
 129         }
 130
 131         /* Edge could point to an unknown Vertex e.g. with inter-domain link */
 132         if ((edge.getDestination() == null) || (edge.getDestination().getVertex() == null)) {
 133             LOG.debug("No Destination");
 134             return true;
 135         }
 136
 137         /* Check that Edge have attributes */
 138         EdgeAttributes attributes = edge.getEdge() != null ? edge.getEdge().getEdgeAttributes() : null;
 139         if (attributes == null) {
 140             LOG.debug("No attributes");
 141             return true;
 142         }
 143
 144         /* Check that Edge belongs to the requested address family */
 145         switch (constraints.getAddressFamily()) {
 146             case Ipv4:
 147                 if ((attributes.getRemoteAddress() == null)
 148                         || (attributes.getRemoteAddress().getIpv4Address() == null)) {
 149                     LOG.debug("No Ipv4 address");
 150                     return true;
 151                 }
 152                 break;
 153             case Ipv6:
 154                 if ((attributes.getRemoteAddress() == null)
 155                         || (attributes.getRemoteAddress().getIpv6Address() == null)) {
 156                     LOG.debug("No Ipv6 address");
 157                     return true;
 158                 }
 159                 break;
 160             case SrIpv4:
 161                 if (getIpv4NodeSid(edge.getDestination()) == null) {
 162                     LOG.debug("No Node-SID for IPv4");
 163                     return true;
 164                 }
 165                 if (attributes.getAdjSid() == null) {
 166                     LOG.debug("No Adjacency-SID");
 167                     return true;
 168                 }
 169                 break;
 170             case SrIpv6:
 171                 if (getIpv6NodeSid(edge.getDestination()) == null) {
 172                     LOG.debug("No Node-SID for IPv6");
 173                     return true;
 174                 }
 175                 if (attributes.getAdjSid() == null) {
 176                     LOG.debug("No SR Adjacency-SID");
 177                     return true;
 178                 }
 179                 break;
 180             default:
 181                 return true;
 182         }
 183
 184         /* Skip checking other Constraints for simple SPF algorithm */
 185         if (this instanceof ShortestPathFirst) {
 186             LOG.trace("Edge {} is valid for Simple Path Computation", edge.toString());
 187             return false;
 188         }
 189
 190         /*
 191          * If specified, check that total TE Metric up to this edge respects the
 192          * initial constraints
 193          */
 194         if (constraints.getTeMetric() != null) {
 195             if (attributes.getTeMetric() == null) {
 196                 return true;
 197             } else {
 198                 int totalCost = attributes.getTeMetric().intValue() + path.getCost();
 199                 if (totalCost > constraints.getTeMetric().intValue()) {
 200                     LOG.debug("TeMetric {} exceed constraint {}", totalCost, constraints.getTeMetric().intValue());
 201                     return true;
 202                 }
 203             }
 204         }
 205
 206         /*
 207          * If specified, check that total Delay up to this edge respects the
 208          * initial constraints
 209          */
 210         if (constraints.getDelay() != null) {
 211             if (attributes.getDelay() == null) {
 212                 return true;
 213             } else {
 214                 int totalDelay = attributes.getDelay().getValue().intValue() + path.getDelay();
 215                 if (totalDelay > constraints.getDelay().getValue().intValue()) {
 216                     LOG.debug("Delay {} exceed constraint {}", totalDelay,
 217                             constraints.getDelay().getValue().intValue());
 218                     return true;
 219                 }
 220             }
 221         }
 222
 223         /* Check that Edge respect Loss constraint */
 224         if (constraints.getLoss() != null) {
 225             if ((attributes.getLoss() == null)
 226                     || (attributes.getLoss().getValue().intValue() > constraints.getLoss().getValue().intValue())) {
 227                 return true;
 228             }
 229         }
 230
 231         /* Check that Edge meet Bandwidth constraint */
 232         if (constraints.getBandwidth() != null) {
 233             if ((attributes.getMaxLinkBandwidth() == null) || (attributes.getMaxResvLinkBandwidth() == null)
 234                     || (attributes.getUnreservedBandwidth() == null)
 235                     || (attributes.getUnreservedBandwidth().get(constraints.getClassType().intValue()) == null)) {
 236                 return true;
 237             } else {
 238                 Long bandwidth = constraints.getBandwidth().getValue().longValue();
 239                 Long unrsv = 0L;
 240                 for (UnreservedBandwidth unResBw : attributes.getUnreservedBandwidth()) {
 241                     if (unResBw.getClassType().intValue() == constraints.getClassType().intValue()) {
 242                         unrsv = unResBw.getBandwidth().getValue().longValue();
 243                         break;
 244                     }
 245                 }
 246                 if (unrsv < bandwidth || attributes.getMaxLinkBandwidth().getValue().longValue() < bandwidth
 247                         || attributes.getMaxResvLinkBandwidth().getValue().longValue() < bandwidth) {
 248                     LOG.debug("Bandwidth constraint is not met");
 249                     return true;
 250                 }
 251             }
 252         }
 253
 254         /* Check that Edge belongs to admin group */
 255         if ((constraints.getAdminGroup() != null)
 256                 && !(constraints.getAdminGroup().equals(attributes.getAdminGroup()))) {
 257             LOG.debug("Not in the requested admin-group");
 258             return true;
 259         }
 260
 261         /*
 262          * OK. All is fine. We can consider this Edge valid, so not to be prune
 263          */
 264         LOG.trace("Edge {} is valid for Constrained Path Computation", edge.toString());
 265         return false;
 266     }
 267
 268     /**
 269      * Return the MPLS Label corresponding to the Node SID for IPv4 when the
 270      * Connected Vertex is Segment Routing aware.
 271      *
 272      * @return MPLS Label if Connected Vertex is Segment Routing aware, Null
 273      *         otherwise
 274      */
 275     protected @Nullable MplsLabel getIpv4NodeSid(ConnectedVertex cvertex) {
 276         /*
 277          * Check that Vertex is Segment Routing aware
 278          */
 279         if ((cvertex.getVertex() == null) || (cvertex.getVertex().getSrgb() == null)) {
 280             return null;
 281         }
 282         /*
 283          * Find in Prefix List Node SID attached to the IPv4 of the next Vertex
 284          * and return the MPLS Label that corresponds to the index in the SRGB
 285          */
 286         if (cvertex.getPrefixes() == null) {
 287             return null;
 288         }
 289         for (Prefix prefix : cvertex.getPrefixes()) {
 290             if ((prefix.getPrefixSid() == null) || (prefix.isNodeSid() == null)) {
 291                 continue;
 292             }
 293             if (prefix.isNodeSid() && prefix.getPrefix().getIpv4Prefix() != null) {
 294                 return new MplsLabel(Uint32.valueOf(prefix.getPrefixSid().intValue()));
 295             }
 296         }
 297         return null;
 298     }
 299
 300     /**
 301      * Return the MPLS Label corresponding to the Node SID for IPv6 when the
 302      * Connected Vertex is Segment Routing aware.
 303      *
 304      * @return MPLS Label if Connected Vertex is Segment Routing aware, Null
 305      *         otherwise
 306      */
 307     protected @Nullable MplsLabel getIpv6NodeSid(ConnectedVertex cvertex) {
 308         /*
 309          * Check that Vertex is Segment Routing aware
 310          */
 311         if ((cvertex.getVertex() == null) || (cvertex.getVertex().getSrgb() == null)) {
 312             return null;
 313         }
 314         /*
 315          * Find in Prefix List Node SID attached to the IPv6 of the next Vertex
 316          * and return the MPLS Label that corresponds to the index in the SRGB
 317          */
 318         if (cvertex.getPrefixes() == null) {
 319             return null;
 320         }
 321         for (Prefix prefix : cvertex.getPrefixes()) {
 322             if ((prefix.getPrefixSid() == null) || (prefix.isNodeSid() == null)) {
 323                 continue;
 324             }
 325             if (prefix.isNodeSid() && prefix.getPrefix().getIpv6Prefix() != null) {
 326                 return new MplsLabel(Uint32.valueOf(prefix.getPrefixSid().intValue()));
 327             }
 328         }
 329         return null;
 330     }
 331
 332     /**
 333      * Convert List of Connected Edges into a Path Description as a List of
 334      * IPv4, IPv6 or MPLS Label depending of the requested Address Family.
 335      *
 336      * @param edges
 337      *            List of Connected Edges
 338      *
 339      * @return Path Description
 340      */
 341     protected List<PathDescription> getPathDescription(List<ConnectedEdge> edges) {
 342         ArrayList<PathDescription> list = new ArrayList<PathDescription>();
 343
 344         for (ConnectedEdge edge : edges) {
 345             PathDescription pathDesc = null;
 346             switch (constraints.getAddressFamily()) {
 347                 case Ipv4:
 348                     pathDesc = new PathDescriptionBuilder()
 349                             .setIpv4(edge.getEdge().getEdgeAttributes().getRemoteAddress().getIpv4Address()).build();
 350                     break;
 351                 case Ipv6:
 352                     pathDesc = new PathDescriptionBuilder()
 353                             .setIpv6(edge.getEdge().getEdgeAttributes().getRemoteAddress().getIpv6Address()).build();
 354                     break;
 355                 case SrIpv4:
 356                     pathDesc = new PathDescriptionBuilder()
 357                             .setLocalIpv4(edge.getEdge().getEdgeAttributes().getLocalAddress().getIpv4Address())
 358                             .setRemoteIpv4(edge.getEdge().getEdgeAttributes().getRemoteAddress().getIpv4Address())
 359                             .setSid(edge.getEdge().getEdgeAttributes().getAdjSid())
 360                             .build();
 361                     break;
 362                 case SrIpv6:
 363                     pathDesc = new PathDescriptionBuilder()
 364                             .setLocalIpv6(edge.getEdge().getEdgeAttributes().getLocalAddress().getIpv6Address())
 365                             .setRemoteIpv6(edge.getEdge().getEdgeAttributes().getRemoteAddress().getIpv6Address())
 366                             .setSid(edge.getEdge().getEdgeAttributes().getAdjSid())
 367                             .build();
 368                     break;
 369                 default:
 370                     break;
 371             }
 372             list.add(pathDesc);
 373         }
 374         return list;
 375     }
 376
 377     @Override
 378     public abstract ConstrainedPath computeP2pPath(VertexKey source, VertexKey destination,
 379             PathConstraints constraints);
 380
 381 }