impl/src/main/java/org/opendaylight/unimgr/mef/nrp/impl/decomposer/DecompositionAction.java

   1 /*
   2  * Copyright (c) 2017 Cisco Systems Inc and others.  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
   9 package org.opendaylight.unimgr.mef.nrp.impl.decomposer;
  10
  11 import java.util.ArrayList;
  12 import java.util.Collection;
  13 import java.util.Collections;
  14 import java.util.HashMap;
  15 import java.util.HashSet;
  16 import java.util.List;
  17 import java.util.Objects;
  18 import java.util.Optional;
  19 import java.util.Set;
  20 import java.util.function.Function;
  21 import java.util.function.Predicate;
  22 import java.util.stream.Collectors;
  23 import java.util.stream.Stream;
  24
  25 import org.jgrapht.Graph;
  26 import org.jgrapht.GraphPath;
  27 import org.jgrapht.alg.shortestpath.DijkstraShortestPath;
  28 import org.jgrapht.graph.DefaultDirectedGraph;
  29 import org.jgrapht.graph.DefaultEdge;
  30 import org.opendaylight.controller.md.sal.binding.api.DataBroker;
  31 import org.opendaylight.controller.md.sal.binding.api.ReadWriteTransaction;
  32 import org.opendaylight.controller.md.sal.common.api.data.ReadFailedException;
  33 import org.opendaylight.unimgr.mef.nrp.api.EndPoint;
  34 import org.opendaylight.unimgr.mef.nrp.api.FailureResult;
  35 import org.opendaylight.unimgr.mef.nrp.api.Subrequrest;
  36 import org.opendaylight.unimgr.mef.nrp.api.TapiConstants;
  37 import org.opendaylight.unimgr.mef.nrp.common.NrpDao;
  38 import org.opendaylight.unimgr.mef.nrp.common.TapiUtils;
  39 import org.opendaylight.yang.gen.v1.urn.odl.unimgr.yang.unimgr.ext.rev170531.NodeAdiAugmentation;
  40 import org.opendaylight.yang.gen.v1.urn.onf.otcc.yang.tapi.common.rev180307.OperationalState;
  41 import org.opendaylight.yang.gen.v1.urn.onf.otcc.yang.tapi.common.rev180307.PortDirection;
  42 import org.opendaylight.yang.gen.v1.urn.onf.otcc.yang.tapi.common.rev180307.ServiceInterfacePointRef;
  43 import org.opendaylight.yang.gen.v1.urn.onf.otcc.yang.tapi.common.rev180307.Uuid;
  44 import org.opendaylight.yang.gen.v1.urn.onf.otcc.yang.tapi.connectivity.rev180307.connectivity.service.end.point.ServiceInterfacePoint;
  45 import org.opendaylight.yang.gen.v1.urn.onf.otcc.yang.tapi.topology.rev180307.topology.Node;
  46 import org.opendaylight.yang.gen.v1.urn.onf.otcc.yang.tapi.topology.rev180307.topology.context.Topology;
  47 import org.slf4j.Logger;
  48 import org.slf4j.LoggerFactory;
  49
  50
  51 /**
  52  * Decompose request into sub-requests {@link Subrequrest} for drivers using graph path computation.
  53  * @author bartosz.michalik@amartus.com
  54  */
  55 class DecompositionAction {
  56     private static final Logger LOG = LoggerFactory.getLogger(DecompositionAction.class);
  57     private final List<EndPoint> endpoints;
  58     private final DataBroker broker;
  59     private final HashMap<Uuid, Vertex> sipToNep = new HashMap<>();
  60
  61     DecompositionAction(List<EndPoint> endpoints, DataBroker broker) {
  62         Objects.requireNonNull(endpoints);
  63         Objects.requireNonNull(broker);
  64         if (endpoints.size() < 2) {
  65             throw new IllegalArgumentException("there should be at least two endpoints defined");
  66         }
  67         this.endpoints = endpoints;
  68         this.broker = broker;
  69     }
  70
  71     Function<ServiceInterfacePoint, Uuid> toUuid = s -> s == null ? null : s.getServiceInterfacePointId();
  72
  73     List<Subrequrest> decompose() throws FailureResult {
  74         Graph<Vertex, DefaultEdge> graph = prepareData();
  75
  76
  77
  78         Set<String> missingSips = endpoints.stream()
  79                 .filter(e -> sipToNep.get(toUuid.apply(e.getEndpoint().getServiceInterfacePoint())) == null)
  80                 .map(e -> toUuid.apply(e.getEndpoint().getServiceInterfacePoint()).getValue())
  81                 .collect(Collectors.toSet());
  82         if (!missingSips.isEmpty()) {
  83             throw new FailureResult("Some service interface points not found in the system: "
  84                     + missingSips.stream().collect(Collectors.joining(",", "[", "]")));
  85         }
  86
  87         List<Vertex> vertices = endpoints.stream().map(e -> {
  88             Vertex vertex = sipToNep.get(toUuid.apply(e.getEndpoint().getServiceInterfacePoint()));
  89             if ((vertex.dir == PortDirection.OUTPUT && e.getEndpoint().getDirection() != PortDirection.OUTPUT)
  90                     ||  (vertex.dir == PortDirection.INPUT && e.getEndpoint().getDirection() != PortDirection.INPUT)) {
  91                 throw new IllegalArgumentException("Port direction for "
  92                         + e.getEndpoint().getLocalId() + " incompatible with NEP."
  93                         + "CEP " + e.getEndpoint().getDirection() + "  NEP " + vertex.dir);
  94             }
  95             return new Vertex(vertex, e.getEndpoint().getDirection());
  96         }).collect(Collectors.toList());
  97
  98         assert vertices.size() > 1;
  99
 100         Set<GraphPath<Vertex, DefaultEdge>> paths = new HashSet<>();
 101
 102         Set<Vertex> inV = vertices.stream().filter(isInput).collect(Collectors.toSet());
 103         Set<Vertex> outV = vertices.stream().filter(isOutput).collect(Collectors.toSet());
 104
 105         //do the verification whether it is possible to connect two nodes.
 106         inV.forEach(i ->
 107                 outV.stream().filter(o -> i != o).forEach(o -> {
 108                     GraphPath<Vertex, DefaultEdge> path = DijkstraShortestPath.findPathBetween(graph, i, o);
 109                     if (path != null) {
 110                         LOG.debug("Couldn't find path between {} and  {}", i, o);
 111                     }
 112                     paths.add(path);
 113                 })
 114         );
 115
 116         if (paths.stream().anyMatch(Objects::isNull)) {
 117             LOG.info("At least single path between endpoints not found");
 118             return null;
 119         }
 120
 121         List<Subrequrest> result = toSublists(paths);
 122         return result.isEmpty() ? null : result;
 123     }
 124
 125     private List<Subrequrest> toSublists(Set<GraphPath<Vertex, DefaultEdge>> paths) {
 126         return paths.stream()
 127                 .flatMap(gp -> gp.getVertexList().stream()).collect(Collectors.groupingBy(Vertex::getNodeUuid))
 128                 .entrySet().stream()
 129                 .map(e -> {
 130                     Set<EndPoint> fromVertexes = e.getValue().stream()
 131                             .map(this::toEndPoint).collect(Collectors.toSet());
 132                     return new Subrequrest(
 133                             e.getKey(),
 134                             new ArrayList<>(fromVertexes),
 135                             e.getValue().stream().findFirst().get().getActivationDriverId());
 136                 }).collect(Collectors.toList());
 137     }
 138
 139     private EndPoint toEndPoint(Vertex vertex) {
 140         EndPoint ep = endpoints.stream()
 141                 .filter(e -> e.getEndpoint().getServiceInterfacePoint()
 142                         .getServiceInterfacePointId().equals(vertex.getSip()))
 143                 .findFirst()
 144                 .orElse(new EndPoint(null, null));
 145         Objects.requireNonNull(vertex.getUuid());
 146         ep.setNepRef(TapiUtils.toSysNepRef(vertex.getNodeUuid(), vertex.getUuid()));
 147         return ep;
 148     }
 149
 150     private final Predicate<Vertex> isInput = v -> v.getDir() == PortDirection.BIDIRECTIONAL
 151             || v.getDir() == PortDirection.INPUT;
 152     private final Predicate<Vertex> isOutput = v -> v.getDir() == PortDirection.BIDIRECTIONAL
 153             || v.getDir() == PortDirection.OUTPUT;
 154
 155     private void interconnectNode(Graph<Vertex, DefaultEdge> graph, List<Vertex> vertices) {
 156         vertices.forEach(graph::addVertex);
 157         Set<Vertex> inV = vertices.stream().filter(isInput).collect(Collectors.toSet());
 158         Set<Vertex> outV = vertices.stream().filter(isOutput).collect(Collectors.toSet());
 159         interconnect(graph, inV, outV);
 160     }
 161
 162     private void interconnectLink(Graph<Vertex, DefaultEdge> graph, List<Vertex> vertices) {
 163         vertices.forEach(graph::addVertex);
 164         Set<Vertex> inV = vertices.stream().filter(isInput).collect(Collectors.toSet());
 165         Set<Vertex> outV = vertices.stream().filter(isOutput).collect(Collectors.toSet());
 166         interconnect(graph, outV, inV);
 167
 168
 169     }
 170
 171     private void interconnect(Graph<Vertex, DefaultEdge> graph, Collection<Vertex> from, Collection<Vertex> to) {
 172         from.forEach(iV ->
 173                 to.stream().filter(oV -> iV != oV).forEach(oV -> graph.addEdge(iV,oV)));
 174     }
 175
 176
 177     private Graph<Vertex, DefaultEdge> prepareData() throws FailureResult {
 178         ReadWriteTransaction tx = broker.newReadWriteTransaction();
 179         try {
 180             Topology topo = new NrpDao(tx).getTopology(TapiConstants.PRESTO_SYSTEM_TOPO);
 181             if (topo.getNode() == null) {
 182                 throw new FailureResult("There are no nodes in {0} topology", TapiConstants.PRESTO_SYSTEM_TOPO);
 183             }
 184
 185             Graph<Vertex, DefaultEdge> graph = new DefaultDirectedGraph<>(DefaultEdge.class);
 186
 187             topo.getNode().stream().map(this::nodeToGraph).forEach(vs -> {
 188                 List<Vertex> vertices = vs.collect(Collectors.toList());
 189                 vertices.forEach(v -> sipToNep.put(v.getSip(), v));
 190                 interconnectNode(graph, vertices);
 191             });
 192
 193             if (topo.getLink() != null) {
 194                 topo.getLink().stream()
 195                     .filter(l -> OperationalState.ENABLED == l.getOperationalState())
 196                     .forEach(l -> {
 197                         //we probably need to take link bidir/unidir into consideration as well
 198                         List<Vertex> vertices = l.getNodeEdgePoint().stream()
 199                             .map(nep -> graph.vertexSet().stream()
 200                                     .filter(v -> v.getUuid().equals(nep.getOwnedNodeEdgePointId())).findFirst())
 201                             .filter(Optional::isPresent).map(Optional::get).collect(Collectors.toList());
 202                         interconnectLink(graph, vertices);
 203                     });
 204             }
 205
 206             return graph;
 207         } catch (ReadFailedException e) {
 208             throw new FailureResult("Cannot read {0} topology", TapiConstants.PRESTO_SYSTEM_TOPO);
 209         }
 210     }
 211
 212     private Stream<Vertex> nodeToGraph(Node node) {
 213         Uuid nodeUuid = node.getUuid();
 214         String activationDriverId = node.augmentation(NodeAdiAugmentation.class).getActivationDriverId();
 215
 216
 217         return node.getOwnedNodeEdgePoint().stream()
 218             .filter(ep -> ep.getLinkPortDirection() != null
 219                     && ep.getLinkPortDirection() != PortDirection.UNIDENTIFIEDORUNKNOWN)
 220             .map(nep -> {
 221                 List<Uuid> sips = Collections.emptyList();
 222                 if (nep.getMappedServiceInterfacePoint() != null) {
 223                     sips = nep.getMappedServiceInterfacePoint().stream()
 224                         .map(ServiceInterfacePointRef::getServiceInterfacePointId)
 225                         .collect(Collectors.toList());
 226                 }
 227
 228                 if (sips.isEmpty()) {
 229                     return  new Vertex(nodeUuid, nep.getUuid(), null, nep.getLinkPortDirection(),activationDriverId);
 230                 }
 231                 if (sips.size() > 1) {
 232                     LOG.warn("NodeEdgePoint {} have multiple ServiceInterfacePoint mapped, selecting first one",
 233                             nep.getUuid());
 234                 }
 235                 return new Vertex(nodeUuid, nep.getUuid(), sips.get(0), nep.getLinkPortDirection(),activationDriverId);
 236
 237             });
 238     }
 239
 240     class Vertex implements Comparable<Vertex> {
 241
 242         private final Uuid nodeUuid;
 243         private final Uuid uuid;
 244         private final Uuid sip;
 245         private final String activationDriverId;
 246         private final PortDirection dir;
 247
 248         Vertex(Vertex px, PortDirection csDir) {
 249             this.nodeUuid = px.nodeUuid;
 250             this.uuid = px.uuid;
 251             this.sip = px.sip;
 252             this.dir = csDir;
 253             this.activationDriverId = px.activationDriverId;
 254         }
 255
 256         Vertex(Uuid nodeUuid, Uuid uuid, Uuid sip, PortDirection dir, String activationDriverId) {
 257             this.sip = sip;
 258             this.dir = dir;
 259             Objects.requireNonNull(nodeUuid);
 260             Objects.requireNonNull(uuid);
 261             Objects.requireNonNull(activationDriverId);
 262
 263             this.nodeUuid = nodeUuid;
 264             this.uuid = uuid;
 265             this.activationDriverId = activationDriverId;
 266         }
 267
 268         Uuid getNodeUuid() {
 269             return nodeUuid;
 270         }
 271
 272         Uuid getUuid() {
 273             return uuid;
 274         }
 275
 276         Uuid getSip() {
 277             return sip;
 278         }
 279
 280         public String getActivationDriverId() {
 281             return activationDriverId;
 282         }
 283
 284         @Override
 285         public boolean equals(Object other) {
 286             if (this == other) {
 287                 return true;
 288             }
 289             if (other == null || getClass() != other.getClass()) {
 290                 return false;
 291             }
 292             Vertex vertex = (Vertex) other;
 293             return Objects.equals(uuid, vertex.uuid);
 294         }
 295
 296         PortDirection getDir() {
 297             return dir;
 298         }
 299
 300         @Override
 301         public int hashCode() {
 302             return Objects.hash(uuid);
 303         }
 304
 305         @Override
 306         public int compareTo(Vertex other) {
 307             if (other == null) {
 308                 return -1;
 309             }
 310             return uuid.getValue().compareTo(other.uuid.getValue());
 311         }
 312
 313         @Override
 314         public String toString() {
 315             return "V{" + uuid.getValue() + '}';
 316         }
 317     }
 318 }