conductor/conductor/solver/optimizer/optimizer.py

   1 #
   2 # -------------------------------------------------------------------------
   3 #   Copyright (c) 2015-2017 AT&T Intellectual Property
   4 #
   5 #   Licensed under the Apache License, Version 2.0 (the "License");
   6 #   you may not use this file except in compliance with the License.
   7 #   You may obtain a copy of the License at
   8 #
   9 #       http://www.apache.org/licenses/LICENSE-2.0
  10 #
  11 #   Unless required by applicable law or agreed to in writing, software
  12 #   distributed under the License is distributed on an "AS IS" BASIS,
  13 #   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14 #   See the License for the specific language governing permissions and
  15 #   limitations under the License.
  16 #
  17 # -------------------------------------------------------------------------
  18 #
  19
  20 from oslo_config import cfg
  21 from oslo_log import log
  22 import copy
  23 import time
  24
  25
  26 from conductor import service
  27 # from conductor.solver.optimizer import decision_path as dpath
  28 # from conductor.solver.optimizer import best_first
  29 # from conductor.solver.optimizer import greedy
  30 from conductor.solver.optimizer import fit_first
  31 from conductor.solver.optimizer import random_pick
  32 from conductor.solver.request import demand
  33 from conductor.solver.triage_tool.triage_data import TriageData
  34
  35 LOG = log.getLogger(__name__)
  36
  37 CONF = cfg.CONF
  38
  39 SOLVER_OPTS = [
  40
  41 ]
  42
  43 CONF.register_opts(SOLVER_OPTS, group='solver')
  44
  45
  46 class Optimizer(object):
  47
  48     # FIXME(gjung): _requests should be request (no underscore, one item)
  49     def __init__(self, conf, _requests=None, _begin_time=None):
  50         self.conf = conf
  51
  52         # start time of solving the plan
  53         if _begin_time is not None:
  54             self._begin_time = _begin_time
  55
  56         # self.search = greedy.Greedy(self.conf)
  57         self.search = None
  58         # self.search = best_first.BestFirst(self.conf)
  59
  60         if _requests is not None:
  61             self.requests = _requests
  62
  63         # Were the 'simulators' ever used? It doesn't look like this.
  64         # Since solver/simulator code needs cleansing before being moved to ONAP,
  65         # I see no value for having this piece of code which is not letting us do
  66         # that cleanup. Also, Shankar has confirmed solver/simulators folder needs
  67         # to go away. Commenting out for now - may be should be removed permanently.
  68         # Shankar (TODO).
  69         # else:
  70         #     ''' for simulation '''
  71         #     req_sim = request_simulator.RequestSimulator(self.conf)
  72         #     req_sim.generate_requests()
  73         #     self.requests = req_sim.requests
  74
  75     def get_solution(self, num_solutions):
  76
  77         LOG.debug("search start")
  78         for rk in self.requests:
  79             request = self.requests[rk]
  80             LOG.debug("--- request = {}".format(rk))
  81
  82             decision_list = list()
  83
  84             LOG.debug("1. sort demands")
  85             demand_list = self._sort_demands(request)
  86             for d in demand_list:
  87                 LOG.debug("    demand = {}".format(d.name))
  88
  89             LOG.debug("2. search")
  90
  91             while (num_solutions == 'all' or num_solutions > 0):
  92
  93                 LOG.debug("searching for the solution {}".format(len(decision_list) + 1))
  94
  95                 st = time.time()
  96                 _copy_demand_list = copy.deepcopy(demand_list)
  97
  98                 if not request.objective.goal:
  99                     LOG.debug("No objective function is provided. "
 100                               "Random pick algorithm is used")
 101                     self.search = random_pick.RandomPick(self.conf)
 102                     best_path = self.search.search(demand_list, request)
 103                 else:
 104                     LOG.debug("Fit first algorithm is used")
 105                     self.search = fit_first.FitFirst(self.conf)
 106                     best_path = self.search.search(demand_list,
 107                                                    request.objective, request)
 108
 109                 if best_path is not None:
 110                     self.search.print_decisions(best_path)
 111                 else:
 112                     LOG.debug("no solution found")
 113                     break
 114
 115                 LOG.debug("search delay = {} sec".format(time.time() - st))
 116
 117                 # add the current solution to decision_list
 118                 decision_list.append(best_path.decisions)
 119
 120                 #remove the candidate with "uniqueness = true"
 121                 demand_list = copy.deepcopy(_copy_demand_list)
 122                 self._remove_unique_candidate(request, best_path, demand_list)
 123
 124                 if num_solutions != 'all':
 125                     num_solutions -= 1
 126             self.search.triageSolver.getSolution(decision_list)
 127             return decision_list
 128
 129     def _remove_unique_candidate(self, _request, current_decision, demand_list):
 130
 131         # This method is to remove previous solved/used candidate from consideration
 132         # when Conductor needs to provide multiple solutions to the user/client
 133
 134         for demand_name, candidate_attr in current_decision.decisions.items():
 135             candidate_uniqueness = candidate_attr.get('uniqueness')
 136             if candidate_uniqueness and candidate_uniqueness == 'true':
 137                 # if the candidate uniqueness is 'false', then remove
 138                 # that solved candidate from the translated candidates list
 139                 _request.demands[demand_name].resources.pop(candidate_attr.get('candidate_id'))
 140                 # update the demand_list
 141                 for demand in demand_list:
 142                     if(getattr(demand, 'name') == demand_name):
 143                         demand.resources = _request.demands[demand_name].resources
 144
 145     def _sort_demands(self, _request):
 146         LOG.debug(" _sort_demands")
 147         demand_list = []
 148
 149         # first, find loc-demand dependencies
 150         # using constraints and objective functions
 151         open_demand_list = []
 152         for key in _request.constraints:
 153             c = _request.constraints[key]
 154             if c.constraint_type == "access_distance":
 155                 for dk in c.demand_list:
 156                     if _request.demands[dk].sort_base != 1:
 157                         _request.demands[dk].sort_base = 1
 158                         open_demand_list.append(_request.demands[dk])
 159         for op in _request.objective.operand_list:
 160             if op.function.func_type == "latency_between": #TODO   do i need to include the region_group here?
 161                 if isinstance(op.function.loc_a, demand.Location):
 162                     if _request.demands[op.function.loc_z.name].sort_base != 1:
 163                         _request.demands[op.function.loc_z.name].sort_base = 1
 164                         open_demand_list.append(op.function.loc_z)
 165                 elif isinstance(op.function.loc_z, demand.Location):
 166                     if _request.demands[op.function.loc_a.name].sort_base != 1:
 167                         _request.demands[op.function.loc_a.name].sort_base = 1
 168                         open_demand_list.append(op.function.loc_a)
 169             elif op.function.func_type == "distance_between":
 170                 if isinstance(op.function.loc_a, demand.Location):
 171                     if _request.demands[op.function.loc_z.name].sort_base != 1:
 172                         _request.demands[op.function.loc_z.name].sort_base = 1
 173                         open_demand_list.append(op.function.loc_z)
 174                 elif isinstance(op.function.loc_z, demand.Location):
 175                     if _request.demands[op.function.loc_a.name].sort_base != 1:
 176                         _request.demands[op.function.loc_a.name].sort_base = 1
 177                         open_demand_list.append(op.function.loc_a)
 178
 179         if len(open_demand_list) == 0:
 180             init_demand = self._exist_not_sorted_demand(_request.demands)
 181             open_demand_list.append(init_demand)
 182
 183         # second, find demand-demand dependencies
 184         while True:
 185             d_list = self._get_depended_demands(open_demand_list, _request)
 186             for d in d_list:
 187                 demand_list.append(d)
 188
 189             init_demand = self._exist_not_sorted_demand(_request.demands)
 190             if init_demand is None:
 191                 break
 192             open_demand_list.append(init_demand)
 193
 194         return demand_list
 195
 196     def _get_depended_demands(self, _open_demand_list, _request):
 197         demand_list = []
 198
 199         while True:
 200             if len(_open_demand_list) == 0:
 201                 break
 202
 203             d = _open_demand_list.pop(0)
 204             if d.sort_base != 1:
 205                 d.sort_base = 1
 206             demand_list.append(d)
 207
 208             for key in _request.constraints:
 209                 c = _request.constraints[key]
 210                 # FIXME(snarayanan): "aic" only to be known by conductor-data
 211                 if c.constraint_type == "aic_distance":
 212                     if d.name in c.demand_list:
 213                         for dk in c.demand_list:
 214                             if dk != d.name and \
 215                                     _request.demands[dk].sort_base != 1:
 216                                 _request.demands[dk].sort_base = 1
 217                                 _open_demand_list.append(
 218                                     _request.demands[dk])
 219
 220             for op in _request.objective.operand_list:
 221                 if op.function.func_type == "latency_between":  #TODO
 222                     if op.function.loc_a.name == d.name:
 223                         if op.function.loc_z.name in \
 224                                 _request.demands.keys():
 225                             if _request.demands[
 226                                     op.function.loc_z.name].sort_base != 1:
 227                                 _request.demands[
 228                                     op.function.loc_z.name].sort_base = 1
 229                                 _open_demand_list.append(op.function.loc_z)
 230                     elif op.function.loc_z.name == d.name:
 231                         if op.function.loc_a.name in \
 232                                 _request.demands.keys():
 233                             if _request.demands[
 234                                     op.function.loc_a.name].sort_base != 1:
 235                                 _request.demands[
 236                                     op.function.loc_a.name].sort_base = 1
 237                                 _open_demand_list.append(op.function.loc_a)
 238
 239                 elif op.function.func_type == "distance_between":
 240                     if op.function.loc_a.name == d.name:
 241                         if op.function.loc_z.name in \
 242                                 _request.demands.keys():
 243                             if _request.demands[
 244                                     op.function.loc_z.name].sort_base != 1:
 245                                 _request.demands[
 246                                     op.function.loc_z.name].sort_base = 1
 247                                 _open_demand_list.append(op.function.loc_z)
 248                     elif op.function.loc_z.name == d.name:
 249                         if op.function.loc_a.name in \
 250                                 _request.demands.keys():
 251                             if _request.demands[
 252                                     op.function.loc_a.name].sort_base != 1:
 253                                 _request.demands[
 254                                     op.function.loc_a.name].sort_base = 1
 255                                 _open_demand_list.append(op.function.loc_a)
 256
 257         return demand_list
 258
 259     def _exist_not_sorted_demand(self, _demands):
 260         not_sorted_demand = None
 261         for key in _demands:
 262             demand = _demands[key]
 263             if demand.sort_base != 1:
 264                 not_sorted_demand = demand
 265                 break
 266         return not_sorted_demand
 267