pcep/server/server-provider/src/main/java/org/opendaylight/bgpcep/pcep/server/provider/PathComputationImpl.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.bgpcep.pcep.server.provider;
   9
  10 import static java.util.Objects.requireNonNull;
  11
  12 import java.nio.ByteBuffer;
  13 import java.util.ArrayList;
  14 import java.util.List;
  15 import org.opendaylight.algo.PathComputationAlgorithm;
  16 import org.opendaylight.algo.PathComputationProvider;
  17 import org.opendaylight.bgpcep.pcep.server.PathComputation;
  18 import org.opendaylight.graph.ConnectedGraph;
  19 import org.opendaylight.graph.ConnectedVertex;
  20 import org.opendaylight.protocol.pcep.spi.PCEPErrors;
  21 import org.opendaylight.protocol.pcep.spi.PSTUtil;
  22 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.inet.types.rev130715.IpAddress;
  23 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.inet.types.rev130715.Ipv4Address;
  24 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.inet.types.rev130715.Ipv6Address;
  25 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev220720.DecimalBandwidth;
  26 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev220720.Delay;
  27 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev220720.graph.topology.graph.VertexKey;
  28 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev220324.AddressFamily;
  29 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev220324.AlgorithmType;
  30 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev220324.ComputationStatus;
  31 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev220324.ConstrainedPath;
  32 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev220324.PathConstraints;
  33 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev220324.get.constrained.path.input.ConstraintsBuilder;
  34 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev220324.path.constraints.ExcludeRoute;
  35 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev220324.path.constraints.ExcludeRouteBuilder;
  36 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev220324.path.constraints.IncludeRoute;
  37 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev220324.path.constraints.IncludeRouteBuilder;
  38 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.pcep.server.rev220321.pcc.configured.lsp.configured.lsp.ComputedPath;
  39 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.pcep.server.rev220321.pcc.configured.lsp.configured.lsp.ComputedPathBuilder;
  40 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.pcep.server.rev220321.pcc.configured.lsp.configured.lsp.IntendedPath;
  41 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.pcep.types.rev181109.Message;
  42 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.pcep.types.rev181109.bandwidth.object.Bandwidth;
  43 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.pcep.types.rev181109.classtype.object.ClassType;
  44 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.pcep.types.rev181109.endpoints.address.family.Ipv4Case;
  45 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.pcep.types.rev181109.endpoints.address.family.Ipv6Case;
  46 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.pcep.types.rev181109.endpoints.object.EndpointsObj;
  47 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.pcep.types.rev181109.exclude.route.object.Xro;
  48 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.pcep.types.rev181109.explicit.route.object.Ero;
  49 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.pcep.types.rev181109.include.route.object.Iro;
  50 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.pcep.types.rev181109.lsp.attributes.Metrics;
  51 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.pcep.types.rev181109.pcreq.message.pcreq.message.Requests;
  52 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.pcep.types.rev181109.pcreq.message.pcreq.message.requests.segment.computation.P2p;
  53 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.rsvp.rev150820.basic.explicit.route.subobjects.subobject.type.IpPrefixCase;
  54 import org.opendaylight.yangtools.yang.common.Decimal64;
  55 import org.opendaylight.yangtools.yang.common.Uint32;
  56 import org.slf4j.Logger;
  57 import org.slf4j.LoggerFactory;
  58
  59 public class PathComputationImpl implements PathComputation {
  60
  61     private static final Logger LOG = LoggerFactory.getLogger(PathComputationImpl.class);
  62
  63     private final ConnectedGraph tedGraph;
  64     private final PathComputationProvider algoProvider;
  65
  66     public PathComputationImpl(final ConnectedGraph tedGraph, final PathComputationProvider algoProvider) {
  67         this.tedGraph = requireNonNull(tedGraph);
  68         this.algoProvider = requireNonNull(algoProvider);
  69     }
  70
  71     @Override
  72     public Message computePath(final Requests req) {
  73         LOG.info("Received Compute Path request");
  74
  75         /* Check that Request Parameter Object is present */
  76         if (req == null || req.getRp() == null) {
  77             LOG.error("Missing Request Parameter Objects. Abort!");
  78             return MessagesUtil.createErrorMsg(PCEPErrors.RP_MISSING, Uint32.ZERO);
  79         }
  80
  81         LOG.debug("Request for path computation {}", req);
  82
  83         /*
  84          * Check that mandatory End Point Objects are present and Source /
  85          * Destination are know in the TED Graph
  86          */
  87         P2p input = req.getSegmentComputation().getP2p();
  88         if (input == null || input.getEndpointsObj() == null) {
  89             LOG.error("Missing End Point Objects. Abort!");
  90             Uint32 reqID = req.getRp().getRequestId().getValue();
  91             return MessagesUtil.createErrorMsg(PCEPErrors.END_POINTS_MISSING, reqID);
  92         }
  93         VertexKey source = getSourceVertexKey(input.getEndpointsObj());
  94         VertexKey destination = getDestinationVertexKey(input.getEndpointsObj());
  95         if (source == null) {
  96             return MessagesUtil.createNoPathMessage(req.getRp(), MessagesUtil.UNKNOWN_SOURCE);
  97         }
  98         if (destination == null) {
  99             return MessagesUtil.createNoPathMessage(req.getRp(), MessagesUtil.UNKNOWN_DESTINATION);
 100         }
 101
 102         /* Create new Constraints Object from the request */
 103         PathConstraints cts = getConstraints(input, !PSTUtil.isDefaultPST(req.getRp().getTlvs().getPathSetupType()));
 104
 105         /* Determine Path Computation Algorithm according to Input choice */
 106         AlgorithmType algoType;
 107         if (cts.getDelay() != null) {
 108             algoType = AlgorithmType.Samcra;
 109         } else if (cts.getTeMetric() != null) {
 110             algoType = AlgorithmType.Cspf;
 111         } else {
 112             algoType = AlgorithmType.Spf;
 113         }
 114         PathComputationAlgorithm algo = algoProvider.getPathComputationAlgorithm(tedGraph, algoType);
 115         if (algo == null) {
 116             return MessagesUtil.createErrorMsg(PCEPErrors.RESOURCE_LIMIT_EXCEEDED, Uint32.ZERO);
 117         }
 118
 119         /* Request Path Computation for given source, destination and constraints */
 120         LOG.debug("Call Path Computation {} algorithm for path from {} to {} with contraints {}",
 121                 algoType, source, destination, cts);
 122         final ConstrainedPath cpath = algo.computeP2pPath(source, destination, cts);
 123
 124         LOG.info("Computed path: {}", cpath.getPathDescription());
 125
 126         /* Check if we got a valid Path and return appropriate message */
 127         if (cpath.getStatus() == ComputationStatus.Completed) {
 128             return MessagesUtil.createPcRepMessage(req.getRp(), req.getSegmentComputation().getP2p(), cpath);
 129         } else {
 130             return MessagesUtil.createNoPathMessage(req.getRp(), MessagesUtil.NO_PATH);
 131         }
 132     }
 133
 134     public ComputedPath computeTePath(final IntendedPath intend) {
 135         final ComputedPathBuilder cpb = new ComputedPathBuilder();
 136         ConnectedVertex source = tedGraph.getConnectedVertex(intend.getSource());
 137         ConnectedVertex destination = tedGraph.getConnectedVertex(intend.getDestination());
 138
 139         if (source == null) {
 140             return cpb.setComputationStatus(ComputationStatus.NoSource).build();
 141         }
 142         if (destination == null) {
 143             return cpb.setComputationStatus(ComputationStatus.NoDestination).build();
 144         }
 145
 146         /* Determine Path Computation Algorithm according to parameters */
 147         AlgorithmType algoType;
 148         if (intend.getConstraints().getDelay() != null) {
 149             algoType = AlgorithmType.Samcra;
 150         } else if (intend.getConstraints().getTeMetric() != null) {
 151             algoType = AlgorithmType.Cspf;
 152         } else {
 153             algoType = AlgorithmType.Spf;
 154         }
 155         PathComputationAlgorithm algo = algoProvider.getPathComputationAlgorithm(tedGraph, algoType);
 156         if (algo == null) {
 157             return cpb.setComputationStatus(ComputationStatus.Failed).build();
 158         }
 159
 160         /* Request Path Computation for given source, destination and constraints */
 161         final ConstrainedPath cpath = algo.computeP2pPath(source.getVertex().key(), destination.getVertex().key(),
 162                 intend.getConstraints());
 163
 164         LOG.info("Computed path: {}", cpath.getPathDescription());
 165
 166         /* Check if we got a valid Path and return appropriate Path Description */
 167         if (cpath.getStatus() == ComputationStatus.Completed) {
 168             cpb.setPathDescription(cpath.getPathDescription()).setComputationStatus(ComputationStatus.Completed);
 169             if (intend.getConstraints().getDelay() != null) {
 170                 cpb.setComputedMetric(cpath.getDelay().getValue());
 171             } else if (intend.getConstraints().getTeMetric() != null) {
 172                 cpb.setComputedMetric(cpath.getTeMetric());
 173             } else {
 174                 cpb.setComputedMetric(cpath.getMetric());
 175             }
 176             return cpb.build();
 177         } else {
 178             return cpb.setComputationStatus(ComputationStatus.NoPath).build();
 179         }
 180     }
 181
 182     @Override
 183     public Ero computeEro(final EndpointsObj endpoints, final Bandwidth bandwidth, final ClassType classType,
 184             final List<Metrics> metrics, final Xro xro, final Iro iro, final boolean segmentRouting) {
 185         /* Get source and destination Vertex and verify there are valid */
 186         VertexKey source = getSourceVertexKey(endpoints);
 187         if (source == null) {
 188             return null;
 189         }
 190         VertexKey destination = getDestinationVertexKey(endpoints);
 191         if (destination == null) {
 192             return null;
 193         }
 194         /* Create new Constraints Object from the request */
 195         PathConstraints cts = getConstraints(endpoints, bandwidth, classType, metrics, xro, iro, segmentRouting);
 196
 197         /* Determine Path Computation Algorithm according to parameters */
 198         AlgorithmType algoType;
 199         if (cts.getDelay() != null) {
 200             algoType = AlgorithmType.Samcra;
 201         } else if (cts.getTeMetric() != null) {
 202             algoType = AlgorithmType.Cspf;
 203         } else {
 204             algoType = AlgorithmType.Spf;
 205         }
 206         PathComputationAlgorithm algo = algoProvider.getPathComputationAlgorithm(tedGraph, algoType);
 207         if (algo == null) {
 208             return null;
 209         }
 210
 211         /*
 212          * Request Path Computation for given source, destination and
 213          * constraints
 214          */
 215         final ConstrainedPath cpath = algo.computeP2pPath(source, destination, cts);
 216
 217         LOG.info("Computed path: {}", cpath.getPathDescription());
 218
 219         /* Check if we got a valid Path and return appropriate ERO */
 220         if (cpath.getStatus() == ComputationStatus.Completed) {
 221             return MessagesUtil.getEro(cpath.getPathDescription());
 222         } else {
 223             return null;
 224         }
 225     }
 226
 227     private VertexKey getSourceVertexKey(final EndpointsObj endPoints) {
 228         IpAddress address = null;
 229
 230         if (endPoints.getAddressFamily() instanceof Ipv4Case) {
 231             address = new IpAddress(((Ipv4Case) endPoints.getAddressFamily()).getIpv4().getSourceIpv4Address());
 232         }
 233         if (endPoints.getAddressFamily() instanceof Ipv6Case) {
 234             address = new IpAddress(((Ipv6Case) endPoints.getAddressFamily()).getIpv6().getSourceIpv6Address());
 235         }
 236         if (address == null) {
 237             return null;
 238         }
 239
 240         ConnectedVertex vertex = tedGraph.getConnectedVertex(address);
 241         LOG.debug("Compute path from Source {}", vertex != null ? vertex : "Unknown");
 242         return vertex != null ? vertex.getVertex().key() : null;
 243     }
 244
 245     private VertexKey getDestinationVertexKey(final EndpointsObj endPoints) {
 246         IpAddress address = null;
 247
 248         if (endPoints.getAddressFamily() instanceof Ipv4Case ipv4) {
 249             address = new IpAddress(ipv4.getIpv4().getDestinationIpv4Address());
 250         }
 251         if (endPoints.getAddressFamily() instanceof Ipv6Case ipv6) {
 252             address = new IpAddress(ipv6.getIpv6().getDestinationIpv6Address());
 253         }
 254         if (address == null) {
 255             return null;
 256         }
 257
 258         ConnectedVertex vertex = tedGraph.getConnectedVertex(address);
 259         LOG.debug("Compute path to Destination {}", vertex != null ? vertex : "Unknown");
 260         return vertex != null ? vertex.getVertex().key() : null;
 261     }
 262
 263     /* Convert Exclude Route Object (list of IP prefix) into Exclude Route (list of IP address) */
 264     private static List<ExcludeRoute> getExcludeRoute(final Xro xro, final AddressFamily af) {
 265         if (xro == null) {
 266             return null;
 267         }
 268         final var subobjects = xro.getSubobject();
 269         if (subobjects == null || subobjects.isEmpty()) {
 270             return null;
 271         }
 272
 273         final var erl = new ArrayList<ExcludeRoute>();
 274         for (var element : subobjects) {
 275             final var sbt = element.getSubobjectType();
 276             if (sbt instanceof IpPrefixCase ipc) {
 277                 switch (af) {
 278                     case Ipv4, SrIpv4 -> {
 279                         erl.add(new ExcludeRouteBuilder()
 280                             .setIpv4(new Ipv4Address(
 281                                 ipc.getIpPrefix().getIpPrefix().getIpv4Prefix().getValue().split("/")[0]))
 282                             .build());
 283                     }
 284                     case Ipv6, SrIpv6 -> {
 285                         erl.add(new ExcludeRouteBuilder()
 286                             .setIpv6(new Ipv6Address(
 287                                 ipc.getIpPrefix().getIpPrefix().getIpv6Prefix().getValue().split("/")[0]))
 288                             .build());
 289                     }
 290                     default -> {
 291                         // No-op
 292                     }
 293                 }
 294             }
 295         }
 296         return erl;
 297     }
 298
 299     /* Convert Include Route Object (list of IP prefix) into Exclude Route (list of IP address) */
 300     private static List<IncludeRoute> getIncludeRoute(final Iro iro, final AddressFamily af) {
 301         if (iro == null) {
 302             return null;
 303         }
 304
 305         final var subobjects = iro.getSubobject();
 306         if (subobjects == null || subobjects.isEmpty()) {
 307             return null;
 308         }
 309         final var irl = new ArrayList<IncludeRoute>();
 310         for (var element : subobjects) {
 311             final var sbt = element.getSubobjectType();
 312             if (sbt instanceof IpPrefixCase ipc) {
 313                 switch (af) {
 314                     case Ipv4, SrIpv4 -> {
 315                         irl.add(new IncludeRouteBuilder()
 316                             .setIpv4(new Ipv4Address(
 317                                 ipc.getIpPrefix().getIpPrefix().getIpv4Prefix().getValue().split("/")[0]))
 318                             .build());
 319                     }
 320                     case Ipv6, SrIpv6 -> {
 321                         irl.add(new IncludeRouteBuilder()
 322                             .setIpv6(new Ipv6Address(
 323                                 ipc.getIpPrefix().getIpPrefix().getIpv6Prefix().getValue().split("/")[0]))
 324                             .build());
 325                     }
 326                     default -> {
 327                         // No-op
 328                     }
 329                 }
 330             }
 331         }
 332         return irl;
 333     }
 334
 335     private static PathConstraints getConstraints(final P2p parameters, final boolean segmentRouting) {
 336         return getConstraints(parameters.getEndpointsObj(), parameters.getBandwidth(), parameters.getClassType(),
 337                 parameters.getMetrics(), parameters.getXro(), parameters.getIro(), segmentRouting);
 338     }
 339
 340     private static PathConstraints getConstraints(final EndpointsObj endpoints, final Bandwidth bandwidth,
 341             final ClassType classType, final List<Metrics> metrics, final Xro xro, final Iro iro,
 342             final boolean segmentRouting) {
 343         ConstraintsBuilder ctsBuilder = new ConstraintsBuilder();
 344
 345         /* Set Metrics if any */
 346         if (metrics != null) {
 347             for (Metrics metric : metrics) {
 348                 Float convert = ByteBuffer.wrap(metric.getMetric().getValue().getValue()).getFloat();
 349                 final long value = convert.longValue();
 350                 /* Skip Metric with value equal to 0 */
 351                 if (value == 0) {
 352                     continue;
 353                 }
 354
 355                 switch (metric.getMetric().getMetricType().intValue()) {
 356                     case MessagesUtil.IGP_METRIC:
 357                         ctsBuilder.setMetric(Uint32.valueOf(value));
 358                         break;
 359                     case MessagesUtil.TE_METRIC:
 360                         ctsBuilder.setTeMetric(Uint32.valueOf(value));
 361                         break;
 362                     case MessagesUtil.PATH_DELAY:
 363                         ctsBuilder.setDelay(new Delay(Uint32.valueOf(value)));
 364                         break;
 365                     default:
 366                         LOG.warn("Metric {} is not handle by Path Computation Constraints", metric);
 367                         break;
 368                 }
 369             }
 370         }
 371
 372         /* Set Bandwidth and Class Type */
 373         if (bandwidth != null) {
 374             Float convert = ByteBuffer.wrap(bandwidth.getBandwidth().getValue()).getFloat();
 375             final long value = convert.longValue();
 376             /* Skip Bandwidth with value equal to 0 */
 377             if (value != 0) {
 378                 // FIXME: correct rounding/truncation!
 379                 ctsBuilder.setBandwidth(new DecimalBandwidth(Decimal64.valueOf(2, value)));
 380                 if (classType != null) {
 381                     ctsBuilder.setClassType(classType.getClassType().getValue());
 382                 }
 383             }
 384         }
 385
 386         AddressFamily af = endpoints.getAddressFamily() instanceof Ipv4Case
 387                 ? segmentRouting ? AddressFamily.SrIpv4 : AddressFamily.Ipv4
 388                 : segmentRouting ? AddressFamily.SrIpv6 : AddressFamily.Ipv6;
 389
 390         /* Set Address Family, Exclude Route and Include Route if any */
 391         return ctsBuilder
 392                 .setAddressFamily(af)
 393                 .setExcludeRoute(getExcludeRoute(xro, af))
 394                 .setIncludeRoute(getIncludeRoute(iro, af))
 395                 .build();
 396     }
 397 }