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