Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 1 | /* |
Brian O'Connor | a09fe5b | 2017-08-03 21:12:30 -0700 | [diff] [blame] | 2 | * Copyright 2016-present Open Networking Foundation |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -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 | |
| 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; |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 32 | import org.onosproject.net.resource.Resource; |
| 33 | import org.onosproject.net.resource.ResourceAllocation; |
Yi Tseng | 0db1f3b | 2017-05-25 10:08:06 -0700 | [diff] [blame] | 34 | import org.onosproject.net.resource.ResourceConsumer; |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 35 | import org.onosproject.net.resource.ResourceService; |
| 36 | import org.onosproject.net.resource.Resources; |
Pier Luigi | 0b4222e | 2017-07-21 09:47:14 +0200 | [diff] [blame] | 37 | import org.slf4j.Logger; |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 38 | |
Yuta HIGUCHI | 1f72203 | 2016-12-03 13:56:50 -0800 | [diff] [blame] | 39 | import static com.google.common.base.Preconditions.checkNotNull; |
Pier Luigi | 0b4222e | 2017-07-21 09:47:14 +0200 | [diff] [blame] | 40 | import static org.slf4j.LoggerFactory.getLogger; |
Yuta HIGUCHI | 1f72203 | 2016-12-03 13:56:50 -0800 | [diff] [blame] | 41 | |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 42 | import java.util.Collections; |
Pier Luigi | 0b4222e | 2017-07-21 09:47:14 +0200 | [diff] [blame] | 43 | import java.util.LinkedHashSet; |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 44 | import java.util.List; |
| 45 | import java.util.Map; |
| 46 | import java.util.Set; |
alessio | 225e2b0 | 2020-10-28 17:44:44 +0100 | [diff] [blame] | 47 | import java.util.Optional; |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 48 | import java.util.stream.Collectors; |
| 49 | import java.util.stream.Stream; |
| 50 | |
| 51 | /** |
| 52 | * Helper class which interacts with the ResourceService and provides |
| 53 | * a unified API to allocate MPLS labels and VLAN Ids. |
| 54 | */ |
| 55 | public final class LabelAllocator { |
| 56 | |
Pier Luigi | 0b4222e | 2017-07-21 09:47:14 +0200 | [diff] [blame] | 57 | private final Logger log = getLogger(getClass()); |
| 58 | |
| 59 | /** |
| 60 | * Defines possible behaviors for the selection of the labels. |
| 61 | */ |
| 62 | private enum SelectionBehavior { |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 63 | /** |
| 64 | * Random selection. |
| 65 | */ |
| 66 | RANDOM, |
| 67 | /** |
| 68 | * First fit selection. |
| 69 | */ |
| 70 | FIRST_FIT |
| 71 | } |
| 72 | |
Pier Luigi | 0b4222e | 2017-07-21 09:47:14 +0200 | [diff] [blame] | 73 | /** |
| 74 | * Defines possible optimizations for the selection of the labels. |
| 75 | */ |
| 76 | enum OptimizationBehavior { |
| 77 | /** |
| 78 | * Allocator does not try to optimize, it defines a new candidates |
| 79 | * set at each hop and select label according to the selection strategy. |
| 80 | */ |
| 81 | NONE, |
| 82 | /** |
| 83 | * Allocator enforces same label along the path, it builds a common |
| 84 | * set of candidate and select a common label according to the selection |
| 85 | * strategy. |
| 86 | */ |
| 87 | NO_SWAP, |
| 88 | /** |
| 89 | * Allocator try to minimize the swapping of labels along the path. If |
| 90 | * it is possible try to reuse the label of the previous hop. |
| 91 | */ |
| 92 | MIN_SWAP |
| 93 | } |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 94 | |
| 95 | private ResourceService resourceService; |
| 96 | private LabelSelection labelSelection; |
Pier Luigi | 0b4222e | 2017-07-21 09:47:14 +0200 | [diff] [blame] | 97 | private OptimizationBehavior optLabelSelection; |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 98 | |
| 99 | /** |
Pier Luigi | 0b4222e | 2017-07-21 09:47:14 +0200 | [diff] [blame] | 100 | * Creates a new label allocator. Random is the default selection behavior. |
| 101 | * None is the default optimization behavior |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 102 | * |
| 103 | * @param rs the resource service |
| 104 | */ |
| 105 | public LabelAllocator(ResourceService rs) { |
Yuta HIGUCHI | 1f72203 | 2016-12-03 13:56:50 -0800 | [diff] [blame] | 106 | this.resourceService = checkNotNull(rs); |
Pier Luigi | 0b4222e | 2017-07-21 09:47:14 +0200 | [diff] [blame] | 107 | this.labelSelection = this.getLabelSelection(SelectionBehavior.RANDOM); |
| 108 | this.optLabelSelection = OptimizationBehavior.NONE; |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 109 | } |
| 110 | |
| 111 | /** |
Pier Luigi | 0b4222e | 2017-07-21 09:47:14 +0200 | [diff] [blame] | 112 | * Checks if a given string is a valid Selection Behavior. |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 113 | * |
| 114 | * @param value the string to check |
Pier Luigi | 0b4222e | 2017-07-21 09:47:14 +0200 | [diff] [blame] | 115 | * @return true if value is a valid Selection Behavior, false otherwise |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 116 | */ |
Pier Luigi | 0b4222e | 2017-07-21 09:47:14 +0200 | [diff] [blame] | 117 | public static boolean isInSelEnum(String value) { |
| 118 | for (SelectionBehavior b : SelectionBehavior.values()) { |
| 119 | if (b.name().equals(value)) { |
| 120 | return true; |
| 121 | } |
| 122 | } |
| 123 | return false; |
| 124 | } |
| 125 | |
| 126 | /** |
| 127 | * Checks if a given string is a valid Optimization Behavior. |
| 128 | * |
| 129 | * @param value the string to check |
| 130 | * @return true if value is a valid Optimization Behavior, false otherwise |
| 131 | */ |
| 132 | public static boolean isInOptEnum(String value) { |
| 133 | for (OptimizationBehavior b : OptimizationBehavior.values()) { |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 134 | if (b.name().equals(value)) { |
| 135 | return true; |
| 136 | } |
| 137 | } |
| 138 | return false; |
| 139 | } |
| 140 | |
| 141 | /** |
| 142 | * Changes the selection behavior. |
| 143 | * |
| 144 | * @param type the behavior type |
| 145 | */ |
| 146 | public void setLabelSelection(String type) { |
Pier Luigi | 0b4222e | 2017-07-21 09:47:14 +0200 | [diff] [blame] | 147 | if (isInSelEnum(type)) { |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 148 | this.labelSelection = this.getLabelSelection(type); |
| 149 | } |
| 150 | } |
| 151 | |
| 152 | /** |
Pier Luigi | 0b4222e | 2017-07-21 09:47:14 +0200 | [diff] [blame] | 153 | * Retrieves the selection behavior. |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 154 | * |
Pier Luigi | 0b4222e | 2017-07-21 09:47:14 +0200 | [diff] [blame] | 155 | * @return the selection behavior in use |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 156 | */ |
| 157 | public LabelSelection getLabelSelection() { |
| 158 | return this.labelSelection; |
| 159 | } |
| 160 | |
| 161 | /** |
Pier Luigi | 0b4222e | 2017-07-21 09:47:14 +0200 | [diff] [blame] | 162 | * Changes the optimization behavior. |
| 163 | * |
| 164 | * @param type the optimization type |
| 165 | */ |
| 166 | public void setOptLabelSelection(String type) { |
| 167 | if (isInOptEnum(type)) { |
| 168 | this.optLabelSelection = OptimizationBehavior.valueOf(type); |
| 169 | } |
| 170 | } |
| 171 | |
| 172 | /** |
| 173 | * Retrieves the optimization behavior. |
| 174 | * |
| 175 | * @return the optimization behavior in use |
| 176 | */ |
| 177 | public OptimizationBehavior getOptLabelSelection() { |
| 178 | return this.optLabelSelection; |
| 179 | } |
| 180 | |
| 181 | /** |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 182 | * Returns the label selection behavior, given a behavior type. |
| 183 | * |
| 184 | * @param type the behavior type |
| 185 | * @return the label selection behavior in use |
| 186 | */ |
| 187 | private LabelSelection getLabelSelection(String type) { |
Pier Luigi | 0b4222e | 2017-07-21 09:47:14 +0200 | [diff] [blame] | 188 | SelectionBehavior behavior = SelectionBehavior.valueOf(type); |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 189 | return this.getLabelSelection(behavior); |
| 190 | } |
| 191 | |
| 192 | /** |
Pier Luigi | 0b4222e | 2017-07-21 09:47:14 +0200 | [diff] [blame] | 193 | * Creates a new LabelSelection. Random is the default |
| 194 | * label selection behavior. |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 195 | * |
| 196 | * @param type the behavior type |
| 197 | * @return the object implementing the behavior |
| 198 | */ |
Pier Luigi | 0b4222e | 2017-07-21 09:47:14 +0200 | [diff] [blame] | 199 | private LabelSelection getLabelSelection(SelectionBehavior type) { |
| 200 | LabelSelection selection; |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 201 | switch (type) { |
| 202 | case FIRST_FIT: |
| 203 | selection = new FirstFitSelection(); |
| 204 | break; |
| 205 | case RANDOM: |
| 206 | default: |
| 207 | selection = new RandomSelection(); |
| 208 | break; |
| 209 | } |
| 210 | return selection; |
| 211 | } |
| 212 | |
Pier Luigi | 0b4222e | 2017-07-21 09:47:14 +0200 | [diff] [blame] | 213 | // Given a link and a encapsulation type, returns a set of candidates |
| 214 | private Set<Identifier<?>> getCandidates(LinkKey link, EncapsulationType type) { |
| 215 | // Available ids on src port |
| 216 | Set<Identifier<?>> availableIDsatSrc = getAvailableIDs(link.src(), type); |
| 217 | // Available ids on dst port |
| 218 | Set<Identifier<?>> availableIDsatDst = getAvailableIDs(link.dst(), type); |
| 219 | // Create the candidate set doing an intersection of the previous sets |
| 220 | return Sets.intersection(availableIDsatSrc, availableIDsatDst); |
| 221 | } |
| 222 | |
| 223 | // Implements NONE behavior |
| 224 | private Map<LinkKey, Identifier<?>> noOptimizeBehavior(Set<LinkKey> links, EncapsulationType type) { |
| 225 | // Init step |
| 226 | Map<LinkKey, Identifier<?>> ids = Maps.newHashMap(); |
| 227 | Set<Identifier<?>> candidates; |
| 228 | Identifier<?> selected; |
| 229 | // Iterates for each link selecting a label in the candidate set |
| 230 | for (LinkKey link : links) { |
| 231 | // Get candidates set for the current link |
| 232 | candidates = getCandidates(link, type); |
| 233 | // Select a label for the current link |
| 234 | selected = labelSelection.select(candidates); |
| 235 | // If candidates is empty, selected is null |
| 236 | if (selected == null) { |
| 237 | log.warn("No labels for {}", link); |
| 238 | return Collections.emptyMap(); |
| 239 | } |
| 240 | // Selected is associated to link |
| 241 | ids.put(link, selected); |
| 242 | } |
| 243 | return ids; |
| 244 | } |
| 245 | |
alessio | 225e2b0 | 2020-10-28 17:44:44 +0100 | [diff] [blame] | 246 | // Implements suggestedIdentifier behavior |
| 247 | private Map<LinkKey, Identifier<?>> suggestedIdentifierBehavior(Set<LinkKey> links, |
| 248 | EncapsulationType type, |
| 249 | Identifier<?> suggested) { |
| 250 | // Init step |
| 251 | Map<LinkKey, Identifier<?>> ids = Maps.newHashMap(); |
| 252 | Set<Identifier<?>> candidates; |
| 253 | Identifier<?> selected = null; |
| 254 | |
| 255 | // Iterates for each link selecting a label in the candidate set |
| 256 | // Select the suggested if available on the whole path |
| 257 | for (LinkKey link : links) { |
| 258 | // Get candidates set for the current link |
| 259 | candidates = getCandidates(link, type); |
| 260 | |
| 261 | // Select the suggested if included in the candidates |
| 262 | // Otherwise select an other label for the current link |
| 263 | if (candidates.contains(suggested)) { |
| 264 | selected = suggested; |
| 265 | } else { |
| 266 | // If candidates is empty or does not contain suggested |
| 267 | log.warn("Suggested label {} is not available on link {}", suggested, link); |
| 268 | return Collections.emptyMap(); |
| 269 | } |
| 270 | // Selected is associated to link |
| 271 | ids.put(link, selected); |
| 272 | } |
| 273 | return ids; |
| 274 | } |
| 275 | |
Pier Luigi | 0b4222e | 2017-07-21 09:47:14 +0200 | [diff] [blame] | 276 | // Implements NO_SWAP behavior |
| 277 | private Map<LinkKey, Identifier<?>> noSwapBehavior(Set<LinkKey> links, EncapsulationType type) { |
| 278 | // Init steps |
| 279 | Map<LinkKey, Identifier<?>> ids = Maps.newHashMap(); |
| 280 | Identifier<?> selected; |
| 281 | Set<Identifier<?>> candidates = null; |
| 282 | Set<Identifier<?>> linkCandidates; |
| 283 | // Iterates for each link building the candidate set |
| 284 | for (LinkKey link : links) { |
| 285 | // Get candidates set for the current link |
| 286 | linkCandidates = getCandidates(link, type); |
| 287 | // Warm up |
| 288 | if (candidates == null) { |
| 289 | candidates = linkCandidates; |
| 290 | // Build step by step the intersection |
| 291 | } else { |
| 292 | candidates = Sets.intersection(candidates, linkCandidates); |
| 293 | } |
| 294 | } |
| 295 | // Pick a label according to the defined strategy |
| 296 | selected = labelSelection.select(candidates); |
| 297 | if (selected == null) { |
| 298 | // If there are no candidates, exit. This will throw a compile exception |
| 299 | log.warn("No common label for path"); |
| 300 | return Collections.emptyMap(); |
| 301 | } |
| 302 | // For each link create an entry |
| 303 | links.forEach(linkKey -> ids.put(linkKey, selected)); |
| 304 | return ids; |
| 305 | } |
| 306 | |
| 307 | // Implements MIN_SWAP behavior |
| 308 | private Map<LinkKey, Identifier<?>> minSwapBehavior(Set<LinkKey> links, EncapsulationType type) { |
| 309 | // Init step |
| 310 | Map<LinkKey, Identifier<?>> ids = Maps.newHashMap(); |
| 311 | Set<Identifier<?>> candidates; |
| 312 | Identifier<?> selected = null; |
| 313 | // Iterates for each link selecting a label in the candidate set |
| 314 | for (LinkKey link : links) { |
| 315 | // Get candidates set for the current link |
| 316 | candidates = getCandidates(link, type); |
| 317 | // If we are in the first link or selected is not available |
| 318 | if (selected == null || !candidates.contains(selected)) { |
| 319 | // Select a label for the current link |
| 320 | selected = labelSelection.select(candidates); |
| 321 | // If candidates is empty, selected is null |
| 322 | if (selected == null) { |
| 323 | log.warn("No labels for {}", link); |
| 324 | return Collections.emptyMap(); |
| 325 | } |
| 326 | } |
| 327 | // Selected is associated to link |
| 328 | ids.put(link, selected); |
| 329 | } |
| 330 | return ids; |
| 331 | } |
| 332 | |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 333 | /** |
| 334 | * Looks for available Ids. |
| 335 | * |
| 336 | * @param links the links where to look for Ids |
| 337 | * @param type the encapsulation type |
| 338 | * @return the mappings between key and id |
| 339 | */ |
alessio | 225e2b0 | 2020-10-28 17:44:44 +0100 | [diff] [blame] | 340 | private Map<LinkKey, Identifier<?>> findAvailableIDs(Set<LinkKey> links, |
| 341 | EncapsulationType type, |
| 342 | Optional<Identifier<?>> suggestedIdentifier) { |
Pier Luigi | 0b4222e | 2017-07-21 09:47:14 +0200 | [diff] [blame] | 343 | // Init step |
| 344 | Map<LinkKey, Identifier<?>> ids; |
alessio | 225e2b0 | 2020-10-28 17:44:44 +0100 | [diff] [blame] | 345 | |
| 346 | //Use suggested identifier if possible |
| 347 | if (suggestedIdentifier.isPresent()) { |
| 348 | ids = suggestedIdentifierBehavior(links, type, suggestedIdentifier.get()); |
| 349 | |
| 350 | if (!ids.isEmpty()) { |
| 351 | return ids; |
| 352 | } |
| 353 | } |
| 354 | |
Pier Luigi | 0b4222e | 2017-07-21 09:47:14 +0200 | [diff] [blame] | 355 | // Performs label selection according to the defined optimization behavior |
| 356 | switch (optLabelSelection) { |
| 357 | // No swapping of the labels |
| 358 | case NO_SWAP: |
| 359 | ids = noSwapBehavior(links, type); |
| 360 | break; |
| 361 | // Swapping is minimized |
| 362 | case MIN_SWAP: |
| 363 | ids = minSwapBehavior(links, type); |
| 364 | break; |
| 365 | // No optimizations are in place |
| 366 | case NONE: |
| 367 | default: |
| 368 | ids = noOptimizeBehavior(links, type); |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 369 | } |
Pier Luigi | 0b4222e | 2017-07-21 09:47:14 +0200 | [diff] [blame] | 370 | // Done exit |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 371 | return ids; |
| 372 | } |
| 373 | |
| 374 | /** |
| 375 | * Looks for available Ids associated to the given connection point. |
| 376 | * |
| 377 | * @param cp the connection point |
| 378 | * @param type the type of Id |
| 379 | * @return the set of available Ids |
| 380 | */ |
| 381 | private Set<Identifier<?>> getAvailableIDs(ConnectPoint cp, EncapsulationType type) { |
| 382 | return resourceService.getAvailableResourceValues( |
| 383 | Resources.discrete(cp.deviceId(), cp.port()).id(), getEncapsulationClass(type) |
| 384 | ); |
| 385 | } |
| 386 | |
| 387 | /** |
| 388 | * Method to map the encapsulation type to identifier class. |
| 389 | * VLAN is the default encapsulation. |
| 390 | * |
| 391 | * @param type the type of encapsulation |
| 392 | * @return the id class |
| 393 | */ |
| 394 | private Class getEncapsulationClass(EncapsulationType type) { |
| 395 | Class idType; |
| 396 | switch (type) { |
| 397 | case MPLS: |
| 398 | idType = MplsLabel.class; |
| 399 | break; |
| 400 | case VLAN: |
| 401 | default: |
| 402 | idType = VlanId.class; |
| 403 | } |
| 404 | return idType; |
| 405 | } |
| 406 | |
| 407 | /** |
| 408 | * Allocates labels and associates them to links. |
| 409 | * |
| 410 | * @param links the links where labels will be allocated |
Yi Tseng | 0db1f3b | 2017-05-25 10:08:06 -0700 | [diff] [blame] | 411 | * @param resourceConsumer the resource consumer |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 412 | * @param type the encapsulation type |
alessio | 225e2b0 | 2020-10-28 17:44:44 +0100 | [diff] [blame] | 413 | * @param suggestedIdentifier used if available |
| 414 | * @return the list of links and associated labels |
| 415 | */ |
| 416 | public Map<LinkKey, Identifier<?>> assignLabelToLinks(Set<Link> links, |
| 417 | ResourceConsumer resourceConsumer, |
| 418 | EncapsulationType type, |
| 419 | Optional<Identifier<?>> suggestedIdentifier) { |
| 420 | // To preserve order of the links. This is important for MIN_SWAP behavior |
| 421 | Set<LinkKey> linkRequest = links.stream() |
| 422 | .map(LinkKey::linkKey) |
| 423 | .collect(Collectors.toCollection(LinkedHashSet::new)); |
| 424 | |
| 425 | Map<LinkKey, Identifier<?>> availableIds = findAvailableIDs(linkRequest, type, suggestedIdentifier); |
| 426 | if (availableIds.isEmpty()) { |
| 427 | return Collections.emptyMap(); |
| 428 | } |
| 429 | |
| 430 | Set<Resource> resources = availableIds.entrySet().stream() |
| 431 | .flatMap(x -> Stream.of( |
| 432 | Resources.discrete( |
| 433 | x.getKey().src().deviceId(), |
| 434 | x.getKey().src().port(), |
| 435 | x.getValue() |
| 436 | ).resource(), |
| 437 | Resources.discrete( |
| 438 | x.getKey().dst().deviceId(), |
| 439 | x.getKey().dst().port(), |
| 440 | x.getValue() |
| 441 | ).resource() |
| 442 | )) |
| 443 | .collect(Collectors.toSet()); |
| 444 | |
| 445 | List<ResourceAllocation> allocations = resourceService.allocate(resourceConsumer, |
| 446 | ImmutableList.copyOf(resources)); |
| 447 | |
| 448 | if (allocations.isEmpty()) { |
| 449 | return Collections.emptyMap(); |
| 450 | } |
| 451 | |
| 452 | return ImmutableMap.copyOf(availableIds); |
| 453 | } |
| 454 | |
| 455 | /** |
| 456 | * Allocates labels and associates them to links. |
| 457 | * |
| 458 | * @param links the links where labels will be allocated |
| 459 | * @param resourceConsumer the resource consumer |
| 460 | * @param type the encapsulation type |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 461 | * @return the list of links and associated labels |
| 462 | */ |
Yi Tseng | 0db1f3b | 2017-05-25 10:08:06 -0700 | [diff] [blame] | 463 | public Map<LinkKey, Identifier<?>> assignLabelToLinks(Set<Link> links, |
| 464 | ResourceConsumer resourceConsumer, |
| 465 | EncapsulationType type) { |
Pier Luigi | 0b4222e | 2017-07-21 09:47:14 +0200 | [diff] [blame] | 466 | // To preserve order of the links. This is important for MIN_SWAP behavior |
Sho SHIMIZU | 4c7fcdf | 2016-12-22 11:17:43 -0800 | [diff] [blame] | 467 | Set<LinkKey> linkRequest = links.stream() |
| 468 | .map(LinkKey::linkKey) |
Pier Luigi | 0b4222e | 2017-07-21 09:47:14 +0200 | [diff] [blame] | 469 | .collect(Collectors.toCollection(LinkedHashSet::new)); |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 470 | |
alessio | 225e2b0 | 2020-10-28 17:44:44 +0100 | [diff] [blame] | 471 | Map<LinkKey, Identifier<?>> availableIds = findAvailableIDs(linkRequest, type, Optional.empty()); |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 472 | if (availableIds.isEmpty()) { |
| 473 | return Collections.emptyMap(); |
| 474 | } |
| 475 | |
| 476 | Set<Resource> resources = availableIds.entrySet().stream() |
| 477 | .flatMap(x -> Stream.of( |
| 478 | Resources.discrete( |
| 479 | x.getKey().src().deviceId(), |
| 480 | x.getKey().src().port(), |
| 481 | x.getValue() |
| 482 | ).resource(), |
| 483 | Resources.discrete( |
| 484 | x.getKey().dst().deviceId(), |
| 485 | x.getKey().dst().port(), |
| 486 | x.getValue() |
| 487 | ).resource() |
| 488 | )) |
| 489 | .collect(Collectors.toSet()); |
| 490 | |
Yi Tseng | 0db1f3b | 2017-05-25 10:08:06 -0700 | [diff] [blame] | 491 | List<ResourceAllocation> allocations = resourceService.allocate(resourceConsumer, |
| 492 | ImmutableList.copyOf(resources)); |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 493 | |
| 494 | if (allocations.isEmpty()) { |
| 495 | return Collections.emptyMap(); |
| 496 | } |
| 497 | |
| 498 | return ImmutableMap.copyOf(availableIds); |
| 499 | } |
| 500 | |
| 501 | /** |
| 502 | * Allocates labels and associates them to source |
| 503 | * and destination ports of a link. |
| 504 | * |
| 505 | * @param links the links on which labels will be reserved |
Yi Tseng | 0db1f3b | 2017-05-25 10:08:06 -0700 | [diff] [blame] | 506 | * @param resourceConsumer the resource consumer |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 507 | * @param type the encapsulation type |
alessio | 225e2b0 | 2020-10-28 17:44:44 +0100 | [diff] [blame] | 508 | * @param suggestedIdentifier used if available |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 509 | * @return the list of ports and associated labels |
| 510 | */ |
Yi Tseng | 0db1f3b | 2017-05-25 10:08:06 -0700 | [diff] [blame] | 511 | public Map<ConnectPoint, Identifier<?>> assignLabelToPorts(Set<Link> links, |
| 512 | ResourceConsumer resourceConsumer, |
alessio | 225e2b0 | 2020-10-28 17:44:44 +0100 | [diff] [blame] | 513 | EncapsulationType type, |
| 514 | Optional<Identifier<?>> suggestedIdentifier) { |
Yi Tseng | 0db1f3b | 2017-05-25 10:08:06 -0700 | [diff] [blame] | 515 | Map<LinkKey, Identifier<?>> allocation = this.assignLabelToLinks(links, |
alessio | 225e2b0 | 2020-10-28 17:44:44 +0100 | [diff] [blame] | 516 | resourceConsumer, |
| 517 | type, |
| 518 | suggestedIdentifier); |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 519 | if (allocation.isEmpty()) { |
| 520 | return Collections.emptyMap(); |
| 521 | } |
| 522 | Map<ConnectPoint, Identifier<?>> finalAllocation = Maps.newHashMap(); |
Yi Tseng | 0db1f3b | 2017-05-25 10:08:06 -0700 | [diff] [blame] | 523 | allocation.forEach((link, value) -> { |
| 524 | finalAllocation.putIfAbsent(link.src(), value); |
| 525 | finalAllocation.putIfAbsent(link.dst(), value); |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 526 | }); |
| 527 | return ImmutableMap.copyOf(finalAllocation); |
| 528 | } |
| 529 | |
| 530 | /** |
alessio | 225e2b0 | 2020-10-28 17:44:44 +0100 | [diff] [blame] | 531 | * Allocates labels and associates them to source |
| 532 | * and destination ports of a link. |
| 533 | * |
| 534 | * @param links the links on which labels will be reserved |
| 535 | * @param resourceConsumer the resource consumer |
| 536 | * @param type the encapsulation type |
| 537 | * @return the list of ports and associated labels |
| 538 | */ |
| 539 | public Map<ConnectPoint, Identifier<?>> assignLabelToPorts(Set<Link> links, |
| 540 | ResourceConsumer resourceConsumer, |
| 541 | EncapsulationType type) { |
| 542 | Map<LinkKey, Identifier<?>> allocation = this.assignLabelToLinks(links, |
| 543 | resourceConsumer, |
| 544 | type); |
| 545 | if (allocation.isEmpty()) { |
| 546 | return Collections.emptyMap(); |
| 547 | } |
| 548 | Map<ConnectPoint, Identifier<?>> finalAllocation = Maps.newHashMap(); |
| 549 | allocation.forEach((link, value) -> { |
| 550 | finalAllocation.putIfAbsent(link.src(), value); |
| 551 | finalAllocation.putIfAbsent(link.dst(), value); |
| 552 | }); |
| 553 | return ImmutableMap.copyOf(finalAllocation); |
| 554 | } |
| 555 | |
| 556 | /** |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 557 | * Interface for selection algorithms of the labels. |
| 558 | */ |
| 559 | public interface LabelSelection { |
| 560 | |
| 561 | /** |
| 562 | * Picks an element from values using a particular algorithm. |
| 563 | * |
| 564 | * @param values the values to select from |
| 565 | * @return the selected identifier if values are present, null otherwise |
| 566 | */ |
| 567 | Identifier<?> select(Set<Identifier<?>> values); |
| 568 | |
| 569 | } |
| 570 | |
| 571 | /** |
| 572 | * Random label selection. |
| 573 | */ |
| 574 | public static class RandomSelection implements LabelSelection { |
| 575 | |
| 576 | /** |
| 577 | * Selects an identifier from a given set of values using |
| 578 | * the random selection algorithm. |
| 579 | * |
| 580 | * @param values the values to select from |
| 581 | * @return the selected identifier if values are present, null otherwise |
| 582 | */ |
| 583 | @Override |
| 584 | public Identifier<?> select(Set<Identifier<?>> values) { |
| 585 | if (!values.isEmpty()) { |
| 586 | int size = values.size(); |
| 587 | int index = RandomUtils.nextInt(size); |
| 588 | return Iterables.get(values, index); |
| 589 | } |
| 590 | return null; |
| 591 | } |
| 592 | } |
| 593 | |
| 594 | /** |
| 595 | * First fit label selection. |
| 596 | */ |
| 597 | public static class FirstFitSelection implements LabelSelection { |
| 598 | |
| 599 | /** |
| 600 | * Selects an identifier from a given set of values using |
Pier Luigi | 0b4222e | 2017-07-21 09:47:14 +0200 | [diff] [blame] | 601 | * the first fit selection algorithm. |
Pier Ventre | f8543d8 | 2016-09-28 19:49:33 -0700 | [diff] [blame] | 602 | * |
| 603 | * @param values the values to select from |
| 604 | * @return the selected identifier if values are present, null otherwise. |
| 605 | */ |
| 606 | @Override |
| 607 | public Identifier<?> select(Set<Identifier<?>> values) { |
| 608 | if (!values.isEmpty()) { |
| 609 | return values.iterator().next(); |
| 610 | } |
| 611 | return null; |
| 612 | } |
| 613 | } |
| 614 | |
| 615 | } |