Add K-shortest path API to PathService.
Change-Id: I96732666f31a7a2b2df9a16f63e77bc0a367da83
diff --git a/core/api/src/main/java/org/onosproject/net/topology/AbstractPathService.java b/core/api/src/main/java/org/onosproject/net/topology/AbstractPathService.java
index 2c43fc7..35b9fce 100644
--- a/core/api/src/main/java/org/onosproject/net/topology/AbstractPathService.java
+++ b/core/api/src/main/java/org/onosproject/net/topology/AbstractPathService.java
@@ -39,6 +39,7 @@
import java.util.List;
import java.util.Map;
import java.util.Set;
+import java.util.stream.Stream;
import static com.google.common.base.Preconditions.checkNotNull;
import static org.onosproject.net.topology.AdapterLinkWeigher.adapt;
@@ -105,6 +106,40 @@
}
@Override
+ public Stream<Path> getKShortestPaths(ElementId src, ElementId dst,
+ LinkWeigher weigher) {
+ checkNotNull(src, ELEMENT_ID_NULL);
+ checkNotNull(dst, ELEMENT_ID_NULL);
+
+ LinkWeigher internalWeigher = weigher != null ? weigher : DEFAULT_WEIGHER;
+
+ // Get the source and destination edge locations
+ EdgeLink srcEdge = getEdgeLink(src, true);
+ EdgeLink dstEdge = getEdgeLink(dst, false);
+
+ // If either edge is null, bail with no paths.
+ if (srcEdge == null || dstEdge == null) {
+ return Stream.empty();
+ }
+
+ DeviceId srcDevice = srcEdge != NOT_HOST ? srcEdge.dst().deviceId() : (DeviceId) src;
+ DeviceId dstDevice = dstEdge != NOT_HOST ? dstEdge.src().deviceId() : (DeviceId) dst;
+
+ // If the source and destination are on the same edge device, there
+ // is just one path, so build it and return it.
+ if (srcDevice.equals(dstDevice)) {
+ return Stream.of(edgeToEdgePath(srcEdge, dstEdge, null, internalWeigher));
+ }
+
+ // Otherwise get all paths between the source and destination edge
+ // devices.
+ Topology topology = topologyService.currentTopology();
+
+ return topologyService.getKShortestPaths(topology, srcDevice, dstDevice, internalWeigher)
+ .map(path -> edgeToEdgePath(srcEdge, dstEdge, path, internalWeigher));
+ }
+
+ @Override
public Set<DisjointPath> getDisjointPaths(ElementId src, ElementId dst, LinkWeight weight) {
return getDisjointPaths(src, dst, adapt(weight));
}
diff --git a/core/api/src/main/java/org/onosproject/net/topology/HopCountLinkWeigher.java b/core/api/src/main/java/org/onosproject/net/topology/HopCountLinkWeigher.java
new file mode 100644
index 0000000..efcba8c
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/net/topology/HopCountLinkWeigher.java
@@ -0,0 +1,73 @@
+/*
+ * Copyright 2017-present 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.topology;
+
+import static org.onosproject.net.Link.State.ACTIVE;
+import static org.onosproject.net.Link.Type.INDIRECT;
+
+import org.onlab.graph.ScalarWeight;
+import org.onlab.graph.Weight;
+
+/**
+ * Link weight for measuring link cost as hop count with indirect links
+ * being as expensive as traversing the entire graph to assume the worst.
+ */
+public class HopCountLinkWeigher implements LinkWeigher {
+
+ public static final LinkWeigher DEFAULT_HOP_COUNT_WEIGHER = new HopCountLinkWeigher();
+
+ private static final ScalarWeight ZERO = new ScalarWeight(0.0);
+ private static final ScalarWeight ONE = new ScalarWeight(1.0);
+ private static final ScalarWeight DEFAULT_INDIRECT = new ScalarWeight(Short.MAX_VALUE);
+
+ private final ScalarWeight indirectLinkCost;
+
+ /**
+ * Creates a new hop-count weight.
+ */
+ public HopCountLinkWeigher() {
+ this.indirectLinkCost = DEFAULT_INDIRECT;
+ }
+
+ /**
+ * Creates a new hop-count weight with the specified cost of indirect links.
+ *
+ * @param indirectLinkCost indirect link cost
+ */
+ public HopCountLinkWeigher(double indirectLinkCost) {
+ this.indirectLinkCost = new ScalarWeight(indirectLinkCost);
+ }
+
+ @Override
+ public Weight weight(TopologyEdge edge) {
+ if (edge.link().state() == ACTIVE) {
+ return edge.link().type() == INDIRECT ? indirectLinkCost : ONE;
+ } else {
+ return getNonViableWeight();
+ }
+ }
+
+ @Override
+ public Weight getInitialWeight() {
+ return ZERO;
+ }
+
+ @Override
+ public Weight getNonViableWeight() {
+ return ScalarWeight.NON_VIABLE_WEIGHT;
+ }
+
+}
diff --git a/core/api/src/main/java/org/onosproject/net/topology/PathService.java b/core/api/src/main/java/org/onosproject/net/topology/PathService.java
index adfca3d..1530649 100644
--- a/core/api/src/main/java/org/onosproject/net/topology/PathService.java
+++ b/core/api/src/main/java/org/onosproject/net/topology/PathService.java
@@ -20,8 +20,11 @@
import org.onosproject.net.Link;
import org.onosproject.net.Path;
+import static org.onosproject.net.topology.HopCountLinkWeigher.DEFAULT_HOP_COUNT_WEIGHER;
+
import java.util.Map;
import java.util.Set;
+import java.util.stream.Stream;
/**
* Service for obtaining pre-computed paths or for requesting computation of
@@ -68,6 +71,33 @@
Set<Path> getPaths(ElementId src, ElementId dst, LinkWeigher weigher);
/**
+ * Returns the k-shortest paths between source and
+ * destination devices.
+ *
+ * @param src source device
+ * @param dst destination device
+ * @return stream of k-shortest paths
+ */
+ default Stream<Path> getKShortestPaths(ElementId src, ElementId dst) {
+ return getKShortestPaths(src, dst, DEFAULT_HOP_COUNT_WEIGHER);
+ }
+
+ /**
+ * Returns the k-shortest paths between source and
+ * destination devices.
+ *
+ * @param src source device
+ * @param dst destination device
+ * @param weigher edge-weight entity
+ * @return stream of k-shortest paths
+ */
+ default Stream<Path> getKShortestPaths(ElementId src, ElementId dst,
+ LinkWeigher weigher) {
+ return getPaths(src, dst, weigher).stream();
+ }
+
+
+ /**
* Returns the set of all disjoint shortest path pairs between the
* specified source and destination elements. The path is computed using
* the default edge-weight function, which by default is hop-count.
diff --git a/core/api/src/main/java/org/onosproject/net/topology/TopologyService.java b/core/api/src/main/java/org/onosproject/net/topology/TopologyService.java
index 76ae91e..70a38f9 100644
--- a/core/api/src/main/java/org/onosproject/net/topology/TopologyService.java
+++ b/core/api/src/main/java/org/onosproject/net/topology/TopologyService.java
@@ -23,6 +23,8 @@
import org.onosproject.net.Link;
import org.onosproject.net.Path;
+import static org.onosproject.net.topology.HopCountLinkWeigher.DEFAULT_HOP_COUNT_WEIGHER;
+
import java.util.Map;
import java.util.Set;
import java.util.stream.Stream;
@@ -158,8 +160,19 @@
* Returns the k-shortest paths between source and
* destination devices.
*
- * The first {@code maxPaths} paths will be returned
- * in ascending order according to the provided {@code weigher}
+ * @param topology topology descriptor
+ * @param src source device
+ * @param dst destination device
+ * @return stream of k-shortest paths
+ */
+ default Stream<Path> getKShortestPaths(Topology topology,
+ DeviceId src, DeviceId dst) {
+ return getKShortestPaths(topology, src, dst, DEFAULT_HOP_COUNT_WEIGHER);
+ }
+
+ /**
+ * Returns the k-shortest paths between source and
+ * destination devices.
*
* @param topology topology descriptor
* @param src source device
diff --git a/core/api/src/test/java/org/onosproject/net/topology/TopologyServiceAdapter.java b/core/api/src/test/java/org/onosproject/net/topology/TopologyServiceAdapter.java
index bbc8fde..79ec17c 100644
--- a/core/api/src/test/java/org/onosproject/net/topology/TopologyServiceAdapter.java
+++ b/core/api/src/test/java/org/onosproject/net/topology/TopologyServiceAdapter.java
@@ -23,7 +23,6 @@
import java.util.Map;
import java.util.Set;
-import java.util.stream.Stream;
/**
* Test adapter for topology service.
@@ -84,17 +83,6 @@
}
@Override
- public Set<Path> getKShortestPaths(Topology topology, DeviceId src, DeviceId dst,
- LinkWeigher weigher, int maxPaths) {
- return null;
- }
-
- @Override
- public Stream<Path> getKShortestPaths(Topology topology, DeviceId src, DeviceId dst, LinkWeigher weigher) {
- return null;
- }
-
- @Override
public boolean isInfrastructure(Topology topology,
ConnectPoint connectPoint) {
return false;
diff --git a/core/net/src/main/java/org/onosproject/net/topology/impl/PathManager.java b/core/net/src/main/java/org/onosproject/net/topology/impl/PathManager.java
index ec650da..6f0a1b8 100644
--- a/core/net/src/main/java/org/onosproject/net/topology/impl/PathManager.java
+++ b/core/net/src/main/java/org/onosproject/net/topology/impl/PathManager.java
@@ -34,6 +34,7 @@
import org.slf4j.Logger;
import java.util.Set;
+import java.util.stream.Stream;
import java.util.Map;
@@ -90,6 +91,12 @@
return super.getPaths(src, dst, weigher);
}
+ @Override
+ public Stream<Path> getKShortestPaths(ElementId src, ElementId dst,
+ LinkWeigher weigher) {
+ checkPermission(TOPOLOGY_READ);
+ return super.getKShortestPaths(src, dst, weigher);
+ }
@Override
public Set<DisjointPath> getDisjointPaths(ElementId src, ElementId dst) {
diff --git a/core/net/src/test/java/org/onosproject/net/topology/impl/PathManagerTest.java b/core/net/src/test/java/org/onosproject/net/topology/impl/PathManagerTest.java
index cca8b4a..bb899d2 100644
--- a/core/net/src/test/java/org/onosproject/net/topology/impl/PathManagerTest.java
+++ b/core/net/src/test/java/org/onosproject/net/topology/impl/PathManagerTest.java
@@ -35,6 +35,7 @@
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
+import java.util.stream.Collectors;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
@@ -74,6 +75,10 @@
fakeTopoMgr.paths.add(createPath("src", "middle", "dst"));
Set<Path> paths = service.getPaths(src, dst);
validatePaths(paths, 1, 2, src, dst);
+
+ validatePaths(service.getKShortestPaths(src, dst)
+ .collect(Collectors.toSet()),
+ 1, 2, src, dst);
}
@Test
@@ -105,6 +110,10 @@
fakeHostMgr.hosts.put(dst, host("12:34:56:78:90:ef/1", "dstEdge"));
Set<Path> paths = service.getPaths(src, dst);
validatePaths(paths, 1, 4, src, dst);
+
+ validatePaths(service.getKShortestPaths(src, dst)
+ .collect(Collectors.toSet()),
+ 1, 4, src, dst);
}
@Test
@@ -115,6 +124,10 @@
fakeHostMgr.hosts.put(dst, host("12:34:56:78:90:ef/1", "edge"));
Set<Path> paths = service.getPaths(src, dst);
validatePaths(paths, 1, 2, src, dst);
+
+ validatePaths(service.getKShortestPaths(src, dst)
+ .collect(Collectors.toSet()),
+ 1, 2, src, dst);
}
@Test