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/flowcache/FlowManager.java b/src/main/java/net/floodlightcontroller/flowcache/FlowManager.java
index 51e0509..36d1059 100644
--- a/src/main/java/net/floodlightcontroller/flowcache/FlowManager.java
+++ b/src/main/java/net/floodlightcontroller/flowcache/FlowManager.java
@@ -115,16 +115,20 @@
@Override
public void run() {
+ /*
String logMsg = "MEASUREMENT: Running Thread hint " + this.hint;
log.debug(logMsg);
long startTime = System.nanoTime();
+ */
for (DataPath dp : this.dpList) {
- topoRouteService.getShortestPath(dp.srcPort(), dp.dstPort());
+ topoRouteService.getTopoShortestPath(dp.srcPort(), dp.dstPort());
}
+ /*
long estimatedTime = System.nanoTime() - startTime;
double rate = (estimatedTime > 0)? ((double)dpList.size() * 1000000000) / estimatedTime: 0.0;
logMsg = "MEASUREMENT: Computed Thread hint " + hint + ": " + dpList.size() + " shortest paths in " + (double)estimatedTime / 1000000000 + " sec: " + rate + " flows/s";
log.debug(logMsg);
+ */
}
}
@@ -158,6 +162,9 @@
int hint = 0;
ArrayList<DataPath> dpList = new ArrayList<DataPath>();
long startTime = System.nanoTime();
+
+ topoRouteService.prepareShortestPathTopo();
+
Iterable<IFlowPath> allFlowPaths = conn.utils().getAllFlowPaths(conn);
for (IFlowPath flowPathObj : allFlowPaths) {
FlowId flowId = new FlowId(flowPathObj.getFlowId());
@@ -169,6 +176,8 @@
Port dstPort = new Port(flowPathObj.getDstPort());
SwitchPort srcSwitchPort = new SwitchPort(srcDpid, srcPort);
SwitchPort dstSwitchPort = new SwitchPort(dstDpid, dstPort);
+
+ /*
DataPath dp = new DataPath();
dp.setSrcPort(srcSwitchPort);
dp.setDstPort(dstSwitchPort);
@@ -180,18 +189,11 @@
dpList = new ArrayList<DataPath>();
hint++;
}
- /*
- DataPath dataPath =
- topoRouteService.getShortestPath(srcSwitchPort,
- dstSwitchPort);
*/
- /*
- shortestPathExecutor.execute(
- new ShortestPathTask(topoRouteService,
- srcSwitchPort,
- dstSwitchPort));
- */
+ DataPath dataPath =
+ topoRouteService.getTopoShortestPath(srcSwitchPort,
+ dstSwitchPort);
counter++;
}
if (dpList.size() > 0) {
@@ -200,6 +202,7 @@
dpList));
}
+ /*
// Wait for all tasks to finish
try {
while (shortestPathExecutor.getQueue().size() > 0) {
@@ -208,7 +211,10 @@
} catch (InterruptedException ex) {
log.debug("MEASUREMENT: Shortest Path Computation interrupted");
}
+ */
+
conn.endTx(Transaction.COMMIT);
+ topoRouteService.dropShortestPathTopo();
long estimatedTime = System.nanoTime() - startTime;
double rate = (estimatedTime > 0)? ((double)counter * 1000000000) / estimatedTime: 0.0;
@@ -458,13 +464,13 @@
measureShortestPathScheduler.scheduleAtFixedRate(measureShortestPath, 10, 10, TimeUnit.SECONDS);
*/
- /*
final ScheduledFuture<?> measureMapReaderHandle =
measureMapReaderScheduler.scheduleAtFixedRate(measureMapReader, 10, 10, TimeUnit.SECONDS);
- */
+ /*
final ScheduledFuture<?> mapReaderHandle =
mapReaderScheduler.scheduleAtFixedRate(mapReader, 3, 3, TimeUnit.SECONDS);
+ */
@Override
public void init(String conf) {