--- /dev/null
+
+/*
+ * Copyright (c) 2013 Cisco Systems, Inc. and others. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+
+/**
+ * @file DijkstraImplementation.java
+ *
+ *
+ * @brief Implementation of a routing engine using
+ * dijkstra. Implementation of dijkstra come from Jung2 library
+ *
+ */
+package org.opendaylight.controller.routing.dijkstra_implementation.internal;
+
+import org.opendaylight.controller.sal.core.Bandwidth;
+import org.opendaylight.controller.sal.core.ConstructionException;
+import org.opendaylight.controller.sal.core.Edge;
+import org.opendaylight.controller.sal.core.Node;
+import org.opendaylight.controller.sal.core.NodeConnector;
+import org.opendaylight.controller.sal.core.Path;
+import org.opendaylight.controller.sal.core.Property;
+import org.opendaylight.controller.sal.core.UpdateType;
+import org.opendaylight.controller.sal.core.NodeConnector.NodeConnectorIDType;
+import org.opendaylight.controller.sal.reader.IReadService;
+import org.opendaylight.controller.sal.routing.IListenRoutingUpdates;
+import org.opendaylight.controller.sal.routing.IRouting;
+import org.opendaylight.controller.sal.topology.IListenTopoUpdates;
+import org.opendaylight.controller.switchmanager.ISwitchManager;
+
+import edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath;
+import edu.uci.ics.jung.graph.Graph;
+import edu.uci.ics.jung.graph.SparseMultigraph;
+import edu.uci.ics.jung.graph.util.EdgeType;
+import java.lang.Exception;
+import java.lang.IllegalArgumentException;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+import java.util.Map;
+import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.ConcurrentMap;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+import org.apache.commons.collections15.Transformer;
+
+public class DijkstraImplementation implements IRouting, IListenTopoUpdates {
+ private static Logger log = LoggerFactory
+ .getLogger(DijkstraImplementation.class);
+ private ConcurrentMap<Short, Graph<Node, Edge>> topologyBWAware;
+ private ConcurrentMap<Short, DijkstraShortestPath<Node, Edge>> sptBWAware;
+ DijkstraShortestPath<Node, Edge> mtp; //Max Throughput Path
+ private Set<IListenRoutingUpdates> routingAware;
+ private ISwitchManager switchManager;
+ private IReadService readService;
+ private static final long DEFAULT_LINK_SPEED = Bandwidth.BW1Gbps;
+
+ public void setLIstenRoutingUpdates(IListenRoutingUpdates i) {
+ if (this.routingAware == null) {
+ this.routingAware = new HashSet<IListenRoutingUpdates>();
+ }
+ if (this.routingAware != null) {
+ log.debug("Adding routingAware listener");
+ this.routingAware.add(i);
+ }
+ }
+
+ public void unsetRoutingUpdates(IListenRoutingUpdates i) {
+ if (this.routingAware == null) {
+ return;
+ }
+ log.debug("Removing routingAware listener");
+ this.routingAware.remove(i);
+ if (this.routingAware.isEmpty()) {
+ // We don't have any listener lets dereference
+ this.routingAware = null;
+ }
+ }
+
+ @SuppressWarnings( { "unchecked", "rawtypes" })
+ public DijkstraImplementation() {
+ this.topologyBWAware = (ConcurrentMap<Short, Graph<Node, Edge>>) new ConcurrentHashMap();
+ this.sptBWAware = (ConcurrentMap<Short, DijkstraShortestPath<Node, Edge>>) new ConcurrentHashMap();
+ // Now create the default topology, which doesn't consider the
+ // BW, also create the corresponding Dijkstra calculation
+ Graph<Node, Edge> g = new SparseMultigraph();
+ Short sZero = Short.valueOf((short) 0);
+ this.topologyBWAware.put(sZero, g);
+ this.sptBWAware.put(sZero, new DijkstraShortestPath(g));
+ // Topologies for other BW will be added on a needed base
+ }
+
+ @Override
+ public synchronized void initMaxThroughput(
+ final Map<Edge, Number> EdgeWeightMap) {
+ if (mtp != null) {
+ log.error("Max Throughput Dijkstra is already enabled!");
+ return;
+ }
+ Transformer<Edge, ? extends Number> mtTransformer = null;
+ if (EdgeWeightMap == null) {
+ mtTransformer = new Transformer<Edge, Double>() {
+ public Double transform(Edge e) {
+ if (switchManager == null) {
+ log.error("switchManager is null");
+ return (double) -1;
+ }
+ NodeConnector srcNC = e.getTailNodeConnector();
+ NodeConnector dstNC = e.getHeadNodeConnector();
+ if ((srcNC == null) || (dstNC == null)) {
+ log.error("srcNC:{} or dstNC:{} is null", srcNC, dstNC);
+ return (double) -1;
+ }
+ Bandwidth bwSrc = (Bandwidth) switchManager
+ .getNodeConnectorProp(srcNC,
+ Bandwidth.BandwidthPropName);
+ Bandwidth bwDst = (Bandwidth) switchManager
+ .getNodeConnectorProp(dstNC,
+ Bandwidth.BandwidthPropName);
+
+ if ((bwSrc == null) || (bwDst == null)) {
+ log.error("bwSrc:{} or bwDst:{} is null", bwSrc, bwDst);
+ return (double) -1;
+ }
+
+ long srcLinkSpeed = bwSrc.getValue();
+ if (srcLinkSpeed == 0) {
+ log.trace("Edge {}: srcLinkSpeed is 0. Setting to {}!",
+ e, DEFAULT_LINK_SPEED);
+ srcLinkSpeed = DEFAULT_LINK_SPEED;
+ }
+
+ long dstLinkSpeed = bwDst.getValue();
+ if (dstLinkSpeed == 0) {
+ log.trace("Edge {}: dstLinkSpeed is 0. Setting to {}!",
+ e, DEFAULT_LINK_SPEED);
+ dstLinkSpeed = DEFAULT_LINK_SPEED;
+ }
+
+ long avlSrcThruPut = srcLinkSpeed
+ - readService.getTransmitRate(srcNC);
+ long avlDstThruPut = dstLinkSpeed
+ - readService.getTransmitRate(dstNC);
+
+ //Use lower of the 2 available thruput as the available thruput
+ long avlThruPut = avlSrcThruPut < avlDstThruPut ? avlSrcThruPut
+ : avlDstThruPut;
+
+ if (avlThruPut <= 0) {
+ log
+ .trace(
+ "Edge {}: Available Throughput {} is Zero/Negative",
+ e, avlThruPut);
+ return (double) -1;
+ }
+ return (double) (Bandwidth.BW1Pbps / avlThruPut);
+ }
+ };
+ } else {
+ mtTransformer = new Transformer<Edge, Number>() {
+ public Number transform(Edge e) {
+ return EdgeWeightMap.get(e);
+ }
+ };
+ }
+ Short baseBW = Short.valueOf((short) 0);
+ //Initialize mtp also using the default topo
+ Graph<Node, Edge> g = this.topologyBWAware.get(baseBW);
+ if (g == null) {
+ log.error("Default Topology Graph is null");
+ return;
+ }
+ mtp = new DijkstraShortestPath<Node, Edge>(g, mtTransformer);
+ }
+
+ @Override
+ public Path getRoute(Node src, Node dst) {
+ if (src == null || dst == null) {
+ return null;
+ }
+ return getRoute(src, dst, (short) 0);
+ }
+
+ @Override
+ public synchronized Path getMaxThroughputRoute(Node src, Node dst) {
+ if (mtp == null) {
+ log
+ .error("Max Throughput Path Calculation has not been Initialized!");
+ return null;
+ }
+
+ List<Edge> path;
+ try {
+ path = mtp.getMaxThroughputPath(src, dst);
+ } catch (IllegalArgumentException ie) {
+ log.debug("A vertex is yet not known between " + src.toString()
+ + " " + dst.toString());
+ return null;
+ }
+ Path res;
+ try {
+ res = new Path(path);
+ } catch (ConstructionException e) {
+ log.debug("A vertex is yet not known between " + src.toString()
+ + " " + dst.toString());
+ return null;
+ }
+ return res;
+ }
+
+ @Override
+ public synchronized Path getRoute(Node src, Node dst, Short Bw) {
+ DijkstraShortestPath<Node, Edge> spt = this.sptBWAware.get(Bw);
+ if (spt == null)
+ return null;
+ List<Edge> path;
+ try {
+ path = spt.getPath(src, dst);
+ } catch (IllegalArgumentException ie) {
+ log.debug("A vertex is yet not known between " + src.toString()
+ + " " + dst.toString());
+ return null;
+ }
+ Path res;
+ try {
+ res = new Path(path);
+ } catch (ConstructionException e) {
+ log.debug("A vertex is yet not known between " + src.toString()
+ + " " + dst.toString());
+ return null;
+ }
+ return res;
+ }
+
+ @Override
+ public synchronized void clear() {
+ DijkstraShortestPath<Node, Edge> spt;
+ for (Short bw : this.sptBWAware.keySet()) {
+ spt = this.sptBWAware.get(bw);
+ if (spt != null) {
+ spt.reset();
+ }
+ }
+ clearMaxThroughput();
+ }
+
+ @Override
+ public synchronized void clearMaxThroughput() {
+ if (mtp != null) {
+ mtp.reset(); //reset maxthruput path
+ }
+ }
+
+ @SuppressWarnings( { "rawtypes", "unchecked" })
+ private synchronized boolean updateTopo(Edge edge, Short bw, boolean added) {
+ Graph<Node, Edge> topo = this.topologyBWAware.get(bw);
+ DijkstraShortestPath<Node, Edge> spt = this.sptBWAware.get(bw);
+ boolean edgePresentInGraph = false;
+ Short baseBW = Short.valueOf((short) 0);
+
+ if (topo == null) {
+ // Create topology for this BW
+ Graph<Node, Edge> g = new SparseMultigraph();
+ this.topologyBWAware.put(bw, g);
+ topo = this.topologyBWAware.get(bw);
+ this.sptBWAware.put(bw, new DijkstraShortestPath(g));
+ spt = this.sptBWAware.get(bw);
+ }
+
+ if (topo != null) {
+ NodeConnector src = edge.getTailNodeConnector();
+ NodeConnector dst = edge.getHeadNodeConnector();
+ if (spt == null) {
+ spt = new DijkstraShortestPath(topo);
+ this.sptBWAware.put(bw, spt);
+ }
+
+ if (added) {
+ // Make sure the vertex are there before adding the edge
+ topo.addVertex(src.getNode());
+ topo.addVertex(dst.getNode());
+ // Add the link between
+ edgePresentInGraph = topo.containsEdge(edge);
+ if (edgePresentInGraph == false) {
+ try {
+ topo.addEdge(new Edge(src, dst), src
+ .getNode(), dst
+ .getNode(), EdgeType.DIRECTED);
+ } catch (ConstructionException e) {
+ e.printStackTrace();
+ return edgePresentInGraph;
+ }
+ }
+ } else {
+ //Remove the edge
+ try {
+ topo.removeEdge(new Edge(src, dst));
+ } catch (ConstructionException e) {
+ e.printStackTrace();
+ return edgePresentInGraph;
+ }
+
+ // If the src and dst vertex don't have incoming or
+ // outgoing links we can get ride of them
+ if (topo.containsVertex(src.getNode())
+ && topo.inDegree(src.getNode()) == 0
+ && topo.outDegree(src.getNode()) == 0) {
+ log.debug("Removing vertex " + src);
+ topo.removeVertex(src.getNode());
+ }
+
+ if (topo.containsVertex(dst.getNode())
+ && topo.inDegree(dst.getNode()) == 0
+ && topo.outDegree(dst.getNode()) == 0) {
+ log.debug("Removing vertex " + dst);
+ topo.removeVertex(dst.getNode());
+ }
+ }
+ spt.reset();
+ if (bw.equals(baseBW)) {
+ clearMaxThroughput();
+ }
+ } else {
+ log.error("Cannot find topology for BW " + bw
+ + " this is unexpected!");
+ }
+ return edgePresentInGraph;
+ }
+
+ @Override
+ public void edgeUpdate(Edge e, UpdateType type, Set<Property> props) {
+ String srcType = null;
+ String dstType = null;
+
+ if (e == null || type == null) {
+ log.error("Edge or Update type are null!");
+ return;
+ } else {
+ srcType = e.getTailNodeConnector().getType();
+ dstType = e.getHeadNodeConnector().getType();
+
+ if (srcType.equals(NodeConnector.NodeConnectorIDType.PRODUCTION)) {
+ log.debug("Skip updates for {}", e);
+ return;
+ }
+
+ if (dstType.equals(NodeConnector.NodeConnectorIDType.PRODUCTION)) {
+ log.debug("Skip updates for {}", e);
+ return;
+ }
+ }
+
+ Bandwidth bw = new Bandwidth(0);
+ boolean newEdge = false;
+ if (props != null)
+ props.remove(bw);
+
+ log.debug("edgeUpdate: " + e.toString() + " bw: " + bw.getValue());
+
+ Short baseBW = Short.valueOf((short) 0);
+ boolean add = (type == UpdateType.ADDED) ? true : false;
+ // Update base topo
+ newEdge = !updateTopo(e, baseBW, add);
+ if (newEdge == true) {
+ if (bw.getValue() != baseBW) {
+ // Update BW topo
+ updateTopo(e, (short) bw.getValue(), add);
+ }
+ if (this.routingAware != null) {
+ log.info("Invoking routingAware listeners");
+ for (IListenRoutingUpdates ra : this.routingAware) {
+ try {
+ ra.recalculateDone();
+ } catch (Exception ex) {
+ log.error("Exception on routingAware listener call", e);
+ }
+ }
+ }
+ }
+ }
+
+ public void startUp() {
+ log.debug(this.getClass().getName() + ":startUp Method Called");
+ }
+
+ public void shutDown() {
+ log.debug(this.getClass().getName() + ":shutDown Method Called");
+ }
+
+ @Override
+ public void edgeOverUtilized(Edge edge) {
+ // TODO Auto-generated method stub
+
+ }
+
+ @Override
+ public void edgeUtilBackToNormal(Edge edge) {
+ // TODO Auto-generated method stub
+
+ }
+
+ public void setSwitchManager(ISwitchManager switchManager) {
+ this.switchManager = switchManager;
+ }
+
+ public void unsetSwitchManager(ISwitchManager switchManager) {
+ if (this.switchManager == switchManager) {
+ this.switchManager = null;
+ }
+ }
+
+ public void setReadService(IReadService readService) {
+ this.readService = readService;
+ }
+
+ public void unsetReadService(IReadService readService) {
+ if (this.readService == readService) {
+ this.readService = null;
+ }
+ }
+}
Code Review / controller.git / blobdiff