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