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.debug("Edge {}: Available Throughput {} <= 0!",
 144                                           e, avlThruPut);
 145                         return (double) -1;
 146                     }
 147                     return (double) (Bandwidth.BW1Pbps / avlThruPut);
 148                 }
 149             };
 150         } else {
 151             mtTransformer = new Transformer<Edge, Number>() {
 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(Node src, 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.toString(),
 187                            dst.toString());
 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.toString(),
 195                           dst.toString());
 196             return null;
 197         }
 198         return res;
 199     }
 200
 201     @Override
 202     public synchronized Path getRoute(Node src, Node dst, Short Bw) {
 203         DijkstraShortestPath<Node, Edge> spt = this.sptBWAware.get(Bw);
 204         if (spt == null)
 205             return null;
 206         List<Edge> path;
 207         try {
 208             path = spt.getPath(src, dst);
 209         } catch (IllegalArgumentException ie) {
 210                 log.debug("A vertex is yet not known between {} {}", src.toString(),
 211                            dst.toString());
 212             return null;
 213         }
 214         Path res;
 215         try {
 216             res = new Path(path);
 217         } catch (ConstructionException e) {
 218                 log.debug("A vertex is yet not known between {} {}", src.toString(),
 219                            dst.toString());
 220             return null;
 221         }
 222         return res;
 223     }
 224
 225     @Override
 226     public synchronized void clear() {
 227         DijkstraShortestPath<Node, Edge> spt;
 228         for (Short bw : this.sptBWAware.keySet()) {
 229             spt = this.sptBWAware.get(bw);
 230             if (spt != null) {
 231                 spt.reset();
 232             }
 233         }
 234         clearMaxThroughput();
 235     }
 236
 237     @Override
 238     public synchronized void clearMaxThroughput() {
 239         if (mtp != null) {
 240             mtp.reset(); //reset maxthruput path
 241         }
 242     }
 243
 244     @SuppressWarnings( { "rawtypes", "unchecked" })
 245     private synchronized boolean updateTopo(Edge edge, Short bw, boolean added) {
 246         Graph<Node, Edge> topo = this.topologyBWAware.get(bw);
 247         DijkstraShortestPath<Node, Edge> spt = this.sptBWAware.get(bw);
 248         boolean edgePresentInGraph = false;
 249         Short baseBW = Short.valueOf((short) 0);
 250
 251         if (topo == null) {
 252             // Create topology for this BW
 253             Graph<Node, Edge> g = new SparseMultigraph();
 254             this.topologyBWAware.put(bw, g);
 255             topo = this.topologyBWAware.get(bw);
 256             this.sptBWAware.put(bw, new DijkstraShortestPath(g));
 257             spt = this.sptBWAware.get(bw);
 258         }
 259
 260         if (topo != null) {
 261             NodeConnector src = edge.getTailNodeConnector();
 262             NodeConnector dst = edge.getHeadNodeConnector();
 263             if (spt == null) {
 264                 spt = new DijkstraShortestPath(topo);
 265                 this.sptBWAware.put(bw, spt);
 266             }
 267
 268             if (added) {
 269                 // Make sure the vertex are there before adding the edge
 270                 topo.addVertex(src.getNode());
 271                 topo.addVertex(dst.getNode());
 272                 // Add the link between
 273                 edgePresentInGraph = topo.containsEdge(edge);
 274                 if (edgePresentInGraph == false) {
 275                     try {
 276                         topo.addEdge(new Edge(src, dst), src
 277                                 .getNode(), dst
 278                                 .getNode(), EdgeType.DIRECTED);
 279                     } catch (ConstructionException e) {
 280                         e.printStackTrace();
 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                     e.printStackTrace();
 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     @Override
 320     public void edgeUpdate(Edge e, UpdateType type, Set<Property> props) {
 321         String srcType = null;
 322         String dstType = null;
 323
 324         if (e == null || type == null) {
 325             log.error("Edge or Update type are null!");
 326             return;
 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;
 334             }
 335
 336             if (dstType.equals(NodeConnector.NodeConnectorIDType.PRODUCTION)) {
 337                 log.debug("Skip updates for {}", e);
 338                 return;
 339             }
 340         }
 341
 342         Bandwidth bw = new Bandwidth(0);
 343         boolean newEdge = false;
 344         if (props != null)
 345             props.remove(bw);
 346
 347         log.debug("edgeUpdate: {} bw: {}", e.toString(), bw.getValue());
 348
 349         Short baseBW = Short.valueOf((short) 0);
 350         boolean add = (type == UpdateType.ADDED) ? true : false;
 351         // Update base topo
 352         newEdge = !updateTopo(e, baseBW, add);
 353         if (newEdge == true) {
 354             if (bw.getValue() != baseBW) {
 355                 // Update BW topo
 356                 updateTopo(e, (short) bw.getValue(), add);
 357             }
 358             if (this.routingAware != null) {
 359                 for (IListenRoutingUpdates ra : this.routingAware) {
 360                     try {
 361                         ra.recalculateDone();
 362                     } catch (Exception ex) {
 363                         log.error("Exception on routingAware listener call", e);
 364                     }
 365                 }
 366             }
 367         }
 368     }
 369
 370     /**
 371      * Function called by the dependency manager when all the required
 372      * dependencies are satisfied
 373      *
 374      */
 375     @SuppressWarnings({ "unchecked", "rawtypes" })
 376     public void init() {
 377         log.debug("Routing init() is called");
 378         this.topologyBWAware = (ConcurrentMap<Short, Graph<Node, Edge>>) new ConcurrentHashMap();
 379         this.sptBWAware = (ConcurrentMap<Short, DijkstraShortestPath<Node, Edge>>) new ConcurrentHashMap();
 380         // Now create the default topology, which doesn't consider the
 381         // BW, also create the corresponding Dijkstra calculation
 382         Graph<Node, Edge> g = new SparseMultigraph();
 383         Short sZero = Short.valueOf((short) 0);
 384         this.topologyBWAware.put(sZero, g);
 385         this.sptBWAware.put(sZero, new DijkstraShortestPath(g));
 386         // Topologies for other BW will be added on a needed base
 387     }
 388     /**
 389      * Function called by the dependency manager when at least one dependency
 390      * become unsatisfied or when the component is shutting down because for
 391      * example bundle is being stopped.
 392      *
 393      */
 394     void destroy() {
 395         log.debug("Routing destroy() is called");
 396     }
 397
 398     /**
 399      * Function called by dependency manager after "init ()" is called
 400      * and after the services provided by the class are registered in
 401      * the service registry
 402      *
 403      */
 404    void start() {
 405            log.debug("Routing start() is called");
 406            // build the routing database from the topology if it exists.
 407            Map<Edge, Set<Property>> edges = topologyManager.getEdges();
 408            if (edges.isEmpty()) {
 409                    return;
 410            }
 411            log.debug("Creating routing database from the topology");
 412            for (Iterator<Map.Entry<Edge,Set<Property>>> i = edges.entrySet().iterator();  i.hasNext();) {
 413                    Map.Entry<Edge, Set<Property>> entry = i.next();
 414                    Edge e = entry.getKey();
 415                    Set<Property> props = entry.getValue();
 416                    edgeUpdate(e, UpdateType.ADDED, props);
 417            }
 418    }
 419
 420     /**
 421      * Function called by the dependency manager before the services exported by
 422      * the component are unregistered, this will be followed by a "destroy ()"
 423      * calls
 424      *
 425      */
 426    public void stop() {
 427            log.debug("Routing stop() is called");
 428    }
 429
 430     @Override
 431     public void edgeOverUtilized(Edge edge) {
 432         // TODO Auto-generated method stub
 433
 434     }
 435
 436     @Override
 437     public void edgeUtilBackToNormal(Edge edge) {
 438         // TODO Auto-generated method stub
 439
 440     }
 441
 442     public void setSwitchManager(ISwitchManager switchManager) {
 443         this.switchManager = switchManager;
 444     }
 445
 446     public void unsetSwitchManager(ISwitchManager switchManager) {
 447         if (this.switchManager == switchManager) {
 448             this.switchManager = null;
 449         }
 450     }
 451
 452     public void setReadService(IReadService readService) {
 453         this.readService = readService;
 454     }
 455
 456     public void unsetReadService(IReadService readService) {
 457         if (this.readService == readService) {
 458             this.readService = null;
 459         }
 460     }
 461
 462     public void setTopologyManager(ITopologyManager tm) {
 463         this.topologyManager = tm;
 464     }
 465
 466     public void unsetTopologyManager(ITopologyManager tm) {
 467         if (this.topologyManager == tm) {
 468                 this.topologyManager = null;
 469         }
 470     }
 471 }