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