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.sal.core.Bandwidth;
  20 import org.opendaylight.controller.sal.core.ConstructionException;
  21 import org.opendaylight.controller.sal.core.Edge;
  22 import org.opendaylight.controller.sal.core.Node;
  23 import org.opendaylight.controller.sal.core.NodeConnector;
  24 import org.opendaylight.controller.sal.core.Path;
  25 import org.opendaylight.controller.sal.core.Property;
  26 import org.opendaylight.controller.sal.core.UpdateType;
  27 import org.opendaylight.controller.sal.reader.IReadService;
  28 import org.opendaylight.controller.sal.routing.IListenRoutingUpdates;
  29
  30 import org.opendaylight.controller.sal.routing.IRouting;
  31 import org.opendaylight.controller.sal.topology.TopoEdgeUpdate;
  32 import org.opendaylight.controller.switchmanager.ISwitchManager;
  33 import org.opendaylight.controller.topologymanager.ITopologyManager;
  34 import org.opendaylight.controller.topologymanager.ITopologyManagerAware;
  35
  36 import edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath;
  37 import edu.uci.ics.jung.graph.Graph;
  38 import edu.uci.ics.jung.graph.SparseMultigraph;
  39 import edu.uci.ics.jung.graph.util.EdgeType;
  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 import org.slf4j.Logger;
  51 import org.slf4j.LoggerFactory;
  52 import org.apache.commons.collections15.Transformer;
  53
  54 public class DijkstraImplementation implements IRouting, ITopologyManagerAware {
  55     private static Logger log = LoggerFactory
  56             .getLogger(DijkstraImplementation.class);
  57     private ConcurrentMap<Short, Graph<Node, Edge>> topologyBWAware;
  58     private ConcurrentMap<Short, DijkstraShortestPath<Node, Edge>> sptBWAware;
  59     DijkstraShortestPath<Node, Edge> mtp; // Max Throughput Path
  60     private Set<IListenRoutingUpdates> routingAware;
  61     private ISwitchManager switchManager;
  62     private ITopologyManager topologyManager;
  63     private IReadService readService;
  64     private static final long DEFAULT_LINK_SPEED = Bandwidth.BW1Gbps;
  65
  66     public void setListenRoutingUpdates(IListenRoutingUpdates i) {
  67         if (this.routingAware == null) {
  68             this.routingAware = new HashSet<IListenRoutingUpdates>();
  69         }
  70         if (this.routingAware != null) {
  71             log.debug("Adding routingAware listener: {}", i);
  72             this.routingAware.add(i);
  73         }
  74     }
  75
  76     public void unsetListenRoutingUpdates(IListenRoutingUpdates i) {
  77         if (this.routingAware == null) {
  78             return;
  79         }
  80         log.debug("Removing routingAware listener");
  81         this.routingAware.remove(i);
  82         if (this.routingAware.isEmpty()) {
  83             // We don't have any listener lets dereference
  84             this.routingAware = null;
  85         }
  86     }
  87
  88     @Override
  89     public synchronized void initMaxThroughput(
  90             final Map<Edge, Number> EdgeWeightMap) {
  91         if (mtp != null) {
  92             log.error("Max Throughput Dijkstra is already enabled!");
  93             return;
  94         }
  95         Transformer<Edge, ? extends Number> mtTransformer = null;
  96         if (EdgeWeightMap == null) {
  97             mtTransformer = new Transformer<Edge, Double>() {
  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
 110                             .getNodeConnectorProp(srcNC,
 111                                     Bandwidth.BandwidthPropName);
 112                     Bandwidth bwDst = (Bandwidth) switchManager
 113                             .getNodeConnectorProp(dstNC,
 114                                     Bandwidth.BandwidthPropName);
 115
 116                     long srcLinkSpeed = 0, dstLinkSpeed = 0;
 117                     if ((bwSrc == null)
 118                             || ((srcLinkSpeed = bwSrc.getValue()) == 0)) {
 119                         log.debug(
 120                                 "srcNC: {} - Setting srcLinkSpeed to Default!",
 121                                 srcNC);
 122                         srcLinkSpeed = DEFAULT_LINK_SPEED;
 123                     }
 124
 125                     if ((bwDst == null)
 126                             || ((dstLinkSpeed = bwDst.getValue()) == 0)) {
 127                         log.debug(
 128                                 "dstNC: {} - Setting dstLinkSpeed to Default!",
 129                                 dstNC);
 130                         dstLinkSpeed = DEFAULT_LINK_SPEED;
 131                     }
 132
 133                     long avlSrcThruPut = srcLinkSpeed
 134                             - readService.getTransmitRate(srcNC);
 135                     long avlDstThruPut = dstLinkSpeed
 136                             - readService.getTransmitRate(dstNC);
 137
 138                     // Use lower of the 2 available thruput as the available
 139                     // thruput
 140                     long avlThruPut = avlSrcThruPut < avlDstThruPut ? avlSrcThruPut
 141                             : avlDstThruPut;
 142
 143                     if (avlThruPut <= 0) {
 144                         log.debug("Edge {}: Available Throughput {} <= 0!", e,
 145                                 avlThruPut);
 146                         return (double) -1;
 147                     }
 148                     return (double) (Bandwidth.BW1Pbps / avlThruPut);
 149                 }
 150             };
 151         } else {
 152             mtTransformer = new Transformer<Edge, Number>() {
 153                 public Number transform(Edge e) {
 154                     return EdgeWeightMap.get(e);
 155                 }
 156             };
 157         }
 158         Short baseBW = Short.valueOf((short) 0);
 159         // Initialize mtp also using the default topo
 160         Graph<Node, Edge> g = this.topologyBWAware.get(baseBW);
 161         if (g == null) {
 162             log.error("Default Topology Graph is null");
 163             return;
 164         }
 165         mtp = new DijkstraShortestPath<Node, Edge>(g, mtTransformer);
 166     }
 167
 168     @Override
 169     public Path getRoute(Node src, Node dst) {
 170         if (src == null || dst == null) {
 171             return null;
 172         }
 173         return getRoute(src, dst, (short) 0);
 174     }
 175
 176     @Override
 177     public synchronized Path getMaxThroughputRoute(Node src, Node dst) {
 178         if (mtp == null) {
 179             log.error("Max Throughput Path Calculation Uninitialized!");
 180             return null;
 181         }
 182
 183         List<Edge> path;
 184         try {
 185             path = mtp.getMaxThroughputPath(src, dst);
 186         } catch (IllegalArgumentException ie) {
 187             log.debug("A vertex is yet not known between {} {}", src, dst);
 188             return null;
 189         }
 190         Path res;
 191         try {
 192             res = new Path(path);
 193         } catch (ConstructionException e) {
 194             log.debug("A vertex is yet not known between {} {}", src, dst);
 195             return null;
 196         }
 197         return res;
 198     }
 199
 200     @Override
 201     public synchronized Path getRoute(Node src, Node dst, Short Bw) {
 202         DijkstraShortestPath<Node, Edge> spt = this.sptBWAware.get(Bw);
 203         if (spt == null)
 204             return null;
 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({ "rawtypes", "unchecked" })
 242     private synchronized boolean updateTopo(Edge edge, Short bw, boolean added) {
 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             if (added) {
 266                 // Make sure the vertex are there before adding the edge
 267                 topo.addVertex(src.getNode());
 268                 topo.addVertex(dst.getNode());
 269                 // Add the link between
 270                 edgePresentInGraph = topo.containsEdge(edge);
 271                 if (edgePresentInGraph == false) {
 272                     try {
 273                         topo.addEdge(new Edge(src, dst), src.getNode(),
 274                                 dst.getNode(), EdgeType.DIRECTED);
 275                     } catch (ConstructionException e) {
 276                         log.error("", e);
 277                         return edgePresentInGraph;
 278                     }
 279                 }
 280             } else {
 281                 // Remove the edge
 282                 try {
 283                     topo.removeEdge(new Edge(src, dst));
 284                 } catch (ConstructionException e) {
 285                     log.error("", e);
 286                     return edgePresentInGraph;
 287                 }
 288
 289                 // If the src and dst vertex don't have incoming or
 290                 // outgoing links we can get ride of them
 291                 if (topo.containsVertex(src.getNode())
 292                         && topo.inDegree(src.getNode()) == 0
 293                         && topo.outDegree(src.getNode()) == 0) {
 294                     log.debug("Removing vertex {}", src);
 295                     topo.removeVertex(src.getNode());
 296                 }
 297
 298                 if (topo.containsVertex(dst.getNode())
 299                         && topo.inDegree(dst.getNode()) == 0
 300                         && topo.outDegree(dst.getNode()) == 0) {
 301                     log.debug("Removing vertex {}", dst);
 302                     topo.removeVertex(dst.getNode());
 303                 }
 304             }
 305             spt.reset();
 306             if (bw.equals(baseBW)) {
 307                 clearMaxThroughput();
 308             }
 309         } else {
 310             log.error("Cannot find topology for BW {} this is unexpected!", bw);
 311         }
 312         return edgePresentInGraph;
 313     }
 314
 315     private boolean edgeUpdate(Edge e, UpdateType type, Set<Property> props) {
 316         String srcType = null;
 317         String dstType = null;
 318
 319         if (e == null || type == null) {
 320             log.error("Edge or Update type are null!");
 321             return false;
 322         } else {
 323             srcType = e.getTailNodeConnector().getType();
 324             dstType = e.getHeadNodeConnector().getType();
 325
 326             if (srcType.equals(NodeConnector.NodeConnectorIDType.PRODUCTION)) {
 327                 log.debug("Skip updates for {}", e);
 328                 return false;
 329             }
 330
 331             if (dstType.equals(NodeConnector.NodeConnectorIDType.PRODUCTION)) {
 332                 log.debug("Skip updates for {}", e);
 333                 return false;
 334             }
 335         }
 336
 337         Bandwidth bw = new Bandwidth(0);
 338         boolean newEdge = false;
 339         if (props != null)
 340             props.remove(bw);
 341
 342         if (log.isDebugEnabled()) {
 343           log.debug("edgeUpdate: {} bw: {}", e, bw.getValue());
 344         }
 345
 346         Short baseBW = Short.valueOf((short) 0);
 347         boolean add = (type == UpdateType.ADDED) ? true : false;
 348         // Update base topo
 349         newEdge = !updateTopo(e, baseBW, add);
 350         if (newEdge == true) {
 351             if (bw.getValue() != baseBW) {
 352                 // Update BW topo
 353                 updateTopo(e, (short) bw.getValue(), add);
 354             }
 355         }
 356         return newEdge;
 357     }
 358
 359     @Override
 360     public void edgeUpdate(List<TopoEdgeUpdate> topoedgeupdateList) {
 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).getProperty();
 365             UpdateType type = topoedgeupdateList.get(i).getUpdateType();
 366             if ((edgeUpdate(e, type, p)) && (!callListeners)) {
 367                 callListeners = true;
 368             }
 369         }
 370         if ((callListeners) && (this.routingAware != null)) {
 371             for (IListenRoutingUpdates ra : this.routingAware) {
 372                 try {
 373                     ra.recalculateDone();
 374                 } catch (Exception ex) {
 375                     log.error("Exception on routingAware listener call", ex);
 376                 }
 377             }
 378         }
 379     }
 380
 381     /**
 382      * Function called by the dependency manager when all the required
 383      * dependencies are satisfied
 384      *
 385      */
 386     @SuppressWarnings({ "unchecked", "rawtypes" })
 387     public void init() {
 388         log.debug("Routing init() is called");
 389         this.topologyBWAware = (ConcurrentMap<Short, Graph<Node, Edge>>) new ConcurrentHashMap();
 390         this.sptBWAware = (ConcurrentMap<Short, DijkstraShortestPath<Node, Edge>>) new ConcurrentHashMap();
 391         // Now create the default topology, which doesn't consider the
 392         // BW, also create the corresponding Dijkstra calculation
 393         Graph<Node, Edge> g = new SparseMultigraph();
 394         Short sZero = Short.valueOf((short) 0);
 395         this.topologyBWAware.put(sZero, g);
 396         this.sptBWAware.put(sZero, new DijkstraShortestPath(g));
 397         // Topologies for other BW will be added on a needed base
 398     }
 399
 400     /**
 401      * Function called by the dependency manager when at least one dependency
 402      * become unsatisfied or when the component is shutting down because for
 403      * example bundle is being stopped.
 404      *
 405      */
 406     void destroy() {
 407         log.debug("Routing destroy() is called");
 408     }
 409
 410     /**
 411      * Function called by dependency manager after "init ()" is called and after
 412      * the services provided by the class are registered in the service registry
 413      *
 414      */
 415     void start() {
 416         log.debug("Routing start() is called");
 417         // build the routing database from the topology if it exists.
 418         Map<Edge, Set<Property>> edges = topologyManager.getEdges();
 419         if (edges.isEmpty()) {
 420             return;
 421         }
 422         List<TopoEdgeUpdate> topoedgeupdateList = new ArrayList<TopoEdgeUpdate>();
 423         log.debug("Creating routing database from the topology");
 424         for (Iterator<Map.Entry<Edge, Set<Property>>> i = edges.entrySet()
 425                 .iterator(); i.hasNext();) {
 426             Map.Entry<Edge, Set<Property>> entry = i.next();
 427             Edge e = entry.getKey();
 428             Set<Property> props = entry.getValue();
 429             TopoEdgeUpdate topoedgeupdate = new TopoEdgeUpdate(e, props,
 430                     UpdateType.ADDED);
 431             topoedgeupdateList.add(topoedgeupdate);
 432         }
 433         edgeUpdate(topoedgeupdateList);
 434     }
 435
 436     /**
 437      * Function called by the dependency manager before the services exported by
 438      * the component are unregistered, this will be followed by a "destroy ()"
 439      * calls
 440      *
 441      */
 442     public void stop() {
 443         log.debug("Routing stop() is called");
 444     }
 445
 446     @Override
 447     public void edgeOverUtilized(Edge edge) {
 448         // TODO Auto-generated method stub
 449
 450     }
 451
 452     @Override
 453     public void edgeUtilBackToNormal(Edge edge) {
 454         // TODO Auto-generated method stub
 455
 456     }
 457
 458     public void setSwitchManager(ISwitchManager switchManager) {
 459         this.switchManager = switchManager;
 460     }
 461
 462     public void unsetSwitchManager(ISwitchManager switchManager) {
 463         if (this.switchManager == switchManager) {
 464             this.switchManager = null;
 465         }
 466     }
 467
 468     public void setReadService(IReadService readService) {
 469         this.readService = readService;
 470     }
 471
 472     public void unsetReadService(IReadService readService) {
 473         if (this.readService == readService) {
 474             this.readService = null;
 475         }
 476     }
 477
 478     public void setTopologyManager(ITopologyManager tm) {
 479         this.topologyManager = tm;
 480     }
 481
 482     public void unsetTopologyManager(ITopologyManager tm) {
 483         if (this.topologyManager == tm) {
 484             this.topologyManager = null;
 485         }
 486     }
 487 }