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

   1
   2 /*
   3  * Copyright (c) 2013 Cisco Systems, Inc. and others.  All rights reserved.
   4  *
   5  * This program and the accompanying materials are made available under the
   6  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   7  * and is available at http://www.eclipse.org/legal/epl-v10.html
   8  */
   9
  10 /**
  11  * @file   DijkstraImplementation.java
  12  *
  13  *
  14  * @brief  Implementation of a routing engine using
  15  * dijkstra. Implementation of dijkstra come from Jung2 library
  16  *
  17  */
  18 package org.opendaylight.controller.routing.dijkstra_implementation.internal;
  19
  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.reader.IReadService;
  29 import org.opendaylight.controller.sal.routing.IListenRoutingUpdates;
  30 import org.opendaylight.controller.sal.routing.IRouting;
  31 import org.opendaylight.controller.switchmanager.ISwitchManager;
  32 import org.opendaylight.controller.topologymanager.ITopologyManager;
  33 import org.opendaylight.controller.topologymanager.ITopologyManagerAware;
  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 import java.lang.Exception;
  40 import java.lang.IllegalArgumentException;
  41 import java.util.HashSet;
  42 import java.util.Iterator;
  43 import java.util.List;
  44 import java.util.Set;
  45 import java.util.Map;
  46 import java.util.concurrent.ConcurrentHashMap;
  47 import java.util.concurrent.ConcurrentMap;
  48 import org.slf4j.Logger;
  49 import org.slf4j.LoggerFactory;
  50 import org.apache.commons.collections15.Transformer;
  51
  52 public class DijkstraImplementation implements IRouting, ITopologyManagerAware {
  53     private static Logger log = LoggerFactory
  54             .getLogger(DijkstraImplementation.class);
  55     private ConcurrentMap<Short, Graph<Node, Edge>> topologyBWAware;
  56     private ConcurrentMap<Short, DijkstraShortestPath<Node, Edge>> sptBWAware;
  57     DijkstraShortestPath<Node, Edge> mtp; //Max Throughput Path
  58     private Set<IListenRoutingUpdates> routingAware;
  59     private ISwitchManager switchManager;
  60     private ITopologyManager topologyManager;
  61     private IReadService readService;
  62     private static final long DEFAULT_LINK_SPEED = Bandwidth.BW1Gbps;
  63
  64     public void setLIstenRoutingUpdates(IListenRoutingUpdates i) {
  65         if (this.routingAware == null) {
  66             this.routingAware = new HashSet<IListenRoutingUpdates>();
  67         }
  68         if (this.routingAware != null) {
  69             log.debug("Adding routingAware listener: " + i);
  70             this.routingAware.add(i);
  71         }
  72     }
  73
  74     public void unsetRoutingUpdates(IListenRoutingUpdates i) {
  75         if (this.routingAware == null) {
  76             return;
  77         }
  78         log.debug("Removing routingAware listener");
  79         this.routingAware.remove(i);
  80         if (this.routingAware.isEmpty()) {
  81             // We don't have any listener lets dereference
  82             this.routingAware = null;
  83         }
  84     }
  85
  86     @Override
  87     public synchronized void initMaxThroughput(
  88             final Map<Edge, Number> EdgeWeightMap) {
  89         if (mtp != null) {
  90             log.error("Max Throughput Dijkstra is already enabled!");
  91             return;
  92         }
  93         Transformer<Edge, ? extends Number> mtTransformer = null;
  94         if (EdgeWeightMap == null) {
  95             mtTransformer = new Transformer<Edge, Double>() {
  96                 public Double transform(Edge e) {
  97                     if (switchManager == null) {
  98                         log.error("switchManager is null");
  99                         return (double) -1;
 100                     }
 101                     NodeConnector srcNC = e.getTailNodeConnector();
 102                     NodeConnector dstNC = e.getHeadNodeConnector();
 103                     if ((srcNC == null) || (dstNC == null)) {
 104                         log.error("srcNC:{} or dstNC:{} is null", srcNC, dstNC);
 105                         return (double) -1;
 106                     }
 107                     Bandwidth bwSrc = (Bandwidth) switchManager
 108                             .getNodeConnectorProp(srcNC,
 109                                     Bandwidth.BandwidthPropName);
 110                     Bandwidth bwDst = (Bandwidth) switchManager
 111                             .getNodeConnectorProp(dstNC,
 112                                     Bandwidth.BandwidthPropName);
 113
 114                     if ((bwSrc == null) || (bwDst == null)) {
 115                         log.error("bwSrc:{} or bwDst:{} is null", bwSrc, bwDst);
 116                         return (double) -1;
 117                     }
 118
 119                     long srcLinkSpeed = bwSrc.getValue();
 120                     if (srcLinkSpeed == 0) {
 121                         log.trace("Edge {}: srcLinkSpeed is 0. Setting to {}!",
 122                                 e, DEFAULT_LINK_SPEED);
 123                         srcLinkSpeed = DEFAULT_LINK_SPEED;
 124                     }
 125
 126                     long dstLinkSpeed = bwDst.getValue();
 127                     if (dstLinkSpeed == 0) {
 128                         log.trace("Edge {}: dstLinkSpeed is 0. Setting to {}!",
 129                                 e, DEFAULT_LINK_SPEED);
 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 thruput
 139                     long avlThruPut = avlSrcThruPut < avlDstThruPut ? avlSrcThruPut
 140                             : avlDstThruPut;
 141
 142                     if (avlThruPut <= 0) {
 143                         log
 144                                 .trace(
 145                                         "Edge {}: Available Throughput {} is Zero/Negative",
 146                                         e, avlThruPut);
 147                         return (double) -1;
 148                     }
 149                     return (double) (Bandwidth.BW1Pbps / avlThruPut);
 150                 }
 151             };
 152         } else {
 153             mtTransformer = new Transformer<Edge, Number>() {
 154                 public Number transform(Edge e) {
 155                     return EdgeWeightMap.get(e);
 156                 }
 157             };
 158         }
 159         Short baseBW = Short.valueOf((short) 0);
 160         //Initialize mtp also using the default topo
 161         Graph<Node, Edge> g = this.topologyBWAware.get(baseBW);
 162         if (g == null) {
 163             log.error("Default Topology Graph is null");
 164             return;
 165         }
 166         mtp = new DijkstraShortestPath<Node, Edge>(g, mtTransformer);
 167     }
 168
 169     @Override
 170     public Path getRoute(Node src, Node dst) {
 171         if (src == null || dst == null) {
 172             return null;
 173         }
 174         return getRoute(src, dst, (short) 0);
 175     }
 176
 177     @Override
 178     public synchronized Path getMaxThroughputRoute(Node src, Node dst) {
 179         if (mtp == null) {
 180             log
 181                     .error("Max Throughput Path Calculation has not been Initialized!");
 182             return null;
 183         }
 184
 185         List<Edge> path;
 186         try {
 187             path = mtp.getMaxThroughputPath(src, dst);
 188         } catch (IllegalArgumentException ie) {
 189             log.debug("A vertex is yet not known between " + src.toString()
 190                     + " " + dst.toString());
 191             return null;
 192         }
 193         Path res;
 194         try {
 195             res = new Path(path);
 196         } catch (ConstructionException e) {
 197             log.debug("A vertex is yet not known between " + src.toString()
 198                     + " " + dst.toString());
 199             return null;
 200         }
 201         return res;
 202     }
 203
 204     @Override
 205     public synchronized Path getRoute(Node src, Node dst, Short Bw) {
 206         DijkstraShortestPath<Node, Edge> spt = this.sptBWAware.get(Bw);
 207         if (spt == null)
 208             return null;
 209         List<Edge> path;
 210         try {
 211             path = spt.getPath(src, dst);
 212         } catch (IllegalArgumentException ie) {
 213             log.debug("A vertex is yet not known between " + src.toString()
 214                     + " " + dst.toString());
 215             return null;
 216         }
 217         Path res;
 218         try {
 219             res = new Path(path);
 220         } catch (ConstructionException e) {
 221             log.debug("A vertex is yet not known between " + src.toString()
 222                     + " " + dst.toString());
 223             return null;
 224         }
 225         return res;
 226     }
 227
 228     @Override
 229     public synchronized void clear() {
 230         DijkstraShortestPath<Node, Edge> spt;
 231         for (Short bw : this.sptBWAware.keySet()) {
 232             spt = this.sptBWAware.get(bw);
 233             if (spt != null) {
 234                 spt.reset();
 235             }
 236         }
 237         clearMaxThroughput();
 238     }
 239
 240     @Override
 241     public synchronized void clearMaxThroughput() {
 242         if (mtp != null) {
 243             mtp.reset(); //reset maxthruput path
 244         }
 245     }
 246
 247     @SuppressWarnings( { "rawtypes", "unchecked" })
 248     private synchronized boolean updateTopo(Edge edge, Short bw, boolean added) {
 249         Graph<Node, Edge> topo = this.topologyBWAware.get(bw);
 250         DijkstraShortestPath<Node, Edge> spt = this.sptBWAware.get(bw);
 251         boolean edgePresentInGraph = false;
 252         Short baseBW = Short.valueOf((short) 0);
 253
 254         if (topo == null) {
 255             // Create topology for this BW
 256             Graph<Node, Edge> g = new SparseMultigraph();
 257             this.topologyBWAware.put(bw, g);
 258             topo = this.topologyBWAware.get(bw);
 259             this.sptBWAware.put(bw, new DijkstraShortestPath(g));
 260             spt = this.sptBWAware.get(bw);
 261         }
 262
 263         if (topo != null) {
 264             NodeConnector src = edge.getTailNodeConnector();
 265             NodeConnector dst = edge.getHeadNodeConnector();
 266             if (spt == null) {
 267                 spt = new DijkstraShortestPath(topo);
 268                 this.sptBWAware.put(bw, spt);
 269             }
 270
 271             if (added) {
 272                 // Make sure the vertex are there before adding the edge
 273                 topo.addVertex(src.getNode());
 274                 topo.addVertex(dst.getNode());
 275                 // Add the link between
 276                 edgePresentInGraph = topo.containsEdge(edge);
 277                 if (edgePresentInGraph == false) {
 278                     try {
 279                         topo.addEdge(new Edge(src, dst), src
 280                                 .getNode(), dst
 281                                 .getNode(), EdgeType.DIRECTED);
 282                     } catch (ConstructionException e) {
 283                         e.printStackTrace();
 284                         return edgePresentInGraph;
 285                     }
 286                 }
 287             } else {
 288                 //Remove the edge
 289                 try {
 290                     topo.removeEdge(new Edge(src, dst));
 291                 } catch (ConstructionException e) {
 292                     e.printStackTrace();
 293                     return edgePresentInGraph;
 294                 }
 295
 296                 // If the src and dst vertex don't have incoming or
 297                 // outgoing links we can get ride of them
 298                 if (topo.containsVertex(src.getNode())
 299                         && topo.inDegree(src.getNode()) == 0
 300                         && topo.outDegree(src.getNode()) == 0) {
 301                     log.debug("Removing vertex " + src);
 302                     topo.removeVertex(src.getNode());
 303                 }
 304
 305                 if (topo.containsVertex(dst.getNode())
 306                         && topo.inDegree(dst.getNode()) == 0
 307                         && topo.outDegree(dst.getNode()) == 0) {
 308                     log.debug("Removing vertex " + dst);
 309                     topo.removeVertex(dst.getNode());
 310                 }
 311             }
 312             spt.reset();
 313             if (bw.equals(baseBW)) {
 314                 clearMaxThroughput();
 315             }
 316         } else {
 317             log.error("Cannot find topology for BW " + bw
 318                     + " this is unexpected!");
 319         }
 320         return edgePresentInGraph;
 321     }
 322
 323     @Override
 324     public void edgeUpdate(Edge e, UpdateType type, Set<Property> props) {
 325         String srcType = null;
 326         String dstType = null;
 327
 328         if (e == null || type == null) {
 329             log.error("Edge or Update type are null!");
 330             return;
 331         } else {
 332             srcType = e.getTailNodeConnector().getType();
 333             dstType = e.getHeadNodeConnector().getType();
 334
 335             if (srcType.equals(NodeConnector.NodeConnectorIDType.PRODUCTION)) {
 336                 log.debug("Skip updates for {}", e);
 337                 return;
 338             }
 339
 340             if (dstType.equals(NodeConnector.NodeConnectorIDType.PRODUCTION)) {
 341                 log.debug("Skip updates for {}", e);
 342                 return;
 343             }
 344         }
 345
 346         Bandwidth bw = new Bandwidth(0);
 347         boolean newEdge = false;
 348         if (props != null)
 349             props.remove(bw);
 350
 351         log.debug("edgeUpdate: " + e.toString() + " bw: " + bw.getValue());
 352
 353         Short baseBW = Short.valueOf((short) 0);
 354         boolean add = (type == UpdateType.ADDED) ? true : false;
 355         // Update base topo
 356         newEdge = !updateTopo(e, baseBW, add);
 357         if (newEdge == true) {
 358             if (bw.getValue() != baseBW) {
 359                 // Update BW topo
 360                 updateTopo(e, (short) bw.getValue(), add);
 361             }
 362             if (this.routingAware != null) {
 363                 for (IListenRoutingUpdates ra : this.routingAware) {
 364                     try {
 365                         ra.recalculateDone();
 366                     } catch (Exception ex) {
 367                         log.error("Exception on routingAware listener call", e);
 368                     }
 369                 }
 370             }
 371         }
 372     }
 373
 374     /**
 375      * Function called by the dependency manager when all the required
 376      * dependencies are satisfied
 377      *
 378      */
 379     @SuppressWarnings({ "unchecked", "rawtypes" })
 380     public void init() {
 381         log.debug("Routing init() is called");
 382         this.topologyBWAware = (ConcurrentMap<Short, Graph<Node, Edge>>) new ConcurrentHashMap();
 383         this.sptBWAware = (ConcurrentMap<Short, DijkstraShortestPath<Node, Edge>>) new ConcurrentHashMap();
 384         // Now create the default topology, which doesn't consider the
 385         // BW, also create the corresponding Dijkstra calculation
 386         Graph<Node, Edge> g = new SparseMultigraph();
 387         Short sZero = Short.valueOf((short) 0);
 388         this.topologyBWAware.put(sZero, g);
 389         this.sptBWAware.put(sZero, new DijkstraShortestPath(g));
 390         // Topologies for other BW will be added on a needed base
 391     }
 392     /**
 393      * Function called by the dependency manager when at least one dependency
 394      * become unsatisfied or when the component is shutting down because for
 395      * example bundle is being stopped.
 396      *
 397      */
 398     void destroy() {
 399         log.debug("Routing destroy() is called");
 400     }
 401
 402     /**
 403      * Function called by dependency manager after "init ()" is called
 404      * and after the services provided by the class are registered in
 405      * the service registry
 406      *
 407      */
 408    void start() {
 409            log.debug("Routing start() is called");
 410            // build the routing database from the topology if it exists.
 411            Map<Edge, Set<Property>> edges = topologyManager.getEdges();
 412            if (edges.isEmpty()) {
 413                    return;
 414            }
 415            log.debug("Creating routing database from the topology");
 416            for (Iterator<Map.Entry<Edge,Set<Property>>> i = edges.entrySet().iterator();  i.hasNext();) {
 417                    Map.Entry<Edge, Set<Property>> entry = i.next();
 418                    Edge e = entry.getKey();
 419                    Set<Property> props = entry.getValue();
 420                    edgeUpdate(e, UpdateType.ADDED, props);
 421            }
 422    }
 423
 424     /**
 425      * Function called by the dependency manager before the services exported by
 426      * the component are unregistered, this will be followed by a "destroy ()"
 427      * calls
 428      *
 429      */
 430    public void stop() {
 431            log.debug("Routing stop() is called");
 432    }
 433
 434     @Override
 435     public void edgeOverUtilized(Edge edge) {
 436         // TODO Auto-generated method stub
 437
 438     }
 439
 440     @Override
 441     public void edgeUtilBackToNormal(Edge edge) {
 442         // TODO Auto-generated method stub
 443
 444     }
 445
 446     public void setSwitchManager(ISwitchManager switchManager) {
 447         this.switchManager = switchManager;
 448     }
 449
 450     public void unsetSwitchManager(ISwitchManager switchManager) {
 451         if (this.switchManager == switchManager) {
 452             this.switchManager = null;
 453         }
 454     }
 455
 456     public void setReadService(IReadService readService) {
 457         this.readService = readService;
 458     }
 459
 460     public void unsetReadService(IReadService readService) {
 461         if (this.readService == readService) {
 462             this.readService = null;
 463         }
 464     }
 465
 466     public void setTopologyManager(ITopologyManager tm) {
 467         this.topologyManager = tm;
 468     }
 469
 470     public void unsetTopologyManager(ITopologyManager tm) {
 471         if (this.topologyManager == tm) {
 472                 this.topologyManager = null;
 473         }
 474     }
 475 }