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