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.ietf.params.xml.ns.yang.ietf.inet.types.rev130715.IpAddress;
  20 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.inet.types.rev130715.Ipv4Address;
  21 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.inet.types.rev130715.Ipv6Address;
  22 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev220720.edge.EdgeAttributes;
  23 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev220720.edge.attributes.UnreservedBandwidth;
  24 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev220720.graph.topology.graph.Prefix;
  25 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev220720.graph.topology.graph.VertexKey;
  26 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.network.concepts.rev131125.MplsLabel;
  27 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev220324.AddressFamily;
  28 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev220324.ComputationStatus;
  29 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev220324.ConstrainedPath;
  30 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev220324.ConstrainedPathBuilder;
  31 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev220324.PathConstraints;
  32 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev220324.path.constraints.ExcludeRoute;
  33 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev220324.path.constraints.IncludeRoute;
  34 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev220324.path.descriptions.PathDescription;
  35 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev220324.path.descriptions.PathDescriptionBuilder;
  36 import org.slf4j.Logger;
  37 import org.slf4j.LoggerFactory;
  38
  39 public abstract class AbstractPathComputation implements PathComputationAlgorithm {
  40     private static final Logger LOG = LoggerFactory.getLogger(AbstractPathComputation.class);
  41
  42     protected final ConnectedGraph graph;
  43
  44     /* Source and Destination of the path */
  45     protected CspfPath pathSource = null;
  46     protected CspfPath pathDestination = null;
  47
  48     /* Constraints that the path must respect */
  49     protected PathConstraints constraints = null;
  50
  51     /* Priority Queue and HashMap to manage path computation */
  52     protected final PriorityQueue<CspfPath> priorityQueue = new PriorityQueue<>();
  53     protected final HashMap<Long, CspfPath> processedPath = new HashMap<>();
  54
  55     protected AbstractPathComputation(final ConnectedGraph graph) {
  56         this.graph = graph;
  57     }
  58
  59     /**
  60      * Initialize the various parameters for Path Computation, in particular the
  61      * Source and Destination CspfPath.
  62      *
  63      * @param src
  64      *            Source Vertex Identifier in the Connected Graph
  65      * @param dst
  66      *            Destination Vertex Identifier in the Connected Graph
  67      *
  68      * @return Constrained Path Builder with status set to 'OnGoing' if
  69      *         initialization success, 'Failed' otherwise
  70      */
  71     protected ConstrainedPathBuilder initializePathComputation(final VertexKey src, final VertexKey dst) {
  72         ConstrainedPathBuilder cpathBuilder = new ConstrainedPathBuilder().setStatus(ComputationStatus.InProgress);
  73
  74         /* Check that source and destination vertexKey are not identical */
  75         if (src.equals(dst)) {
  76             LOG.warn("Source and Destination are equal: Abort!");
  77             return cpathBuilder.setStatus(ComputationStatus.EqualEndpoints);
  78         }
  79
  80         /*
  81          * Get the Connected Vertex from the Graph to initialize the source of
  82          * the Cspf Path
  83          */
  84         ConnectedVertex vertex = graph.getConnectedVertex(src.getVertexId().longValue());
  85         if (vertex == null) {
  86             LOG.warn("Found no source for Vertex Key {}", src);
  87             return cpathBuilder.setStatus(ComputationStatus.NoSource);
  88         }
  89         LOG.debug("Create Path Source with Vertex {}", vertex);
  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             return cpathBuilder.setStatus(ComputationStatus.NoDestination);
 101         }
 102         LOG.debug("Create Path Destination with Vertex {}", vertex);
 103         pathDestination = new CspfPath(vertex);
 104         cpathBuilder.setDestination(vertex.getVertex().getVertexId());
 105
 106         /* Initialize the Priority Queue, HashMap */
 107         priorityQueue.clear();
 108         priorityQueue.add(pathSource);
 109         processedPath.clear();
 110         processedPath.put(pathSource.getVertexKey(), pathSource);
 111         processedPath.put(pathDestination.getVertexKey(), pathDestination);
 112
 113         return cpathBuilder;
 114     }
 115
 116     private boolean verifyAddressFamily(final ConnectedEdge edge, final EdgeAttributes attributes) {
 117         /* Check that Edge belongs to the Address Family of the requested path */
 118         switch (constraints.getAddressFamily()) {
 119             case Ipv4:
 120                 if (attributes.getRemoteAddress() == null) {
 121                     LOG.debug("No Ipv4 address");
 122                     return true;
 123                 }
 124                 break;
 125             case Ipv6:
 126                 if (attributes.getRemoteAddress6() == null) {
 127                     LOG.debug("No Ipv6 address");
 128                     return true;
 129                 }
 130                 break;
 131             case SrIpv4:
 132                 if (getIpv4NodeSid(edge.getDestination()) == null) {
 133                     LOG.debug("No Node-SID for IPv4");
 134                     return true;
 135                 }
 136                 if (attributes.getAdjSid() == null) {
 137                     LOG.debug("No SR Adjacency-SID for IPv4");
 138                     return true;
 139                 }
 140                 break;
 141             case SrIpv6:
 142                 if (getIpv6NodeSid(edge.getDestination()) == null) {
 143                     LOG.debug("No Node-SID for IPv6");
 144                     return true;
 145                 }
 146                 if (attributes.getAdjSid6() == null) {
 147                     LOG.debug("No SR Adjacency-SID for IPv6");
 148                     return true;
 149                 }
 150                 break;
 151             default:
 152                 return true;
 153         }
 154
 155         return false;
 156     }
 157
 158     private boolean verifyMetrics(final EdgeAttributes attributes, final CspfPath path) {
 159         /* If specified, check that total TE Metric up to this edge respects the initial constraints */
 160         if (constraints.getTeMetric() != null) {
 161             if (attributes.getTeMetric() == null) {
 162                 return true;
 163             } else {
 164                 int totalCost = attributes.getTeMetric().intValue() + path.getCost();
 165                 if (totalCost > constraints.getTeMetric().intValue()) {
 166                     LOG.debug("TeMetric {} exceed constraint {}", totalCost, constraints.getTeMetric().intValue());
 167                     return true;
 168                 }
 169             }
 170         }
 171
 172         /* If specified, check that total Delay up to this edge respects the initial constraints */
 173         if (constraints.getDelay() != null) {
 174             if (attributes.getDelay() == null) {
 175                 return true;
 176             } else {
 177                 int totalDelay = attributes.getDelay().getValue().intValue() + path.getDelay();
 178                 if (totalDelay > constraints.getDelay().getValue().intValue()) {
 179                     LOG.debug("Delay {} exceed constraint {}", totalDelay,
 180                             constraints.getDelay().getValue().intValue());
 181                     return true;
 182                 }
 183             }
 184         }
 185
 186         /* Check that Edge respect Loss constraint */
 187         if (constraints.getLoss() != null) {
 188             if (attributes.getLoss() == null
 189                     || attributes.getLoss().getValue().intValue() > constraints.getLoss().getValue().intValue()) {
 190                 return true;
 191             }
 192         }
 193
 194         return false;
 195     }
 196
 197     private boolean verifyBandwidth(final ConnectedEdge edge, final EdgeAttributes attributes) {
 198         if (constraints.getBandwidth() == null) {
 199             return false;
 200         }
 201
 202         int cos = constraints.getClassType() != null ? constraints.getClassType().intValue() : 0;
 203         if (attributes.getMaxLinkBandwidth() == null
 204                 || attributes.getMaxResvLinkBandwidth() == null
 205                 || attributes.getUnreservedBandwidth() == null
 206                 || attributes.getUnreservedBandwidth().get(cos) == null) {
 207             return true;
 208         }
 209
 210         /* Get Unreserved Bandwidth for the given Class of Service / Priority */
 211         Long bandwidth = constraints.getBandwidth().getValue().longValue();
 212         Long unrsv = 0L;
 213         for (UnreservedBandwidth unResBw : attributes.getUnreservedBandwidth()) {
 214             if (unResBw.getClassType().intValue() == cos) {
 215                 unrsv = unResBw.getBandwidth().getValue().longValue();
 216                 break;
 217             }
 218         }
 219         Long maxBW = attributes.getMaxLinkBandwidth().getValue().longValue();
 220         if (bandwidth > List.of(unrsv,
 221                 // maxBW might be on the list but will always be greater
 222                 // than the next items
 223                 maxBW - edge.getCosResvBandwidth(cos), maxBW - edge.getGlobalResvBandwidth(),
 224                 attributes.getMaxResvLinkBandwidth().getValue().longValue()).stream().mapToLong(v -> v).min()
 225                 .getAsLong()) {
 226             LOG.debug("Bandwidth constraint is not met");
 227             return true;
 228         }
 229
 230         return false;
 231     }
 232
 233     private boolean verifyExcludeRoute(final ConnectedEdge edge, final EdgeAttributes attributes) {
 234         final var xro = constraints.getExcludeRoute();
 235         if (xro == null || xro.isEmpty()) {
 236             return false;
 237         }
 238
 239         switch (constraints.getAddressFamily()) {
 240             case Ipv4, SrIpv4:
 241                 for (ExcludeRoute element : xro) {
 242                     final Ipv4Address address = element.getIpv4();
 243                     if (address.equals(attributes.getRemoteAddress())
 244                             || address.equals(attributes.getLocalAddress())
 245                             || address.equals(edge.getSource().getVertex().getRouterId())
 246                             || address.equals(edge.getDestination().getVertex().getRouterId())) {
 247                         return true;
 248                     }
 249                 }
 250                 break;
 251             case Ipv6, SrIpv6:
 252                 for (ExcludeRoute element : xro) {
 253                     final Ipv6Address address = element.getIpv6();
 254                     if (address.equals(attributes.getRemoteAddress6())
 255                             || address.equals(attributes.getLocalAddress6())
 256                             || address.equals(edge.getSource().getVertex().getRouterId6())
 257                             || address.equals(edge.getDestination().getVertex().getRouterId6())) {
 258                         return true;
 259                     }
 260                 }
 261                 break;
 262             default:
 263                 return true;
 264         }
 265
 266         return false;
 267     }
 268
 269     /**
 270      * Check if Edge need to be prune regarding all constraints including
 271      * address family.
 272      *
 273      * @return True if Edge must be prune, False if Edge must be keep
 274      */
 275     protected boolean pruneEdge(final ConnectedEdge edge, final CspfPath path) {
 276         /* Check that Constraints are initialized */
 277         if (constraints == null) {
 278             LOG.warn("Constraints not set");
 279             return true;
 280         }
 281
 282         /* Edge could point to an unknown Vertex e.g. with inter-domain link */
 283         final var destination = edge.getDestination();
 284         if (destination == null || destination.getVertex() == null) {
 285             LOG.debug("No Destination");
 286             return true;
 287         }
 288
 289         /* Check that Edge have attributes */
 290         final var graphEdge = edge.getEdge();
 291         final var attributes = graphEdge != null ? graphEdge.getEdgeAttributes() : null;
 292         if (attributes == null) {
 293             LOG.debug("No attributes");
 294             return true;
 295         }
 296
 297         /* Check that Edge belongs to the requested address family */
 298         if (verifyAddressFamily(edge, attributes)) {
 299             return true;
 300         }
 301
 302         /* Check only IGP Metric, if specified, for simple SPF algorithm */
 303         if (this instanceof ShortestPathFirst) {
 304             final var metricConstraint = constraints.getMetric();
 305             if (metricConstraint != null) {
 306                 final var metric = attributes.getMetric();
 307                 if (metric == null) {
 308                     return true;
 309                 }
 310                 final int totalCost = metric.intValue() + path.getCost();
 311                 final var maxCost = metricConstraint.intValue();
 312                 if (totalCost > maxCost) {
 313                     LOG.debug("Metric {} exceed constraint {}", totalCost, maxCost);
 314                     return true;
 315                 }
 316             }
 317             LOG.trace("Edge {} is valid for Simple Path Computation", edge);
 318             return false;
 319         }
 320
 321         /* Check that Edge respect Metric constraints */
 322         if (verifyMetrics(attributes, path)) {
 323             return true;
 324         }
 325
 326         /* Check that Edge meet Bandwidth constraint */
 327         if (verifyBandwidth(edge, attributes)) {
 328             return true;
 329         }
 330
 331         /* Check that Edge belongs to admin group */
 332         final var adminGroup = constraints.getAdminGroup();
 333         if (adminGroup != null && !adminGroup.equals(attributes.getAdminGroup())) {
 334             LOG.debug("Not in the requested admin-group");
 335             return true;
 336         }
 337
 338         /* Check that Edge is not part of Exclude Route */
 339         if (verifyExcludeRoute(edge, attributes)) {
 340             return true;
 341         }
 342
 343         /*
 344          * OK. All is fine. We can consider this Edge valid, so not to be prune
 345          */
 346         LOG.trace("Edge {} is valid for Constrained Path Computation", edge);
 347         return false;
 348     }
 349
 350     /**
 351      * Return the MPLS Label corresponding to the Node SID for IPv4 when the
 352      * Connected Vertex is Segment Routing aware.
 353      *
 354      * @return MPLS Label if Connected Vertex is Segment Routing aware, Null
 355      *         otherwise
 356      */
 357     protected @Nullable MplsLabel getIpv4NodeSid(final ConnectedVertex cvertex) {
 358         /*
 359          * Check that Vertex is Segment Routing aware
 360          */
 361         final var vertex = cvertex.getVertex();
 362         if (vertex == null || vertex.getSrgb() == null) {
 363             return null;
 364         }
 365         /*
 366          * Find in Prefix List Node SID attached to the IPv4 of the next Vertex
 367          * and return the MPLS Label that corresponds to the index in the SRGB
 368          */
 369         final var prefixes = cvertex.getPrefixes();
 370         if (prefixes != null) {
 371             for (Prefix prefix : prefixes) {
 372                 final var prefixSid = prefix.getPrefixSid();
 373                 final var nodeSid = prefix.getNodeSid();
 374                 if (prefixSid != null && nodeSid != null) {
 375                     if (nodeSid && prefix.getPrefix().getIpv4Prefix() != null) {
 376                         return new MplsLabel(prefixSid);
 377                     }
 378                 }
 379             }
 380         }
 381         return null;
 382     }
 383
 384     /**
 385      * Return the MPLS Label corresponding to the Node SID for IPv6 when the
 386      * Connected Vertex is Segment Routing aware.
 387      *
 388      * @return MPLS Label if Connected Vertex is Segment Routing aware, Null
 389      *         otherwise
 390      */
 391     protected @Nullable MplsLabel getIpv6NodeSid(final ConnectedVertex cvertex) {
 392         /*
 393          * Check that Vertex is Segment Routing aware
 394          */
 395         final var vertex = cvertex.getVertex();
 396         if (cvertex == null || vertex.getSrgb() == null) {
 397             return null;
 398         }
 399         /*
 400          * Find in Prefix List Node SID attached to the IPv6 of the next Vertex
 401          * and return the MPLS Label that corresponds to the index in the SRGB
 402          */
 403         final var prefixes = cvertex.getPrefixes();
 404         if (prefixes != null) {
 405             for (var prefix : cvertex.getPrefixes()) {
 406                 final var prefixSid = prefix.getPrefixSid();
 407                 final var nodeSid = prefix.getNodeSid();
 408                 if (prefixSid != null && nodeSid != null) {
 409                     if (nodeSid && prefix.getPrefix().getIpv6Prefix() != null) {
 410                         return new MplsLabel(prefixSid);
 411                     }
 412                 }
 413             }
 414         }
 415         return null;
 416     }
 417
 418     /**
 419      * Convert List of Connected Edges into a Path Description as a List of
 420      * IPv4, IPv6 or MPLS Label depending of the requested Address Family.
 421      *
 422      * @param edges
 423      *            List of Connected Edges
 424      *
 425      * @return Path Description
 426      */
 427     protected List<PathDescription> getPathDescription(final List<ConnectedEdge> edges) {
 428         final var list = new ArrayList<PathDescription>(edges.size());
 429         for (var edge : edges) {
 430             final var pathDesc = switch (constraints.getAddressFamily()) {
 431                 case Ipv4 -> new PathDescriptionBuilder()
 432                             .setIpv4(edge.getEdge().getEdgeAttributes().getLocalAddress())
 433                             .setRemoteIpv4(edge.getEdge().getEdgeAttributes().getRemoteAddress())
 434                             .build();
 435                 case Ipv6 -> new PathDescriptionBuilder()
 436                             .setIpv6(edge.getEdge().getEdgeAttributes().getLocalAddress6())
 437                             .setRemoteIpv6(edge.getEdge().getEdgeAttributes().getRemoteAddress6())
 438                             .build();
 439                 case SrIpv4 -> new PathDescriptionBuilder()
 440                             .setIpv4(edge.getEdge().getEdgeAttributes().getLocalAddress())
 441                             .setRemoteIpv4(edge.getEdge().getEdgeAttributes().getRemoteAddress())
 442                             .setSid(edge.getEdge().getEdgeAttributes().getAdjSid())
 443                             .build();
 444                 case SrIpv6 -> new PathDescriptionBuilder()
 445                             .setIpv6(edge.getEdge().getEdgeAttributes().getLocalAddress6())
 446                             .setRemoteIpv6(edge.getEdge().getEdgeAttributes().getRemoteAddress6())
 447                             .setSid(edge.getEdge().getEdgeAttributes().getAdjSid6())
 448                             .build();
 449             };
 450             list.add(pathDesc);
 451         }
 452         return list;
 453     }
 454
 455     private VertexKey getVertexKey(final IncludeRoute iro, final AddressFamily af) {
 456         final var address = switch (af) {
 457             case Ipv4, SrIpv4 -> new IpAddress(iro.getIpv4());
 458             case Ipv6, SrIpv6 -> new IpAddress(iro.getIpv6());
 459         };
 460
 461         final var vertex = graph.getConnectedVertex(address);
 462         return vertex != null ? vertex.getVertex().key() : null;
 463     }
 464
 465     private static ConstrainedPath mergePath(final ConstrainedPath cp1, final ConstrainedPath cp2) {
 466         final var mergePathDesc = new ArrayList<>(cp1.getPathDescription());
 467         mergePathDesc.addAll(cp2.getPathDescription());
 468
 469         final var cp1status = cp1.getStatus();
 470         final var cp2status = cp2.getStatus();
 471         return new ConstrainedPathBuilder(cp1)
 472             .setPathDescription(mergePathDesc)
 473             .setStatus(cp1status.equals(cp2status) ? cp1status : cp2status)
 474             .build();
 475     }
 476
 477     @Override
 478     public ConstrainedPath computeP2pPath(final VertexKey source, final VertexKey destination,
 479             final PathConstraints cts) {
 480         constraints = cts;
 481
 482         final var includeRoute = constraints.getIncludeRoute();
 483         if (includeRoute == null || includeRoute.isEmpty()) {
 484             return computeSimplePath(source, destination);
 485         }
 486
 487         final var it = includeRoute.iterator();
 488         /* Start by computing Path from source to the first Include Route address */
 489         VertexKey key = getVertexKey(it.next(), constraints.getAddressFamily());
 490         ConstrainedPath ctsPath = computeSimplePath(source, key);
 491         if (ctsPath.getStatus() != ComputationStatus.Completed) {
 492             return ctsPath;
 493         }
 494
 495         /* Then, loop other subsequent Include Route address */
 496         while (it.hasNext()) {
 497             VertexKey next = getVertexKey(it.next(), constraints.getAddressFamily());
 498             ctsPath = mergePath(ctsPath, computeSimplePath(key, next));
 499             if (ctsPath.getStatus() != ComputationStatus.Completed) {
 500                 return ctsPath;
 501             }
 502             key = next;
 503         }
 504
 505         /* Finish path up to the destination */
 506         return mergePath(ctsPath, computeSimplePath(key, destination));
 507     }
 508
 509     protected abstract ConstrainedPath computeSimplePath(VertexKey source, VertexKey destination);
 510 }