Jonathan Hart | aa38097 | 2014-04-03 10:24:46 -0700 | [diff] [blame] | 1 | package net.onrc.onos.core.intent; |
Toshio Koide | c8c3432 | 2014-02-11 12:59:44 -0800 | [diff] [blame] | 2 | |
| 3 | import java.util.HashMap; |
| 4 | import java.util.HashSet; |
| 5 | import java.util.LinkedList; |
| 6 | |
Jonathan Hart | 472062d | 2014-04-03 10:56:48 -0700 | [diff] [blame] | 7 | import net.onrc.onos.core.topology.Link; |
| 8 | import net.onrc.onos.core.topology.LinkEvent; |
Jonathan Hart | 472062d | 2014-04-03 10:56:48 -0700 | [diff] [blame] | 9 | import net.onrc.onos.core.topology.Switch; |
Toshio Koide | c8c3432 | 2014-02-11 12:59:44 -0800 | [diff] [blame] | 10 | |
| 11 | /** |
| 12 | * This class creates bandwidth constrained breadth first tree |
| 13 | * and returns paths from root switch to leaf switches |
| 14 | * which satisfies the bandwidth condition. |
| 15 | * If bandwidth parameter is not specified, the normal breadth first tree will be calculated. |
| 16 | * The paths are snapshot paths at the point of the class instantiation. |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 17 | * |
Toshio Koide | c8c3432 | 2014-02-11 12:59:44 -0800 | [diff] [blame] | 18 | * @author Toshio Koide (t-koide@onlab.us) |
| 19 | */ |
| 20 | public class ConstrainedBFSTree { |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 21 | LinkedList<Switch> switchQueue = new LinkedList<>(); |
| 22 | HashSet<Switch> switchSearched = new HashSet<>(); |
| 23 | HashMap<Long, LinkEvent> upstreamLinks = new HashMap<>(); |
| 24 | HashMap<Switch, Path> paths = new HashMap<>(); |
| 25 | Switch rootSwitch; |
| 26 | PathIntentMap intents = null; |
| 27 | double bandwidth = 0.0; // 0.0 means no limit for bandwidth (normal BFS tree) |
Toshio Koide | c8c3432 | 2014-02-11 12:59:44 -0800 | [diff] [blame] | 28 | |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 29 | public ConstrainedBFSTree(Switch rootSwitch) { |
| 30 | this.rootSwitch = rootSwitch; |
| 31 | calcTree(); |
| 32 | } |
Toshio Koide | c8c3432 | 2014-02-11 12:59:44 -0800 | [diff] [blame] | 33 | |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 34 | public ConstrainedBFSTree(Switch rootSwitch, PathIntentMap intents, double bandwidth) { |
| 35 | this.rootSwitch = rootSwitch; |
| 36 | this.intents = intents; |
| 37 | this.bandwidth = bandwidth; |
| 38 | calcTree(); |
| 39 | } |
Toshio Koide | c8c3432 | 2014-02-11 12:59:44 -0800 | [diff] [blame] | 40 | |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 41 | protected void calcTree() { |
| 42 | switchQueue.add(rootSwitch); |
| 43 | switchSearched.add(rootSwitch); |
| 44 | while (!switchQueue.isEmpty()) { |
| 45 | Switch sw = switchQueue.poll(); |
| 46 | for (Link link : sw.getOutgoingLinks()) { |
| 47 | Switch reachedSwitch = link.getDstPort().getSwitch(); |
Ray Milkey | b29e626 | 2014-04-09 16:02:14 -0700 | [diff] [blame] | 48 | if (switchSearched.contains(reachedSwitch)) { |
| 49 | continue; |
| 50 | } |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 51 | if (intents != null && |
| 52 | intents.getAvailableBandwidth(link) < bandwidth) { |
| 53 | continue; |
| 54 | } |
| 55 | switchQueue.add(reachedSwitch); |
| 56 | switchSearched.add(reachedSwitch); |
| 57 | upstreamLinks.put(reachedSwitch.getDpid(), new LinkEvent(link)); |
| 58 | } |
| 59 | } |
| 60 | } |
Toshio Koide | c8c3432 | 2014-02-11 12:59:44 -0800 | [diff] [blame] | 61 | |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 62 | public Path getPath(Switch leafSwitch) { |
| 63 | Path path = paths.get(leafSwitch); |
| 64 | Long rootSwitchDpid = rootSwitch.getDpid(); |
| 65 | if (path == null && switchSearched.contains(leafSwitch)) { |
| 66 | path = new Path(); |
| 67 | Long sw = leafSwitch.getDpid(); |
| 68 | while (!sw.equals(rootSwitchDpid)) { |
| 69 | LinkEvent upstreamLink = upstreamLinks.get(sw); |
| 70 | path.add(0, upstreamLink); |
| 71 | sw = upstreamLink.getSrc().getDpid(); |
| 72 | } |
| 73 | paths.put(leafSwitch, path); |
| 74 | } |
| 75 | return path; |
| 76 | } |
Toshio Koide | c8c3432 | 2014-02-11 12:59:44 -0800 | [diff] [blame] | 77 | } |