+++ /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.clustering.services.IClusterContainerServices;
-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.routing.IListenRoutingUpdates;
-import org.opendaylight.controller.sal.routing.IRouting;
-import org.opendaylight.controller.sal.topology.TopoEdgeUpdate;
-import org.opendaylight.controller.switchmanager.ISwitchManager;
-import org.opendaylight.controller.topologymanager.ITopologyManager;
-import org.opendaylight.controller.topologymanager.ITopologyManagerClusterWideAware;
-
-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.util.HashSet;
-import java.util.Iterator;
-import java.util.List;
-import java.util.ArrayList;
-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;
-
-@SuppressWarnings("rawtypes")
-public class DijkstraImplementation implements IRouting, ITopologyManagerClusterWideAware {
- 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 ITopologyManager topologyManager;
- private static final long DEFAULT_LINK_SPEED = Bandwidth.BW1Gbps;
- private IClusterContainerServices clusterContainerService;
-
- public void setListenRoutingUpdates(final IListenRoutingUpdates i) {
- if (this.routingAware == null) {
- this.routingAware = new HashSet<IListenRoutingUpdates>();
- }
- if (this.routingAware != null) {
- log.debug("Adding routingAware listener: {}", i);
- this.routingAware.add(i);
- }
- }
-
- public void unsetListenRoutingUpdates(final 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;
- }
- }
-
- @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>() {
- @Override
- 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);
-
- long srcLinkSpeed = 0, dstLinkSpeed = 0;
- if ((bwSrc == null) || ((srcLinkSpeed = bwSrc.getValue()) == 0)) {
- log.debug("srcNC: {} - Setting srcLinkSpeed to Default!", srcNC);
- srcLinkSpeed = DEFAULT_LINK_SPEED;
- }
-
- if ((bwDst == null) || ((dstLinkSpeed = bwDst.getValue()) == 0)) {
- log.debug("dstNC: {} - Setting dstLinkSpeed to Default!", dstNC);
- dstLinkSpeed = DEFAULT_LINK_SPEED;
- }
-
- // TODO: revisit the logic below with the real use case in
- // mind
- // For now we assume the throughput to be the speed of the
- // link itself
- // this kind of logic require information that should be
- // polled by statistic manager and are not yet available,
- // also this service at the moment is not used, so to be
- // revisited later on
- long avlSrcThruPut = srcLinkSpeed;
- long avlDstThruPut = dstLinkSpeed;
-
- // Use lower of the 2 available throughput as the available
- // throughput
- long avlThruPut = avlSrcThruPut < avlDstThruPut ? avlSrcThruPut : avlDstThruPut;
-
- if (avlThruPut <= 0) {
- log.debug("Edge {}: Available Throughput {} <= 0!", e, avlThruPut);
- return (double) -1;
- }
- return (double) (Bandwidth.BW1Pbps / avlThruPut);
- }
- };
- } else {
- mtTransformer = new Transformer<Edge, Number>() {
- @Override
- 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(final Node src, final 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 Uninitialized!");
- return null;
- }
-
- List<Edge> path;
- try {
- path = mtp.getMaxThroughputPath(src, dst);
- } catch (IllegalArgumentException ie) {
- log.debug("A vertex is yet not known between {} {}", src, dst);
- return null;
- }
- Path res;
- try {
- res = new Path(path);
- } catch (ConstructionException e) {
- log.debug("A vertex is yet not known between {} {}", src, dst);
- return null;
- }
- return res;
- }
-
- @Override
- public synchronized Path getRoute(final Node src, final Node dst, final 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, dst);
- return null;
- }
- Path res;
- try {
- res = new Path(path);
- } catch (ConstructionException e) {
- log.debug("A vertex is yet not known between {} {}", src, dst);
- 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 max throughput path
- }
- }
-
- @SuppressWarnings({ "unchecked" })
- private synchronized boolean updateTopo(Edge edge, Short bw, UpdateType type) {
- 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);
- }
-
- switch (type) {
- case 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 (final ConstructionException e) {
- log.error("", e);
- return edgePresentInGraph;
- }
- }
- case CHANGED:
- // Mainly raised only on properties update, so not really useful
- // in this case
- break;
- case REMOVED:
- // Remove the edge
- try {
- topo.removeEdge(new Edge(src, dst));
- } catch (final ConstructionException e) {
- log.error("", e);
- 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());
- }
- break;
- }
- spt.reset();
- if (bw.equals(baseBW)) {
- clearMaxThroughput();
- }
- } else {
- log.error("Cannot find topology for BW {} this is unexpected!", bw);
- }
- return edgePresentInGraph;
- }
-
- private boolean edgeUpdate(Edge e, UpdateType type, Set<Property> props, boolean local) {
- String srcType = null;
- String dstType = null;
-
- log.trace("Got an edgeUpdate: {} props: {} update type: {} local: {}", new Object[] { e, props, type, local });
-
- if ((e == null) || (type == null)) {
- log.error("Edge or Update type are null!");
- return false;
- } else {
- srcType = e.getTailNodeConnector().getType();
- dstType = e.getHeadNodeConnector().getType();
-
- if (srcType.equals(NodeConnector.NodeConnectorIDType.PRODUCTION)) {
- log.debug("Skip updates for {}", e);
- return false;
- }
-
- if (dstType.equals(NodeConnector.NodeConnectorIDType.PRODUCTION)) {
- log.debug("Skip updates for {}", e);
- return false;
- }
- }
-
- Bandwidth bw = new Bandwidth(0);
- boolean newEdge = false;
- if (props != null) {
- props.remove(bw);
- }
-
- Short baseBW = Short.valueOf((short) 0);
- // Update base topo
- newEdge = !updateTopo(e, baseBW, type);
- if (newEdge == true) {
- if (bw.getValue() != baseBW) {
- // Update BW topo
- updateTopo(e, (short) bw.getValue(), type);
- }
- }
- return newEdge;
- }
-
- @Override
- public void edgeUpdate(List<TopoEdgeUpdate> topoedgeupdateList) {
- log.trace("Start of a Bulk EdgeUpdate with " + topoedgeupdateList.size() + " elements");
- boolean callListeners = false;
- for (int i = 0; i < topoedgeupdateList.size(); i++) {
- Edge e = topoedgeupdateList.get(i).getEdge();
- Set<Property> p = topoedgeupdateList.get(i)
- .getProperty();
- UpdateType type = topoedgeupdateList.get(i)
- .getUpdateType();
- boolean isLocal = topoedgeupdateList.get(i)
- .isLocal();
- if ((edgeUpdate(e, type, p, isLocal)) && (!callListeners)) {
- callListeners = true;
- }
- }
-
- // The routing listeners should only be called on the coordinator, to
- // avoid multiple controller cluster nodes to actually do the
- // recalculation when only one need to react
- boolean amICoordinator = true;
- if (this.clusterContainerService != null) {
- amICoordinator = this.clusterContainerService.amICoordinator();
- }
- if ((callListeners) && (this.routingAware != null) && amICoordinator) {
- log.trace("Calling the routing listeners");
- for (IListenRoutingUpdates ra : this.routingAware) {
- try {
- ra.recalculateDone();
- } catch (Exception ex) {
- log.error("Exception on routingAware listener call", ex);
- }
- }
- }
- log.trace("End of a Bulk EdgeUpdate");
- }
-
- /**
- * Function called by the dependency manager when all the required
- * dependencies are satisfied
- *
- */
- @SuppressWarnings({ "unchecked", "rawtypes" })
- public void init() {
- log.debug("Routing init() is called");
- this.topologyBWAware = new ConcurrentHashMap<Short, Graph<Node, Edge>>();
- this.sptBWAware = new ConcurrentHashMap<Short, DijkstraShortestPath<Node, Edge>>();
- // 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
- }
-
- /**
- * Function called by the dependency manager when at least one dependency
- * become unsatisfied or when the component is shutting down because for
- * example bundle is being stopped.
- *
- */
- void destroy() {
- log.debug("Routing destroy() is called");
- }
-
- /**
- * Function called by dependency manager after "init ()" is called and after
- * the services provided by the class are registered in the service registry
- *
- */
- void start() {
- log.debug("Routing start() is called");
- // build the routing database from the topology if it exists.
- Map<Edge, Set<Property>> edges = topologyManager.getEdges();
- if (edges.isEmpty()) {
- return;
- }
- List<TopoEdgeUpdate> topoedgeupdateList = new ArrayList<TopoEdgeUpdate>();
- log.debug("Creating routing database from the topology");
- for (Iterator<Map.Entry<Edge, Set<Property>>> i = edges.entrySet()
- .iterator(); i.hasNext();) {
- Map.Entry<Edge, Set<Property>> entry = i.next();
- Edge e = entry.getKey();
- Set<Property> props = entry.getValue();
- TopoEdgeUpdate topoedgeupdate = new TopoEdgeUpdate(e, props,
- UpdateType.ADDED);
- topoedgeupdateList.add(topoedgeupdate);
- }
- edgeUpdate(topoedgeupdateList);
- }
-
- /**
- * Function called by the dependency manager before the services exported by
- * the component are unregistered, this will be followed by a "destroy ()"
- * calls
- *
- */
- public void stop() {
- log.debug("Routing stop() is called");
- }
-
- public void setSwitchManager(ISwitchManager switchManager) {
- this.switchManager = switchManager;
- }
-
- public void unsetSwitchManager(ISwitchManager switchManager) {
- if (this.switchManager == switchManager) {
- this.switchManager = null;
- }
- }
-
- public void setTopologyManager(ITopologyManager tm) {
- this.topologyManager = tm;
- }
-
- public void unsetTopologyManager(ITopologyManager tm) {
- if (this.topologyManager == tm) {
- this.topologyManager = null;
- }
- }
-
- void setClusterContainerService(IClusterContainerServices s) {
- log.debug("Cluster Service set");
- this.clusterContainerService = s;
- }
-
- void unsetClusterContainerService(IClusterContainerServices s) {
- if (this.clusterContainerService == s) {
- log.debug("Cluster Service removed!");
- this.clusterContainerService = null;
- }
- }
-
- @Override
- public void edgeOverUtilized(Edge edge) {
- // TODO Auto-generated method stub
-
- }
-
- @Override
- public void edgeUtilBackToNormal(Edge edge) {
- // TODO Auto-generated method stub
-
- }
-}
Code Review / controller.git / blobdiff