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.core.NodeConnector.NodeConnectorIDType;
  29 import org.opendaylight.controller.sal.reader.IReadService;
  30 import org.opendaylight.controller.sal.routing.IListenRoutingUpdates;
  31 import org.opendaylight.controller.sal.routing.IRouting;
  32 import org.opendaylight.controller.sal.topology.IListenTopoUpdates;
  33 import org.opendaylight.controller.switchmanager.ISwitchManager;
  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.List;
  43 import java.util.Set;
  44 import java.util.Map;
  45 import java.util.concurrent.ConcurrentHashMap;
  46 import java.util.concurrent.ConcurrentMap;
  47 import org.slf4j.Logger;
  48 import org.slf4j.LoggerFactory;
  49 import org.apache.commons.collections15.Transformer;
  50
  51 public class DijkstraImplementation implements IRouting, IListenTopoUpdates {
  52     private static Logger log = LoggerFactory
  53             .getLogger(DijkstraImplementation.class);
  54     private ConcurrentMap<Short, Graph<Node, Edge>> topologyBWAware;
  55     private ConcurrentMap<Short, DijkstraShortestPath<Node, Edge>> sptBWAware;
  56     DijkstraShortestPath<Node, Edge> mtp; //Max Throughput Path
  57     private Set<IListenRoutingUpdates> routingAware;
  58     private ISwitchManager switchManager;
  59     private IReadService readService;
  60     private static final long DEFAULT_LINK_SPEED = Bandwidth.BW1Gbps;
  61
  62     public void setLIstenRoutingUpdates(IListenRoutingUpdates i) {
  63         if (this.routingAware == null) {
  64             this.routingAware = new HashSet<IListenRoutingUpdates>();
  65         }
  66         if (this.routingAware != null) {
  67             log.debug("Adding routingAware listener");
  68             this.routingAware.add(i);
  69         }
  70     }
  71
  72     public void unsetRoutingUpdates(IListenRoutingUpdates i) {
  73         if (this.routingAware == null) {
  74             return;
  75         }
  76         log.debug("Removing routingAware listener");
  77         this.routingAware.remove(i);
  78         if (this.routingAware.isEmpty()) {
  79             // We don't have any listener lets dereference
  80             this.routingAware = null;
  81         }
  82     }
  83
  84     @SuppressWarnings( { "unchecked", "rawtypes" })
  85     public DijkstraImplementation() {
  86         this.topologyBWAware = (ConcurrentMap<Short, Graph<Node, Edge>>) new ConcurrentHashMap();
  87         this.sptBWAware = (ConcurrentMap<Short, DijkstraShortestPath<Node, Edge>>) new ConcurrentHashMap();
  88         // Now create the default topology, which doesn't consider the
  89         // BW, also create the corresponding Dijkstra calculation
  90         Graph<Node, Edge> g = new SparseMultigraph();
  91         Short sZero = Short.valueOf((short) 0);
  92         this.topologyBWAware.put(sZero, g);
  93         this.sptBWAware.put(sZero, new DijkstraShortestPath(g));
  94         // Topologies for other BW will be added on a needed base
  95     }
  96
  97     @Override
  98     public synchronized void initMaxThroughput(
  99             final Map<Edge, Number> EdgeWeightMap) {
 100         if (mtp != null) {
 101             log.error("Max Throughput Dijkstra is already enabled!");
 102             return;
 103         }
 104         Transformer<Edge, ? extends Number> mtTransformer = null;
 105         if (EdgeWeightMap == null) {
 106             mtTransformer = new Transformer<Edge, Double>() {
 107                 public Double transform(Edge e) {
 108                     if (switchManager == null) {
 109                         log.error("switchManager is null");
 110                         return (double) -1;
 111                     }
 112                     NodeConnector srcNC = e.getTailNodeConnector();
 113                     NodeConnector dstNC = e.getHeadNodeConnector();
 114                     if ((srcNC == null) || (dstNC == null)) {
 115                         log.error("srcNC:{} or dstNC:{} is null", srcNC, dstNC);
 116                         return (double) -1;
 117                     }
 118                     Bandwidth bwSrc = (Bandwidth) switchManager
 119                             .getNodeConnectorProp(srcNC,
 120                                     Bandwidth.BandwidthPropName);
 121                     Bandwidth bwDst = (Bandwidth) switchManager
 122                             .getNodeConnectorProp(dstNC,
 123                                     Bandwidth.BandwidthPropName);
 124
 125                     if ((bwSrc == null) || (bwDst == null)) {
 126                         log.error("bwSrc:{} or bwDst:{} is null", bwSrc, bwDst);
 127                         return (double) -1;
 128                     }
 129
 130                     long srcLinkSpeed = bwSrc.getValue();
 131                     if (srcLinkSpeed == 0) {
 132                         log.trace("Edge {}: srcLinkSpeed is 0. Setting to {}!",
 133                                 e, DEFAULT_LINK_SPEED);
 134                         srcLinkSpeed = DEFAULT_LINK_SPEED;
 135                     }
 136
 137                     long dstLinkSpeed = bwDst.getValue();
 138                     if (dstLinkSpeed == 0) {
 139                         log.trace("Edge {}: dstLinkSpeed is 0. Setting to {}!",
 140                                 e, DEFAULT_LINK_SPEED);
 141                         dstLinkSpeed = DEFAULT_LINK_SPEED;
 142                     }
 143
 144                     long avlSrcThruPut = srcLinkSpeed
 145                             - readService.getTransmitRate(srcNC);
 146                     long avlDstThruPut = dstLinkSpeed
 147                             - readService.getTransmitRate(dstNC);
 148
 149                     //Use lower of the 2 available thruput as the available thruput
 150                     long avlThruPut = avlSrcThruPut < avlDstThruPut ? avlSrcThruPut
 151                             : avlDstThruPut;
 152
 153                     if (avlThruPut <= 0) {
 154                         log
 155                                 .trace(
 156                                         "Edge {}: Available Throughput {} is Zero/Negative",
 157                                         e, avlThruPut);
 158                         return (double) -1;
 159                     }
 160                     return (double) (Bandwidth.BW1Pbps / avlThruPut);
 161                 }
 162             };
 163         } else {
 164             mtTransformer = new Transformer<Edge, Number>() {
 165                 public Number transform(Edge e) {
 166                     return EdgeWeightMap.get(e);
 167                 }
 168             };
 169         }
 170         Short baseBW = Short.valueOf((short) 0);
 171         //Initialize mtp also using the default topo
 172         Graph<Node, Edge> g = this.topologyBWAware.get(baseBW);
 173         if (g == null) {
 174             log.error("Default Topology Graph is null");
 175             return;
 176         }
 177         mtp = new DijkstraShortestPath<Node, Edge>(g, mtTransformer);
 178     }
 179
 180     @Override
 181     public Path getRoute(Node src, Node dst) {
 182         if (src == null || dst == null) {
 183             return null;
 184         }
 185         return getRoute(src, dst, (short) 0);
 186     }
 187
 188     @Override
 189     public synchronized Path getMaxThroughputRoute(Node src, Node dst) {
 190         if (mtp == null) {
 191             log
 192                     .error("Max Throughput Path Calculation has not been Initialized!");
 193             return null;
 194         }
 195
 196         List<Edge> path;
 197         try {
 198             path = mtp.getMaxThroughputPath(src, dst);
 199         } catch (IllegalArgumentException ie) {
 200             log.debug("A vertex is yet not known between " + src.toString()
 201                     + " " + dst.toString());
 202             return null;
 203         }
 204         Path res;
 205         try {
 206             res = new Path(path);
 207         } catch (ConstructionException e) {
 208             log.debug("A vertex is yet not known between " + src.toString()
 209                     + " " + dst.toString());
 210             return null;
 211         }
 212         return res;
 213     }
 214
 215     @Override
 216     public synchronized Path getRoute(Node src, Node dst, Short Bw) {
 217         DijkstraShortestPath<Node, Edge> spt = this.sptBWAware.get(Bw);
 218         if (spt == null)
 219             return null;
 220         List<Edge> path;
 221         try {
 222             path = spt.getPath(src, dst);
 223         } catch (IllegalArgumentException ie) {
 224             log.debug("A vertex is yet not known between " + src.toString()
 225                     + " " + dst.toString());
 226             return null;
 227         }
 228         Path res;
 229         try {
 230             res = new Path(path);
 231         } catch (ConstructionException e) {
 232             log.debug("A vertex is yet not known between " + src.toString()
 233                     + " " + dst.toString());
 234             return null;
 235         }
 236         return res;
 237     }
 238
 239     @Override
 240     public synchronized void clear() {
 241         DijkstraShortestPath<Node, Edge> spt;
 242         for (Short bw : this.sptBWAware.keySet()) {
 243             spt = this.sptBWAware.get(bw);
 244             if (spt != null) {
 245                 spt.reset();
 246             }
 247         }
 248         clearMaxThroughput();
 249     }
 250
 251     @Override
 252     public synchronized void clearMaxThroughput() {
 253         if (mtp != null) {
 254             mtp.reset(); //reset maxthruput path
 255         }
 256     }
 257
 258     @SuppressWarnings( { "rawtypes", "unchecked" })
 259     private synchronized boolean updateTopo(Edge edge, Short bw, boolean added) {
 260         Graph<Node, Edge> topo = this.topologyBWAware.get(bw);
 261         DijkstraShortestPath<Node, Edge> spt = this.sptBWAware.get(bw);
 262         boolean edgePresentInGraph = false;
 263         Short baseBW = Short.valueOf((short) 0);
 264
 265         if (topo == null) {
 266             // Create topology for this BW
 267             Graph<Node, Edge> g = new SparseMultigraph();
 268             this.topologyBWAware.put(bw, g);
 269             topo = this.topologyBWAware.get(bw);
 270             this.sptBWAware.put(bw, new DijkstraShortestPath(g));
 271             spt = this.sptBWAware.get(bw);
 272         }
 273
 274         if (topo != null) {
 275             NodeConnector src = edge.getTailNodeConnector();
 276             NodeConnector dst = edge.getHeadNodeConnector();
 277             if (spt == null) {
 278                 spt = new DijkstraShortestPath(topo);
 279                 this.sptBWAware.put(bw, spt);
 280             }
 281
 282             if (added) {
 283                 // Make sure the vertex are there before adding the edge
 284                 topo.addVertex(src.getNode());
 285                 topo.addVertex(dst.getNode());
 286                 // Add the link between
 287                 edgePresentInGraph = topo.containsEdge(edge);
 288                 if (edgePresentInGraph == false) {
 289                     try {
 290                         topo.addEdge(new Edge(src, dst), src
 291                                 .getNode(), dst
 292                                 .getNode(), EdgeType.DIRECTED);
 293                     } catch (ConstructionException e) {
 294                         e.printStackTrace();
 295                         return edgePresentInGraph;
 296                     }
 297                 }
 298             } else {
 299                 //Remove the edge
 300                 try {
 301                     topo.removeEdge(new Edge(src, dst));
 302                 } catch (ConstructionException e) {
 303                     e.printStackTrace();
 304                     return edgePresentInGraph;
 305                 }
 306
 307                 // If the src and dst vertex don't have incoming or
 308                 // outgoing links we can get ride of them
 309                 if (topo.containsVertex(src.getNode())
 310                         && topo.inDegree(src.getNode()) == 0
 311                         && topo.outDegree(src.getNode()) == 0) {
 312                     log.debug("Removing vertex " + src);
 313                     topo.removeVertex(src.getNode());
 314                 }
 315
 316                 if (topo.containsVertex(dst.getNode())
 317                         && topo.inDegree(dst.getNode()) == 0
 318                         && topo.outDegree(dst.getNode()) == 0) {
 319                     log.debug("Removing vertex " + dst);
 320                     topo.removeVertex(dst.getNode());
 321                 }
 322             }
 323             spt.reset();
 324             if (bw.equals(baseBW)) {
 325                 clearMaxThroughput();
 326             }
 327         } else {
 328             log.error("Cannot find topology for BW " + bw
 329                     + " this is unexpected!");
 330         }
 331         return edgePresentInGraph;
 332     }
 333
 334     @Override
 335     public void edgeUpdate(Edge e, UpdateType type, Set<Property> props) {
 336         String srcType = null;
 337         String dstType = null;
 338
 339         if (e == null || type == null) {
 340             log.error("Edge or Update type are null!");
 341             return;
 342         } else {
 343             srcType = e.getTailNodeConnector().getType();
 344             dstType = e.getHeadNodeConnector().getType();
 345
 346             if (srcType.equals(NodeConnector.NodeConnectorIDType.PRODUCTION)) {
 347                 log.debug("Skip updates for {}", e);
 348                 return;
 349             }
 350
 351             if (dstType.equals(NodeConnector.NodeConnectorIDType.PRODUCTION)) {
 352                 log.debug("Skip updates for {}", e);
 353                 return;
 354             }
 355         }
 356
 357         Bandwidth bw = new Bandwidth(0);
 358         boolean newEdge = false;
 359         if (props != null)
 360             props.remove(bw);
 361
 362         log.debug("edgeUpdate: " + e.toString() + " bw: " + bw.getValue());
 363
 364         Short baseBW = Short.valueOf((short) 0);
 365         boolean add = (type == UpdateType.ADDED) ? true : false;
 366         // Update base topo
 367         newEdge = !updateTopo(e, baseBW, add);
 368         if (newEdge == true) {
 369             if (bw.getValue() != baseBW) {
 370                 // Update BW topo
 371                 updateTopo(e, (short) bw.getValue(), add);
 372             }
 373             if (this.routingAware != null) {
 374                 log.info("Invoking routingAware listeners");
 375                 for (IListenRoutingUpdates ra : this.routingAware) {
 376                     try {
 377                         ra.recalculateDone();
 378                     } catch (Exception ex) {
 379                         log.error("Exception on routingAware listener call", e);
 380                     }
 381                 }
 382             }
 383         }
 384     }
 385
 386     public void startUp() {
 387         log.debug(this.getClass().getName() + ":startUp Method Called");
 388     }
 389
 390     public void shutDown() {
 391         log.debug(this.getClass().getName() + ":shutDown Method Called");
 392     }
 393
 394     @Override
 395     public void edgeOverUtilized(Edge edge) {
 396         // TODO Auto-generated method stub
 397
 398     }
 399
 400     @Override
 401     public void edgeUtilBackToNormal(Edge edge) {
 402         // TODO Auto-generated method stub
 403
 404     }
 405
 406     public void setSwitchManager(ISwitchManager switchManager) {
 407         this.switchManager = switchManager;
 408     }
 409
 410     public void unsetSwitchManager(ISwitchManager switchManager) {
 411         if (this.switchManager == switchManager) {
 412             this.switchManager = null;
 413         }
 414     }
 415
 416     public void setReadService(IReadService readService) {
 417         this.readService = readService;
 418     }
 419
 420     public void unsetReadService(IReadService readService) {
 421         if (this.readService == readService) {
 422             this.readService = null;
 423         }
 424     }
 425 }