Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2016-present Open Networking Laboratory |
| 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 | |
| 17 | package org.onosproject.net.resource.impl; |
| 18 | |
| 19 | import com.google.common.collect.ImmutableList; |
| 20 | import com.google.common.collect.ImmutableMap; |
| 21 | import com.google.common.collect.Iterables; |
| 22 | import com.google.common.collect.Maps; |
| 23 | import com.google.common.collect.Sets; |
| 24 | import org.apache.commons.lang.math.RandomUtils; |
| 25 | import org.onlab.packet.MplsLabel; |
| 26 | import org.onlab.packet.VlanId; |
| 27 | import org.onlab.util.Identifier; |
| 28 | import org.onosproject.net.ConnectPoint; |
| 29 | import org.onosproject.net.EncapsulationType; |
| 30 | import org.onosproject.net.Link; |
| 31 | import org.onosproject.net.LinkKey; |
| 32 | import org.onosproject.net.intent.IntentId; |
| 33 | import org.onosproject.net.resource.Resource; |
| 34 | import org.onosproject.net.resource.ResourceAllocation; |
| 35 | import org.onosproject.net.resource.ResourceService; |
| 36 | import org.onosproject.net.resource.Resources; |
| 37 | |
Yuta HIGUCHI | 1f72203 | 2016-12-03 13:56:50 -0800 | [diff] [blame] | 38 | import static com.google.common.base.Preconditions.checkNotNull; |
| 39 | |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 40 | import java.util.Collections; |
| 41 | import java.util.List; |
| 42 | import java.util.Map; |
| 43 | import java.util.Set; |
| 44 | import java.util.stream.Collectors; |
| 45 | import java.util.stream.Stream; |
| 46 | |
| 47 | /** |
| 48 | * Helper class which interacts with the ResourceService and provides |
| 49 | * a unified API to allocate MPLS labels and VLAN Ids. |
| 50 | */ |
| 51 | public final class LabelAllocator { |
| 52 | |
| 53 | private enum Behavior { |
| 54 | /** |
| 55 | * Random selection. |
| 56 | */ |
| 57 | RANDOM, |
| 58 | /** |
| 59 | * First fit selection. |
| 60 | */ |
| 61 | FIRST_FIT |
| 62 | } |
| 63 | |
| 64 | private static final Behavior[] BEHAVIORS = Behavior.values(); |
| 65 | |
| 66 | private ResourceService resourceService; |
| 67 | private LabelSelection labelSelection; |
| 68 | |
| 69 | /** |
| 70 | * Creates a new label allocator. Random is the |
| 71 | * default behavior. |
| 72 | * |
| 73 | * @param rs the resource service |
| 74 | */ |
| 75 | public LabelAllocator(ResourceService rs) { |
Yuta HIGUCHI | 1f72203 | 2016-12-03 13:56:50 -0800 | [diff] [blame] | 76 | this.resourceService = checkNotNull(rs); |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 77 | this.labelSelection = this.getLabelSelection(Behavior.RANDOM); |
| 78 | } |
| 79 | |
| 80 | /** |
| 81 | * Checks if a given string is a valid Behavior. |
| 82 | * |
| 83 | * @param value the string to check |
| 84 | * @return true if value is a valid Behavior, false otherwise |
| 85 | */ |
| 86 | public static boolean isInEnum(String value) { |
| 87 | for (Behavior b : BEHAVIORS) { |
| 88 | if (b.name().equals(value)) { |
| 89 | return true; |
| 90 | } |
| 91 | } |
| 92 | return false; |
| 93 | } |
| 94 | |
| 95 | /** |
| 96 | * Changes the selection behavior. |
| 97 | * |
| 98 | * @param type the behavior type |
| 99 | */ |
| 100 | public void setLabelSelection(String type) { |
| 101 | if (isInEnum(type)) { |
| 102 | this.labelSelection = this.getLabelSelection(type); |
| 103 | } |
| 104 | } |
| 105 | |
| 106 | /** |
| 107 | * Retrieves the label selection behavior. |
| 108 | * |
| 109 | * @return the label selection behavior in use |
| 110 | */ |
| 111 | public LabelSelection getLabelSelection() { |
| 112 | return this.labelSelection; |
| 113 | } |
| 114 | |
| 115 | /** |
| 116 | * Returns the label selection behavior, given a behavior type. |
| 117 | * |
| 118 | * @param type the behavior type |
| 119 | * @return the label selection behavior in use |
| 120 | */ |
| 121 | private LabelSelection getLabelSelection(String type) { |
| 122 | Behavior behavior = Behavior.valueOf(type); |
| 123 | return this.getLabelSelection(behavior); |
| 124 | } |
| 125 | |
| 126 | /** |
| 127 | * Creates a new LabelSelection. Random is |
| 128 | * the default label selection behavior. |
| 129 | * |
| 130 | * @param type the behavior type |
| 131 | * @return the object implementing the behavior |
| 132 | */ |
| 133 | private LabelSelection getLabelSelection(Behavior type) { |
| 134 | LabelSelection selection = null; |
| 135 | switch (type) { |
| 136 | case FIRST_FIT: |
| 137 | selection = new FirstFitSelection(); |
| 138 | break; |
| 139 | case RANDOM: |
| 140 | default: |
| 141 | selection = new RandomSelection(); |
| 142 | break; |
| 143 | } |
| 144 | return selection; |
| 145 | } |
| 146 | |
| 147 | /** |
| 148 | * Looks for available Ids. |
| 149 | * |
| 150 | * @param links the links where to look for Ids |
| 151 | * @param type the encapsulation type |
| 152 | * @return the mappings between key and id |
| 153 | */ |
| 154 | private Map<LinkKey, Identifier<?>> findAvailableIDs(Set<LinkKey> links, EncapsulationType type) { |
| 155 | |
| 156 | Map<LinkKey, Identifier<?>> ids = Maps.newHashMap(); |
| 157 | for (LinkKey link : links) { |
| 158 | Set<Identifier<?>> availableIDsatSrc = getAvailableIDs(link.src(), type); |
| 159 | Set<Identifier<?>> availableIDsatDst = getAvailableIDs(link.dst(), type); |
| 160 | Set<Identifier<?>> common = Sets.intersection(availableIDsatSrc, availableIDsatDst); |
| 161 | if (common.isEmpty()) { |
| 162 | continue; |
| 163 | } |
| 164 | Identifier<?> selected = labelSelection.select(common); |
| 165 | if (selected == null) { |
| 166 | continue; |
| 167 | } |
| 168 | ids.put(link, selected); |
| 169 | } |
| 170 | return ids; |
| 171 | } |
| 172 | |
| 173 | /** |
| 174 | * Looks for available Ids associated to the given connection point. |
| 175 | * |
| 176 | * @param cp the connection point |
| 177 | * @param type the type of Id |
| 178 | * @return the set of available Ids |
| 179 | */ |
| 180 | private Set<Identifier<?>> getAvailableIDs(ConnectPoint cp, EncapsulationType type) { |
| 181 | return resourceService.getAvailableResourceValues( |
| 182 | Resources.discrete(cp.deviceId(), cp.port()).id(), getEncapsulationClass(type) |
| 183 | ); |
| 184 | } |
| 185 | |
| 186 | /** |
| 187 | * Method to map the encapsulation type to identifier class. |
| 188 | * VLAN is the default encapsulation. |
| 189 | * |
| 190 | * @param type the type of encapsulation |
| 191 | * @return the id class |
| 192 | */ |
| 193 | private Class getEncapsulationClass(EncapsulationType type) { |
| 194 | Class idType; |
| 195 | switch (type) { |
| 196 | case MPLS: |
| 197 | idType = MplsLabel.class; |
| 198 | break; |
| 199 | case VLAN: |
| 200 | default: |
| 201 | idType = VlanId.class; |
| 202 | } |
| 203 | return idType; |
| 204 | } |
| 205 | |
| 206 | /** |
| 207 | * Allocates labels and associates them to links. |
| 208 | * |
| 209 | * @param links the links where labels will be allocated |
| 210 | * @param id the intent Id |
| 211 | * @param type the encapsulation type |
| 212 | * @return the list of links and associated labels |
| 213 | */ |
| 214 | public Map<LinkKey, Identifier<?>> assignLabelToLinks(Set<Link> links, IntentId id, EncapsulationType type) { |
| 215 | |
Sho SHIMIZU | 4c7fcdf | 2016-12-22 11:17:43 -0800 | [diff] [blame] | 216 | Set<LinkKey> linkRequest = links.stream() |
| 217 | .map(LinkKey::linkKey) |
| 218 | .collect(Collectors.toSet()); |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 219 | |
| 220 | Map<LinkKey, Identifier<?>> availableIds = findAvailableIDs(linkRequest, type); |
| 221 | if (availableIds.isEmpty()) { |
| 222 | return Collections.emptyMap(); |
| 223 | } |
| 224 | |
| 225 | Set<Resource> resources = availableIds.entrySet().stream() |
| 226 | .flatMap(x -> Stream.of( |
| 227 | Resources.discrete( |
| 228 | x.getKey().src().deviceId(), |
| 229 | x.getKey().src().port(), |
| 230 | x.getValue() |
| 231 | ).resource(), |
| 232 | Resources.discrete( |
| 233 | x.getKey().dst().deviceId(), |
| 234 | x.getKey().dst().port(), |
| 235 | x.getValue() |
| 236 | ).resource() |
| 237 | )) |
| 238 | .collect(Collectors.toSet()); |
| 239 | |
| 240 | List<ResourceAllocation> allocations = resourceService.allocate(id, ImmutableList.copyOf(resources)); |
| 241 | |
| 242 | if (allocations.isEmpty()) { |
| 243 | return Collections.emptyMap(); |
| 244 | } |
| 245 | |
| 246 | return ImmutableMap.copyOf(availableIds); |
| 247 | } |
| 248 | |
| 249 | /** |
| 250 | * Allocates labels and associates them to source |
| 251 | * and destination ports of a link. |
| 252 | * |
| 253 | * @param links the links on which labels will be reserved |
| 254 | * @param id the intent Id |
| 255 | * @param type the encapsulation type |
| 256 | * @return the list of ports and associated labels |
| 257 | */ |
| 258 | public Map<ConnectPoint, Identifier<?>> assignLabelToPorts(Set<Link> links, IntentId id, EncapsulationType type) { |
| 259 | Map<LinkKey, Identifier<?>> allocation = this.assignLabelToLinks(links, id, type); |
| 260 | if (allocation.isEmpty()) { |
| 261 | return Collections.emptyMap(); |
| 262 | } |
| 263 | Map<ConnectPoint, Identifier<?>> finalAllocation = Maps.newHashMap(); |
| 264 | allocation.forEach((key, value) -> { |
| 265 | finalAllocation.putIfAbsent(key.src(), value); |
| 266 | finalAllocation.putIfAbsent(key.dst(), value); |
| 267 | }); |
| 268 | return ImmutableMap.copyOf(finalAllocation); |
| 269 | } |
| 270 | |
| 271 | /** |
| 272 | * Interface for selection algorithms of the labels. |
| 273 | */ |
| 274 | public interface LabelSelection { |
| 275 | |
| 276 | /** |
| 277 | * Picks an element from values using a particular algorithm. |
| 278 | * |
| 279 | * @param values the values to select from |
| 280 | * @return the selected identifier if values are present, null otherwise |
| 281 | */ |
| 282 | Identifier<?> select(Set<Identifier<?>> values); |
| 283 | |
| 284 | } |
| 285 | |
| 286 | /** |
| 287 | * Random label selection. |
| 288 | */ |
| 289 | public static class RandomSelection implements LabelSelection { |
| 290 | |
| 291 | /** |
| 292 | * Selects an identifier from a given set of values using |
| 293 | * the random selection algorithm. |
| 294 | * |
| 295 | * @param values the values to select from |
| 296 | * @return the selected identifier if values are present, null otherwise |
| 297 | */ |
| 298 | @Override |
| 299 | public Identifier<?> select(Set<Identifier<?>> values) { |
| 300 | if (!values.isEmpty()) { |
| 301 | int size = values.size(); |
| 302 | int index = RandomUtils.nextInt(size); |
| 303 | return Iterables.get(values, index); |
| 304 | } |
| 305 | return null; |
| 306 | } |
| 307 | } |
| 308 | |
| 309 | /** |
| 310 | * First fit label selection. |
| 311 | */ |
| 312 | public static class FirstFitSelection implements LabelSelection { |
| 313 | |
| 314 | /** |
| 315 | * Selects an identifier from a given set of values using |
| 316 | * the first fir selection algorithm. |
| 317 | * |
| 318 | * @param values the values to select from |
| 319 | * @return the selected identifier if values are present, null otherwise. |
| 320 | */ |
| 321 | @Override |
| 322 | public Identifier<?> select(Set<Identifier<?>> values) { |
| 323 | if (!values.isEmpty()) { |
| 324 | return values.iterator().next(); |
| 325 | } |
| 326 | return null; |
| 327 | } |
| 328 | } |
| 329 | |
| 330 | } |