3 * Copyright (c) 2013 Cisco Systems, Inc. and others. All rights reserved.
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
11 * @file DijkstraImplementation.java
14 * @brief Implementation of a routing engine using
15 * dijkstra. Implementation of dijkstra come from Jung2 library
18 package org.opendaylight.controller.routing.dijkstra_implementation.internal;
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;
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;
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;
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;
64 public void setLIstenRoutingUpdates(IListenRoutingUpdates i) {
65 if (this.routingAware == null) {
66 this.routingAware = new HashSet<IListenRoutingUpdates>();
68 if (this.routingAware != null) {
69 log.debug("Adding routingAware listener: " + i);
70 this.routingAware.add(i);
74 public void unsetRoutingUpdates(IListenRoutingUpdates i) {
75 if (this.routingAware == null) {
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;
87 public synchronized void initMaxThroughput(
88 final Map<Edge, Number> EdgeWeightMap) {
90 log.error("Max Throughput Dijkstra is already enabled!");
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");
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);
107 Bandwidth bwSrc = (Bandwidth) switchManager
108 .getNodeConnectorProp(srcNC,
109 Bandwidth.BandwidthPropName);
110 Bandwidth bwDst = (Bandwidth) switchManager
111 .getNodeConnectorProp(dstNC,
112 Bandwidth.BandwidthPropName);
114 if ((bwSrc == null) || (bwDst == null)) {
115 log.error("bwSrc:{} or bwDst:{} is null", bwSrc, bwDst);
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;
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;
133 long avlSrcThruPut = srcLinkSpeed
134 - readService.getTransmitRate(srcNC);
135 long avlDstThruPut = dstLinkSpeed
136 - readService.getTransmitRate(dstNC);
138 //Use lower of the 2 available thruput as the available thruput
139 long avlThruPut = avlSrcThruPut < avlDstThruPut ? avlSrcThruPut
142 if (avlThruPut <= 0) {
145 "Edge {}: Available Throughput {} is Zero/Negative",
149 return (double) (Bandwidth.BW1Pbps / avlThruPut);
153 mtTransformer = new Transformer<Edge, Number>() {
154 public Number transform(Edge e) {
155 return EdgeWeightMap.get(e);
159 Short baseBW = Short.valueOf((short) 0);
160 //Initialize mtp also using the default topo
161 Graph<Node, Edge> g = this.topologyBWAware.get(baseBW);
163 log.error("Default Topology Graph is null");
166 mtp = new DijkstraShortestPath<Node, Edge>(g, mtTransformer);
170 public Path getRoute(Node src, Node dst) {
171 if (src == null || dst == null) {
174 return getRoute(src, dst, (short) 0);
178 public synchronized Path getMaxThroughputRoute(Node src, Node dst) {
181 .error("Max Throughput Path Calculation has not been Initialized!");
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());
195 res = new Path(path);
196 } catch (ConstructionException e) {
197 log.debug("A vertex is yet not known between " + src.toString()
198 + " " + dst.toString());
205 public synchronized Path getRoute(Node src, Node dst, Short Bw) {
206 DijkstraShortestPath<Node, Edge> spt = this.sptBWAware.get(Bw);
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());
219 res = new Path(path);
220 } catch (ConstructionException e) {
221 log.debug("A vertex is yet not known between " + src.toString()
222 + " " + dst.toString());
229 public synchronized void clear() {
230 DijkstraShortestPath<Node, Edge> spt;
231 for (Short bw : this.sptBWAware.keySet()) {
232 spt = this.sptBWAware.get(bw);
237 clearMaxThroughput();
241 public synchronized void clearMaxThroughput() {
243 mtp.reset(); //reset maxthruput path
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);
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);
264 NodeConnector src = edge.getTailNodeConnector();
265 NodeConnector dst = edge.getHeadNodeConnector();
267 spt = new DijkstraShortestPath(topo);
268 this.sptBWAware.put(bw, spt);
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) {
279 topo.addEdge(new Edge(src, dst), src
281 .getNode(), EdgeType.DIRECTED);
282 } catch (ConstructionException e) {
284 return edgePresentInGraph;
290 topo.removeEdge(new Edge(src, dst));
291 } catch (ConstructionException e) {
293 return edgePresentInGraph;
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());
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());
313 if (bw.equals(baseBW)) {
314 clearMaxThroughput();
317 log.error("Cannot find topology for BW " + bw
318 + " this is unexpected!");
320 return edgePresentInGraph;
324 public void edgeUpdate(Edge e, UpdateType type, Set<Property> props) {
325 String srcType = null;
326 String dstType = null;
328 if (e == null || type == null) {
329 log.error("Edge or Update type are null!");
332 srcType = e.getTailNodeConnector().getType();
333 dstType = e.getHeadNodeConnector().getType();
335 if (srcType.equals(NodeConnector.NodeConnectorIDType.PRODUCTION)) {
336 log.debug("Skip updates for {}", e);
340 if (dstType.equals(NodeConnector.NodeConnectorIDType.PRODUCTION)) {
341 log.debug("Skip updates for {}", e);
346 Bandwidth bw = new Bandwidth(0);
347 boolean newEdge = false;
351 log.debug("edgeUpdate: " + e.toString() + " bw: " + bw.getValue());
353 Short baseBW = Short.valueOf((short) 0);
354 boolean add = (type == UpdateType.ADDED) ? true : false;
356 newEdge = !updateTopo(e, baseBW, add);
357 if (newEdge == true) {
358 if (bw.getValue() != baseBW) {
360 updateTopo(e, (short) bw.getValue(), add);
362 if (this.routingAware != null) {
363 for (IListenRoutingUpdates ra : this.routingAware) {
365 ra.recalculateDone();
366 } catch (Exception ex) {
367 log.error("Exception on routingAware listener call", e);
375 * Function called by the dependency manager when all the required
376 * dependencies are satisfied
379 @SuppressWarnings({ "unchecked", "rawtypes" })
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
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.
399 log.debug("Routing destroy() is called");
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
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()) {
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);
425 * Function called by the dependency manager before the services exported by
426 * the component are unregistered, this will be followed by a "destroy ()"
431 log.debug("Routing stop() is called");
435 public void edgeOverUtilized(Edge edge) {
436 // TODO Auto-generated method stub
441 public void edgeUtilBackToNormal(Edge edge) {
442 // TODO Auto-generated method stub
446 public void setSwitchManager(ISwitchManager switchManager) {
447 this.switchManager = switchManager;
450 public void unsetSwitchManager(ISwitchManager switchManager) {
451 if (this.switchManager == switchManager) {
452 this.switchManager = null;
456 public void setReadService(IReadService readService) {
457 this.readService = readService;
460 public void unsetReadService(IReadService readService) {
461 if (this.readService == readService) {
462 this.readService = null;
466 public void setTopologyManager(ITopologyManager tm) {
467 this.topologyManager = tm;
470 public void unsetTopologyManager(ITopologyManager tm) {
471 if (this.topologyManager == tm) {
472 this.topologyManager = null;