blob: 3f92a2911044865a8f0c22eeabe6080f307b2ed0 [file] [log] [blame]
Jonathan Hartaa380972014-04-03 10:24:46 -07001package net.onrc.onos.core.intent;
Toshio Koidec8c34322014-02-11 12:59:44 -08002
3import java.util.HashMap;
4import java.util.HashSet;
5import java.util.LinkedList;
6
Jonathan Hart472062d2014-04-03 10:56:48 -07007import net.onrc.onos.core.topology.Link;
8import net.onrc.onos.core.topology.LinkEvent;
Jonathan Hart472062d2014-04-03 10:56:48 -07009import net.onrc.onos.core.topology.Switch;
Toshio Koidec8c34322014-02-11 12:59:44 -080010
11/**
Brian O'Connora581b9d2014-06-15 23:32:36 -070012 * This class creates bandwidth constrained breadth first tree and returns paths
13 * from root switch to leaf switches which satisfies the bandwidth condition. If
14 * bandwidth parameter is not specified, the normal breadth first tree will be
15 * calculated. The paths are snapshot paths at the point of the class
16 * instantiation.
Toshio Koidec8c34322014-02-11 12:59:44 -080017 */
18public class ConstrainedBFSTree {
Ray Milkey269ffb92014-04-03 14:43:30 -070019 LinkedList<Switch> switchQueue = new LinkedList<>();
20 HashSet<Switch> switchSearched = new HashSet<>();
21 HashMap<Long, LinkEvent> upstreamLinks = new HashMap<>();
22 HashMap<Switch, Path> paths = new HashMap<>();
23 Switch rootSwitch;
24 PathIntentMap intents = null;
25 double bandwidth = 0.0; // 0.0 means no limit for bandwidth (normal BFS tree)
Toshio Koidec8c34322014-02-11 12:59:44 -080026
Brian O'Connora581b9d2014-06-15 23:32:36 -070027 /**
28 * Constructor.
29 *
30 * @param rootSwitch root of the BFS tree
31 */
Ray Milkey269ffb92014-04-03 14:43:30 -070032 public ConstrainedBFSTree(Switch rootSwitch) {
33 this.rootSwitch = rootSwitch;
34 calcTree();
35 }
Toshio Koidec8c34322014-02-11 12:59:44 -080036
Brian O'Connora581b9d2014-06-15 23:32:36 -070037 /**
38 * Constructor.
39 *
40 * @param rootSwitch root switch of the BFS tree
41 * @param intents map of Intents
Sho SHIMIZU69474452014-06-20 09:17:40 -070042 * @param bandwidth bandwidth constraint
Brian O'Connora581b9d2014-06-15 23:32:36 -070043 */
Ray Milkey269ffb92014-04-03 14:43:30 -070044 public ConstrainedBFSTree(Switch rootSwitch, PathIntentMap intents, double bandwidth) {
45 this.rootSwitch = rootSwitch;
46 this.intents = intents;
47 this.bandwidth = bandwidth;
48 calcTree();
49 }
Toshio Koidec8c34322014-02-11 12:59:44 -080050
Brian O'Connora581b9d2014-06-15 23:32:36 -070051 /**
52 * Calculates the BFS tree using any provided constraints and Intents.
53 */
Ray Milkey269ffb92014-04-03 14:43:30 -070054 protected void calcTree() {
55 switchQueue.add(rootSwitch);
56 switchSearched.add(rootSwitch);
57 while (!switchQueue.isEmpty()) {
58 Switch sw = switchQueue.poll();
59 for (Link link : sw.getOutgoingLinks()) {
60 Switch reachedSwitch = link.getDstPort().getSwitch();
Ray Milkeyb29e6262014-04-09 16:02:14 -070061 if (switchSearched.contains(reachedSwitch)) {
62 continue;
63 }
Ray Milkey269ffb92014-04-03 14:43:30 -070064 if (intents != null &&
Brian O'Connora581b9d2014-06-15 23:32:36 -070065 intents.getAvailableBandwidth(link) < bandwidth) {
Ray Milkey269ffb92014-04-03 14:43:30 -070066 continue;
67 }
68 switchQueue.add(reachedSwitch);
69 switchSearched.add(reachedSwitch);
70 upstreamLinks.put(reachedSwitch.getDpid(), new LinkEvent(link));
71 }
72 }
73 }
Toshio Koidec8c34322014-02-11 12:59:44 -080074
Brian O'Connora581b9d2014-06-15 23:32:36 -070075 /**
76 * Return the computed path from the root switch to the leaf switch.
77 *
78 * @param leafSwitch the leaf switch
79 * @return the Path from the root switch to the leaf switch
80 */
Ray Milkey269ffb92014-04-03 14:43:30 -070081 public Path getPath(Switch leafSwitch) {
82 Path path = paths.get(leafSwitch);
83 Long rootSwitchDpid = rootSwitch.getDpid();
84 if (path == null && switchSearched.contains(leafSwitch)) {
85 path = new Path();
86 Long sw = leafSwitch.getDpid();
87 while (!sw.equals(rootSwitchDpid)) {
88 LinkEvent upstreamLink = upstreamLinks.get(sw);
89 path.add(0, upstreamLink);
90 sw = upstreamLink.getSrc().getDpid();
91 }
92 paths.put(leafSwitch, path);
93 }
94 return path;
95 }
Toshio Koidec8c34322014-02-11 12:59:44 -080096}