2 * Copyright (c) 2013 Cisco Systems, Inc. and others. All rights reserved.
4 * This program and the accompanying materials are made available under the
5 * terms of the Eclipse Public License v1.0 which accompanies this distribution,
6 * and is available at http://www.eclipse.org/legal/epl-v10.html
10 * @file DijkstraImplementation.java
13 * @brief Implementation of a routing engine using
14 * dijkstra. Implementation of dijkstra come from Jung2 library
17 package org.opendaylight.controller.routing.dijkstra_implementation.internal;
19 import org.opendaylight.controller.clustering.services.IClusterContainerServices;
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.routing.IListenRoutingUpdates;
29 import org.opendaylight.controller.sal.routing.IRouting;
30 import org.opendaylight.controller.sal.topology.TopoEdgeUpdate;
31 import org.opendaylight.controller.switchmanager.ISwitchManager;
32 import org.opendaylight.controller.topologymanager.ITopologyManager;
33 import org.opendaylight.controller.topologymanager.ITopologyManagerClusterWideAware;
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;
40 import java.lang.Exception;
41 import java.lang.IllegalArgumentException;
42 import java.util.HashSet;
43 import java.util.Iterator;
44 import java.util.List;
45 import java.util.ArrayList;
48 import java.util.concurrent.ConcurrentHashMap;
49 import java.util.concurrent.ConcurrentMap;
51 import org.slf4j.Logger;
52 import org.slf4j.LoggerFactory;
53 import org.apache.commons.collections15.Transformer;
55 @SuppressWarnings("rawtypes")
56 public class DijkstraImplementation implements IRouting, ITopologyManagerClusterWideAware {
57 private static Logger log = LoggerFactory.getLogger(DijkstraImplementation.class);
58 private ConcurrentMap<Short, Graph<Node, Edge>> topologyBWAware;
59 private ConcurrentMap<Short, DijkstraShortestPath<Node, Edge>> sptBWAware;
60 DijkstraShortestPath<Node, Edge> mtp; // Max Throughput Path
61 private Set<IListenRoutingUpdates> routingAware;
62 private ISwitchManager switchManager;
63 private ITopologyManager topologyManager;
64 private static final long DEFAULT_LINK_SPEED = Bandwidth.BW1Gbps;
65 private IClusterContainerServices clusterContainerService;
67 public void setListenRoutingUpdates(final IListenRoutingUpdates i) {
68 if (this.routingAware == null) {
69 this.routingAware = new HashSet<IListenRoutingUpdates>();
71 if (this.routingAware != null) {
72 log.debug("Adding routingAware listener: {}", i);
73 this.routingAware.add(i);
77 public void unsetListenRoutingUpdates(final IListenRoutingUpdates i) {
78 if (this.routingAware == null) {
81 log.debug("Removing routingAware listener");
82 this.routingAware.remove(i);
83 if (this.routingAware.isEmpty()) {
84 // We don't have any listener lets dereference
85 this.routingAware = null;
90 public synchronized void initMaxThroughput(
91 final Map<Edge, Number> EdgeWeightMap) {
93 log.error("Max Throughput Dijkstra is already enabled!");
96 Transformer<Edge, ? extends Number> mtTransformer = null;
97 if (EdgeWeightMap == null) {
98 mtTransformer = new Transformer<Edge, Double>() {
100 public Double transform(Edge e) {
101 if (switchManager == null) {
102 log.error("switchManager is null");
105 NodeConnector srcNC = e.getTailNodeConnector();
106 NodeConnector dstNC = e.getHeadNodeConnector();
107 if ((srcNC == null) || (dstNC == null)) {
108 log.error("srcNC:{} or dstNC:{} is null", srcNC, dstNC);
111 Bandwidth bwSrc = (Bandwidth) switchManager.getNodeConnectorProp(srcNC,
112 Bandwidth.BandwidthPropName);
113 Bandwidth bwDst = (Bandwidth) switchManager.getNodeConnectorProp(dstNC,
114 Bandwidth.BandwidthPropName);
116 long srcLinkSpeed = 0, dstLinkSpeed = 0;
117 if ((bwSrc == null) || ((srcLinkSpeed = bwSrc.getValue()) == 0)) {
118 log.debug("srcNC: {} - Setting srcLinkSpeed to Default!", srcNC);
119 srcLinkSpeed = DEFAULT_LINK_SPEED;
122 if ((bwDst == null) || ((dstLinkSpeed = bwDst.getValue()) == 0)) {
123 log.debug("dstNC: {} - Setting dstLinkSpeed to Default!", dstNC);
124 dstLinkSpeed = DEFAULT_LINK_SPEED;
127 // TODO: revisit the logic below with the real use case in
129 // For now we assume the throughput to be the speed of the
131 // this kind of logic require information that should be
132 // polled by statistic manager and are not yet available,
133 // also this service at the moment is not used, so to be
134 // revisited later on
135 long avlSrcThruPut = srcLinkSpeed;
136 long avlDstThruPut = dstLinkSpeed;
138 // Use lower of the 2 available throughput as the available
140 long avlThruPut = avlSrcThruPut < avlDstThruPut ? avlSrcThruPut : avlDstThruPut;
142 if (avlThruPut <= 0) {
143 log.debug("Edge {}: Available Throughput {} <= 0!", e, avlThruPut);
146 return (double) (Bandwidth.BW1Pbps / avlThruPut);
150 mtTransformer = new Transformer<Edge, Number>() {
152 public Number transform(Edge e) {
153 return EdgeWeightMap.get(e);
157 Short baseBW = Short.valueOf((short) 0);
158 // Initialize mtp also using the default topo
159 Graph<Node, Edge> g = this.topologyBWAware.get(baseBW);
161 log.error("Default Topology Graph is null");
164 mtp = new DijkstraShortestPath<Node, Edge>(g, mtTransformer);
168 public Path getRoute(final Node src, final Node dst) {
169 if ((src == null) || (dst == null)) {
172 return getRoute(src, dst, (short) 0);
176 public synchronized Path getMaxThroughputRoute(Node src, Node dst) {
178 log.error("Max Throughput Path Calculation Uninitialized!");
184 path = mtp.getMaxThroughputPath(src, dst);
185 } catch (IllegalArgumentException ie) {
186 log.debug("A vertex is yet not known between {} {}", src, dst);
191 res = new Path(path);
192 } catch (ConstructionException e) {
193 log.debug("A vertex is yet not known between {} {}", src, dst);
200 public synchronized Path getRoute(final Node src, final Node dst, final Short Bw) {
201 DijkstraShortestPath<Node, Edge> spt = this.sptBWAware.get(Bw);
207 path = spt.getPath(src, dst);
208 } catch (IllegalArgumentException ie) {
209 log.debug("A vertex is yet not known between {} {}", src, dst);
214 res = new Path(path);
215 } catch (ConstructionException e) {
216 log.debug("A vertex is yet not known between {} {}", src, dst);
223 public synchronized void clear() {
224 DijkstraShortestPath<Node, Edge> spt;
225 for (Short bw : this.sptBWAware.keySet()) {
226 spt = this.sptBWAware.get(bw);
231 clearMaxThroughput();
235 public synchronized void clearMaxThroughput() {
237 mtp.reset(); // reset maxthruput path
241 @SuppressWarnings({ "unchecked" })
242 private synchronized boolean updateTopo(Edge edge, Short bw, UpdateType type) {
243 Graph<Node, Edge> topo = this.topologyBWAware.get(bw);
244 DijkstraShortestPath<Node, Edge> spt = this.sptBWAware.get(bw);
245 boolean edgePresentInGraph = false;
246 Short baseBW = Short.valueOf((short) 0);
249 // Create topology for this BW
250 Graph<Node, Edge> g = new SparseMultigraph();
251 this.topologyBWAware.put(bw, g);
252 topo = this.topologyBWAware.get(bw);
253 this.sptBWAware.put(bw, new DijkstraShortestPath(g));
254 spt = this.sptBWAware.get(bw);
258 NodeConnector src = edge.getTailNodeConnector();
259 NodeConnector dst = edge.getHeadNodeConnector();
261 spt = new DijkstraShortestPath(topo);
262 this.sptBWAware.put(bw, spt);
267 // Make sure the vertex are there before adding the edge
268 topo.addVertex(src.getNode());
269 topo.addVertex(dst.getNode());
270 // Add the link between
271 edgePresentInGraph = topo.containsEdge(edge);
272 if (edgePresentInGraph == false) {
274 topo.addEdge(new Edge(src, dst), src.getNode(), dst.getNode(), EdgeType.DIRECTED);
275 } catch (final ConstructionException e) {
277 return edgePresentInGraph;
281 // Mainly raised only on properties update, so not really useful
287 topo.removeEdge(new Edge(src, dst));
288 } catch (final ConstructionException e) {
290 return edgePresentInGraph;
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()) && (topo.inDegree(src.getNode()) == 0)
296 && (topo.outDegree(src.getNode()) == 0)) {
297 log.debug("Removing vertex {}", src);
298 topo.removeVertex(src.getNode());
301 if (topo.containsVertex(dst.getNode()) && (topo.inDegree(dst.getNode()) == 0)
302 && (topo.outDegree(dst.getNode()) == 0)) {
303 log.debug("Removing vertex {}", dst);
304 topo.removeVertex(dst.getNode());
309 if (bw.equals(baseBW)) {
310 clearMaxThroughput();
313 log.error("Cannot find topology for BW {} this is unexpected!", bw);
315 return edgePresentInGraph;
318 private boolean edgeUpdate(Edge e, UpdateType type, Set<Property> props, boolean local) {
319 String srcType = null;
320 String dstType = null;
322 log.trace("Got an edgeUpdate: {} props: {} update type: {} local: {}", new Object[] { e, props, type, local });
324 if ((e == null) || (type == null)) {
325 log.error("Edge or Update type are null!");
328 srcType = e.getTailNodeConnector().getType();
329 dstType = e.getHeadNodeConnector().getType();
331 if (srcType.equals(NodeConnector.NodeConnectorIDType.PRODUCTION)) {
332 log.debug("Skip updates for {}", e);
336 if (dstType.equals(NodeConnector.NodeConnectorIDType.PRODUCTION)) {
337 log.debug("Skip updates for {}", e);
342 Bandwidth bw = new Bandwidth(0);
343 boolean newEdge = false;
348 Short baseBW = Short.valueOf((short) 0);
350 newEdge = !updateTopo(e, baseBW, type);
351 if (newEdge == true) {
352 if (bw.getValue() != baseBW) {
354 updateTopo(e, (short) bw.getValue(), type);
361 public void edgeUpdate(List<TopoEdgeUpdate> topoedgeupdateList) {
362 log.trace("Start of a Bulk EdgeUpdate with " + topoedgeupdateList.size() + " elements");
363 boolean callListeners = false;
364 for (int i = 0; i < topoedgeupdateList.size(); i++) {
365 Edge e = topoedgeupdateList.get(i).getEdge();
366 Set<Property> p = topoedgeupdateList.get(i)
368 UpdateType type = topoedgeupdateList.get(i)
370 boolean isLocal = topoedgeupdateList.get(i)
372 if ((edgeUpdate(e, type, p, isLocal)) && (!callListeners)) {
373 callListeners = true;
377 // The routing listeners should only be called on the coordinator, to
378 // avoid multiple controller cluster nodes to actually do the
379 // recalculation when only one need to react
380 boolean amICoordinator = true;
381 if (this.clusterContainerService != null) {
382 amICoordinator = this.clusterContainerService.amICoordinator();
384 if ((callListeners) && (this.routingAware != null) && amICoordinator) {
385 log.trace("Calling the routing listeners");
386 for (IListenRoutingUpdates ra : this.routingAware) {
388 ra.recalculateDone();
389 } catch (Exception ex) {
390 log.error("Exception on routingAware listener call", ex);
394 log.trace("End of a Bulk EdgeUpdate");
398 * Function called by the dependency manager when all the required
399 * dependencies are satisfied
402 @SuppressWarnings({ "unchecked", "rawtypes" })
404 log.debug("Routing init() is called");
405 this.topologyBWAware = new ConcurrentHashMap<Short, Graph<Node, Edge>>();
406 this.sptBWAware = new ConcurrentHashMap<Short, DijkstraShortestPath<Node, Edge>>();
407 // Now create the default topology, which doesn't consider the
408 // BW, also create the corresponding Dijkstra calculation
409 Graph<Node, Edge> g = new SparseMultigraph();
410 Short sZero = Short.valueOf((short) 0);
411 this.topologyBWAware.put(sZero, g);
412 this.sptBWAware.put(sZero, new DijkstraShortestPath(g));
413 // Topologies for other BW will be added on a needed base
417 * Function called by the dependency manager when at least one dependency
418 * become unsatisfied or when the component is shutting down because for
419 * example bundle is being stopped.
423 log.debug("Routing destroy() is called");
427 * Function called by dependency manager after "init ()" is called and after
428 * the services provided by the class are registered in the service registry
432 log.debug("Routing start() is called");
433 // build the routing database from the topology if it exists.
434 Map<Edge, Set<Property>> edges = topologyManager.getEdges();
435 if (edges.isEmpty()) {
438 List<TopoEdgeUpdate> topoedgeupdateList = new ArrayList<TopoEdgeUpdate>();
439 log.debug("Creating routing database from the topology");
440 for (Iterator<Map.Entry<Edge, Set<Property>>> i = edges.entrySet()
441 .iterator(); i.hasNext();) {
442 Map.Entry<Edge, Set<Property>> entry = i.next();
443 Edge e = entry.getKey();
444 Set<Property> props = entry.getValue();
445 TopoEdgeUpdate topoedgeupdate = new TopoEdgeUpdate(e, props,
447 topoedgeupdateList.add(topoedgeupdate);
449 edgeUpdate(topoedgeupdateList);
453 * Function called by the dependency manager before the services exported by
454 * the component are unregistered, this will be followed by a "destroy ()"
459 log.debug("Routing stop() is called");
462 public void setSwitchManager(ISwitchManager switchManager) {
463 this.switchManager = switchManager;
466 public void unsetSwitchManager(ISwitchManager switchManager) {
467 if (this.switchManager == switchManager) {
468 this.switchManager = null;
472 public void setTopologyManager(ITopologyManager tm) {
473 this.topologyManager = tm;
476 public void unsetTopologyManager(ITopologyManager tm) {
477 if (this.topologyManager == tm) {
478 this.topologyManager = null;
482 void setClusterContainerService(IClusterContainerServices s) {
483 log.debug("Cluster Service set");
484 this.clusterContainerService = s;
487 void unsetClusterContainerService(IClusterContainerServices s) {
488 if (this.clusterContainerService == s) {
489 log.debug("Cluster Service removed!");
490 this.clusterContainerService = null;
495 public void edgeOverUtilized(Edge edge) {
496 // TODO Auto-generated method stub
501 public void edgeUtilBackToNormal(Edge edge) {
502 // TODO Auto-generated method stub