diff options
Diffstat (limited to 'framework/src/onos/core/net/src/main/java/org/onosproject/net/flowobjective/impl/composition/FlowObjectiveCompositionUtil.java')
| -rw-r--r-- | framework/src/onos/core/net/src/main/java/org/onosproject/net/flowobjective/impl/composition/FlowObjectiveCompositionUtil.java | 488 |
1 files changed, 488 insertions, 0 deletions
diff --git a/framework/src/onos/core/net/src/main/java/org/onosproject/net/flowobjective/impl/composition/FlowObjectiveCompositionUtil.java b/framework/src/onos/core/net/src/main/java/org/onosproject/net/flowobjective/impl/composition/FlowObjectiveCompositionUtil.java new file mode 100644 index 00000000..137aca1e --- /dev/null +++ b/framework/src/onos/core/net/src/main/java/org/onosproject/net/flowobjective/impl/composition/FlowObjectiveCompositionUtil.java @@ -0,0 +1,488 @@ +/* + * Copyright 2015 Open Networking Laboratory + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.onosproject.net.flowobjective.impl.composition; + +import org.onlab.packet.IpPrefix; +import org.onosproject.net.flow.DefaultTrafficSelector; +import org.onosproject.net.flow.DefaultTrafficTreatment; +import org.onosproject.net.flow.TrafficSelector; +import org.onosproject.net.flow.TrafficTreatment; +import org.onosproject.net.flow.criteria.Criterion; +import org.onosproject.net.flow.criteria.LambdaCriterion; +import org.onosproject.net.flow.criteria.OchSignalCriterion; +import org.onosproject.net.flow.criteria.EthCriterion; +import org.onosproject.net.flow.criteria.VlanIdCriterion; +import org.onosproject.net.flow.criteria.VlanPcpCriterion; +import org.onosproject.net.flow.criteria.MplsCriterion; +import org.onosproject.net.flow.criteria.IPCriterion; +import org.onosproject.net.flow.criteria.IPv6FlowLabelCriterion; +import org.onosproject.net.flow.criteria.Criteria; +import org.onosproject.net.flow.instructions.Instruction; +import org.onosproject.net.flow.instructions.L0ModificationInstruction; +import org.onosproject.net.flow.instructions.L2ModificationInstruction; +import org.onosproject.net.flow.instructions.L3ModificationInstruction; +import org.onosproject.net.flowobjective.DefaultForwardingObjective; +import org.onosproject.net.flowobjective.ForwardingObjective; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.HashMap; +import java.util.HashSet; +import java.util.List; +import java.util.Map; +import java.util.Set; +import java.util.Stack; + +/** + * Provide util functions for FlowObjectiveComposition. + */ +public final class FlowObjectiveCompositionUtil { + + private FlowObjectiveCompositionUtil() {} + + // only work with VERSATILE + public static ForwardingObjective composeParallel(ForwardingObjective fo1, ForwardingObjective fo2) { + + TrafficSelector trafficSelector = intersectTrafficSelector(fo1.selector(), fo2.selector()); + if (trafficSelector == null) { + return null; + } + + TrafficTreatment trafficTreatment = unionTrafficTreatment(fo1.treatment(), fo2.treatment()); + + return DefaultForwardingObjective.builder() + .fromApp(fo1.appId()) + .makePermanent() + .withFlag(ForwardingObjective.Flag.VERSATILE) + .withPriority(fo1.priority() + fo2.priority()) + .withSelector(trafficSelector) + .withTreatment(trafficTreatment) + .add(); + } + + public static ForwardingObjective composeSequential(ForwardingObjective fo1, + ForwardingObjective fo2, + int priorityMultiplier) { + + TrafficSelector revertTrafficSelector = revertTreatmentSelector(fo1.treatment(), fo2.selector()); + if (revertTrafficSelector == null) { + return null; + } + + TrafficSelector trafficSelector = intersectTrafficSelector(fo1.selector(), revertTrafficSelector); + if (trafficSelector == null) { + return null; + } + + TrafficTreatment trafficTreatment = unionTrafficTreatment(fo1.treatment(), fo2.treatment()); + + return DefaultForwardingObjective.builder() + .fromApp(fo1.appId()) + .makePermanent() + .withFlag(ForwardingObjective.Flag.VERSATILE) + .withPriority(fo1.priority() * priorityMultiplier + fo2.priority()) + .withSelector(trafficSelector) + .withTreatment(trafficTreatment) + .add(); + } + + public static ForwardingObjective composeOverride(ForwardingObjective fo, int priorityAddend) { + return DefaultForwardingObjective.builder() + .fromApp(fo.appId()) + .makePermanent() + .withFlag(fo.flag()) + .withPriority(fo.priority() + priorityAddend) + .withSelector(fo.selector()) + .withTreatment(fo.treatment()) + .add(); + } + + public static TrafficSelector intersectTrafficSelector(TrafficSelector ts1, TrafficSelector ts2) { + + TrafficSelector.Builder selectorBuilder = DefaultTrafficSelector.builder(); + + Set<Criterion.Type> ts1IntersectTs2 = getTypeSet(ts1); + ts1IntersectTs2.retainAll(getTypeSet(ts2)); + for (Criterion.Type type : ts1IntersectTs2) { + Criterion criterion = intersectCriterion(ts1.getCriterion(type), ts2.getCriterion(type)); + if (criterion == null) { + return null; + } else { + selectorBuilder.add(criterion); + } + } + + Set<Criterion.Type> ts1MinusTs2 = getTypeSet(ts1); + ts1MinusTs2.removeAll(getTypeSet(ts2)); + for (Criterion.Type type : ts1MinusTs2) { + selectorBuilder.add(ts1.getCriterion(type)); + } + + Set<Criterion.Type> ts2MinusTs1 = getTypeSet(ts2); + ts2MinusTs1.removeAll(getTypeSet(ts1)); + for (Criterion.Type type : ts2MinusTs1) { + selectorBuilder.add(ts2.getCriterion(type)); + } + + return selectorBuilder.build(); + } + + public static TrafficTreatment unionTrafficTreatment(TrafficTreatment tt1, TrafficTreatment tt2) { + + TrafficTreatment.Builder treatmentBuilder = DefaultTrafficTreatment.builder(); + + for (Instruction instruction : tt1.allInstructions()) { + treatmentBuilder.add(instruction); + } + + for (Instruction instruction : tt2.allInstructions()) { + treatmentBuilder.add(instruction); + } + + return treatmentBuilder.build(); + } + + public static TrafficSelector revertTreatmentSelector(TrafficTreatment trafficTreatment, + TrafficSelector trafficSelector) { + + TrafficSelector.Builder selectorBuilder = DefaultTrafficSelector.builder(); + + Map<Criterion.Type, Criterion> criterionMap = new HashMap<>(); + for (Criterion criterion : trafficSelector.criteria()) { + criterionMap.put(criterion.type(), criterion); + } + + for (Instruction instruction : trafficTreatment.allInstructions()) { + switch (instruction.type()) { + case DROP: + return null; + case OUTPUT: + break; + case GROUP: + break; + case L0MODIFICATION: { + L0ModificationInstruction l0 = (L0ModificationInstruction) instruction; + switch (l0.subtype()) { + case LAMBDA: + if (criterionMap.containsKey(Criterion.Type.OCH_SIGID)) { + if (((LambdaCriterion) criterionMap.get((Criterion.Type.OCH_SIGID))).lambda() + == ((L0ModificationInstruction.ModLambdaInstruction) l0).lambda()) { + criterionMap.remove(Criterion.Type.OCH_SIGID); + } else { + return null; + } + } else { + break; + } + case OCH: + if (criterionMap.containsKey(Criterion.Type.OCH_SIGID)) { + if (((OchSignalCriterion) criterionMap.get((Criterion.Type.OCH_SIGID))).lambda() + .equals(((L0ModificationInstruction.ModOchSignalInstruction) l0).lambda())) { + criterionMap.remove(Criterion.Type.OCH_SIGID); + } else { + return null; + } + } else { + break; + } + default: + break; + } + break; + } + case L2MODIFICATION: { + L2ModificationInstruction l2 = (L2ModificationInstruction) instruction; + switch (l2.subtype()) { + case ETH_SRC: + if (criterionMap.containsKey(Criterion.Type.ETH_SRC)) { + if (((EthCriterion) criterionMap.get((Criterion.Type.ETH_SRC))).mac() + .equals(((L2ModificationInstruction.ModEtherInstruction) l2).mac())) { + criterionMap.remove(Criterion.Type.ETH_SRC); + } else { + return null; + } + } else { + break; + } + case ETH_DST: + if (criterionMap.containsKey(Criterion.Type.ETH_DST)) { + if (((EthCriterion) criterionMap.get((Criterion.Type.ETH_DST))).mac() + .equals(((L2ModificationInstruction.ModEtherInstruction) l2).mac())) { + criterionMap.remove(Criterion.Type.ETH_DST); + } else { + return null; + } + } else { + break; + } + case VLAN_ID: + if (criterionMap.containsKey(Criterion.Type.VLAN_VID)) { + if (((VlanIdCriterion) criterionMap.get((Criterion.Type.VLAN_VID))).vlanId() + .equals(((L2ModificationInstruction.ModVlanIdInstruction) l2).vlanId())) { + criterionMap.remove(Criterion.Type.VLAN_VID); + } else { + return null; + } + } else { + break; + } + case VLAN_PCP: + if (criterionMap.containsKey(Criterion.Type.VLAN_PCP)) { + if (((VlanPcpCriterion) criterionMap.get((Criterion.Type.VLAN_PCP))).priority() + == ((L2ModificationInstruction.ModVlanPcpInstruction) l2).vlanPcp()) { + criterionMap.remove(Criterion.Type.VLAN_PCP); + } else { + return null; + } + } else { + break; + } + case MPLS_LABEL: + if (criterionMap.containsKey(Criterion.Type.MPLS_LABEL)) { + if (((MplsCriterion) criterionMap.get((Criterion.Type.MPLS_LABEL))).label() + .equals(((L2ModificationInstruction.ModMplsLabelInstruction) l2).mplsLabel())) { + criterionMap.remove(Criterion.Type.ETH_DST); + } else { + return null; + } + } else { + break; + } + default: + break; + } + break; + } + case TABLE: + break; + case L3MODIFICATION: { + L3ModificationInstruction l3 = (L3ModificationInstruction) instruction; + switch (l3.subtype()) { + case IPV4_SRC: + if (criterionMap.containsKey(Criterion.Type.IPV4_SRC)) { + if (((IPCriterion) criterionMap.get(Criterion.Type.IPV4_SRC)).ip() + .contains(((L3ModificationInstruction.ModIPInstruction) l3).ip())) { + criterionMap.remove(Criterion.Type.IPV4_SRC); + } else { + return null; + } + } else { + break; + } + case IPV4_DST: + if (criterionMap.containsKey(Criterion.Type.IPV4_DST)) { + if (((IPCriterion) criterionMap.get(Criterion.Type.IPV4_DST)).ip() + .contains(((L3ModificationInstruction.ModIPInstruction) l3).ip())) { + criterionMap.remove(Criterion.Type.IPV4_DST); + } else { + return null; + } + } else { + break; + } + case IPV6_SRC: + if (criterionMap.containsKey(Criterion.Type.IPV6_SRC)) { + if (((IPCriterion) criterionMap.get(Criterion.Type.IPV6_SRC)).ip() + .contains(((L3ModificationInstruction.ModIPInstruction) l3).ip())) { + criterionMap.remove(Criterion.Type.IPV6_SRC); + } else { + return null; + } + } else { + break; + } + case IPV6_DST: + if (criterionMap.containsKey(Criterion.Type.IPV6_DST)) { + if (((IPCriterion) criterionMap.get(Criterion.Type.IPV6_DST)).ip() + .contains(((L3ModificationInstruction.ModIPInstruction) l3).ip())) { + criterionMap.remove(Criterion.Type.IPV6_DST); + } else { + return null; + } + } else { + break; + } + case IPV6_FLABEL: + if (criterionMap.containsKey(Criterion.Type.IPV6_FLABEL)) { + if (((IPv6FlowLabelCriterion) criterionMap.get(Criterion.Type.IPV6_FLABEL)).flowLabel() + == (((L3ModificationInstruction.ModIPv6FlowLabelInstruction) l3).flowLabel())) { + criterionMap.remove(Criterion.Type.IPV4_SRC); + } else { + return null; + } + } else { + break; + } + default: + break; + } + break; + } + case METADATA: + break; + default: + break; + } + } + + for (Criterion criterion : criterionMap.values()) { + selectorBuilder.add(criterion); + } + + return selectorBuilder.build(); + } + + public static Set<Criterion.Type> getTypeSet(TrafficSelector trafficSelector) { + Set<Criterion.Type> typeSet = new HashSet<>(); + for (Criterion criterion : trafficSelector.criteria()) { + typeSet.add(criterion.type()); + } + return typeSet; + } + + public static Criterion intersectCriterion(Criterion c1, Criterion c2) { + switch (c1.type()) { + case IPV4_SRC: { + IpPrefix ipPrefix = intersectIpPrefix(((IPCriterion) c1).ip(), ((IPCriterion) c2).ip()); + if (ipPrefix == null) { + return null; + } else { + return Criteria.matchIPSrc(ipPrefix); + } + } + case IPV4_DST: { + IpPrefix ipPrefix = intersectIpPrefix(((IPCriterion) c1).ip(), ((IPCriterion) c2).ip()); + if (ipPrefix == null) { + return null; + } else { + return Criteria.matchIPDst(ipPrefix); + } + } + case IPV6_SRC: { + IpPrefix ipPrefix = intersectIpPrefix(((IPCriterion) c1).ip(), ((IPCriterion) c2).ip()); + if (ipPrefix == null) { + return null; + } else { + return Criteria.matchIPv6Src(ipPrefix); + } + } + case IPV6_DST: { + IpPrefix ipPrefix = intersectIpPrefix(((IPCriterion) c1).ip(), ((IPCriterion) c2).ip()); + if (ipPrefix == null) { + return null; + } else { + return Criteria.matchIPv6Dst(ipPrefix); + } + } + default: + if (!c1.equals(c2)) { + return null; + } else { + return c1; + } + } + } + + public static IpPrefix intersectIpPrefix(IpPrefix ip1, IpPrefix ip2) { + if (ip1.contains(ip2)) { + return ip1; + } else if (ip2.contains(ip1)) { + return ip2; + } else { + return null; + } + } + + public static FlowObjectiveCompositionTree parsePolicyString(String policy) { + List<FlowObjectiveCompositionTree> postfix = transformToPostfixForm(policy); + return buildPolicyTree(postfix); + } + + private static List<FlowObjectiveCompositionTree> transformToPostfixForm(String policy) { + Stack<Character> stack = new Stack<>(); + List<FlowObjectiveCompositionTree> postfix = new ArrayList<>(); + + for (int i = 0; i < policy.length(); i++) { + Character ch = policy.charAt(i); + if (Character.isDigit(ch)) { + + int applicationId = ch - '0'; + while (i + 1 < policy.length() && Character.isDigit(policy.charAt(i + 1))) { + i++; + applicationId = applicationId * 10 + policy.charAt(i) - '0'; + } + + postfix.add(new FlowObjectiveCompositionTree((short) applicationId)); + } else if (ch == '(') { + stack.push(ch); + } else if (ch == ')') { + while (stack.peek() != '(') { + postfix.add(new FlowObjectiveCompositionTree(stack.pop())); + } + stack.pop(); + } else { + while (!stack.isEmpty() && compareOperatorPriority(stack.peek(), ch)) { + postfix.add(new FlowObjectiveCompositionTree(stack.pop())); + } + stack.push(ch); + } + } + while (!stack.isEmpty()) { + postfix.add(new FlowObjectiveCompositionTree(stack.pop())); + } + + return postfix; + } + + private static boolean compareOperatorPriority(char peek, char cur) { + if (peek == '/' && (cur == '+' || cur == '>' || cur == '/')) { + return true; + } else if (peek == '>' && (cur == '+' || cur == '>')) { + return true; + } else if (peek == '+' && cur == '+') { + return true; + } + return false; + } + + private static FlowObjectiveCompositionTree buildPolicyTree(List<FlowObjectiveCompositionTree> postfix) { + Stack<FlowObjectiveCompositionTree> stack = new Stack<>(); + for (FlowObjectiveCompositionTree node : postfix) { + if (node.operator == FlowObjectiveCompositionManager.PolicyOperator.Application) { + stack.push(node); + } else { + node.rightChild = stack.pop(); + node.leftChild = stack.pop(); + stack.push(node); + } + } + return stack.pop(); + } + + public static Collection<ForwardingObjective> minusForwardingObjectives(Collection<ForwardingObjective> fo1, + Collection<ForwardingObjective> fo2) { + Map<Integer, ForwardingObjective> map = new HashMap<>(); + for (ForwardingObjective fo : fo1) { + map.put(fo.id(), fo); + } + for (ForwardingObjective fo : fo2) { + map.remove(fo.id()); + } + return map.values(); + } + + +} |