Xin Jin | 313708b | 2015-07-09 13:43:04 -0700 | [diff] [blame] | 1 | /* |
Brian O'Connor | 5ab426f | 2016-04-09 01:19:45 -0700 | [diff] [blame^] | 2 | * Copyright 2015-present Open Networking Laboratory |
Xin Jin | 313708b | 2015-07-09 13:43:04 -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.net.flowobjective.impl.composition; |
| 17 | |
| 18 | import org.onosproject.net.flowobjective.FilteringObjective; |
| 19 | import org.onosproject.net.flowobjective.ForwardingObjective; |
| 20 | import org.onosproject.net.flowobjective.NextObjective; |
| 21 | |
| 22 | import java.util.ArrayList; |
| 23 | import java.util.Collection; |
| 24 | import java.util.List; |
| 25 | |
| 26 | /** |
| 27 | * Provides a policy tree to store all flow tables for each device. |
| 28 | * |
| 29 | * Note: This class uses in-memory structures and is not yet distributed. |
| 30 | */ |
| 31 | public class FlowObjectiveCompositionTree { |
| 32 | |
| 33 | public FlowObjectiveCompositionManager.PolicyOperator operator; |
| 34 | public FlowObjectiveCompositionTree leftChild; |
| 35 | public FlowObjectiveCompositionTree rightChild; |
| 36 | public short applicationId; |
| 37 | protected FilterTable filterTable; |
| 38 | protected ForwardTable forwardTable; |
| 39 | protected NextTable nextTable; |
| 40 | |
| 41 | protected int priorityMultiplier; |
| 42 | protected int priorityAddend; |
| 43 | |
| 44 | public FlowObjectiveCompositionTree(short applicationId) { |
| 45 | this.operator = FlowObjectiveCompositionManager.PolicyOperator.Application; |
| 46 | this.leftChild = null; |
| 47 | this.rightChild = null; |
| 48 | this.applicationId = applicationId; |
| 49 | this.filterTable = new FilterTable(); |
| 50 | this.forwardTable = new ForwardTable(); |
| 51 | this.nextTable = new NextTable(); |
| 52 | this.priorityMultiplier = 10; |
| 53 | this.priorityAddend = 10; |
| 54 | } |
| 55 | |
| 56 | public FlowObjectiveCompositionTree(Character ch) { |
| 57 | switch (ch) { |
| 58 | case '+': |
| 59 | this.operator = FlowObjectiveCompositionManager.PolicyOperator.Parallel; |
| 60 | break; |
| 61 | case '>': |
| 62 | this.operator = FlowObjectiveCompositionManager.PolicyOperator.Sequential; |
| 63 | break; |
| 64 | case '/': |
| 65 | this.operator = FlowObjectiveCompositionManager.PolicyOperator.Override; |
| 66 | break; |
| 67 | default: |
| 68 | this.operator = FlowObjectiveCompositionManager.PolicyOperator.Application; |
| 69 | break; |
| 70 | } |
| 71 | this.leftChild = null; |
| 72 | this.rightChild = null; |
| 73 | this.applicationId = (short) -1; |
| 74 | this.filterTable = new FilterTable(); |
| 75 | this.forwardTable = new ForwardTable(); |
| 76 | this.nextTable = new NextTable(); |
| 77 | this.priorityMultiplier = 10; |
| 78 | this.priorityAddend = 10; |
| 79 | } |
| 80 | |
| 81 | protected List<FilteringObjective> updateFilter(FilteringObjective filteringObjective) { |
| 82 | switch (this.operator) { |
| 83 | case Parallel: |
| 84 | return updateFilterParallel(filteringObjective); |
| 85 | case Sequential: |
| 86 | return updateFilterSequential(filteringObjective); |
| 87 | case Override: |
| 88 | return updateFilterOverride(filteringObjective); |
| 89 | case Application: |
| 90 | if (filteringObjective.appId().id() == this.applicationId) { |
| 91 | return this.filterTable.updateFilter(filteringObjective); |
| 92 | } else { |
| 93 | return new ArrayList<>(); |
| 94 | } |
| 95 | default: |
| 96 | return new ArrayList<>(); |
| 97 | } |
| 98 | } |
| 99 | |
| 100 | // Parallel composition: the filter set is the union of the children |
| 101 | protected List<FilteringObjective> updateFilterParallel(FilteringObjective filteringObjective) { |
| 102 | List<FilteringObjective> leftUpdates = this.leftChild.updateFilter(filteringObjective); |
| 103 | List<FilteringObjective> rightUpdates = this.rightChild.updateFilter(filteringObjective); |
| 104 | |
| 105 | List<FilteringObjective> updates = new ArrayList<>(); |
| 106 | updates.addAll(leftUpdates); |
| 107 | updates.addAll(rightUpdates); |
| 108 | |
| 109 | return this.filterTable.updateFilter(updates); |
| 110 | } |
| 111 | |
| 112 | // Sequential composition: the filter set is the filter set of the left child |
| 113 | protected List<FilteringObjective> updateFilterSequential(FilteringObjective filteringObjective) { |
| 114 | List<FilteringObjective> leftUpdates = this.leftChild.updateFilter(filteringObjective); |
| 115 | List<FilteringObjective> rightUpdates = this.rightChild.updateFilter(filteringObjective); |
| 116 | return this.filterTable.updateFilter(leftUpdates); |
| 117 | } |
| 118 | |
| 119 | // Override composition: the filter set is the filter set of the left child |
| 120 | protected List<FilteringObjective> updateFilterOverride(FilteringObjective filteringObjective) { |
| 121 | List<FilteringObjective> leftUpdates = this.leftChild.updateFilter(filteringObjective); |
| 122 | List<FilteringObjective> rightUpdates = this.rightChild.updateFilter(filteringObjective); |
| 123 | return this.filterTable.updateFilter(leftUpdates); |
| 124 | } |
| 125 | |
| 126 | public List<ForwardingObjective> updateForward(ForwardingObjective forwardingObjective) { |
| 127 | return this.updateForwardNode(forwardingObjective).toForwardingObjectiveList(); |
| 128 | } |
| 129 | |
| 130 | public ForwardUpdateTable updateForwardNode(ForwardingObjective forwardingObjective) { |
| 131 | switch (this.operator) { |
| 132 | case Parallel: |
| 133 | case Sequential: |
| 134 | case Override: |
| 135 | return updateForwardComposition(forwardingObjective); |
| 136 | case Application: |
| 137 | if (forwardingObjective.appId().id() == this.applicationId) { |
| 138 | return this.forwardTable.updateForward(forwardingObjective); |
| 139 | } else { |
| 140 | return (new ForwardUpdateTable()); |
| 141 | } |
| 142 | default: |
| 143 | return (new ForwardUpdateTable()); |
| 144 | } |
| 145 | } |
| 146 | |
| 147 | protected ForwardUpdateTable updateForwardComposition(ForwardingObjective forwardingObjective) { |
| 148 | ForwardUpdateTable leftUpdates = this.leftChild.updateForwardNode(forwardingObjective); |
| 149 | ForwardUpdateTable rightUpdates = this.rightChild.updateForwardNode(forwardingObjective); |
| 150 | |
| 151 | List<ForwardingObjective> addUpdates = new ArrayList<>(); |
| 152 | List<ForwardingObjective> removeUpdates = new ArrayList<>(); |
| 153 | // Handle ADD |
| 154 | if (this.operator == FlowObjectiveCompositionManager.PolicyOperator.Parallel |
| 155 | || this.operator == FlowObjectiveCompositionManager.PolicyOperator.Sequential) { |
| 156 | for (ForwardingObjective fo1 : leftUpdates.addObjectives) { |
| 157 | for (ForwardingObjective fo2 : this.rightChild.forwardTable.getForwardingObjectives()) { |
| 158 | ForwardingObjective composedFo = null; |
| 159 | if (this.operator == FlowObjectiveCompositionManager.PolicyOperator.Parallel) { |
| 160 | composedFo = FlowObjectiveCompositionUtil.composeParallel(fo1, fo2); |
| 161 | } else { |
| 162 | composedFo = FlowObjectiveCompositionUtil.composeSequential(fo1, fo2, this.priorityMultiplier); |
| 163 | } |
| 164 | if (composedFo != null) { |
| 165 | addUpdates.add(composedFo); |
| 166 | this.leftChild.forwardTable.addGeneratedParentForwardingObjective(fo1, composedFo); |
| 167 | this.rightChild.forwardTable.addGeneratedParentForwardingObjective(fo2, composedFo); |
| 168 | } |
| 169 | } |
| 170 | } |
| 171 | Collection<ForwardingObjective> leftTableWithoutAdd = FlowObjectiveCompositionUtil |
| 172 | .minusForwardingObjectives(this.leftChild.forwardTable.getForwardingObjectives(), |
| 173 | leftUpdates.addObjectives); |
| 174 | for (ForwardingObjective fo1 : leftTableWithoutAdd) { |
| 175 | for (ForwardingObjective fo2 : rightUpdates.addObjectives) { |
| 176 | ForwardingObjective composedFo = null; |
| 177 | if (this.operator == FlowObjectiveCompositionManager.PolicyOperator.Parallel) { |
| 178 | composedFo = FlowObjectiveCompositionUtil.composeParallel(fo1, fo2); |
| 179 | } else { |
| 180 | composedFo = FlowObjectiveCompositionUtil.composeSequential(fo1, fo2, this.priorityMultiplier); |
| 181 | } |
| 182 | if (composedFo != null) { |
| 183 | addUpdates.add(composedFo); |
| 184 | this.leftChild.forwardTable.addGeneratedParentForwardingObjective(fo1, composedFo); |
| 185 | this.rightChild.forwardTable.addGeneratedParentForwardingObjective(fo2, composedFo); |
| 186 | } |
| 187 | } |
| 188 | } |
| 189 | } else { |
| 190 | for (ForwardingObjective fo : leftUpdates.addObjectives) { |
| 191 | ForwardingObjective composedFo = FlowObjectiveCompositionUtil.composeOverride(fo, this.priorityAddend); |
| 192 | addUpdates.add(composedFo); |
| 193 | this.leftChild.forwardTable.addGeneratedParentForwardingObjective(fo, composedFo); |
| 194 | } |
| 195 | for (ForwardingObjective fo : rightUpdates.addObjectives) { |
| 196 | ForwardingObjective composedFo = FlowObjectiveCompositionUtil.composeOverride(fo, 0); |
| 197 | addUpdates.add(composedFo); |
| 198 | this.rightChild.forwardTable.addGeneratedParentForwardingObjective(fo, composedFo); |
| 199 | } |
| 200 | } |
| 201 | |
| 202 | // Handle REMOVE |
| 203 | for (ForwardingObjective fo : leftUpdates.removeObjectives) { |
| 204 | List<ForwardingObjective> fos = this.leftChild.forwardTable |
| 205 | .getGeneratedParentForwardingObjectiveForRemove(fo); |
| 206 | removeUpdates.addAll(fos); |
| 207 | } |
| 208 | this.leftChild.forwardTable.deleteGeneratedParentForwardingObjective(leftUpdates.removeObjectives); |
| 209 | for (ForwardingObjective fo : rightUpdates.removeObjectives) { |
| 210 | List<ForwardingObjective> fos = this.rightChild.forwardTable |
| 211 | .getGeneratedParentForwardingObjectiveForRemove(fo); |
| 212 | removeUpdates.addAll(fos); |
| 213 | } |
| 214 | this.rightChild.forwardTable.deleteGeneratedParentForwardingObjective(rightUpdates.removeObjectives); |
| 215 | |
| 216 | ForwardUpdateTable updates = new ForwardUpdateTable(); |
| 217 | updates.addUpdateTable(this.forwardTable.updateForward(addUpdates)); |
| 218 | updates.addUpdateTable(this.forwardTable.updateForward(removeUpdates)); |
| 219 | return updates; |
| 220 | } |
| 221 | |
| 222 | public List<NextObjective> updateNext(NextObjective nextObjective) { |
| 223 | switch (this.operator) { |
| 224 | case Parallel: |
| 225 | case Sequential: |
| 226 | case Override: |
| 227 | return updateNextComposition(nextObjective); |
| 228 | case Application: |
| 229 | if (nextObjective.appId().id() == this.applicationId) { |
| 230 | return this.nextTable.updateNext(nextObjective); |
| 231 | } else { |
| 232 | return new ArrayList<>(); |
| 233 | } |
| 234 | default: |
| 235 | return new ArrayList<>(); |
| 236 | } |
| 237 | } |
| 238 | |
| 239 | // Next: the union of the children |
| 240 | protected List<NextObjective> updateNextComposition(NextObjective nextObjective) { |
| 241 | List<NextObjective> leftUpdates = this.leftChild.updateNext(nextObjective); |
| 242 | List<NextObjective> rightUpdates = this.rightChild.updateNext(nextObjective); |
| 243 | |
| 244 | List<NextObjective> updates = new ArrayList<>(); |
| 245 | updates.addAll(leftUpdates); |
| 246 | updates.addAll(rightUpdates); |
| 247 | |
| 248 | return this.nextTable.updateNext(updates); |
| 249 | } |
| 250 | |
| 251 | @Override |
| 252 | public String toString() { |
| 253 | String str = null; |
| 254 | switch (this.operator) { |
| 255 | case Parallel: |
| 256 | str = "(" + this.leftChild + "+" + this.rightChild + ")"; |
| 257 | break; |
| 258 | case Sequential: |
| 259 | str = "(" + this.leftChild + ">" + this.rightChild + ")"; |
| 260 | break; |
| 261 | case Override: |
| 262 | str = "(" + this.leftChild + "/" + this.rightChild + ")"; |
| 263 | break; |
| 264 | default: |
| 265 | str = " " + applicationId + " "; |
| 266 | break; |
| 267 | } |
| 268 | return str; |
| 269 | } |
| 270 | |
| 271 | } |