resources/libraries/python/search/OptimizedSearchAlgorithm.py

   1 # Copyright (c) 2018 Cisco and/or its affiliates.
   2 # Licensed under the Apache License, Version 2.0 (the "License");
   3 # you may not use this file except in compliance with the License.
   4 # You may obtain a copy of the License at:
   5 #
   6 #     http://www.apache.org/licenses/LICENSE-2.0
   7 #
   8 # Unless required by applicable law or agreed to in writing, software
   9 # distributed under the License is distributed on an "AS IS" BASIS,
  10 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  11 # See the License for the specific language governing permissions and
  12 # limitations under the License.
  13
  14 """Module defining OptimizedSearchAlgorithm class."""
  15
  16 import logging
  17 import math
  18 import time
  19
  20 from .AbstractSearchAlgorithm import AbstractSearchAlgorithm
  21 from .NdrPdrResult import NdrPdrResult
  22 from .ReceiveRateInterval import ReceiveRateInterval
  23
  24
  25 class OptimizedSearchAlgorithm(AbstractSearchAlgorithm):
  26     """Optimized binary search algorithm for finding NDR and PDR bounds.
  27
  28     Traditional binary search algorithm needs initial interval
  29     (lower and upper bound), and returns final interval after bisecting
  30     (until some exit condition is met).
  31     The exit condition is usually related to the interval width,
  32     (upper bound value minus lower bound value).
  33
  34     The optimized algorithm contains several improvements
  35     aimed to reduce overall search time.
  36
  37     One improvement is searching for two intervals at once.
  38     The intervals are for NDR (No Drop Rate) and PDR (Partial Drop Rate).
  39
  40     Next improvement is that the initial interval does need to be valid.
  41     Imagine initial interval (10, 11) where 11 is smaller
  42     than the searched value.
  43     The algorithm will try (11, 13) interval next, and if 13 is still smaller,
  44     (13, 17) and so on, doubling width until the upper bound is valid.
  45     The part when interval expands is called external search,
  46     the part when interval is bisected is called internal search.
  47
  48     Next improvement is that trial measurements at small trial duration
  49     can be used to find a reasonable interval for full trial duration search.
  50     This results in more trials performed, but smaller overall duration
  51     in general.
  52
  53     Next improvement is bisecting in logarithmic quantities,
  54     so that exit criteria can be independent of measurement units.
  55
  56     Next improvement is basing the initial interval on receive rates.
  57
  58     Final improvement is exiting early if the minimal value
  59     is not a valid lower bound.
  60
  61     The complete search consist of several phases,
  62     each phase performing several trial measurements.
  63     Initial phase creates initial interval based on receive rates
  64     at maximum rate and at maximum receive rate (MRR).
  65     Final phase and preceding intermediate phases are performing
  66     external and internal search steps,
  67     each resulting interval is the starting point for the next phase.
  68     The resulting interval of final phase is the result of the whole algorithm.
  69
  70     Each non-initial phase uses its own trial duration and width goal.
  71     Any non-initial phase stops searching (for NDR or PDR independently)
  72     when minimum is not a valid lower bound (at current duration),
  73     or all of the following is true:
  74     Both bounds are valid, bound bounds are measured at the current phase
  75     trial duration, interval width is less than the width goal
  76     for current phase.
  77
  78     TODO: Reviwew and update this docstring according to rst docs.
  79     TODO: Initial phase: Larger min width and search up on zero.
  80     TODO: Support configurable number of Packet Loss Ratios.
  81     TODO: Rename to MultipleDropRateSearch (or MultipleLossRatioSearch).
  82     """
  83
  84     class ProgressState(object):
  85         """Structure containing data to be passed around in recursion."""
  86
  87         def __init__(
  88                 self, result, phases, duration, width_goal, packet_loss_ratio,
  89                 minimum_transmit_rate, maximum_transmit_rate):
  90             """Convert and store the argument values.
  91
  92             :param result: Current measured NDR and PDR intervals.
  93             :param phases: How many intermediate phases to perform
  94                 before the current one.
  95             :param duration: Trial duration to use in the current phase [s].
  96             :param width_goal: The goal relative width for the curreent phase.
  97             :param packet_loss_ratio: PDR fraction for the current search.
  98             :param minimum_transmit_rate: Minimum target transmit rate
  99                 for the current search [pps].
 100             :param maximum_transmit_rate: Maximum target transmit rate
 101                 for the current search [pps].
 102             :type result: NdrPdrResult
 103             :type phases: int
 104             :type duration: float
 105             :type width_goal: float
 106             :type packet_loss_ratio: float
 107             :type minimum_transmit_rate: float
 108             :type maximum_transmit_rate: float
 109             """
 110             self.result = result
 111             self.phases = int(phases)
 112             self.duration = float(duration)
 113             self.width_goal = float(width_goal)
 114             self.packet_loss_ratio = float(packet_loss_ratio)
 115             self.minimum_transmit_rate = float(minimum_transmit_rate)
 116             self.maximum_transmit_rate = float(maximum_transmit_rate)
 117
 118     def __init__(self, rate_provider, final_relative_width=0.005,
 119                  final_trial_duration=30.0, initial_trial_duration=1.0,
 120                  number_of_intermediate_phases=2, timeout=600.0):
 121         """Store rate provider and additional arguments.
 122
 123         :param rate_provider: Rate provider to use by this search object.
 124         :param final_relative_width: Final lower bound transmit rate
 125             cannot be more distant that this multiple of upper bound [1].
 126         :param final_trial_duration: Trial duration for the final phase [s].
 127         :param initial_trial_duration: Trial duration for the initial phase
 128             and also for the first intermediate phase [s].
 129         :param number_of_intermediate_phases: Number of intermediate phases
 130             to perform before the final phase [1].
 131         :param timeout: The search will fail itself when not finished
 132             before this overall time [s].
 133         :type rate_provider: AbstractRateProvider
 134         :type final_relative_width: float
 135         :type final_trial_duration: float
 136         :type initial_trial_duration: int
 137         :type number_of_intermediate_phases: int
 138         :type timeout: float
 139         """
 140         super(OptimizedSearchAlgorithm, self).__init__(rate_provider)
 141         self.final_trial_duration = float(final_trial_duration)
 142         self.final_relative_width = float(final_relative_width)
 143         self.number_of_intermediate_phases = int(number_of_intermediate_phases)
 144         self.initial_trial_duration = float(initial_trial_duration)
 145         self.timeout = float(timeout)
 146
 147     def narrow_down_ndr_and_pdr(
 148             self, minimum_transmit_rate, maximum_transmit_rate,
 149             packet_loss_ratio):
 150         """Perform initial phase, create state object, proceed with next phases.
 151
 152         :param minimum_transmit_rate: Minimal target transmit rate [pps].
 153         :param maximum_transmit_rate: Maximal target transmit rate [pps].
 154         :param packet_loss_ratio: Fraction of packets lost, for PDR [1].
 155         :type minimum_transmit_rate: float
 156         :type maximum_transmit_rate: float
 157         :type packet_loss_ratio: float
 158         :returns: Structure containing narrowed down intervals
 159             and their measurements.
 160         :rtype: NdrPdrResult
 161         :raises RuntimeError: If total duration is larger than timeout.
 162         """
 163         minimum_transmit_rate = float(minimum_transmit_rate)
 164         maximum_transmit_rate = float(maximum_transmit_rate)
 165         packet_loss_ratio = float(packet_loss_ratio)
 166         line_measurement = self.rate_provider.measure(
 167             self.initial_trial_duration, maximum_transmit_rate)
 168         # 0.999 is to avoid rounding errors which make
 169         # the subsequent logic think the width is too broad.
 170         max_lo = max(
 171             minimum_transmit_rate,
 172             maximum_transmit_rate * (1.0 - 0.999 * self.final_relative_width))
 173         mrr = min(
 174             max_lo, max(minimum_transmit_rate, line_measurement.receive_rate))
 175         mrr_measurement = self.rate_provider.measure(
 176             self.initial_trial_duration, mrr)
 177         # Attempt to get narrower width.
 178         max2_lo = max(
 179             minimum_transmit_rate,
 180             mrr * (1.0 - 0.999 * self.final_relative_width))
 181         mrr2 = min(max2_lo, mrr_measurement.receive_rate)
 182         if mrr2 > minimum_transmit_rate:
 183             line_measurement = mrr_measurement
 184             mrr_measurement = self.rate_provider.measure(
 185                 self.initial_trial_duration, mrr2)
 186         starting_interval = ReceiveRateInterval(
 187             mrr_measurement, line_measurement)
 188         starting_result = NdrPdrResult(starting_interval, starting_interval)
 189         state = self.ProgressState(
 190             starting_result, self.number_of_intermediate_phases,
 191             self.final_trial_duration, self.final_relative_width,
 192             packet_loss_ratio, minimum_transmit_rate, maximum_transmit_rate)
 193         state = self.ndrpdr(state)
 194         return state.result
 195
 196     def _measure_and_update_state(self, state, transmit_rate):
 197         """Perform trial measurement, update bounds, return new state.
 198
 199         :param state: State before this measurement.
 200         :param transmit_rate: Target transmit rate for this measurement [pps].
 201         :type state: ProgressState
 202         :type transmit_rate: float
 203         :returns: State after the measurement.
 204         :rtype: ProgressState
 205         """
 206         # TODO: Implement https://stackoverflow.com/a/24683360
 207         # to avoid the string manipulation if log verbosity is too low.
 208         logging.info("result before update: %s", state.result)
 209         logging.debug(
 210             "relative widths in goals: %s", state.result.width_in_goals(
 211                 self.final_relative_width))
 212         measurement = self.rate_provider.measure(state.duration, transmit_rate)
 213         ndr_interval = self._new_interval(
 214             state.result.ndr_interval, measurement, 0.0)
 215         pdr_interval = self._new_interval(
 216             state.result.pdr_interval, measurement, state.packet_loss_ratio)
 217         state.result = NdrPdrResult(ndr_interval, pdr_interval)
 218         return state
 219
 220     @staticmethod
 221     def _new_interval(old_interval, measurement, packet_loss_ratio):
 222         """Return new interval with bounds updated according to the measurement.
 223
 224         :param old_interval: The current interval before the measurement.
 225         :param measurement: The new meaqsurement to take into account.
 226         :param packet_loss_ratio: Fraction for PDR (or zero for NDR).
 227         :type old_interval: ReceiveRateInterval
 228         :type measurement: ReceiveRateMeasurement
 229         :type packet_loss_ratio: float
 230         :returns: The updated interval.
 231         :rtype: ReceiveRateInterval
 232         """
 233         old_lo, old_hi = old_interval.measured_low, old_interval.measured_high
 234         # Priority zero: direct replace if the target Tr is the same.
 235         if measurement.target_tr in (old_lo.target_tr, old_hi.target_tr):
 236             if measurement.target_tr == old_lo.target_tr:
 237                 return ReceiveRateInterval(measurement, old_hi)
 238             else:
 239                 return ReceiveRateInterval(old_lo, measurement)
 240         # Priority one: invalid lower bound allows only one type of update.
 241         if old_lo.loss_fraction > packet_loss_ratio:
 242             # We can only expand down, old bound becomes valid upper one.
 243             if measurement.target_tr < old_lo.target_tr:
 244                 return ReceiveRateInterval(measurement, old_lo)
 245             else:
 246                 return old_interval
 247         # Lower bound is now valid.
 248         # Next priorities depend on target Tr.
 249         if measurement.target_tr < old_lo.target_tr:
 250             # Lower external measurement, relevant only
 251             # if the new measurement has high loss rate.
 252             if measurement.loss_fraction > packet_loss_ratio:
 253                 # Returning the broader interval as old_lo
 254                 # would be invalid upper bound.
 255                 return ReceiveRateInterval(measurement, old_hi)
 256         elif measurement.target_tr > old_hi.target_tr:
 257             # Upper external measurement, only relevant for invalid upper bound.
 258             if old_hi.loss_fraction <= packet_loss_ratio:
 259                 # Old upper bound becomes valid new lower bound.
 260                 return ReceiveRateInterval(old_hi, measurement)
 261         else:
 262             # Internal measurement, replaced boundary
 263             # depends on measured loss fraction.
 264             if measurement.loss_fraction > packet_loss_ratio:
 265                 # We have found a narrow valid interval,
 266                 # regardless of whether old upper bound was valid.
 267                 return ReceiveRateInterval(old_lo, measurement)
 268             else:
 269                 # In ideal world, we would not want to shrink interval
 270                 # if upper bound is not valid.
 271                 # In the real world, we want to shrink it for
 272                 # "invalid upper bound at maximal rate" case.
 273                 return ReceiveRateInterval(measurement, old_hi)
 274         # Fallback, the interval is unchanged by the measurement.
 275         return old_interval
 276
 277     @staticmethod
 278     def double_relative_width(relative_width):
 279         """Return relative width corresponding to double logarithmic width.
 280
 281         :param relative_width: The base relative width to double.
 282         :type relative_width: float
 283         :returns: The relative width of double logarithmic size.
 284         :rtype: float
 285         """
 286         return 1.999 * relative_width - relative_width * relative_width
 287         # The number should be 2.0, but we want to avoid rounding errors,
 288         # and ensure half of double is not larger than the original value.
 289
 290     @staticmethod
 291     def double_step_down(relative_width, current_bound):
 292         """Return rate of double logarithmic width below.
 293
 294         :param relative_width: The base relative width to double.
 295         :param current_bound: The current target transmit rate to move [pps].
 296         :type relative_width: float
 297         :type current_bound: float
 298         :returns: Transmit rate smaller by logarithmically double width [pps].
 299         :rtype: float
 300         """
 301         return current_bound * (
 302             1.0 - OptimizedSearchAlgorithm.double_relative_width(
 303                 relative_width))
 304
 305     @staticmethod
 306     def double_step_up(relative_width, current_bound):
 307         """Return rate of double logarithmic width above.
 308
 309         :param relative_width: The base relative width to double.
 310         :param current_bound: The current target transmit rate to move [pps].
 311         :type relative_width: float
 312         :type current_bound: float
 313         :returns: Transmit rate larger by logarithmically double width [pps].
 314         :rtype: float
 315         """
 316         return current_bound / (
 317             1.0 - OptimizedSearchAlgorithm.double_relative_width(
 318                 relative_width))
 319
 320     @staticmethod
 321     def half_relative_width(relative_width):
 322         """Return relative width corresponding to half logarithmic width.
 323
 324         :param relative_width: The base relative width to halve.
 325         :type relative_width: float
 326         :returns: The relative width of half logarithmic size.
 327         :rtype: float
 328         """
 329         return 1.0 - math.sqrt(1.0 - relative_width)
 330
 331     @staticmethod
 332     def half_step_up(relative_width, current_bound):
 333         """Return rate of half logarithmic width above.
 334
 335         :param relative_width: The base relative width to halve.
 336         :param current_bound: The current target transmit rate to move [pps].
 337         :type relative_width: float
 338         :type current_bound: float
 339         :returns: Transmit rate larger by logarithmically half width [pps].
 340         :rtype: float
 341         """
 342         return current_bound / (
 343             1.0 - OptimizedSearchAlgorithm.half_relative_width(relative_width))
 344
 345     def ndrpdr(self, state):
 346         """Pefrom trials for this phase. Return the new state when done.
 347
 348         :param state: State before this phase.
 349         :type state: ProgressState
 350         :returns: The updates state.
 351         :rtype: ProgressState
 352         :raises RuntimeError: If total duration is larger than timeout.
 353         """
 354         if state.phases > 0:
 355             # We need to finish preceding intermediate phases first.
 356             saved_phases = state.phases
 357             state.phases -= 1
 358             # Preceding phases have shorter duration.
 359             saved_duration = state.duration
 360             duration_multiplier = state.duration / self.initial_trial_duration
 361             phase_exponent = float(state.phases) / saved_phases
 362             state.duration = self.initial_trial_duration * math.pow(
 363                 duration_multiplier, phase_exponent)
 364             # Shorter durations do not need that narrow widths.
 365             saved_width = state.width_goal
 366             state.width_goal = self.double_relative_width(state.width_goal)
 367             # Recurse.
 368             state = self.ndrpdr(state)
 369             # Restore the state for current phase.
 370             state.duration = saved_duration
 371             state.width_goal = saved_width
 372             state.phases = saved_phases  # Not needed, but just in case.
 373         logging.info(
 374             "starting iterations with duration %s and relative width goal %s",
 375             state.duration, state.width_goal)
 376         start_time = time.time()
 377         while 1:
 378             if time.time() > start_time + self.timeout:
 379                 raise RuntimeError("Optimized search takes too long.")
 380             # Order of priorities: improper bounds (nl, pl, nh, ph),
 381             # then narrowing relative Tr widths.
 382             # Durations are not priorities yet,
 383             # they will settle on their own hopefully.
 384             ndr_lo = state.result.ndr_interval.measured_low
 385             ndr_hi = state.result.ndr_interval.measured_high
 386             pdr_lo = state.result.pdr_interval.measured_low
 387             pdr_hi = state.result.pdr_interval.measured_high
 388             ndr_rel_width = max(
 389                 state.width_goal, state.result.ndr_interval.rel_tr_width)
 390             pdr_rel_width = max(
 391                 state.width_goal, state.result.pdr_interval.rel_tr_width)
 392             # If we are hitting maximal or minimal rate, we cannot shift,
 393             # but we can re-measure.
 394             if ndr_lo.loss_fraction > 0.0:
 395                 if ndr_lo.target_tr > state.minimum_transmit_rate:
 396                     new_tr = max(
 397                         state.minimum_transmit_rate,
 398                         self.double_step_down(ndr_rel_width, ndr_lo.target_tr))
 399                     logging.info("ndr lo external %s", new_tr)
 400                     state = self._measure_and_update_state(state, new_tr)
 401                     continue
 402                 elif ndr_lo.duration < state.duration:
 403                     logging.info("ndr lo minimal re-measure")
 404                     state = self._measure_and_update_state(
 405                         state, state.minimum_transmit_rate)
 406                     continue
 407             if pdr_lo.loss_fraction > state.packet_loss_ratio:
 408                 if pdr_lo.target_tr > state.minimum_transmit_rate:
 409                     new_tr = max(
 410                         state.minimum_transmit_rate,
 411                         self.double_step_down(pdr_rel_width, pdr_lo.target_tr))
 412                     logging.info("pdr lo external %s", new_tr)
 413                     state = self._measure_and_update_state(state, new_tr)
 414                     continue
 415                 elif pdr_lo.duration < state.duration:
 416                     logging.info("pdr lo minimal re-measure")
 417                     state = self._measure_and_update_state(
 418                         state, state.minimum_transmit_rate)
 419                     continue
 420             if ndr_hi.loss_fraction <= 0.0:
 421                 if ndr_hi.target_tr < state.maximum_transmit_rate:
 422                     new_tr = min(
 423                         state.maximum_transmit_rate,
 424                         self.double_step_up(ndr_rel_width, ndr_hi.target_tr))
 425                     logging.info("ndr hi external %s", new_tr)
 426                     state = self._measure_and_update_state(state, new_tr)
 427                     continue
 428                 elif ndr_hi.duration < state.duration:
 429                     logging.info("ndr hi maximal re-measure")
 430                     state = self._measure_and_update_state(
 431                         state, state.maximum_transmit_rate)
 432                     continue
 433             if pdr_hi.loss_fraction <= state.packet_loss_ratio:
 434                 if pdr_hi.target_tr < state.maximum_transmit_rate:
 435                     new_tr = min(
 436                         state.maximum_transmit_rate,
 437                         self.double_step_up(pdr_rel_width, pdr_hi.target_tr))
 438                     logging.info("pdr hi external %s", new_tr)
 439                     state = self._measure_and_update_state(state, new_tr)
 440                     continue
 441                 elif pdr_hi.duration < state.duration:
 442                     logging.info("ndr hi maximal re-measure")
 443                     state = self._measure_and_update_state(
 444                         state, state.maximum_transmit_rate)
 445                     continue
 446             # If we are hitting maximum_transmit_rate,
 447             # it is still worth narrowing width,
 448             # hoping large enough loss fraction will happen.
 449             # But if we are hitting the minimal rate (at current duration),
 450             # no additional measurement will help with that,
 451             # so we can stop narrowing in this phase.
 452             if (ndr_lo.target_tr <= state.minimum_transmit_rate
 453                     and ndr_lo.loss_fraction > 0.0):
 454                 ndr_rel_width = 0.0
 455             if (pdr_lo.target_tr <= state.minimum_transmit_rate
 456                     and pdr_lo.loss_fraction > state.packet_loss_ratio):
 457                 pdr_rel_width = 0.0
 458             if max(ndr_rel_width, pdr_rel_width) > state.width_goal:
 459                 # We have to narrow some width.
 460                 # TODO: Prefer NDR, it could invalidate PDR (not vice versa).
 461                 if ndr_rel_width >= pdr_rel_width:
 462                     new_tr = self.half_step_up(ndr_rel_width, ndr_lo.target_tr)
 463                     logging.info("Bisecting for NDR at %s", new_tr)
 464                     state = self._measure_and_update_state(state, new_tr)
 465                     continue
 466                 else:
 467                     new_tr = self.half_step_up(pdr_rel_width, pdr_lo.target_tr)
 468                     logging.info("Bisecting for PDR at %s", new_tr)
 469                     state = self._measure_and_update_state(state, new_tr)
 470                     continue
 471             # We do not need to improve width, but there still might be
 472             # some measurements with smaller duration.
 473             # We need to re-measure with full duration, possibly
 474             # creating invalid bounds to resolve (thus broadening width).
 475             if ndr_lo.duration < state.duration:
 476                 logging.info("re-measuring NDR lower bound")
 477                 self._measure_and_update_state(state, ndr_lo.target_tr)
 478                 continue
 479             if pdr_lo.duration < state.duration:
 480                 logging.info("re-measuring PDR lower bound")
 481                 self._measure_and_update_state(state, pdr_lo.target_tr)
 482                 continue
 483             # Except when lower bounds have high loss fraction, in that case
 484             # we do not need to re-measure _upper_ bounds.
 485             if ndr_hi.duration < state.duration and ndr_rel_width > 0.0:
 486                 logging.info("re-measuring NDR upper bound")
 487                 self._measure_and_update_state(state, ndr_hi.target_tr)
 488                 continue
 489             if pdr_hi.duration < state.duration and pdr_rel_width > 0.0:
 490                 logging.info("re-measuring PDR upper bound")
 491                 self._measure_and_update_state(state, pdr_hi.target_tr)
 492                 continue
 493             # Widths are narrow (or lower bound minimal), bound measurements
 494             # are long enough, we can return.
 495             logging.info("phase done")
 496             break
 497         return state