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 {} {}",
 188                     src.toString(), dst.toString());
 189             return null;
 190         }
 191         Path res;
 192         try {
 193             res = new Path(path);
 194         } catch (ConstructionException e) {
 195             log.debug("A vertex is yet not known between {} {}",
 196                     src.toString(), dst.toString());
 197             return null;
 198         }
 199         return res;
 200     }
 201
 202     @Override
 203     public synchronized Path getRoute(Node src, Node dst, Short Bw) {
 204         DijkstraShortestPath<Node, Edge> spt = this.sptBWAware.get(Bw);
 205         if (spt == null)
 206             return null;
 207         List<Edge> path;
 208         try {
 209             path = spt.getPath(src, dst);
 210         } catch (IllegalArgumentException ie) {
 211             log.debug("A vertex is yet not known between {} {}",
 212                     src.toString(), dst.toString());
 213             return null;
 214         }
 215         Path res;
 216         try {
 217             res = new Path(path);
 218         } catch (ConstructionException e) {
 219             log.debug("A vertex is yet not known between {} {}",
 220                     src.toString(), dst.toString());
 221             return null;
 222         }
 223         return res;
 224     }
 225
 226     @Override
 227     public synchronized void clear() {
 228         DijkstraShortestPath<Node, Edge> spt;
 229         for (Short bw : this.sptBWAware.keySet()) {
 230             spt = this.sptBWAware.get(bw);
 231             if (spt != null) {
 232                 spt.reset();
 233             }
 234         }
 235         clearMaxThroughput();
 236     }
 237
 238     @Override
 239     public synchronized void clearMaxThroughput() {
 240         if (mtp != null) {
 241             mtp.reset(); // reset maxthruput path
 242         }
 243     }
 244
 245     @SuppressWarnings({ "rawtypes", "unchecked" })
 246     private synchronized boolean updateTopo(Edge edge, Short bw, boolean added) {
 247         Graph<Node, Edge> topo = this.topologyBWAware.get(bw);
 248         DijkstraShortestPath<Node, Edge> spt = this.sptBWAware.get(bw);
 249         boolean edgePresentInGraph = false;
 250         Short baseBW = Short.valueOf((short) 0);
 251
 252         if (topo == null) {
 253             // Create topology for this BW
 254             Graph<Node, Edge> g = new SparseMultigraph();
 255             this.topologyBWAware.put(bw, g);
 256             topo = this.topologyBWAware.get(bw);
 257             this.sptBWAware.put(bw, new DijkstraShortestPath(g));
 258             spt = this.sptBWAware.get(bw);
 259         }
 260
 261         if (topo != null) {
 262             NodeConnector src = edge.getTailNodeConnector();
 263             NodeConnector dst = edge.getHeadNodeConnector();
 264             if (spt == null) {
 265                 spt = new DijkstraShortestPath(topo);
 266                 this.sptBWAware.put(bw, spt);
 267             }
 268
 269             if (added) {
 270                 // Make sure the vertex are there before adding the edge
 271                 topo.addVertex(src.getNode());
 272                 topo.addVertex(dst.getNode());
 273                 // Add the link between
 274                 edgePresentInGraph = topo.containsEdge(edge);
 275                 if (edgePresentInGraph == false) {
 276                     try {
 277                         topo.addEdge(new Edge(src, dst), src.getNode(),
 278                                 dst.getNode(), EdgeType.DIRECTED);
 279                     } catch (ConstructionException e) {
 280                         log.error("", e);
 281                         return edgePresentInGraph;
 282                     }
 283                 }
 284             } else {
 285                 // Remove the edge
 286                 try {
 287                     topo.removeEdge(new Edge(src, dst));
 288                 } catch (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())
 296                         && topo.inDegree(src.getNode()) == 0
 297                         && topo.outDegree(src.getNode()) == 0) {
 298                     log.debug("Removing vertex {}", src);
 299                     topo.removeVertex(src.getNode());
 300                 }
 301
 302                 if (topo.containsVertex(dst.getNode())
 303                         && topo.inDegree(dst.getNode()) == 0
 304                         && topo.outDegree(dst.getNode()) == 0) {
 305                     log.debug("Removing vertex {}", dst);
 306                     topo.removeVertex(dst.getNode());
 307                 }
 308             }
 309             spt.reset();
 310             if (bw.equals(baseBW)) {
 311                 clearMaxThroughput();
 312             }
 313         } else {
 314             log.error("Cannot find topology for BW {} this is unexpected!", bw);
 315         }
 316         return edgePresentInGraph;
 317     }
 318
 319     private boolean edgeUpdate(Edge e, UpdateType type, Set<Property> props) {
 320         String srcType = null;
 321         String dstType = null;
 322
 323         if (e == null || type == null) {
 324             log.error("Edge or Update type are null!");
 325             return false;
 326         } else {
 327             srcType = e.getTailNodeConnector().getType();
 328             dstType = e.getHeadNodeConnector().getType();
 329
 330             if (srcType.equals(NodeConnector.NodeConnectorIDType.PRODUCTION)) {
 331                 log.debug("Skip updates for {}", e);
 332                 return false;
 333             }
 334
 335             if (dstType.equals(NodeConnector.NodeConnectorIDType.PRODUCTION)) {
 336                 log.debug("Skip updates for {}", e);
 337                 return false;
 338             }
 339         }
 340
 341         Bandwidth bw = new Bandwidth(0);
 342         boolean newEdge = false;
 343         if (props != null)
 344             props.remove(bw);
 345
 346         log.debug("edgeUpdate: {} bw: {}", e.toString(), bw.getValue());
 347
 348         Short baseBW = Short.valueOf((short) 0);
 349         boolean add = (type == UpdateType.ADDED) ? true : false;
 350         // Update base topo
 351         newEdge = !updateTopo(e, baseBW, add);
 352         if (newEdge == true) {
 353             if (bw.getValue() != baseBW) {
 354                 // Update BW topo
 355                 updateTopo(e, (short) bw.getValue(), add);
 356             }
 357         }
 358         return newEdge;
 359     }
 360
 361     @Override
 362     public void edgeUpdate(List<TopoEdgeUpdate> topoedgeupdateList) {
 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).getProperty();
 367             UpdateType type = topoedgeupdateList.get(i).getUpdateType();
 368             if ((edgeUpdate(e, type, p)) && (!callListeners)) {
 369                 callListeners = true;
 370             }
 371         }
 372         if ((callListeners) && (this.routingAware != null)) {
 373             for (IListenRoutingUpdates ra : this.routingAware) {
 374                 try {
 375                     ra.recalculateDone();
 376                 } catch (Exception ex) {
 377                     log.error("Exception on routingAware listener call", ex);
 378                 }
 379             }
 380         }
 381     }
 382
 383     /**
 384      * Function called by the dependency manager when all the required
 385      * dependencies are satisfied
 386      *
 387      */
 388     @SuppressWarnings({ "unchecked", "rawtypes" })
 389     public void init() {
 390         log.debug("Routing init() is called");
 391         this.topologyBWAware = (ConcurrentMap<Short, Graph<Node, Edge>>) new ConcurrentHashMap();
 392         this.sptBWAware = (ConcurrentMap<Short, DijkstraShortestPath<Node, Edge>>) new ConcurrentHashMap();
 393         // Now create the default topology, which doesn't consider the
 394         // BW, also create the corresponding Dijkstra calculation
 395         Graph<Node, Edge> g = new SparseMultigraph();
 396         Short sZero = Short.valueOf((short) 0);
 397         this.topologyBWAware.put(sZero, g);
 398         this.sptBWAware.put(sZero, new DijkstraShortestPath(g));
 399         // Topologies for other BW will be added on a needed base
 400     }
 401
 402     /**
 403      * Function called by the dependency manager when at least one dependency
 404      * become unsatisfied or when the component is shutting down because for
 405      * example bundle is being stopped.
 406      *
 407      */
 408     void destroy() {
 409         log.debug("Routing destroy() is called");
 410     }
 411
 412     /**
 413      * Function called by dependency manager after "init ()" is called and after
 414      * the services provided by the class are registered in the service registry
 415      *
 416      */
 417     void start() {
 418         log.debug("Routing start() is called");
 419         // build the routing database from the topology if it exists.
 420         Map<Edge, Set<Property>> edges = topologyManager.getEdges();
 421         if (edges.isEmpty()) {
 422             return;
 423         }
 424         List<TopoEdgeUpdate> topoedgeupdateList = new ArrayList<TopoEdgeUpdate>();
 425         log.debug("Creating routing database from the topology");
 426         for (Iterator<Map.Entry<Edge, Set<Property>>> i = edges.entrySet()
 427                 .iterator(); i.hasNext();) {
 428             Map.Entry<Edge, Set<Property>> entry = i.next();
 429             Edge e = entry.getKey();
 430             Set<Property> props = entry.getValue();
 431             TopoEdgeUpdate topoedgeupdate = new TopoEdgeUpdate(e, props,
 432                     UpdateType.ADDED);
 433             topoedgeupdateList.add(topoedgeupdate);
 434         }
 435         edgeUpdate(topoedgeupdateList);
 436     }
 437
 438     /**
 439      * Function called by the dependency manager before the services exported by
 440      * the component are unregistered, this will be followed by a "destroy ()"
 441      * calls
 442      *
 443      */
 444     public void stop() {
 445         log.debug("Routing stop() is called");
 446     }
 447
 448     @Override
 449     public void edgeOverUtilized(Edge edge) {
 450         // TODO Auto-generated method stub
 451
 452     }
 453
 454     @Override
 455     public void edgeUtilBackToNormal(Edge edge) {
 456         // TODO Auto-generated method stub
 457
 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 setReadService(IReadService readService) {
 471         this.readService = readService;
 472     }
 473
 474     public void unsetReadService(IReadService readService) {
 475         if (this.readService == readService) {
 476             this.readService = null;
 477         }
 478     }
 479
 480     public void setTopologyManager(ITopologyManager tm) {
 481         this.topologyManager = tm;
 482     }
 483
 484     public void unsetTopologyManager(ITopologyManager tm) {
 485         if (this.topologyManager == tm) {
 486             this.topologyManager = null;
 487         }
 488     }
 489 }