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; |
Yuta HIGUCHI | 93d35ea | 2014-08-31 23:26:13 -0700 | [diff] [blame] | 8 | import net.onrc.onos.core.topology.LinkData; |
Jonathan Hart | 472062d | 2014-04-03 10:56:48 -0700 | [diff] [blame] | 9 | import net.onrc.onos.core.topology.Switch; |
Yuta HIGUCHI | 8f3dfa3 | 2014-06-25 00:14:25 -0700 | [diff] [blame] | 10 | import net.onrc.onos.core.util.Dpid; |
Toshio Koide | c8c3432 | 2014-02-11 12:59:44 -0800 | [diff] [blame] | 11 | |
| 12 | /** |
Brian O'Connor | a581b9d | 2014-06-15 23:32:36 -0700 | [diff] [blame] | 13 | * This class creates bandwidth constrained breadth first tree and returns paths |
| 14 | * from root switch to leaf switches which satisfies the bandwidth condition. If |
| 15 | * bandwidth parameter is not specified, the normal breadth first tree will be |
| 16 | * calculated. The paths are snapshot paths at the point of the class |
| 17 | * instantiation. |
Toshio Koide | c8c3432 | 2014-02-11 12:59:44 -0800 | [diff] [blame] | 18 | */ |
| 19 | public class ConstrainedBFSTree { |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 20 | LinkedList<Switch> switchQueue = new LinkedList<>(); |
Yuta HIGUCHI | a617e15 | 2014-07-16 19:44:39 -0700 | [diff] [blame] | 21 | HashSet<Dpid> switchSearched = new HashSet<>(); |
Yuta HIGUCHI | 93d35ea | 2014-08-31 23:26:13 -0700 | [diff] [blame] | 22 | HashMap<Dpid, LinkData> upstreamLinks = new HashMap<>(); |
Yuta HIGUCHI | a617e15 | 2014-07-16 19:44:39 -0700 | [diff] [blame] | 23 | HashMap<Dpid, Path> paths = new HashMap<>(); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 24 | Switch rootSwitch; |
| 25 | PathIntentMap intents = null; |
| 26 | 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] | 27 | |
Brian O'Connor | a581b9d | 2014-06-15 23:32:36 -0700 | [diff] [blame] | 28 | /** |
| 29 | * Constructor. |
| 30 | * |
| 31 | * @param rootSwitch root of the BFS tree |
| 32 | */ |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 33 | public ConstrainedBFSTree(Switch rootSwitch) { |
| 34 | this.rootSwitch = rootSwitch; |
| 35 | calcTree(); |
| 36 | } |
Toshio Koide | c8c3432 | 2014-02-11 12:59:44 -0800 | [diff] [blame] | 37 | |
Brian O'Connor | a581b9d | 2014-06-15 23:32:36 -0700 | [diff] [blame] | 38 | /** |
| 39 | * Constructor. |
| 40 | * |
| 41 | * @param rootSwitch root switch of the BFS tree |
| 42 | * @param intents map of Intents |
Sho SHIMIZU | 6947445 | 2014-06-20 09:17:40 -0700 | [diff] [blame] | 43 | * @param bandwidth bandwidth constraint |
Brian O'Connor | a581b9d | 2014-06-15 23:32:36 -0700 | [diff] [blame] | 44 | */ |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 45 | public ConstrainedBFSTree(Switch rootSwitch, PathIntentMap intents, double bandwidth) { |
| 46 | this.rootSwitch = rootSwitch; |
| 47 | this.intents = intents; |
| 48 | this.bandwidth = bandwidth; |
| 49 | calcTree(); |
| 50 | } |
Toshio Koide | c8c3432 | 2014-02-11 12:59:44 -0800 | [diff] [blame] | 51 | |
Brian O'Connor | a581b9d | 2014-06-15 23:32:36 -0700 | [diff] [blame] | 52 | /** |
| 53 | * Calculates the BFS tree using any provided constraints and Intents. |
| 54 | */ |
Ray Milkey | 4373cbe | 2014-08-12 09:58:58 -0700 | [diff] [blame] | 55 | protected final void calcTree() { |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 56 | switchQueue.add(rootSwitch); |
Yuta HIGUCHI | a617e15 | 2014-07-16 19:44:39 -0700 | [diff] [blame] | 57 | switchSearched.add(rootSwitch.getDpid()); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 58 | while (!switchQueue.isEmpty()) { |
| 59 | Switch sw = switchQueue.poll(); |
| 60 | for (Link link : sw.getOutgoingLinks()) { |
| 61 | Switch reachedSwitch = link.getDstPort().getSwitch(); |
Yuta HIGUCHI | a617e15 | 2014-07-16 19:44:39 -0700 | [diff] [blame] | 62 | if (switchSearched.contains(reachedSwitch.getDpid())) { |
Ray Milkey | b29e626 | 2014-04-09 16:02:14 -0700 | [diff] [blame] | 63 | continue; |
| 64 | } |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 65 | if (intents != null && |
Brian O'Connor | a581b9d | 2014-06-15 23:32:36 -0700 | [diff] [blame] | 66 | intents.getAvailableBandwidth(link) < bandwidth) { |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 67 | continue; |
| 68 | } |
| 69 | switchQueue.add(reachedSwitch); |
Yuta HIGUCHI | a617e15 | 2014-07-16 19:44:39 -0700 | [diff] [blame] | 70 | switchSearched.add(reachedSwitch.getDpid()); |
Yuta HIGUCHI | 93d35ea | 2014-08-31 23:26:13 -0700 | [diff] [blame] | 71 | upstreamLinks.put(reachedSwitch.getDpid(), new LinkData(link)); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 72 | } |
| 73 | } |
| 74 | } |
Toshio Koide | c8c3432 | 2014-02-11 12:59:44 -0800 | [diff] [blame] | 75 | |
Brian O'Connor | a581b9d | 2014-06-15 23:32:36 -0700 | [diff] [blame] | 76 | /** |
| 77 | * Return the computed path from the root switch to the leaf switch. |
| 78 | * |
| 79 | * @param leafSwitch the leaf switch |
| 80 | * @return the Path from the root switch to the leaf switch |
| 81 | */ |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 82 | public Path getPath(Switch leafSwitch) { |
Yuta HIGUCHI | a617e15 | 2014-07-16 19:44:39 -0700 | [diff] [blame] | 83 | Path path = paths.get(leafSwitch.getDpid()); |
Yuta HIGUCHI | 8f3dfa3 | 2014-06-25 00:14:25 -0700 | [diff] [blame] | 84 | Dpid rootSwitchDpid = rootSwitch.getDpid(); |
Yuta HIGUCHI | a617e15 | 2014-07-16 19:44:39 -0700 | [diff] [blame] | 85 | if (path == null && switchSearched.contains(leafSwitch.getDpid())) { |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 86 | path = new Path(); |
Yuta HIGUCHI | 8f3dfa3 | 2014-06-25 00:14:25 -0700 | [diff] [blame] | 87 | Dpid sw = leafSwitch.getDpid(); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 88 | while (!sw.equals(rootSwitchDpid)) { |
Yuta HIGUCHI | 93d35ea | 2014-08-31 23:26:13 -0700 | [diff] [blame] | 89 | LinkData upstreamLink = upstreamLinks.get(sw); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 90 | path.add(0, upstreamLink); |
| 91 | sw = upstreamLink.getSrc().getDpid(); |
| 92 | } |
Yuta HIGUCHI | a617e15 | 2014-07-16 19:44:39 -0700 | [diff] [blame] | 93 | paths.put(leafSwitch.getDpid(), path); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 94 | } |
| 95 | return path; |
| 96 | } |
Toshio Koide | c8c3432 | 2014-02-11 12:59:44 -0800 | [diff] [blame] | 97 | } |