[Emu] Disjoint Path Utils Exposed (to DefaultTopology)
Change-Id: I1d59d7a5a89618bd7419f00a0da674e87fe9bdb3
diff --git a/core/common/src/main/java/org/onosproject/common/DefaultTopology.java b/core/common/src/main/java/org/onosproject/common/DefaultTopology.java
index bdf7d73..08b5245 100644
--- a/core/common/src/main/java/org/onosproject/common/DefaultTopology.java
+++ b/core/common/src/main/java/org/onosproject/common/DefaultTopology.java
@@ -25,12 +25,16 @@
import org.onlab.graph.DijkstraGraphSearch;
import org.onlab.graph.GraphPathSearch;
import org.onlab.graph.GraphPathSearch.Result;
+import org.onlab.graph.SRLGGraphSearch;
+import org.onlab.graph.SuurballeGraphSearch;
import org.onlab.graph.TarjanGraphSearch;
import org.onlab.graph.TarjanGraphSearch.SCCResult;
import org.onosproject.net.AbstractModel;
import org.onosproject.net.ConnectPoint;
+import org.onosproject.net.DefaultDisjointPath;
import org.onosproject.net.DefaultPath;
import org.onosproject.net.DeviceId;
+import org.onosproject.net.DisjointPath;
import org.onosproject.net.Link;
import org.onosproject.net.Path;
import org.onosproject.net.provider.ProviderId;
@@ -46,6 +50,7 @@
import org.onosproject.net.topology.TopologyVertex;
import java.util.ArrayList;
+import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
@@ -67,6 +72,9 @@
private static final DijkstraGraphSearch<TopologyVertex, TopologyEdge> DIJKSTRA = new DijkstraGraphSearch<>();
private static final TarjanGraphSearch<TopologyVertex, TopologyEdge> TARJAN = new TarjanGraphSearch<>();
+ private static final SuurballeGraphSearch<TopologyVertex, TopologyEdge> SUURBALLE =
+ new SuurballeGraphSearch<>();
+
private final long time;
private final long creationTime;
@@ -314,6 +322,142 @@
}
return builder.build();
}
+ /**
+ /**
+ * Returns the set of pre-computed shortest disjoint path pairs between source and
+ * destination devices.
+ *
+ * @param src source device
+ * @param dst destination device
+ * @return set of shortest disjoint path pairs
+ */
+ Set<DisjointPath> getDisjointPaths(DeviceId src, DeviceId dst) {
+ return getDisjointPaths(src, dst, null);
+ }
+
+ /**
+ * Computes on-demand the set of shortest disjoint path pairs between source and
+ * destination devices.
+ *
+ * @param src source device
+ * @param dst destination device
+ * @param weight link weight function
+ * @return set of disjoint shortest path pairs
+ */
+ Set<DisjointPath> getDisjointPaths(DeviceId src, DeviceId dst, LinkWeight weight) {
+ final DefaultTopologyVertex srcV = new DefaultTopologyVertex(src);
+ final DefaultTopologyVertex dstV = new DefaultTopologyVertex(dst);
+ Set<TopologyVertex> vertices = graph.getVertexes();
+ if (!vertices.contains(srcV) || !vertices.contains(dstV)) {
+ // src or dst not part of the current graph
+ return ImmutableSet.of();
+ }
+
+ GraphPathSearch.Result<TopologyVertex, TopologyEdge> result =
+ SUURBALLE.search(graph, srcV, dstV, weight, ALL_PATHS);
+ ImmutableSet.Builder<DisjointPath> builder = ImmutableSet.builder();
+ for (org.onlab.graph.Path<TopologyVertex, TopologyEdge> path : result.paths()) {
+ builder.add(networkDisjointPath((org.onlab.graph.DisjointPathPair<TopologyVertex, TopologyEdge>) path));
+ }
+ return builder.build();
+ }
+
+ /**
+ * Computes on-demand the set of shortest disjoint risk groups path pairs between source and
+ * destination devices.
+ *
+ * @param src source device
+ * @param dst destination device
+ * @param riskProfile map representing risk groups for each edge
+ * @return set of shortest disjoint paths
+ */
+ Set<DisjointPath> getSRLGDisjointPathsD(DeviceId src, DeviceId dst, Map<TopologyEdge, Object> riskProfile) {
+ return getSRLGDisjointPathsD(src, dst, null, riskProfile);
+ }
+
+ /**
+ * Computes on-demand the set of shortest disjoint risk groups path pairs between source and
+ * destination devices.
+ *
+ * @param src source device
+ * @param dst destination device
+ * @param weight edge weight object
+ * @param riskProfile map representing risk groups for each edge
+ * @return set of shortest disjoint paths
+ */
+ Set<DisjointPath> getSRLGDisjointPathsD(DeviceId src, DeviceId dst, LinkWeight weight, Map<TopologyEdge,
+ Object> riskProfile) {
+ final DefaultTopologyVertex srcV = new DefaultTopologyVertex(src);
+ final DefaultTopologyVertex dstV = new DefaultTopologyVertex(dst);
+ Set<TopologyVertex> vertices = graph.getVertexes();
+ if (!vertices.contains(srcV) || !vertices.contains(dstV)) {
+ // src or dst not part of the current graph
+ return ImmutableSet.of();
+ }
+
+ SRLGGraphSearch<TopologyVertex, TopologyEdge> srlg = new SRLGGraphSearch<>(riskProfile);
+ GraphPathSearch.Result<TopologyVertex, TopologyEdge> result =
+ srlg.search(graph, srcV, dstV, weight, ALL_PATHS);
+ ImmutableSet.Builder<DisjointPath> builder = ImmutableSet.builder();
+ for (org.onlab.graph.Path<TopologyVertex, TopologyEdge> path : result.paths()) {
+ builder.add(networkDisjointPath((org.onlab.graph.DisjointPathPair<TopologyVertex, TopologyEdge>) path));
+ }
+ return builder.build();
+ }
+
+ /**
+ * Computes on-demand the set of shortest disjoint risk groups path pairs between source and
+ * destination devices.
+ *
+ * @param src source device
+ * @param dst destination device
+ * @param weight edge weight object
+ * @param riskProfile map representing risk groups for each link
+ * @return set of shortest disjoint paths
+ */
+ Set<DisjointPath> getSRLGDisjointPaths(DeviceId src, DeviceId dst, LinkWeight weight,
+ Map<Link, Object> riskProfile) {
+ Map<TopologyEdge, Object> riskProfile2 = new HashMap<>();
+ for (Link l : riskProfile.keySet()) {
+ riskProfile2.put(new TopologyEdge() {
+ final Link cur = l;
+
+ public Link link() {
+ return cur;
+ }
+
+ public TopologyVertex src() {
+ return new TopologyVertex() {
+ public DeviceId deviceId() {
+ return src;
+ }
+ };
+ }
+
+ public TopologyVertex dst() {
+ return new TopologyVertex() {
+ public DeviceId deviceId() {
+ return dst;
+ }
+ };
+ }
+ }, riskProfile.get(l));
+ }
+ return getSRLGDisjointPathsD(src, dst, weight, riskProfile2);
+ }
+
+ /**
+ * Computes on-demand the set of shortest disjoint risk groups path pairs between source and
+ * destination devices.
+ *
+ * @param src source device
+ * @param dst destination device
+ * @param riskProfile map representing risk groups for each link
+ * @return set of shortest disjoint paths
+ */
+ Set<DisjointPath> getSRLGDisjointPaths(DeviceId src, DeviceId dst, Map<Link, Object> riskProfile) {
+ return getSRLGDisjointPaths(src, dst, null, riskProfile);
+ }
// Converts graph path to a network path with the same cost.
private Path networkPath(org.onlab.graph.Path<TopologyVertex, TopologyEdge> path) {
@@ -324,6 +468,11 @@
return new DefaultPath(CORE_PROVIDER_ID, links, path.cost());
}
+ private DisjointPath networkDisjointPath(org.onlab.graph.DisjointPathPair<TopologyVertex, TopologyEdge> path) {
+ return new DefaultDisjointPath(CORE_PROVIDER_ID,
+ (DefaultPath) networkPath(path.path1), (DefaultPath) networkPath(path.path2));
+ }
+
// Searches for SCC clusters in the network topology graph using Tarjan
// algorithm.
private SCCResult<TopologyVertex, TopologyEdge> searchForClusters() {