resource-assignment/provider/src/main/java/org/onap/ccsdk/sli/adaptors/rm/util/LimitUtil.java

   1 /*-
   2  * ============LICENSE_START=======================================================
   3  * openECOMP : SDN-C
   4  * ================================================================================
   5  * Copyright (C) 2017 AT&T Intellectual Property. All rights
   6  *                         reserved.
   7  * ================================================================================
   8  * Licensed under the Apache License, Version 2.0 (the "License");
   9  * you may not use this file except in compliance with the License.
  10  * You may obtain a copy of the License at
  11  *
  12  *      http://www.apache.org/licenses/LICENSE-2.0
  13  *
  14  * Unless required by applicable law or agreed to in writing, software
  15  * distributed under the License is distributed on an "AS IS" BASIS,
  16  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  17  * See the License for the specific language governing permissions and
  18  * limitations under the License.
  19  * ============LICENSE_END=========================================================
  20  */
  21
  22 package org.onap.ccsdk.sli.adaptors.rm.util;
  23
  24 import java.util.ArrayList;
  25 import java.util.Date;
  26 import java.util.HashMap;
  27 import java.util.List;
  28 import java.util.Map;
  29 import java.util.Set;
  30 import org.onap.ccsdk.sli.adaptors.rm.data.AllocationItem;
  31 import org.onap.ccsdk.sli.adaptors.rm.data.LimitAllocationItem;
  32 import org.onap.ccsdk.sli.adaptors.rm.data.LimitAllocationRequest;
  33 import org.onap.ccsdk.sli.adaptors.rm.data.LimitResource;
  34 import org.onap.ccsdk.sli.adaptors.rm.data.ResourceKey;
  35 import org.onap.ccsdk.sli.adaptors.rm.data.ResourceType;
  36 import org.slf4j.Logger;
  37 import org.slf4j.LoggerFactory;
  38
  39 public class LimitUtil {
  40
  41     private static final Logger log = LoggerFactory.getLogger(LimitUtil.class);
  42
  43     public static boolean checkLimit(LimitResource l, LimitAllocationRequest req) {
  44         if (req.checkCount <= 0) {
  45             return true;
  46         }
  47
  48         long checkCount = req.checkCount;
  49         long currentUsage = 0;
  50         if (req.resourceSetId != null) {
  51             LimitAllocationItem lai = (LimitAllocationItem) ResourceUtil.getAllocationItem(l, req.resourceSetId);
  52             if (lai != null) {
  53                 currentUsage = lai.used;
  54             }
  55         }
  56         if (!req.replace) {
  57             checkCount += currentUsage;
  58         }
  59
  60         long used = calculateLimitUsage(l, 0, null, null);
  61         long wouldUse = calculateLimitUsage(l, checkCount, req.resourceUnionId, req.resourceShareGroupList);
  62
  63         // If usage is not increasing by this request, only check the limit if
  64         // strictCheck is true.
  65         if (wouldUse <= used && !req.strict) {
  66             return true;
  67         }
  68
  69         return wouldUse <= req.checkLimit;
  70     }
  71
  72     private static long calculateLimitUsage(
  73             LimitResource l,
  74             long checkCount,
  75             String resourceUnionId,
  76             Set<String> resourceShareGroupList) {
  77         if ((l.allocationItems == null || l.allocationItems.isEmpty()) &&
  78                 (resourceUnionId == null || resourceUnionId.length() == 0)) {
  79             return 0;
  80         }
  81
  82         long t1 = System.currentTimeMillis();
  83         boolean logit = false;
  84         String rn = "Resource: " + l.resourceKey.resourceName + " - " + l.resourceKey.assetId;
  85
  86         // In order to best utilize the resource, we need to take not the sum of all allocation items, but
  87         // instead the maximum usage that could happen at any moment of time (given not all allocation items are active
  88         // at the same time), also taking into account possible resource sharing.
  89         // Thus we need to find all combinations of allocation items that can be active at the same time (allocation
  90         // items with the same first union cannot be active at the same time), compute the usage for each (again,
  91         // taking into account resource sharing), and take the maximum.
  92         //
  93         // Example:
  94         // Let's have the following allocation items:
  95         // ai1: sdid1, vrf1 - usage 5
  96         // ai2: sdid2, vrf1 - usage 10
  97         // ai3: sdid3, vrf2 - usage 15
  98         // ai4: sdid1, vrf3 - usage 20
  99         // ai5: sdid3, vrf1 - usage 25
 100         // The following combinations of active allocation items are possible:
 101         // 1) ai1, ai2, ai3
 102         // 2) ai1, ai2, ai5
 103         // 3) ai2, ai3, ai4
 104         // 4) ai2, ai3, ai5
 105         // Here is how we calculate the usage for combination 1:
 106         // ai1 and ai2 contain the same resource union vrf1, so they share the resource - we take the max of usage,
 107         // so we have:
 108         // max(5, 10) + 15 = 25
 109         // Similarly, we calculate the usage of the other combinations:
 110         // 2) max(5, 10, 25) = 25
 111         // 3) 10 + 15 + 20 = 45
 112         // 4) max(10, 25) + 15 = 40
 113         // So, the result in this case is:
 114         // max(25, 25, 45, 40) = 45
 115         //
 116         // We might have a problem with this approach, if we have a lot of combinations. Assuming we have at most 2
 117         // allocation items with the same resource union (sdid), the number of combinations would be
 118         // 2 ^ n
 119         // where n is the number of allocation items that have the same resource union (sdid). That would be
 120         // the number of change orders currently in progress.
 121         //
 122         // Here is one optimization that we can do:
 123         // If we have allocation items that have all resource unions the same, we don't need to generate combinations
 124         // with each of them, we can just take the one of them with the maximum usage, as it is clear that the others
 125         // will not lead to a bigger usage.
 126         // For example, if we had the following allocation items:
 127         // ai1: sdid1, vrf1 - usage 10
 128         // ai2: sdid1, vrf1 - usage 20
 129         // We only need to take the combinations with ai2, as they will always lead to bigger usage than the remaining
 130         // combinations with ai1.
 131
 132         // First, group the allocation items by the first resource union, using the LimitUsage structure
 133         int regularChangeCount = 0;
 134         Map<String/* resourceUnionId */, List<LimitUsage>> limitUsageMap = new HashMap<>();
 135         if (l.allocationItems != null) {
 136             for (AllocationItem ai : l.allocationItems) {
 137                 LimitAllocationItem lai = (LimitAllocationItem) ai;
 138                 boolean regularChange =
 139                         addLimitUsage(limitUsageMap, lai.resourceUnionId, lai.resourceShareGroupList, lai.used);
 140                 if (regularChange) {
 141                     regularChangeCount++;
 142                 }
 143             }
 144         }
 145         if (checkCount > 0 && resourceUnionId != null) {
 146             boolean regularChange = addLimitUsage(limitUsageMap, resourceUnionId, resourceShareGroupList, checkCount);
 147             if (regularChange) {
 148                 regularChangeCount++;
 149             }
 150         }
 151
 152         // Generate all the combinations, containing one LimitUsage object for each firstResourceUnion
 153         int significantChangeCount = 0;
 154         List<List<LimitUsage>> allCombinations = new ArrayList<>();
 155         for (String firstResourceUnion : limitUsageMap.keySet()) {
 156             List<LimitUsage> limitUsageList = limitUsageMap.get(firstResourceUnion);
 157             if (limitUsageList.size() > 1) {
 158                 significantChangeCount++;
 159             }
 160             if (allCombinations.isEmpty()) {
 161                 for (LimitUsage limitUsage : limitUsageList) {
 162                     List<LimitUsage> newCombination = new ArrayList<>();
 163                     newCombination.add(limitUsage);
 164                     allCombinations.add(newCombination);
 165                 }
 166             } else {
 167                 if (limitUsageList.size() == 1) {
 168                     // No new combinations are generated - just add this one to all combinations we have until now
 169                     for (List<LimitUsage> combination : allCombinations) {
 170                         combination.add(limitUsageList.get(0));
 171                     }
 172                 } else {
 173                     // We have to duplicate each of the current combinations for each element of limitUsageList
 174                     List<List<LimitUsage>> newAllCombinations = new ArrayList<>();
 175                     for (List<LimitUsage> combination : allCombinations) {
 176                         for (LimitUsage limitUsage : limitUsageList) {
 177                             List<LimitUsage> newCombination = new ArrayList<>(combination);
 178                             newCombination.add(limitUsage);
 179                             newAllCombinations.add(newCombination);
 180                         }
 181                     }
 182                     allCombinations = newAllCombinations;
 183                 }
 184             }
 185         }
 186
 187         // Now, go through all combinations and calculate its usage, get the maximum
 188         long maxUsage = 0;
 189         for (List<LimitUsage> combination : allCombinations) {
 190             long usage = calculateUsage(combination);
 191             if (usage > maxUsage) {
 192                 maxUsage = usage;
 193             }
 194         }
 195
 196         long t2 = System.currentTimeMillis();
 197         if (logit) {
 198             log.debug(rn + ": Calculating usage completed:");
 199             log.debug(rn + ":     Regular changes: " + regularChangeCount);
 200             log.debug(rn + ":     Significant changes: " + significantChangeCount);
 201             log.debug(rn + ":     Combinations: " + allCombinations.size());
 202             log.debug(rn + ":     Usage: " + maxUsage);
 203             log.debug(rn + ":     Time: " + (t2 - t1));
 204         }
 205
 206         return maxUsage;
 207     }
 208
 209     private static boolean addLimitUsage(
 210             Map<String/* resourceUnionId */, List<LimitUsage>> limitUsageMap,
 211             String resourceUnionId,
 212             Set<String> resourceShareGroupList,
 213             long used) {
 214         List<LimitUsage> limitUsageList = limitUsageMap.get(resourceUnionId);
 215         if (limitUsageList == null) {
 216             limitUsageList = new ArrayList<>();
 217             limitUsageMap.put(resourceUnionId, limitUsageList);
 218         }
 219         // See if we already have the same shareResourceUnionSet in the list. In such case just update the usage
 220         // to the bigger value.
 221         LimitUsage limitUsage = null;
 222         for (LimitUsage limitUsage1 : limitUsageList) {
 223             if ((limitUsage1.resourceShareGroupList == null || limitUsage1.resourceShareGroupList.isEmpty()) &&
 224                     (resourceShareGroupList == null || resourceShareGroupList.isEmpty())) {
 225                 limitUsage = limitUsage1;
 226                 break;
 227             }
 228             if (limitUsage1.resourceShareGroupList != null &&
 229                     limitUsage1.resourceShareGroupList.equals(resourceShareGroupList)) {
 230                 limitUsage = limitUsage1;
 231                 break;
 232             }
 233         }
 234         if (limitUsage != null) {
 235             if (limitUsage.usage < used) {
 236                 limitUsage.usage = used;
 237             }
 238             return true;
 239         }
 240
 241         limitUsage = new LimitUsage();
 242         limitUsage.resourceUnion = resourceUnionId;
 243         limitUsage.resourceShareGroupList = resourceShareGroupList;
 244         limitUsage.usage = used;
 245         limitUsageList.add(limitUsage);
 246         return false;
 247     }
 248
 249     private static class LimitUsage {
 250
 251         @SuppressWarnings("unused")
 252         public String resourceUnion;
 253         public Set<String> resourceShareGroupList;
 254         public long usage;
 255     }
 256
 257     private static boolean hasCommonSharedResource(LimitUsage limitUsage1, LimitUsage limitUsage2) {
 258         if (limitUsage1.resourceShareGroupList == null || limitUsage1.resourceShareGroupList.isEmpty()) {
 259             return false;
 260         }
 261         if (limitUsage2.resourceShareGroupList == null || limitUsage2.resourceShareGroupList.isEmpty()) {
 262             return false;
 263         }
 264
 265         for (String resourceUnion : limitUsage1.resourceShareGroupList) {
 266             if (limitUsage2.resourceShareGroupList.contains(resourceUnion)) {
 267                 return true;
 268             }
 269         }
 270
 271         return false;
 272     }
 273
 274     private static long calculateUsage(List<LimitUsage> combination) {
 275         // All LimitUsage objects that have a common value in their sharedResourceUnionSet reuse the resource, so
 276         // split the combination in sets that have common value. Then the usage of each set will be the maximum of
 277         // the usages of the LimitUsage objects in the set. The usage of the combination will be the sum of the usages
 278         // of all sets.
 279         List<List<LimitUsage>> sharedSets = new ArrayList<>();
 280         for (LimitUsage limitUsage : combination) {
 281             // See if we can put limitUsage in any of the existing sets - is it has a common resource union with
 282             // any of the LimitUsage objects in a set.
 283             boolean found = false;
 284             for (List<LimitUsage> sharedSet : sharedSets) {
 285                 for (LimitUsage limitUsage1 : sharedSet) {
 286                     if (hasCommonSharedResource(limitUsage, limitUsage1)) {
 287                         found = true;
 288                         break;
 289                     }
 290                 }
 291                 if (found) {
 292                     sharedSet.add(limitUsage);
 293                     break;
 294                 }
 295             }
 296             if (!found) {
 297                 // Start a new set
 298                 List<LimitUsage> newSharedSet = new ArrayList<>();
 299                 newSharedSet.add(limitUsage);
 300                 sharedSets.add(newSharedSet);
 301             }
 302         }
 303
 304         long sum = 0;
 305         for (List<LimitUsage> sharedSet : sharedSets) {
 306             float max = 0;
 307             for (LimitUsage limitUsage : sharedSet) {
 308                 if (max < limitUsage.usage) {
 309                     max = limitUsage.usage;
 310                 }
 311             }
 312             sum += max;
 313         }
 314
 315         return sum;
 316     }
 317
 318     public static long allocateLimit(LimitResource l, LimitAllocationRequest req) {
 319         if (req.allocateCount <= 0) {
 320             return 0;
 321         }
 322         long uu = l.used;
 323
 324         LimitAllocationItem lai = (LimitAllocationItem) ResourceUtil.getAllocationItem(l, req.resourceSetId);
 325         if (lai == null) {
 326             lai = new LimitAllocationItem();
 327             lai.resourceType = ResourceType.Limit;
 328             lai.resourceKey = new ResourceKey();
 329             lai.resourceKey.assetId = req.assetId;
 330             lai.resourceKey.resourceName = req.resourceName;
 331             lai.applicationId = req.applicationId;
 332             lai.resourceSetId = req.resourceSetId;
 333             lai.resourceUnionId = req.resourceUnionId;
 334             lai.resourceShareGroupList = req.resourceShareGroupList;
 335             lai.used = req.allocateCount;
 336
 337             if (l.allocationItems == null) {
 338                 l.allocationItems = new ArrayList<>();
 339             }
 340             l.allocationItems.add(lai);
 341         } else {
 342             lai.used = req.replace ? req.allocateCount : lai.used + req.allocateCount;
 343         }
 344
 345         lai.allocationTime = new Date();
 346
 347         recalculate(l);
 348
 349         return l.used - uu;
 350     }
 351
 352     public static void recalculate(LimitResource l) {
 353         l.used = calculateLimitUsage(l, 0, null, null);
 354     }
 355 }