Thomas Vachuska | 9c9ff7c | 2015-07-20 10:38:59 -0700 | [diff] [blame] | 1 | /* |
Brian O'Connor | a09fe5b | 2017-08-03 21:12:30 -0700 | [diff] [blame] | 2 | * Copyright 2015-present Open Networking Foundation |
Thomas Vachuska | 9c9ff7c | 2015-07-20 10:38:59 -0700 | [diff] [blame] | 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | package org.onosproject.flowanalyzer; |
| 17 | |
Nikhil Cheerla | d6734f6 | 2015-07-21 10:41:44 -0700 | [diff] [blame] | 18 | import org.onosproject.net.ConnectPoint; |
Ray Milkey | d84f89b | 2018-08-17 14:54:17 -0700 | [diff] [blame] | 19 | import org.onosproject.net.DeviceId; |
| 20 | import org.onosproject.net.HostId; |
| 21 | import org.onosproject.net.Link; |
Nikhil Cheerla | d6734f6 | 2015-07-21 10:41:44 -0700 | [diff] [blame] | 22 | import org.onosproject.net.PortNumber; |
| 23 | import org.onosproject.net.flow.FlowEntry; |
Thomas Vachuska | 9c9ff7c | 2015-07-20 10:38:59 -0700 | [diff] [blame] | 24 | import org.onosproject.net.flow.FlowRuleService; |
Nikhil Cheerla | d6734f6 | 2015-07-21 10:41:44 -0700 | [diff] [blame] | 25 | import org.onosproject.net.flow.criteria.Criteria; |
| 26 | import org.onosproject.net.flow.criteria.Criterion; |
| 27 | import org.onosproject.net.flow.criteria.PortCriterion; |
| 28 | import org.onosproject.net.flow.instructions.Instruction; |
| 29 | import org.onosproject.net.flow.instructions.Instructions; |
Thomas Vachuska | 9c9ff7c | 2015-07-20 10:38:59 -0700 | [diff] [blame] | 30 | import org.onosproject.net.link.LinkService; |
Ray Milkey | d84f89b | 2018-08-17 14:54:17 -0700 | [diff] [blame] | 31 | import org.onosproject.net.topology.TopologyGraph; |
| 32 | import org.onosproject.net.topology.TopologyService; |
Nikhil Cheerla | d6734f6 | 2015-07-21 10:41:44 -0700 | [diff] [blame] | 33 | import org.onosproject.net.topology.TopologyVertex; |
Thomas Vachuska | 9c9ff7c | 2015-07-20 10:38:59 -0700 | [diff] [blame] | 34 | import org.osgi.service.component.ComponentContext; |
Ray Milkey | d84f89b | 2018-08-17 14:54:17 -0700 | [diff] [blame] | 35 | import org.osgi.service.component.annotations.Activate; |
| 36 | import org.osgi.service.component.annotations.Component; |
| 37 | import org.osgi.service.component.annotations.Deactivate; |
| 38 | import org.osgi.service.component.annotations.Reference; |
| 39 | import org.osgi.service.component.annotations.ReferenceCardinality; |
Thomas Vachuska | 9c9ff7c | 2015-07-20 10:38:59 -0700 | [diff] [blame] | 40 | import org.slf4j.Logger; |
| 41 | |
Ray Milkey | d84f89b | 2018-08-17 14:54:17 -0700 | [diff] [blame] | 42 | import java.util.HashMap; |
Nikhil Cheerla | d6734f6 | 2015-07-21 10:41:44 -0700 | [diff] [blame] | 43 | import java.util.HashSet; |
| 44 | import java.util.List; |
Nikhil Cheerla | d6734f6 | 2015-07-21 10:41:44 -0700 | [diff] [blame] | 45 | import java.util.Map; |
| 46 | import java.util.Set; |
| 47 | |
Thomas Vachuska | 9c9ff7c | 2015-07-20 10:38:59 -0700 | [diff] [blame] | 48 | import static org.slf4j.LoggerFactory.getLogger; |
| 49 | |
| 50 | /** |
| 51 | * Simple flow space analyzer app. |
| 52 | */ |
Ray Milkey | d84f89b | 2018-08-17 14:54:17 -0700 | [diff] [blame] | 53 | @Component(immediate = true, service = FlowAnalyzer.class) |
Thomas Vachuska | 9c9ff7c | 2015-07-20 10:38:59 -0700 | [diff] [blame] | 54 | public class FlowAnalyzer { |
| 55 | |
| 56 | private final Logger log = getLogger(getClass()); |
| 57 | |
Ray Milkey | d84f89b | 2018-08-17 14:54:17 -0700 | [diff] [blame] | 58 | @Reference(cardinality = ReferenceCardinality.MANDATORY) |
Thomas Vachuska | 9c9ff7c | 2015-07-20 10:38:59 -0700 | [diff] [blame] | 59 | protected FlowRuleService flowRuleService; |
| 60 | |
Ray Milkey | d84f89b | 2018-08-17 14:54:17 -0700 | [diff] [blame] | 61 | @Reference(cardinality = ReferenceCardinality.MANDATORY) |
Nikhil Cheerla | d6734f6 | 2015-07-21 10:41:44 -0700 | [diff] [blame] | 62 | protected TopologyService topologyService; |
Thomas Vachuska | 9c9ff7c | 2015-07-20 10:38:59 -0700 | [diff] [blame] | 63 | |
Ray Milkey | d84f89b | 2018-08-17 14:54:17 -0700 | [diff] [blame] | 64 | @Reference(cardinality = ReferenceCardinality.MANDATORY) |
Nikhil Cheerla | d6734f6 | 2015-07-21 10:41:44 -0700 | [diff] [blame] | 65 | protected LinkService linkService; |
Thomas Vachuska | 9c9ff7c | 2015-07-20 10:38:59 -0700 | [diff] [blame] | 66 | |
| 67 | @Activate |
| 68 | public void activate(ComponentContext context) { |
| 69 | log.info("Started"); |
| 70 | } |
| 71 | |
| 72 | @Deactivate |
| 73 | public void deactivate() { |
| 74 | log.info("Stopped"); |
| 75 | } |
| 76 | |
Nikhil Cheerla | d6734f6 | 2015-07-21 10:41:44 -0700 | [diff] [blame] | 77 | TopologyGraph graph; |
| 78 | Map<FlowEntry, String> label = new HashMap<>(); |
| 79 | Set<FlowEntry> ignoredFlows = new HashSet<>(); |
Thomas Vachuska | 9c9ff7c | 2015-07-20 10:38:59 -0700 | [diff] [blame] | 80 | |
| 81 | /** |
Nikhil Cheerla | d6734f6 | 2015-07-21 10:41:44 -0700 | [diff] [blame] | 82 | * Analyzes and prints out a report on the status of every flow entry inside |
| 83 | * the network. The possible states are: Cleared (implying that the entry leads to |
| 84 | * a host), Cycle (implying that it is part of cycle), and Black Hole (implying |
| 85 | * that the entry does not lead to a single host). |
Brian O'Connor | 5251562 | 2015-10-09 17:03:44 -0700 | [diff] [blame] | 86 | * |
| 87 | * @return result string |
Thomas Vachuska | 9c9ff7c | 2015-07-20 10:38:59 -0700 | [diff] [blame] | 88 | */ |
Nikhil Cheerla | d6734f6 | 2015-07-21 10:41:44 -0700 | [diff] [blame] | 89 | public String analyze() { |
| 90 | graph = topologyService.getGraph(topologyService.currentTopology()); |
| 91 | for (TopologyVertex v: graph.getVertexes()) { |
| 92 | DeviceId srcDevice = v.deviceId(); |
| 93 | Iterable<FlowEntry> flowTable = flowRuleService.getFlowEntries(srcDevice); |
| 94 | for (FlowEntry flow: flowTable) { |
| 95 | dfs(flow); |
| 96 | } |
| 97 | } |
| 98 | |
| 99 | //analyze the cycles to look for "critical flows" that can be removed |
| 100 | //to break the cycle |
| 101 | Set<FlowEntry> critpts = new HashSet<>(); |
| 102 | for (FlowEntry flow: label.keySet()) { |
| 103 | if ("Cycle".equals(label.get(flow))) { |
| 104 | Map<FlowEntry, String> labelSaved = label; |
| 105 | label = new HashMap<FlowEntry, String>(); |
| 106 | ignoredFlows.add(flow); |
| 107 | for (TopologyVertex v: graph.getVertexes()) { |
| 108 | DeviceId srcDevice = v.deviceId(); |
| 109 | Iterable<FlowEntry> flowTable = flowRuleService.getFlowEntries(srcDevice); |
| 110 | for (FlowEntry flow1: flowTable) { |
| 111 | dfs(flow1); |
| 112 | } |
| 113 | } |
| 114 | |
| 115 | boolean replacable = true; |
| 116 | for (FlowEntry flow2: label.keySet()) { |
| 117 | if ("Cleared".equals(labelSaved.get(flow2)) && !("Cleared".equals(label.get(flow2)))) { |
| 118 | replacable = false; |
| 119 | } |
| 120 | } |
| 121 | if (replacable) { |
| 122 | critpts.add(flow); |
| 123 | } |
| 124 | label = labelSaved; |
| 125 | } |
| 126 | } |
| 127 | |
| 128 | for (FlowEntry flow: critpts) { |
| 129 | label.put(flow, "Cycle Critical Point"); |
| 130 | } |
| 131 | |
| 132 | String s = "\n"; |
| 133 | for (FlowEntry flow: label.keySet()) { |
| 134 | s += ("Flow Rule: " + flowEntryRepresentation(flow) + "\n"); |
| 135 | s += ("Analysis: " + label.get(flow) + "!\n\n"); |
| 136 | } |
| 137 | s += ("Analyzed " + label.keySet().size() + " flows."); |
| 138 | //log.info(s); |
| 139 | return s; |
Thomas Vachuska | 9c9ff7c | 2015-07-20 10:38:59 -0700 | [diff] [blame] | 140 | } |
| 141 | |
Nikhil Cheerla | d6734f6 | 2015-07-21 10:41:44 -0700 | [diff] [blame] | 142 | public Map<FlowEntry, String> calcLabels() { |
| 143 | analyze(); |
| 144 | return label; |
| 145 | } |
| 146 | public String analysisOutput() { |
| 147 | analyze(); |
| 148 | String s = "\n"; |
| 149 | for (FlowEntry flow: label.keySet()) { |
| 150 | s += ("Flow Rule: " + flowEntryRepresentation(flow) + "\n"); |
| 151 | s += ("Analysis: " + label.get(flow) + "!\n\n"); |
| 152 | } |
| 153 | return s; |
| 154 | } |
| 155 | |
| 156 | private boolean dfs(FlowEntry flow) { |
| 157 | if (ignoredFlows.contains(flow)) { |
| 158 | return false; |
| 159 | } |
| 160 | if ("Cycle".equals(label.get(flow)) || |
| 161 | "Black Hole".equals(label.get(flow)) || |
| 162 | "Cleared".equals(label.get(flow)) || |
| 163 | "NA".equals(label.get(flow)) || |
| 164 | "Cycle Critical Point".equals(label.get(flow))) { |
| 165 | |
| 166 | // This flow has already been analyzed and there is no need to analyze it further |
| 167 | return !"Black Hole".equals(label.get(flow)); |
| 168 | } |
| 169 | |
| 170 | if ("Visiting".equals(label.get(flow))) { |
| 171 | //you've detected a cycle because you reached the same entry again during your dfs |
| 172 | //let it continue so you can label the whole cycle |
| 173 | label.put(flow, "Cycle"); |
| 174 | } else { |
| 175 | //otherwise, mark off the current flow entry as currently being visited |
| 176 | label.put(flow, "Visiting"); |
| 177 | } |
| 178 | |
| 179 | boolean pointsToLiveEntry = false; |
| 180 | |
| 181 | List<Instruction> instructions = flow.treatment().allInstructions(); |
| 182 | for (Instruction i: instructions) { |
| 183 | if (i instanceof Instructions.OutputInstruction) { |
| 184 | pointsToLiveEntry |= analyzeInstruction(i, flow); |
| 185 | } |
| 186 | if ("NA".equals(label.get(flow))) { |
| 187 | return pointsToLiveEntry; |
| 188 | } |
| 189 | } |
| 190 | |
| 191 | if (!pointsToLiveEntry) { |
| 192 | //this entry does not point to any "live" entries thus must be a black hole |
| 193 | label.put(flow, "Black Hole"); |
| 194 | } else if ("Visiting".equals(label.get(flow))) { |
| 195 | //the flow is not in a cycle or in a black hole |
| 196 | label.put(flow, "Cleared"); |
| 197 | } |
| 198 | return pointsToLiveEntry; |
| 199 | } |
| 200 | |
| 201 | private boolean analyzeInstruction(Instruction i, FlowEntry flow) { |
| 202 | boolean pointsToLiveEntry = false; |
| 203 | Instructions.OutputInstruction output = (Instructions.OutputInstruction) i; |
| 204 | PortNumber port = output.port(); |
| 205 | PortNumber outPort = null; |
| 206 | |
| 207 | DeviceId egress = null; |
| 208 | boolean hasHost = false; |
| 209 | |
| 210 | ConnectPoint portPt = new ConnectPoint(flow.deviceId(), port); |
| 211 | for (Link l: linkService.getEgressLinks(portPt)) { |
| 212 | if (l.dst().elementId() instanceof DeviceId) { |
| 213 | egress = l.dst().deviceId(); |
| 214 | outPort = l.dst().port(); |
| 215 | } else if (l.dst().elementId() instanceof HostId) { |
| 216 | //the port leads to a host: therefore it is not a dead link |
| 217 | pointsToLiveEntry = true; |
| 218 | hasHost = true; |
| 219 | } |
| 220 | } |
| 221 | if (!topologyService.isInfrastructure(topologyService.currentTopology(), portPt) && egress == null) { |
| 222 | pointsToLiveEntry = true; |
| 223 | hasHost = true; |
| 224 | } |
| 225 | if (hasHost) { |
| 226 | return pointsToLiveEntry; |
| 227 | } |
| 228 | if (egress == null) { |
| 229 | //the port that the flow instructions tells you to send the packet |
| 230 | //to doesn't exist or is a controller port |
| 231 | label.put(flow, "NA"); |
| 232 | return pointsToLiveEntry; |
| 233 | } |
| 234 | |
| 235 | Iterable<FlowEntry> dstFlowTable = flowRuleService.getFlowEntries(egress); |
| 236 | |
| 237 | Set<Criterion> flowCriteria = flow.selector().criteria(); |
| 238 | |
| 239 | //filter the criteria in order to remove port dependency |
| 240 | Set<Criterion> filteredCriteria = new HashSet<>(); |
| 241 | for (Criterion criterion : flowCriteria) { |
| 242 | if (!(criterion instanceof PortCriterion)) { |
| 243 | filteredCriteria.add(criterion); |
| 244 | } |
| 245 | } |
| 246 | |
| 247 | //ensure that the in port is equal to the port that it is coming in from |
| 248 | filteredCriteria.add(Criteria.matchInPort(outPort)); |
| 249 | |
| 250 | for (FlowEntry entry: dstFlowTable) { |
| 251 | if (ignoredFlows.contains(entry)) { |
| 252 | continue; |
| 253 | } |
| 254 | if (filteredCriteria.containsAll(entry.selector().criteria())) { |
| 255 | dfs(entry); |
| 256 | |
| 257 | if (!"Black Hole".equals(label.get(entry))) { |
| 258 | //this entry is "live" i.e not a black hole |
| 259 | pointsToLiveEntry = true; |
| 260 | } |
| 261 | } |
| 262 | } |
| 263 | return pointsToLiveEntry; |
| 264 | } |
| 265 | public String flowEntryRepresentation(FlowEntry flow) { |
| 266 | return "Device: " + flow.deviceId() + ", " + flow.selector().criteria() + ", " + flow.treatment().immediate(); |
| 267 | } |
Thomas Vachuska | 9c9ff7c | 2015-07-20 10:38:59 -0700 | [diff] [blame] | 268 | } |