Add ConstrainedBFSTree class
- creates a breadth first search tree that satisfies the bandwidth condition
Change-Id: I2b899f501a431da8ad67e4755776d0bb7d8099b7
diff --git a/src/main/java/net/onrc/onos/intent/ConstrainedBFSTree.java b/src/main/java/net/onrc/onos/intent/ConstrainedBFSTree.java
new file mode 100644
index 0000000..2ea27ae
--- /dev/null
+++ b/src/main/java/net/onrc/onos/intent/ConstrainedBFSTree.java
@@ -0,0 +1,71 @@
+package net.onrc.onos.intent;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.LinkedList;
+
+import net.onrc.onos.ofcontroller.networkgraph.Link;
+import net.onrc.onos.ofcontroller.networkgraph.Path;
+import net.onrc.onos.ofcontroller.networkgraph.Switch;
+
+/**
+ * This class creates bandwidth constrained breadth first tree
+ * and returns paths from root switch to leaf switches
+ * which satisfies the bandwidth condition.
+ * If bandwidth parameter is not specified, the normal breadth first tree will be calculated.
+ * The paths are snapshot paths at the point of the class instantiation.
+ * @author Toshio Koide (t-koide@onlab.us)
+ */
+public class ConstrainedBFSTree {
+ LinkedList<Switch> switchQueue = new LinkedList<Switch>();
+ HashSet<Switch> switchSearched = new HashSet<Switch>();
+ HashMap<Switch, Link> upstreamLinks = new HashMap<Switch, Link>();
+ HashMap<Switch, Path> paths = new HashMap<Switch, Path>();
+ Switch rootSwitch;
+ PathIntents intents = null;
+ Double bandwidth = null;
+
+ public ConstrainedBFSTree(Switch rootSwitch) {
+ this.rootSwitch = rootSwitch;
+ this.intents = new PathIntents();
+ calcTree();
+ }
+
+ public ConstrainedBFSTree(Switch rootSwitch, PathIntents intents, Double bandwidth) {
+ this.rootSwitch = rootSwitch;
+ this.intents = intents;
+ this.bandwidth = bandwidth;
+ calcTree();
+ }
+
+ protected void calcTree() {
+ switchQueue.add(rootSwitch);
+ switchSearched.add(rootSwitch);
+ while (!switchQueue.isEmpty()) {
+ Switch sw = switchQueue.poll();
+ for (Link link: sw.getOutgoingLinks()) {
+ Switch reachedSwitch = link.getDestinationPort().getSwitch();
+ if (switchSearched.contains(reachedSwitch)) continue;
+ if (bandwidth != null && intents.getAvailableBandwidth(link) < bandwidth) continue;
+ switchQueue.add(reachedSwitch);
+ switchSearched.add(reachedSwitch);
+ upstreamLinks.put(reachedSwitch, link);
+ }
+ }
+ }
+
+ public Path getPath(Switch leafSwitch) {
+ Path path = paths.get(leafSwitch);
+ if (path == null && switchSearched.contains(leafSwitch)) {
+ path = new Path();
+ Switch sw = leafSwitch;
+ while (sw != rootSwitch) {
+ Link upstreamLink = upstreamLinks.get(sw);
+ path.add(0, upstreamLink);
+ sw = upstreamLink.getSourcePort().getSwitch();
+ }
+ paths.put(leafSwitch, path);
+ }
+ return path;
+ }
+}