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