opendaylight/routing/dijkstra_implementation/src/main/java/org/opendaylight/controller/routing/dijkstra_implementation/internal/DijkstraImplementation.java

   1 /*
   2  * Copyright (c) 2013 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 /**
  10  * @file   DijkstraImplementation.java
  11  *
  12  *
  13  * @brief  Implementation of a routing engine using
  14  * dijkstra. Implementation of dijkstra come from Jung2 library
  15  *
  16  */
  17 package org.opendaylight.controller.routing.dijkstra_implementation.internal;
  18
  19 import org.opendaylight.controller.clustering.services.IClusterContainerServices;
  20 import org.opendaylight.controller.sal.core.Bandwidth;
  21 import org.opendaylight.controller.sal.core.ConstructionException;
  22 import org.opendaylight.controller.sal.core.Edge;
  23 import org.opendaylight.controller.sal.core.Node;
  24 import org.opendaylight.controller.sal.core.NodeConnector;
  25 import org.opendaylight.controller.sal.core.Path;
  26 import org.opendaylight.controller.sal.core.Property;
  27 import org.opendaylight.controller.sal.core.UpdateType;
  28 import org.opendaylight.controller.sal.routing.IListenRoutingUpdates;
  29 import org.opendaylight.controller.sal.routing.IRouting;
  30 import org.opendaylight.controller.sal.topology.TopoEdgeUpdate;
  31 import org.opendaylight.controller.switchmanager.ISwitchManager;
  32 import org.opendaylight.controller.topologymanager.ITopologyManager;
  33 import org.opendaylight.controller.topologymanager.ITopologyManagerClusterWideAware;
  34
  35 import edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath;
  36 import edu.uci.ics.jung.graph.Graph;
  37 import edu.uci.ics.jung.graph.SparseMultigraph;
  38 import edu.uci.ics.jung.graph.util.EdgeType;
  39
  40 import java.util.HashSet;
  41 import java.util.Iterator;
  42 import java.util.List;
  43 import java.util.ArrayList;
  44 import java.util.Set;
  45 import java.util.Map;
  46 import java.util.concurrent.ConcurrentHashMap;
  47 import java.util.concurrent.ConcurrentMap;
  48
  49 import org.slf4j.Logger;
  50 import org.slf4j.LoggerFactory;
  51 import org.apache.commons.collections15.Transformer;
  52
  53 @SuppressWarnings("rawtypes")
  54 public class DijkstraImplementation implements IRouting, ITopologyManagerClusterWideAware {
  55     private static Logger log = LoggerFactory.getLogger(DijkstraImplementation.class);
  56     private ConcurrentMap<Short, Graph<Node, Edge>> topologyBWAware;
  57     private ConcurrentMap<Short, DijkstraShortestPath<Node, Edge>> sptBWAware;
  58     DijkstraShortestPath<Node, Edge> mtp; // Max Throughput Path
  59     private Set<IListenRoutingUpdates> routingAware;
  60     private ISwitchManager switchManager;
  61     private ITopologyManager topologyManager;
  62     private static final long DEFAULT_LINK_SPEED = Bandwidth.BW1Gbps;
  63     private IClusterContainerServices clusterContainerService;
  64
  65     public void setListenRoutingUpdates(final IListenRoutingUpdates i) {
  66         if (this.routingAware == null) {
  67             this.routingAware = new HashSet<IListenRoutingUpdates>();
  68         }
  69         if (this.routingAware != null) {
  70             log.debug("Adding routingAware listener: {}", i);
  71             this.routingAware.add(i);
  72         }
  73     }
  74
  75     public void unsetListenRoutingUpdates(final IListenRoutingUpdates i) {
  76         if (this.routingAware == null) {
  77             return;
  78         }
  79         log.debug("Removing routingAware listener");
  80         this.routingAware.remove(i);
  81         if (this.routingAware.isEmpty()) {
  82             // We don't have any listener lets dereference
  83             this.routingAware = null;
  84         }
  85     }
  86
  87     @Override
  88     public synchronized void initMaxThroughput(
  89             final Map<Edge, Number> EdgeWeightMap) {
  90         if (mtp != null) {
  91             log.error("Max Throughput Dijkstra is already enabled!");
  92             return;
  93         }
  94         Transformer<Edge, ? extends Number> mtTransformer = null;
  95         if (EdgeWeightMap == null) {
  96             mtTransformer = new Transformer<Edge, Double>() {
  97                 @Override
  98                 public Double transform(Edge e) {
  99                     if (switchManager == null) {
 100                         log.error("switchManager is null");
 101                         return (double) -1;
 102                     }
 103                     NodeConnector srcNC = e.getTailNodeConnector();
 104                     NodeConnector dstNC = e.getHeadNodeConnector();
 105                     if ((srcNC == null) || (dstNC == null)) {
 106                         log.error("srcNC:{} or dstNC:{} is null", srcNC, dstNC);
 107                         return (double) -1;
 108                     }
 109                     Bandwidth bwSrc = (Bandwidth) switchManager.getNodeConnectorProp(srcNC,
 110                             Bandwidth.BandwidthPropName);
 111                     Bandwidth bwDst = (Bandwidth) switchManager.getNodeConnectorProp(dstNC,
 112                             Bandwidth.BandwidthPropName);
 113
 114                     long srcLinkSpeed = 0, dstLinkSpeed = 0;
 115                     if ((bwSrc == null) || ((srcLinkSpeed = bwSrc.getValue()) == 0)) {
 116                         log.debug("srcNC: {} - Setting srcLinkSpeed to Default!", srcNC);
 117                         srcLinkSpeed = DEFAULT_LINK_SPEED;
 118                     }
 119
 120                     if ((bwDst == null) || ((dstLinkSpeed = bwDst.getValue()) == 0)) {
 121                         log.debug("dstNC: {} - Setting dstLinkSpeed to Default!", dstNC);
 122                         dstLinkSpeed = DEFAULT_LINK_SPEED;
 123                     }
 124
 125                     // TODO: revisit the logic below with the real use case in
 126                     // mind
 127                     // For now we assume the throughput to be the speed of the
 128                     // link itself
 129                     // this kind of logic require information that should be
 130                     // polled by statistic manager and are not yet available,
 131                     // also this service at the moment is not used, so to be
 132                     // revisited later on
 133                     long avlSrcThruPut = srcLinkSpeed;
 134                     long avlDstThruPut = dstLinkSpeed;
 135
 136                     // Use lower of the 2 available throughput as the available
 137                     // throughput
 138                     long avlThruPut = avlSrcThruPut < avlDstThruPut ? avlSrcThruPut : avlDstThruPut;
 139
 140                     if (avlThruPut <= 0) {
 141                         log.debug("Edge {}: Available Throughput {} <= 0!", e, avlThruPut);
 142                         return (double) -1;
 143                     }
 144                     return (double) (Bandwidth.BW1Pbps / avlThruPut);
 145                 }
 146             };
 147         } else {
 148             mtTransformer = new Transformer<Edge, Number>() {
 149                 @Override
 150                 public Number transform(Edge e) {
 151                     return EdgeWeightMap.get(e);
 152                 }
 153             };
 154         }
 155         Short baseBW = Short.valueOf((short) 0);
 156         // Initialize mtp also using the default topo
 157         Graph<Node, Edge> g = this.topologyBWAware.get(baseBW);
 158         if (g == null) {
 159             log.error("Default Topology Graph is null");
 160             return;
 161         }
 162         mtp = new DijkstraShortestPath<Node, Edge>(g, mtTransformer);
 163     }
 164
 165     @Override
 166     public Path getRoute(final Node src, final Node dst) {
 167         if ((src == null) || (dst == null)) {
 168             return null;
 169         }
 170         return getRoute(src, dst, (short) 0);
 171     }
 172
 173     @Override
 174     public synchronized Path getMaxThroughputRoute(Node src, Node dst) {
 175         if (mtp == null) {
 176             log.error("Max Throughput Path Calculation Uninitialized!");
 177             return null;
 178         }
 179
 180         List<Edge> path;
 181         try {
 182             path = mtp.getMaxThroughputPath(src, dst);
 183         } catch (IllegalArgumentException ie) {
 184             log.debug("A vertex is yet not known between {} {}", src, dst);
 185             return null;
 186         }
 187         Path res;
 188         try {
 189             res = new Path(path);
 190         } catch (ConstructionException e) {
 191             log.debug("A vertex is yet not known between {} {}", src, dst);
 192             return null;
 193         }
 194         return res;
 195     }
 196
 197     @Override
 198     public synchronized Path getRoute(final Node src, final Node dst, final Short Bw) {
 199         DijkstraShortestPath<Node, Edge> spt = this.sptBWAware.get(Bw);
 200         if (spt == null) {
 201             return null;
 202         }
 203         List<Edge> path;
 204         try {
 205             path = spt.getPath(src, dst);
 206         } catch (IllegalArgumentException ie) {
 207             log.debug("A vertex is yet not known between {} {}", src, dst);
 208             return null;
 209         }
 210         Path res;
 211         try {
 212             res = new Path(path);
 213         } catch (ConstructionException e) {
 214             log.debug("A vertex is yet not known between {} {}", src, dst);
 215             return null;
 216         }
 217         return res;
 218     }
 219
 220     @Override
 221     public synchronized void clear() {
 222         DijkstraShortestPath<Node, Edge> spt;
 223         for (Short bw : this.sptBWAware.keySet()) {
 224             spt = this.sptBWAware.get(bw);
 225             if (spt != null) {
 226                 spt.reset();
 227             }
 228         }
 229         clearMaxThroughput();
 230     }
 231
 232     @Override
 233     public synchronized void clearMaxThroughput() {
 234         if (mtp != null) {
 235             mtp.reset(); // reset max throughput path
 236         }
 237     }
 238
 239     @SuppressWarnings({ "unchecked" })
 240     private synchronized boolean updateTopo(Edge edge, Short bw, UpdateType type) {
 241         Graph<Node, Edge> topo = this.topologyBWAware.get(bw);
 242         DijkstraShortestPath<Node, Edge> spt = this.sptBWAware.get(bw);
 243         boolean edgePresentInGraph = false;
 244         Short baseBW = Short.valueOf((short) 0);
 245
 246         if (topo == null) {
 247             // Create topology for this BW
 248             Graph<Node, Edge> g = new SparseMultigraph();
 249             this.topologyBWAware.put(bw, g);
 250             topo = this.topologyBWAware.get(bw);
 251             this.sptBWAware.put(bw, new DijkstraShortestPath(g));
 252             spt = this.sptBWAware.get(bw);
 253         }
 254
 255         if (topo != null) {
 256             NodeConnector src = edge.getTailNodeConnector();
 257             NodeConnector dst = edge.getHeadNodeConnector();
 258             if (spt == null) {
 259                 spt = new DijkstraShortestPath(topo);
 260                 this.sptBWAware.put(bw, spt);
 261             }
 262
 263             switch (type) {
 264             case ADDED:
 265                 // Make sure the vertex are there before adding the edge
 266                 topo.addVertex(src.getNode());
 267                 topo.addVertex(dst.getNode());
 268                 // Add the link between
 269                 edgePresentInGraph = topo.containsEdge(edge);
 270                 if (edgePresentInGraph == false) {
 271                     try {
 272                         topo.addEdge(new Edge(src, dst), src.getNode(), dst.getNode(), EdgeType.DIRECTED);
 273                     } catch (final ConstructionException e) {
 274                         log.error("", e);
 275                         return edgePresentInGraph;
 276                     }
 277                 }
 278             case CHANGED:
 279                 // Mainly raised only on properties update, so not really useful
 280                 // in this case
 281                 break;
 282             case REMOVED:
 283                 // Remove the edge
 284                 try {
 285                     topo.removeEdge(new Edge(src, dst));
 286                 } catch (final ConstructionException e) {
 287                     log.error("", e);
 288                     return edgePresentInGraph;
 289                 }
 290
 291                 // If the src and dst vertex don't have incoming or
 292                 // outgoing links we can get ride of them
 293                 if (topo.containsVertex(src.getNode()) && (topo.inDegree(src.getNode()) == 0)
 294                         && (topo.outDegree(src.getNode()) == 0)) {
 295                     log.debug("Removing vertex {}", src);
 296                     topo.removeVertex(src.getNode());
 297                 }
 298
 299                 if (topo.containsVertex(dst.getNode()) && (topo.inDegree(dst.getNode()) == 0)
 300                         && (topo.outDegree(dst.getNode()) == 0)) {
 301                     log.debug("Removing vertex {}", dst);
 302                     topo.removeVertex(dst.getNode());
 303                 }
 304                 break;
 305             }
 306             spt.reset();
 307             if (bw.equals(baseBW)) {
 308                 clearMaxThroughput();
 309             }
 310         } else {
 311             log.error("Cannot find topology for BW {} this is unexpected!", bw);
 312         }
 313         return edgePresentInGraph;
 314     }
 315
 316     private boolean edgeUpdate(Edge e, UpdateType type, Set<Property> props, boolean local) {
 317         String srcType = null;
 318         String dstType = null;
 319
 320         log.trace("Got an edgeUpdate: {} props: {} update type: {} local: {}", new Object[] { e, props, type, local });
 321
 322         if ((e == null) || (type == null)) {
 323             log.error("Edge or Update type are null!");
 324             return false;
 325         } else {
 326             srcType = e.getTailNodeConnector().getType();
 327             dstType = e.getHeadNodeConnector().getType();
 328
 329             if (srcType.equals(NodeConnector.NodeConnectorIDType.PRODUCTION)) {
 330                 log.debug("Skip updates for {}", e);
 331                 return false;
 332             }
 333
 334             if (dstType.equals(NodeConnector.NodeConnectorIDType.PRODUCTION)) {
 335                 log.debug("Skip updates for {}", e);
 336                 return false;
 337             }
 338         }
 339
 340         Bandwidth bw = new Bandwidth(0);
 341         boolean newEdge = false;
 342         if (props != null) {
 343             props.remove(bw);
 344         }
 345
 346         Short baseBW = Short.valueOf((short) 0);
 347         // Update base topo
 348         newEdge = !updateTopo(e, baseBW, type);
 349         if (newEdge == true) {
 350             if (bw.getValue() != baseBW) {
 351                 // Update BW topo
 352                 updateTopo(e, (short) bw.getValue(), type);
 353             }
 354         }
 355         return newEdge;
 356     }
 357
 358     @Override
 359     public void edgeUpdate(List<TopoEdgeUpdate> topoedgeupdateList) {
 360         log.trace("Start of a Bulk EdgeUpdate with " + topoedgeupdateList.size() + " elements");
 361         boolean callListeners = false;
 362         for (int i = 0; i < topoedgeupdateList.size(); i++) {
 363             Edge e = topoedgeupdateList.get(i).getEdge();
 364             Set<Property> p = topoedgeupdateList.get(i)
 365                     .getProperty();
 366             UpdateType type = topoedgeupdateList.get(i)
 367                     .getUpdateType();
 368             boolean isLocal = topoedgeupdateList.get(i)
 369                     .isLocal();
 370             if ((edgeUpdate(e, type, p, isLocal)) && (!callListeners)) {
 371                 callListeners = true;
 372             }
 373         }
 374
 375         // The routing listeners should only be called on the coordinator, to
 376         // avoid multiple controller cluster nodes to actually do the
 377         // recalculation when only one need to react
 378         boolean amICoordinator = true;
 379         if (this.clusterContainerService != null) {
 380             amICoordinator = this.clusterContainerService.amICoordinator();
 381         }
 382         if ((callListeners) && (this.routingAware != null) && amICoordinator) {
 383             log.trace("Calling the routing listeners");
 384             for (IListenRoutingUpdates ra : this.routingAware) {
 385                 try {
 386                     ra.recalculateDone();
 387                 } catch (Exception ex) {
 388                     log.error("Exception on routingAware listener call", ex);
 389                 }
 390             }
 391         }
 392         log.trace("End of a Bulk EdgeUpdate");
 393     }
 394
 395     /**
 396      * Function called by the dependency manager when all the required
 397      * dependencies are satisfied
 398      *
 399      */
 400     @SuppressWarnings({ "unchecked", "rawtypes" })
 401     public void init() {
 402         log.debug("Routing init() is called");
 403         this.topologyBWAware = new ConcurrentHashMap<Short, Graph<Node, Edge>>();
 404         this.sptBWAware = new ConcurrentHashMap<Short, DijkstraShortestPath<Node, Edge>>();
 405         // Now create the default topology, which doesn't consider the
 406         // BW, also create the corresponding Dijkstra calculation
 407         Graph<Node, Edge> g = new SparseMultigraph();
 408         Short sZero = Short.valueOf((short) 0);
 409         this.topologyBWAware.put(sZero, g);
 410         this.sptBWAware.put(sZero, new DijkstraShortestPath(g));
 411         // Topologies for other BW will be added on a needed base
 412     }
 413
 414     /**
 415      * Function called by the dependency manager when at least one dependency
 416      * become unsatisfied or when the component is shutting down because for
 417      * example bundle is being stopped.
 418      *
 419      */
 420     void destroy() {
 421         log.debug("Routing destroy() is called");
 422     }
 423
 424     /**
 425      * Function called by dependency manager after "init ()" is called and after
 426      * the services provided by the class are registered in the service registry
 427      *
 428      */
 429     void start() {
 430         log.debug("Routing start() is called");
 431         // build the routing database from the topology if it exists.
 432         Map<Edge, Set<Property>> edges = topologyManager.getEdges();
 433         if (edges.isEmpty()) {
 434             return;
 435         }
 436         List<TopoEdgeUpdate> topoedgeupdateList = new ArrayList<TopoEdgeUpdate>();
 437         log.debug("Creating routing database from the topology");
 438         for (Iterator<Map.Entry<Edge, Set<Property>>> i = edges.entrySet()
 439                 .iterator(); i.hasNext();) {
 440             Map.Entry<Edge, Set<Property>> entry = i.next();
 441             Edge e = entry.getKey();
 442             Set<Property> props = entry.getValue();
 443             TopoEdgeUpdate topoedgeupdate = new TopoEdgeUpdate(e, props,
 444                     UpdateType.ADDED);
 445             topoedgeupdateList.add(topoedgeupdate);
 446         }
 447         edgeUpdate(topoedgeupdateList);
 448     }
 449
 450     /**
 451      * Function called by the dependency manager before the services exported by
 452      * the component are unregistered, this will be followed by a "destroy ()"
 453      * calls
 454      *
 455      */
 456     public void stop() {
 457         log.debug("Routing stop() is called");
 458     }
 459
 460     public void setSwitchManager(ISwitchManager switchManager) {
 461         this.switchManager = switchManager;
 462     }
 463
 464     public void unsetSwitchManager(ISwitchManager switchManager) {
 465         if (this.switchManager == switchManager) {
 466             this.switchManager = null;
 467         }
 468     }
 469
 470     public void setTopologyManager(ITopologyManager tm) {
 471         this.topologyManager = tm;
 472     }
 473
 474     public void unsetTopologyManager(ITopologyManager tm) {
 475         if (this.topologyManager == tm) {
 476             this.topologyManager = null;
 477         }
 478     }
 479
 480     void setClusterContainerService(IClusterContainerServices s) {
 481         log.debug("Cluster Service set");
 482         this.clusterContainerService = s;
 483     }
 484
 485     void unsetClusterContainerService(IClusterContainerServices s) {
 486         if (this.clusterContainerService == s) {
 487             log.debug("Cluster Service removed!");
 488             this.clusterContainerService = null;
 489         }
 490     }
 491
 492     @Override
 493     public void edgeOverUtilized(Edge edge) {
 494         // TODO Auto-generated method stub
 495
 496     }
 497
 498     @Override
 499     public void edgeUtilBackToNormal(Edge edge) {
 500         // TODO Auto-generated method stub
 501
 502     }
 503 }