[Emu] Disjoint Path Utils Exposed (to DefaultTopology)
Change-Id: I1d59d7a5a89618bd7419f00a0da674e87fe9bdb3
diff --git a/core/api/src/main/java/org/onosproject/net/DefaultDisjointPath.java b/core/api/src/main/java/org/onosproject/net/DefaultDisjointPath.java
new file mode 100644
index 0000000..4895964
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/net/DefaultDisjointPath.java
@@ -0,0 +1,100 @@
+/*
+ * Copyright 2015 Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.onosproject.net;
+
+import org.onosproject.net.provider.ProviderId;
+
+import java.util.List;
+import java.util.Objects;
+import static com.google.common.collect.ImmutableSet.of;
+
+/**
+ * Default implementation of a network disjoint path pair.
+ */
+public class DefaultDisjointPath extends DefaultPath implements DisjointPath {
+
+ private final DefaultPath path1;
+ private final DefaultPath path2;
+
+ boolean usingPath1 = true;
+
+ /**
+ * Creates a disjoint path pair from two default paths.
+ *
+ * @param providerId provider identity
+ * @param path1 primary path
+ * @param path2 backup path
+ */
+ public DefaultDisjointPath(ProviderId providerId, DefaultPath path1, DefaultPath path2) {
+ super(providerId, path1.links(), path1.cost() + path2.cost());
+ this.path1 = path1;
+ this.path2 = path2;
+ }
+
+ @Override
+ public List<Link> links() {
+ if (usingPath1) {
+ return path1.links();
+ } else {
+ return path2.links();
+ }
+ }
+
+ @Override
+ public double cost() {
+ if (usingPath1) {
+ return path1.cost();
+ }
+ return path2.cost();
+ }
+
+ @Override
+ public Path primary() {
+ return path1;
+ }
+
+ @Override
+ public Path backup() {
+ return path2;
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(of(path1, path2), src(), dst());
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj) {
+ return true;
+ }
+ if (obj instanceof DefaultDisjointPath) {
+ final DefaultDisjointPath other = (DefaultDisjointPath) obj;
+ return Objects.equals(this.path1, other.path1) && Objects.equals(this.path2, other.path2);
+ }
+ return false;
+ }
+
+ @Override
+ public boolean useBackup() {
+ if (path2 == null || path2.links() == null) {
+ return false;
+ }
+ usingPath1 = !usingPath1;
+ return true;
+ }
+}
diff --git a/core/api/src/main/java/org/onosproject/net/DisjointPath.java b/core/api/src/main/java/org/onosproject/net/DisjointPath.java
new file mode 100644
index 0000000..3d54cbf
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/net/DisjointPath.java
@@ -0,0 +1,49 @@
+/*
+ * Copyright 2015 Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.onosproject.net;
+
+
+/**
+ * Representation of a contiguous directed path in a network. Path comprises
+ * of a sequence of links, where adjacent links must share the same device,
+ * meaning that destination of the source of one link must coincide with the
+ * destination of the previous link.
+ */
+public interface DisjointPath extends Path {
+
+ /**
+ * Uses backup path.
+ *
+ * @return boolean corresponding to whether request to use
+ * backup was successful.
+ */
+ boolean useBackup();
+
+ /**
+ * Gets primary path.
+ *
+ * @return primary path
+ */
+ Path primary();
+
+ /**
+ * Gets secondary path.
+ *
+ * @return secondary path
+ */
+ Path backup();
+}
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() {