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 unsetListenRoutingUpdates(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                     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                     long avlSrcThruPut = srcLinkSpeed
 126                             - readService.getTransmitRate(srcNC);
 127                     long avlDstThruPut = dstLinkSpeed
 128                             - readService.getTransmitRate(dstNC);
 129
 130                     //Use lower of the 2 available thruput as the available thruput
 131                     long avlThruPut = avlSrcThruPut < avlDstThruPut ? avlSrcThruPut
 132                             : avlDstThruPut;
 133
 134                     if (avlThruPut <= 0) {
 135                         log.debug("Edge {}: Available Throughput {} <= 0!",
 136                                           e, avlThruPut);
 137                         return (double) -1;
 138                     }
 139                     return (double) (Bandwidth.BW1Pbps / avlThruPut);
 140                 }
 141             };
 142         } else {
 143             mtTransformer = new Transformer<Edge, Number>() {
 144                 public Number transform(Edge e) {
 145                     return EdgeWeightMap.get(e);
 146                 }
 147             };
 148         }
 149         Short baseBW = Short.valueOf((short) 0);
 150         //Initialize mtp also using the default topo
 151         Graph<Node, Edge> g = this.topologyBWAware.get(baseBW);
 152         if (g == null) {
 153             log.error("Default Topology Graph is null");
 154             return;
 155         }
 156         mtp = new DijkstraShortestPath<Node, Edge>(g, mtTransformer);
 157     }
 158
 159     @Override
 160     public Path getRoute(Node src, Node dst) {
 161         if (src == null || dst == null) {
 162             return null;
 163         }
 164         return getRoute(src, dst, (short) 0);
 165     }
 166
 167     @Override
 168     public synchronized Path getMaxThroughputRoute(Node src, Node dst) {
 169         if (mtp == null) {
 170             log.error("Max Throughput Path Calculation Uninitialized!");
 171             return null;
 172         }
 173
 174         List<Edge> path;
 175         try {
 176             path = mtp.getMaxThroughputPath(src, dst);
 177         } catch (IllegalArgumentException ie) {
 178             log.debug("A vertex is yet not known between {} {}", src.toString(),
 179                            dst.toString());
 180             return null;
 181         }
 182         Path res;
 183         try {
 184             res = new Path(path);
 185         } catch (ConstructionException e) {
 186             log.debug("A vertex is yet not known between {} {}", src.toString(),
 187                           dst.toString());
 188             return null;
 189         }
 190         return res;
 191     }
 192
 193     @Override
 194     public synchronized Path getRoute(Node src, Node dst, Short Bw) {
 195         DijkstraShortestPath<Node, Edge> spt = this.sptBWAware.get(Bw);
 196         if (spt == null)
 197             return null;
 198         List<Edge> path;
 199         try {
 200             path = spt.getPath(src, dst);
 201         } catch (IllegalArgumentException ie) {
 202                 log.debug("A vertex is yet not known between {} {}", src.toString(),
 203                            dst.toString());
 204             return null;
 205         }
 206         Path res;
 207         try {
 208             res = new Path(path);
 209         } catch (ConstructionException e) {
 210                 log.debug("A vertex is yet not known between {} {}", src.toString(),
 211                            dst.toString());
 212             return null;
 213         }
 214         return res;
 215     }
 216
 217     @Override
 218     public synchronized void clear() {
 219         DijkstraShortestPath<Node, Edge> spt;
 220         for (Short bw : this.sptBWAware.keySet()) {
 221             spt = this.sptBWAware.get(bw);
 222             if (spt != null) {
 223                 spt.reset();
 224             }
 225         }
 226         clearMaxThroughput();
 227     }
 228
 229     @Override
 230     public synchronized void clearMaxThroughput() {
 231         if (mtp != null) {
 232             mtp.reset(); //reset maxthruput path
 233         }
 234     }
 235
 236     @SuppressWarnings( { "rawtypes", "unchecked" })
 237     private synchronized boolean updateTopo(Edge edge, Short bw, boolean added) {
 238         Graph<Node, Edge> topo = this.topologyBWAware.get(bw);
 239         DijkstraShortestPath<Node, Edge> spt = this.sptBWAware.get(bw);
 240         boolean edgePresentInGraph = false;
 241         Short baseBW = Short.valueOf((short) 0);
 242
 243         if (topo == null) {
 244             // Create topology for this BW
 245             Graph<Node, Edge> g = new SparseMultigraph();
 246             this.topologyBWAware.put(bw, g);
 247             topo = this.topologyBWAware.get(bw);
 248             this.sptBWAware.put(bw, new DijkstraShortestPath(g));
 249             spt = this.sptBWAware.get(bw);
 250         }
 251
 252         if (topo != null) {
 253             NodeConnector src = edge.getTailNodeConnector();
 254             NodeConnector dst = edge.getHeadNodeConnector();
 255             if (spt == null) {
 256                 spt = new DijkstraShortestPath(topo);
 257                 this.sptBWAware.put(bw, spt);
 258             }
 259
 260             if (added) {
 261                 // Make sure the vertex are there before adding the edge
 262                 topo.addVertex(src.getNode());
 263                 topo.addVertex(dst.getNode());
 264                 // Add the link between
 265                 edgePresentInGraph = topo.containsEdge(edge);
 266                 if (edgePresentInGraph == false) {
 267                     try {
 268                         topo.addEdge(new Edge(src, dst), src
 269                                 .getNode(), dst
 270                                 .getNode(), EdgeType.DIRECTED);
 271                     } catch (ConstructionException e) {
 272                         e.printStackTrace();
 273                         return edgePresentInGraph;
 274                     }
 275                 }
 276             } else {
 277                 //Remove the edge
 278                 try {
 279                     topo.removeEdge(new Edge(src, dst));
 280                 } catch (ConstructionException e) {
 281                     e.printStackTrace();
 282                     return edgePresentInGraph;
 283                 }
 284
 285                 // If the src and dst vertex don't have incoming or
 286                 // outgoing links we can get ride of them
 287                 if (topo.containsVertex(src.getNode())
 288                         && topo.inDegree(src.getNode()) == 0
 289                         && topo.outDegree(src.getNode()) == 0) {
 290                     log.debug("Removing vertex {}", src);
 291                     topo.removeVertex(src.getNode());
 292                 }
 293
 294                 if (topo.containsVertex(dst.getNode())
 295                         && topo.inDegree(dst.getNode()) == 0
 296                         && topo.outDegree(dst.getNode()) == 0) {
 297                     log.debug("Removing vertex {}", dst);
 298                     topo.removeVertex(dst.getNode());
 299                 }
 300             }
 301             spt.reset();
 302             if (bw.equals(baseBW)) {
 303                 clearMaxThroughput();
 304             }
 305         } else {
 306             log.error("Cannot find topology for BW {} this is unexpected!", bw);
 307         }
 308         return edgePresentInGraph;
 309     }
 310
 311     @Override
 312     public void edgeUpdate(Edge e, UpdateType type, Set<Property> props) {
 313         String srcType = null;
 314         String dstType = null;
 315
 316         if (e == null || type == null) {
 317             log.error("Edge or Update type are null!");
 318             return;
 319         } else {
 320             srcType = e.getTailNodeConnector().getType();
 321             dstType = e.getHeadNodeConnector().getType();
 322
 323             if (srcType.equals(NodeConnector.NodeConnectorIDType.PRODUCTION)) {
 324                 log.debug("Skip updates for {}", e);
 325                 return;
 326             }
 327
 328             if (dstType.equals(NodeConnector.NodeConnectorIDType.PRODUCTION)) {
 329                 log.debug("Skip updates for {}", e);
 330                 return;
 331             }
 332         }
 333
 334         Bandwidth bw = new Bandwidth(0);
 335         boolean newEdge = false;
 336         if (props != null)
 337             props.remove(bw);
 338
 339         log.debug("edgeUpdate: {} bw: {}", e.toString(), bw.getValue());
 340
 341         Short baseBW = Short.valueOf((short) 0);
 342         boolean add = (type == UpdateType.ADDED) ? true : false;
 343         // Update base topo
 344         newEdge = !updateTopo(e, baseBW, add);
 345         if (newEdge == true) {
 346             if (bw.getValue() != baseBW) {
 347                 // Update BW topo
 348                 updateTopo(e, (short) bw.getValue(), add);
 349             }
 350             if (this.routingAware != null) {
 351                 for (IListenRoutingUpdates ra : this.routingAware) {
 352                     try {
 353                         ra.recalculateDone();
 354                     } catch (Exception ex) {
 355                         log.error("Exception on routingAware listener call", e);
 356                     }
 357                 }
 358             }
 359         }
 360     }
 361
 362     /**
 363      * Function called by the dependency manager when all the required
 364      * dependencies are satisfied
 365      *
 366      */
 367     @SuppressWarnings({ "unchecked", "rawtypes" })
 368     public void init() {
 369         log.debug("Routing init() is called");
 370         this.topologyBWAware = (ConcurrentMap<Short, Graph<Node, Edge>>) new ConcurrentHashMap();
 371         this.sptBWAware = (ConcurrentMap<Short, DijkstraShortestPath<Node, Edge>>) new ConcurrentHashMap();
 372         // Now create the default topology, which doesn't consider the
 373         // BW, also create the corresponding Dijkstra calculation
 374         Graph<Node, Edge> g = new SparseMultigraph();
 375         Short sZero = Short.valueOf((short) 0);
 376         this.topologyBWAware.put(sZero, g);
 377         this.sptBWAware.put(sZero, new DijkstraShortestPath(g));
 378         // Topologies for other BW will be added on a needed base
 379     }
 380     /**
 381      * Function called by the dependency manager when at least one dependency
 382      * become unsatisfied or when the component is shutting down because for
 383      * example bundle is being stopped.
 384      *
 385      */
 386     void destroy() {
 387         log.debug("Routing destroy() is called");
 388     }
 389
 390     /**
 391      * Function called by dependency manager after "init ()" is called
 392      * and after the services provided by the class are registered in
 393      * the service registry
 394      *
 395      */
 396    void start() {
 397            log.debug("Routing start() is called");
 398            // build the routing database from the topology if it exists.
 399            Map<Edge, Set<Property>> edges = topologyManager.getEdges();
 400            if (edges.isEmpty()) {
 401                    return;
 402            }
 403            log.debug("Creating routing database from the topology");
 404            for (Iterator<Map.Entry<Edge,Set<Property>>> i = edges.entrySet().iterator();  i.hasNext();) {
 405                    Map.Entry<Edge, Set<Property>> entry = i.next();
 406                    Edge e = entry.getKey();
 407                    Set<Property> props = entry.getValue();
 408                    edgeUpdate(e, UpdateType.ADDED, props);
 409            }
 410    }
 411
 412     /**
 413      * Function called by the dependency manager before the services exported by
 414      * the component are unregistered, this will be followed by a "destroy ()"
 415      * calls
 416      *
 417      */
 418    public void stop() {
 419            log.debug("Routing stop() is called");
 420    }
 421
 422     @Override
 423     public void edgeOverUtilized(Edge edge) {
 424         // TODO Auto-generated method stub
 425
 426     }
 427
 428     @Override
 429     public void edgeUtilBackToNormal(Edge edge) {
 430         // TODO Auto-generated method stub
 431
 432     }
 433
 434     public void setSwitchManager(ISwitchManager switchManager) {
 435         this.switchManager = switchManager;
 436     }
 437
 438     public void unsetSwitchManager(ISwitchManager switchManager) {
 439         if (this.switchManager == switchManager) {
 440             this.switchManager = null;
 441         }
 442     }
 443
 444     public void setReadService(IReadService readService) {
 445         this.readService = readService;
 446     }
 447
 448     public void unsetReadService(IReadService readService) {
 449         if (this.readService == readService) {
 450             this.readService = null;
 451         }
 452     }
 453
 454     public void setTopologyManager(ITopologyManager tm) {
 455         this.topologyManager = tm;
 456     }
 457
 458     public void unsetTopologyManager(ITopologyManager tm) {
 459         if (this.topologyManager == tm) {
 460                 this.topologyManager = null;
 461         }
 462     }
 463 }