graph/graph-impl/src/main/java/org/opendaylight/graph/impl/ConnectedGraphImpl.java

   1 /*
   2  * Copyright (c) 2019 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.graph.impl;
   9
  10 import static com.google.common.base.Preconditions.checkArgument;
  11
  12 import com.google.common.util.concurrent.ListeningExecutorService;
  13 import com.google.common.util.concurrent.MoreExecutors;
  14 import java.nio.ByteBuffer;
  15 import java.util.ArrayList;
  16 import java.util.HashMap;
  17 import java.util.List;
  18 import java.util.concurrent.ConcurrentHashMap;
  19 import java.util.concurrent.Executors;
  20 import org.eclipse.jdt.annotation.NonNull;
  21 import org.opendaylight.graph.ConnectedEdge;
  22 import org.opendaylight.graph.ConnectedEdgeTrigger;
  23 import org.opendaylight.graph.ConnectedGraph;
  24 import org.opendaylight.graph.ConnectedGraphTrigger;
  25 import org.opendaylight.graph.ConnectedVertex;
  26 import org.opendaylight.graph.ConnectedVertexTrigger;
  27 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.inet.types.rev130715.IetfInetUtil;
  28 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.inet.types.rev130715.IpAddress;
  29 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.inet.types.rev130715.IpPrefix;
  30 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.inet.types.rev130715.Ipv4Address;
  31 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.inet.types.rev130715.Ipv4Prefix;
  32 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.inet.types.rev130715.Ipv6Address;
  33 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.inet.types.rev130715.Ipv6Prefix;
  34 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev220720.graph.topology.Graph;
  35 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev220720.graph.topology.graph.Edge;
  36 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev220720.graph.topology.graph.EdgeKey;
  37 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev220720.graph.topology.graph.Prefix;
  38 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev220720.graph.topology.graph.Vertex;
  39 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev220720.graph.topology.graph.VertexKey;
  40 import org.opendaylight.yang.gen.v1.urn.tbd.params.xml.ns.yang.network.topology.rev131021.network.topology.TopologyKey;
  41 import org.opendaylight.yangtools.yang.common.Uint32;
  42 import org.slf4j.Logger;
  43 import org.slf4j.LoggerFactory;
  44
  45 /**
  46  * This Class implements the Connected Graph for path computation algorithms.
  47  *
  48  * @author Olivier Dugeon
  49  * @author Philippe Niger
  50  */
  51 public class ConnectedGraphImpl implements ConnectedGraph {
  52     private static final Logger LOG = LoggerFactory.getLogger(ConnectedGraphImpl.class);
  53
  54     /* List of Connected Vertices that composed this Connected Graph */
  55     private final HashMap<Long, ConnectedVertexImpl> vertices = new HashMap<>();
  56
  57     /* List of Connected Edges that composed this Connected Graph */
  58     private final HashMap<Long, ConnectedEdgeImpl> edges = new HashMap<>();
  59
  60     /* List of IP prefix attached to Vertices */
  61     private final HashMap<IpPrefix, Prefix> prefixes = new HashMap<>();
  62
  63     /* List of Triggers attached to the Connected Graph */
  64     private final ConcurrentHashMap<TopologyKey, ConnectedGraphTrigger> graphTriggers = new ConcurrentHashMap<>();
  65     private final ListeningExecutorService exec = MoreExecutors.listeningDecorator(Executors.newCachedThreadPool());
  66
  67     /* Reference to the non connected Graph stored in DataStore */
  68     private Graph graph;
  69
  70     /* Reference to Graph Model Server to store corresponding graph in DataStore */
  71     private final ConnectedGraphServer connectedGraphServer;
  72
  73     public ConnectedGraphImpl(final Graph newGraph, final ConnectedGraphServer server) {
  74         graph = newGraph;
  75         createConnectedGraph();
  76         connectedGraphServer = server;
  77     }
  78
  79     /**
  80      * Transform the associated Graph in a Connected Graph. This method will automatically create associated Connected
  81      * Vertices, from the Graph Vertices, Connected Edges, from the Graph Edges and Prefix from the Graph Prefix.
  82      *
  83      */
  84     private void createConnectedGraph() {
  85         if (graph == null) {
  86             return;
  87         }
  88         /* Add all vertices */
  89         for (Vertex vertex : graph.nonnullVertex().values()) {
  90             ConnectedVertexImpl cvertex = new ConnectedVertexImpl(vertex);
  91             vertices.put(cvertex.getKey(), cvertex);
  92         }
  93         /* Add all edges */
  94         for (Edge edge : graph.nonnullEdge().values()) {
  95             ConnectedEdgeImpl cedge = new ConnectedEdgeImpl(edge);
  96             edges.put(cedge.getKey(), cedge);
  97         }
  98         /* Add all prefixes */
  99         for (Prefix prefix : graph.nonnullPrefix().values()) {
 100             ConnectedVertexImpl cvertex = vertices.get(prefix.getVertexId().longValue());
 101             if (cvertex != null) {
 102                 cvertex.addPrefix(prefix);
 103             }
 104             prefixes.putIfAbsent(prefix.getPrefix(), prefix);
 105         }
 106     }
 107
 108     /**
 109      * Return Connected Vertex if it exists or create a new one.
 110      *
 111      * @param  key   Unique Vertex Key identifier
 112      * @return new or existing Connected Vertex
 113      */
 114     private ConnectedVertexImpl updateConnectedVertex(final @NonNull Long key) {
 115         checkArgument(key != 0, "Provided Vertex Key must not be equal to 0");
 116         ConnectedVertexImpl vertex = vertices.get(key);
 117         if (vertex == null) {
 118             vertex = new ConnectedVertexImpl(key);
 119             vertices.put(key, vertex);
 120         }
 121         return vertex;
 122     }
 123
 124     /**
 125      * Return Connected Edge if it exist or create a new one.
 126      *
 127      * @param key   Unique Edge Key identifier
 128      * @return new or existing Connected Edge
 129      */
 130     private ConnectedEdgeImpl updateConnectedEdge(final @NonNull Long key) {
 131         checkArgument(key != 0, "Provided Edge Key must not be equal to 0");
 132         ConnectedEdgeImpl edge = edges.get(key);
 133         if (edge == null) {
 134             edge = new ConnectedEdgeImpl(key);
 135             edges.put(edge.getKey(), edge);
 136         }
 137         return edge;
 138     }
 139
 140     /**
 141      * Connect source and destination Connected Vertices with the given Connected Edge.
 142      *
 143      * @param srcVertex Source Connected Vertex
 144      * @param dstVertex Destination Connected Vertex
 145      * @param edge      Connected Edge
 146      */
 147     private static void connectVertices(final ConnectedVertexImpl srcVertex, final ConnectedVertexImpl dstVertex,
 148             final ConnectedEdgeImpl edge) {
 149         if (edge != null) {
 150             edge.setSource(srcVertex);
 151             edge.setDestination(dstVertex);
 152         }
 153         if (srcVertex != null) {
 154             srcVertex.addOutput(edge);
 155         }
 156         if (dstVertex != null) {
 157             dstVertex.addInput(edge);
 158         }
 159     }
 160
 161     @Override
 162     public Graph getGraph() {
 163         return graph;
 164     }
 165
 166     @Override
 167     public List<ConnectedVertex> getVertices() {
 168         return new ArrayList<>(vertices.values());
 169     }
 170
 171     @Override
 172     public ConnectedVertex getConnectedVertex(final Long key) {
 173         return vertices.get(key);
 174     }
 175
 176     @Override
 177     public ConnectedVertex getConnectedVertex(final IpAddress address) {
 178         if (address == null) {
 179             return null;
 180         }
 181         IpPrefix prefix = null;
 182         if (address.getIpv4Address() != null) {
 183             prefix = new IpPrefix(new Ipv4Prefix(address.getIpv4Address().getValue() + "/32"));
 184         }
 185         if (address.getIpv6Address() != null) {
 186             prefix = new IpPrefix(new Ipv6Prefix(address.getIpv6Address().getValue() + "/128"));
 187         }
 188         if (prefix != null && prefixes.containsKey(prefix)) {
 189             long key = prefixes.get(prefix).getVertexId().longValue();
 190             return vertices.get(key);
 191         } else {
 192             return null;
 193         }
 194     }
 195
 196     @Override
 197     public int getVerticesSize() {
 198         return vertices.size();
 199     }
 200
 201     @Override
 202     public List<ConnectedEdge> getEdges() {
 203         return new ArrayList<>(edges.values());
 204     }
 205
 206     @Override
 207     public ConnectedEdge getConnectedEdge(final Long key) {
 208         return edges.get(key);
 209     }
 210
 211     @Override
 212     public ConnectedEdge getConnectedEdge(final IpAddress address) {
 213         if (address == null) {
 214             return null;
 215         }
 216         if (address.getIpv4Address() != null) {
 217             return getConnectedEdge(address.getIpv4Address());
 218         }
 219         if (address.getIpv6Address() != null) {
 220             return getConnectedEdge(address.getIpv6Address());
 221         }
 222         return null;
 223     }
 224
 225     @Override
 226     public ConnectedEdge getConnectedEdge(final Ipv4Address address) {
 227         return address == null ? null : getConnectedEdge(
 228             Uint32.fromIntBits(IetfInetUtil.ipv4AddressBits(address)).longValue());
 229     }
 230
 231     @Override
 232     public ConnectedEdge getConnectedEdge(final Ipv6Address address) {
 233         return address == null ? null : getConnectedEdge(
 234             ByteBuffer.wrap(IetfInetUtil.ipv6AddressBytes(address), Long.BYTES, Long.BYTES).getLong());
 235     }
 236
 237     @Override
 238     public int getEdgesSize() {
 239         return edges.size();
 240     }
 241
 242     @Override
 243     public List<Prefix> getPrefixes() {
 244         return new ArrayList<>(prefixes.values());
 245     }
 246
 247     @Override
 248     public Prefix getPrefix(final IpPrefix prefix) {
 249         return prefixes.get(prefix);
 250     }
 251
 252     private void callVertexTrigger(final ConnectedVertexImpl cvertex, final Vertex vertex) {
 253         List<ConnectedVertexTrigger> vertexTriggers = cvertex.getTriggers();
 254         if (vertexTriggers == null || vertexTriggers.isEmpty()) {
 255             return;
 256         }
 257         for (ConnectedGraphTrigger trigger : graphTriggers.values()) {
 258             exec.submit(() -> trigger.verifyVertex(vertexTriggers, cvertex, vertex));
 259         }
 260     }
 261
 262     @Override
 263     public ConnectedVertex addVertex(final Vertex vertex) {
 264         checkArgument(vertex != null, "Provided Vertex is a null object");
 265         ConnectedVertexImpl cvertex = updateConnectedVertex(vertex.getVertexId().longValue());
 266         Vertex old = cvertex.getVertex();
 267         connectedGraphServer.addVertex(graph, vertex, old);
 268         cvertex.setVertex(vertex);
 269         if (old != null) {
 270             callVertexTrigger(cvertex, old);
 271         }
 272         return cvertex;
 273     }
 274
 275     @Override
 276     public void deleteVertex(final VertexKey key) {
 277         checkArgument(key != null, "Provided Vertex Key is a null object");
 278         ConnectedVertexImpl cvertex = vertices.get(key.getVertexId().longValue());
 279         if (cvertex != null) {
 280             cvertex.disconnect();
 281             vertices.remove(cvertex.getKey());
 282             connectedGraphServer.deleteVertex(graph, cvertex.getVertex());
 283             cvertex.setVertex(null);
 284             callVertexTrigger(cvertex, null);
 285         }
 286     }
 287
 288     private void callEdgeTrigger(final ConnectedEdgeImpl cedge, final Edge edge) {
 289         List<ConnectedEdgeTrigger> edgeTriggers = cedge.getTriggers();
 290         if (edgeTriggers == null || edgeTriggers.isEmpty()) {
 291             return;
 292         }
 293         for (ConnectedGraphTrigger trigger : graphTriggers.values()) {
 294             exec.submit(() -> trigger.verifyEdge(edgeTriggers, cedge, edge));
 295         }
 296     }
 297
 298     @Override
 299     public ConnectedEdge addEdge(final Edge edge) {
 300         checkArgument(edge != null, "Provided Edge is a null object");
 301         ConnectedEdgeImpl cedge = updateConnectedEdge(edge.getEdgeId().longValue());
 302         Edge old = cedge.getEdge();
 303         if (old == null) {
 304             ConnectedVertexImpl source = null;
 305             ConnectedVertexImpl destination = null;
 306             if (edge.getLocalVertexId() != null) {
 307                 source = updateConnectedVertex(edge.getLocalVertexId().longValue());
 308             }
 309             if (edge.getRemoteVertexId() != null) {
 310                 destination = updateConnectedVertex(edge.getRemoteVertexId().longValue());
 311             }
 312             connectVertices(source, destination, cedge);
 313         }
 314         connectedGraphServer.addEdge(graph, edge, old);
 315         cedge.setEdge(edge);
 316         callEdgeTrigger(cedge, old);
 317         return cedge;
 318     }
 319
 320     /**
 321      * Connected Edge is kept in the edges Hash Map in order to memorize the total Bandwidth reserved by
 322      * Constrained Paths that belong to this Edge. Connected Edges are removed when the Connected Graph is cleared.
 323      */
 324     @Override
 325     public void deleteEdge(final EdgeKey key) {
 326         checkArgument(key != null, "Provided Edge Key is a null object");
 327         ConnectedEdgeImpl cedge = edges.get(key.getEdgeId().longValue());
 328         if (cedge != null) {
 329             connectedGraphServer.deleteEdge(graph, cedge.getEdge());
 330             cedge.disconnect();
 331             cedge.setEdge(null);
 332             callEdgeTrigger(cedge, null);
 333         }
 334     }
 335
 336     @Override
 337     public void addPrefix(final Prefix prefix) {
 338         checkArgument(prefix != null, "Provided Prefix is a null object");
 339         ConnectedVertexImpl cvertex = updateConnectedVertex(prefix.getVertexId().longValue());
 340         cvertex.addPrefix(prefix);
 341         prefixes.putIfAbsent(prefix.getPrefix(), prefix);
 342         connectedGraphServer.addPrefix(graph, prefix);
 343     }
 344
 345     @Override
 346     public void deletePrefix(final IpPrefix ippfx) {
 347         checkArgument(ippfx != null, "Provided Prefix is a null object");
 348         Prefix prefix = prefixes.get(ippfx);
 349         if (prefix != null) {
 350             ConnectedVertexImpl cvertex = vertices.get(prefix.getVertexId().longValue());
 351             if (cvertex != null) {
 352                 cvertex.removePrefix(prefix);
 353             }
 354             prefixes.remove(prefix.getPrefix());
 355             connectedGraphServer.deletePrefix(graph, prefix);
 356         }
 357     }
 358
 359     @Override
 360     public void clear() {
 361         LOG.info("Reset Connected Graph({})", graph.getName());
 362         vertices.clear();
 363         edges.clear();
 364         prefixes.clear();
 365         connectedGraphServer.clearGraph(graph);
 366         graph = null;
 367     }
 368
 369     @Override
 370     public String getSummary() {
 371         return vertices.size() + "/" + edges.size() + "/" + prefixes.size();
 372     }
 373
 374     @Override
 375     public boolean registerTrigger(final ConnectedGraphTrigger trigger, final TopologyKey key) {
 376         return graphTriggers.putIfAbsent(key, trigger) == null;
 377     }
 378
 379     @Override
 380     public boolean unRegisterTrigger(final ConnectedGraphTrigger trigger, final TopologyKey key) {
 381         return graphTriggers.remove(key, trigger);
 382     }
 383
 384     /**
 385      * Returns the name of the associated Graph.
 386      *
 387      * @return Graph name
 388      */
 389     @Override
 390     public String toString() {
 391         return graph.getName();
 392     }
 393 }