Shortest-path computation related changes and optimizations:
* Reimplement the original TopoRouteService::getShortestPath()
so it doesn't use anymore the Titan Pipes mechanism.
Instead, it implements internally the Breath First Search
algorithm by walking the Titan vertices.
Test setup: small 21 switches topology with 1000 flows.
Speed improvement: from 20-25 shortest path computations per second
to 50-60 shortest path computations per second.
* Add a new mechanism for computing a large number of shortest paths.
It prefetches the relevant information from the Titan vertices
(Switch DPID, Switch neighbors, Ports info), and stores that
in memory. Then the shortest path computation is done by
using the Breath First Search on that internal state.
Speed improvement: from 50-60 shortest path computations per second
to more than 900 shortest path computations per second in the
same setup as above.
With this new mechanism the bottleneck is not anymore the Shortest Path
computation itself, but the fetching of the data in memory: 1-2 seconds
for 1000 Titan vertices. In the above testing, the speed measurement
also includes the time to fetch 1000 Flows from the Network MAP,
so the Shortest Path computation itself was a small fraction of that time.
Usage info:
/**
* Fetch the Switch and Ports info from the Titan Graph
* and store it locally for fast access during the shortest path
* computation.
*
* After fetching the state, method @ref getTopoShortestPath()
* can be used for fast shortest path computation.
*
* Note: There is certain cost to fetch the state, hence it should
* be used only when there is a large number of shortest path
* computations that need to be done on the same topology.
* Typically, a single call to @ref prepareShortestPathTopo()
* should be followed by a large number of calls to
* method @ref getTopoShortestPath().
* After the last @ref getTopoShortestPath() call,
* method @ref dropShortestPathTopo() should be used to release
* the internal state that is not needed anymore:
*
* prepareShortestPathTopo();
* for (int i = 0; i < 10000; i++) {
* dataPath = getTopoShortestPath(...);
* ...
* }
* dropShortestPathTopo();
*/
diff --git a/src/main/java/net/floodlightcontroller/core/INetMapTopologyService.java b/src/main/java/net/floodlightcontroller/core/INetMapTopologyService.java
index b16e4a9..6cfc974 100644
--- a/src/main/java/net/floodlightcontroller/core/INetMapTopologyService.java
+++ b/src/main/java/net/floodlightcontroller/core/INetMapTopologyService.java
@@ -33,7 +33,74 @@
}
public interface ITopoRouteService extends IFloodlightService {
+ /**
+ * Get the shortest path from a source to a destination.
+ *
+ * @param src the source in the shortest path computation.
+ * @param dest the destination in the shortest path computation.
+ * @return the data path with the computed shortest path if
+ * found, otherwise null.
+ */
DataPath getShortestPath(SwitchPort src, SwitchPort dest);
+
+ /**
+ * Fetch the Switch and Ports info from the Titan Graph
+ * and store it locally for fast access during the shortest path
+ * computation.
+ *
+ * After fetching the state, method @ref getTopoShortestPath()
+ * can be used for fast shortest path computation.
+ *
+ * Note: There is certain cost to fetch the state, hence it should
+ * be used only when there is a large number of shortest path
+ * computations that need to be done on the same topology.
+ * Typically, a single call to @ref prepareShortestPathTopo()
+ * should be followed by a large number of calls to
+ * method @ref getTopoShortestPath().
+ * After the last @ref getTopoShortestPath() call,
+ * method @ref dropShortestPathTopo() should be used to release
+ * the internal state that is not needed anymore:
+ *
+ * prepareShortestPathTopo();
+ * for (int i = 0; i < 10000; i++) {
+ * dataPath = getTopoShortestPath(...);
+ * ...
+ * }
+ * dropShortestPathTopo();
+ */
+ void prepareShortestPathTopo();
+
+ /**
+ * Release the state that was populated by
+ * method @ref prepareShortestPathTopo().
+ *
+ * See the documentation for method @ref prepareShortestPathTopo()
+ * for additional information and usage.
+ */
+ void dropShortestPathTopo();
+
+ /**
+ * Get the shortest path from a source to a destination by
+ * using the pre-populated local topology state prepared
+ * by method @ref prepareShortestPathTopo().
+ *
+ * See the documentation for method @ref prepareShortestPathTopo()
+ * for additional information and usage.
+ *
+ * @param src the source in the shortest path computation.
+ * @param dest the destination in the shortest path computation.
+ * @return the data path with the computed shortest path if
+ * found, otherwise null.
+ */
+ DataPath getTopoShortestPath(SwitchPort src, SwitchPort dest);
+
+ /**
+ * Test whether a route exists from a source to a destination.
+ *
+ * @param src the source node for the test.
+ * @param dest the destination node for the test.
+ * @return true if a route exists, otherwise false.
+ */
Boolean routeExists(SwitchPort src, SwitchPort dest);
}