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