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     class ProgressState(object):
  79         """Structure containing data to be passed around in recursion."""
  80
  81         def __init__(
  82                 self, result, phases, duration, width_goal, packet_loss_ratio,
  83                 minimum_transmit_rate, maximum_transmit_rate):
  84             """Convert and store the argument values.
  85
  86             :param result: Current measured NDR and PDR intervals.
  87             :param phases: How many intermediate phases to perform
  88                 before the current one.
  89             :param duration: Trial duration to use in the current phase [s].
  90             :param width_goal: The goal relative width for the curreent phase.
  91             :param packet_loss_ratio: PDR fraction for the current search.
  92             :param minimum_transmit_rate: Minimum target transmit rate
  93                 for the current search [pps].
  94             :param maximum_transmit_rate: Maximum target transmit rate
  95                 for the current search [pps].
  96             :type result: NdrPdrResult
  97             :type phases: int
  98             :type duration: float
  99             :type width_goal: float
 100             :type packet_loss_ratio: float
 101             :type minimum_transmit_rate: float
 102             :type maximum_transmit_rate: float
 103             """
 104             self.result = result
 105             self.phases = int(phases)
 106             self.duration = float(duration)
 107             self.width_goal = float(width_goal)
 108             self.packet_loss_ratio = float(packet_loss_ratio)
 109             self.minimum_transmit_rate = float(minimum_transmit_rate)
 110             self.maximum_transmit_rate = float(maximum_transmit_rate)
 111
 112     def __init__(self, rate_provider, final_relative_width=0.005,
 113                  final_trial_duration=30.0, initial_trial_duration=1.0,
 114                  number_of_intermediate_phases=2, timeout=600.0):
 115         """Store rate provider and additional arguments.
 116
 117         :param rate_provider: Rate provider to use by this search object.
 118         :param final_relative_width: Final lower bound transmit rate
 119             cannot be more distant that this multiple of upper bound [1].
 120         :param final_trial_duration: Trial duration for the final phase [s].
 121         :param initial_trial_duration: Trial duration for the initial phase
 122             and also for the first intermediate phase [s].
 123         :param number_of_intermediate_phases: Number of intermediate phases
 124             to perform before the final phase [1].
 125         :param timeout: The search will fail itself when not finished
 126             before this overall time [s].
 127         :type rate_provider: AbstractRateProvider
 128         :type final_relative_width: float
 129         :type final_trial_duration: float
 130         :type initial_trial_duration: int
 131         :type number_of_intermediate_phases: int
 132         :type timeout: float
 133         """
 134         super(OptimizedSearchAlgorithm, self).__init__(rate_provider)
 135         self.final_trial_duration = float(final_trial_duration)
 136         self.final_relative_width = float(final_relative_width)
 137         self.number_of_intermediate_phases = int(number_of_intermediate_phases)
 138         self.initial_trial_duration = float(initial_trial_duration)
 139         self.timeout = float(timeout)
 140
 141     def narrow_down_ndr_and_pdr(
 142             self, minimum_transmit_rate, maximum_transmit_rate,
 143             packet_loss_ratio):
 144         """Perform initial phase, create state object, proceed with next phases.
 145
 146         :param minimum_transmit_rate: Minimal target transmit rate [pps].
 147         :param maximum_transmit_rate: Maximal target transmit rate [pps].
 148         :param packet_loss_ratio: Fraction of packets lost, for PDR [1].
 149         :type minimum_transmit_rate: float
 150         :type maximum_transmit_rate: float
 151         :type packet_loss_ratio: float
 152         :returns: Structure containing narrowed down intervals
 153             and their measurements.
 154         :rtype: NdrPdrResult
 155         :raises RuntimeError: If total duration is larger than timeout.
 156         """
 157         minimum_transmit_rate = float(minimum_transmit_rate)
 158         maximum_transmit_rate = float(maximum_transmit_rate)
 159         packet_loss_ratio = float(packet_loss_ratio)
 160         line_measurement = self.rate_provider.measure(
 161             self.initial_trial_duration, maximum_transmit_rate)
 162         # 0.999 is to avoid rounding errors which make
 163         # the subsequent logic think the width is too broad.
 164         max_lo = max(
 165             minimum_transmit_rate,
 166             maximum_transmit_rate * (1.0 - 0.999 * self.final_relative_width))
 167         mrr = min(
 168             max_lo, max(minimum_transmit_rate, line_measurement.receive_rate))
 169         mrr_measurement = self.rate_provider.measure(
 170             self.initial_trial_duration, mrr)
 171         # Attempt to get narrower width.
 172         max2_lo = max(
 173             minimum_transmit_rate,
 174             mrr * (1.0 - 0.999 * self.final_relative_width))
 175         mrr2 = min(max2_lo, mrr_measurement.receive_rate)
 176         if mrr2 > minimum_transmit_rate:
 177             line_measurement = mrr_measurement
 178             mrr_measurement = self.rate_provider.measure(
 179                 self.initial_trial_duration, mrr2)
 180         starting_interval = ReceiveRateInterval(
 181             mrr_measurement, line_measurement)
 182         starting_result = NdrPdrResult(starting_interval, starting_interval)
 183         state = self.ProgressState(
 184             starting_result, self.number_of_intermediate_phases,
 185             self.final_trial_duration, self.final_relative_width,
 186             packet_loss_ratio, minimum_transmit_rate, maximum_transmit_rate)
 187         state = self.ndrpdr(state)
 188         return state.result
 189
 190     def _measure_and_update_state(self, state, transmit_rate):
 191         """Perform trial measurement, update bounds, return new state.
 192
 193         :param state: State before this measurement.
 194         :param transmit_rate: Target transmit rate for this measurement [pps].
 195         :type state: ProgressState
 196         :type transmit_rate: float
 197         :returns: State after the measurement.
 198         :rtype: ProgressState
 199         """
 200         # TODO: Implement https://stackoverflow.com/a/24683360
 201         # to avoid the string manipulation if log verbosity is too low.
 202         logging.info("result before update: %s", state.result)
 203         logging.debug(
 204             "relative widths in goals: %s", state.result.width_in_goals(
 205                 self.final_relative_width))
 206         measurement = self.rate_provider.measure(state.duration, transmit_rate)
 207         ndr_interval = self._new_interval(
 208             state.result.ndr_interval, measurement, 0.0)
 209         pdr_interval = self._new_interval(
 210             state.result.pdr_interval, measurement, state.packet_loss_ratio)
 211         state.result = NdrPdrResult(ndr_interval, pdr_interval)
 212         return state
 213
 214     @staticmethod
 215     def _new_interval(old_interval, measurement, packet_loss_ratio):
 216         """Return new interval with bounds updated according to the measurement.
 217
 218         :param old_interval: The current interval before the measurement.
 219         :param measurement: The new meaqsurement to take into account.
 220         :param packet_loss_ratio: Fraction for PDR (or zero for NDR).
 221         :type old_interval: ReceiveRateInterval
 222         :type measurement: ReceiveRateMeasurement
 223         :type packet_loss_ratio: float
 224         :returns: The updated interval.
 225         :rtype: ReceiveRateInterval
 226         """
 227         old_lo, old_hi = old_interval.measured_low, old_interval.measured_high
 228         # Priority zero: direct replace if the target Tr is the same.
 229         if measurement.target_tr in (old_lo.target_tr, old_hi.target_tr):
 230             if measurement.target_tr == old_lo.target_tr:
 231                 return ReceiveRateInterval(measurement, old_hi)
 232             else:
 233                 return ReceiveRateInterval(old_lo, measurement)
 234         # Priority one: invalid lower bound allows only one type of update.
 235         if old_lo.loss_fraction > packet_loss_ratio:
 236             # We can only expand down, old bound becomes valid upper one.
 237             if measurement.target_tr < old_lo.target_tr:
 238                 return ReceiveRateInterval(measurement, old_lo)
 239             else:
 240                 return old_interval
 241         # Lower bound is now valid.
 242         # Next priorities depend on target Tr.
 243         if measurement.target_tr < old_lo.target_tr:
 244             # Lower external measurement, relevant only
 245             # if the new measurement has high loss rate.
 246             if measurement.loss_fraction > packet_loss_ratio:
 247                 # Returning the broader interval as old_lo
 248                 # would be invalid upper bound.
 249                 return ReceiveRateInterval(measurement, old_hi)
 250         elif measurement.target_tr > old_hi.target_tr:
 251             # Upper external measurement, only relevant for invalid upper bound.
 252             if old_hi.loss_fraction <= packet_loss_ratio:
 253                 # Old upper bound becomes valid new lower bound.
 254                 return ReceiveRateInterval(old_hi, measurement)
 255         else:
 256             # Internal measurement, replaced boundary
 257             # depends on measured loss fraction.
 258             if measurement.loss_fraction > packet_loss_ratio:
 259                 # We have found a narrow valid interval,
 260                 # regardless of whether old upper bound was valid.
 261                 return ReceiveRateInterval(old_lo, measurement)
 262             else:
 263                 # In ideal world, we would not want to shrink interval
 264                 # if upper bound is not valid.
 265                 # In the real world, we want to shrink it for
 266                 # "invalid upper bound at maximal rate" case.
 267                 return ReceiveRateInterval(measurement, old_hi)
 268         # Fallback, the interval is unchanged by the measurement.
 269         return old_interval
 270
 271     @staticmethod
 272     def double_relative_width(relative_width):
 273         """Return relative width corresponding to double logarithmic width.
 274
 275         :param relative_width: The base relative width to double.
 276         :type relative_width: float
 277         :returns: The relative width of double logarithmic size.
 278         :rtype: float
 279         """
 280         return 1.999 * relative_width - relative_width * relative_width
 281         # The number should be 2.0, but we want to avoid rounding errors,
 282         # and ensure half of double is not larger than the original value.
 283
 284     @staticmethod
 285     def double_step_down(relative_width, current_bound):
 286         """Return rate of double logarithmic width below.
 287
 288         :param relative_width: The base relative width to double.
 289         :param current_bound: The current target transmit rate to move [pps].
 290         :type relative_width: float
 291         :type current_bound: float
 292         :returns: Transmit rate smaller by logarithmically double width [pps].
 293         :rtype: float
 294         """
 295         return current_bound * (
 296             1.0 - OptimizedSearchAlgorithm.double_relative_width(
 297                 relative_width))
 298
 299     @staticmethod
 300     def double_step_up(relative_width, current_bound):
 301         """Return rate of double logarithmic width above.
 302
 303         :param relative_width: The base relative width to double.
 304         :param current_bound: The current target transmit rate to move [pps].
 305         :type relative_width: float
 306         :type current_bound: float
 307         :returns: Transmit rate larger by logarithmically double width [pps].
 308         :rtype: float
 309         """
 310         return current_bound / (
 311             1.0 - OptimizedSearchAlgorithm.double_relative_width(
 312                 relative_width))
 313
 314     @staticmethod
 315     def half_relative_width(relative_width):
 316         """Return relative width corresponding to half logarithmic width.
 317
 318         :param relative_width: The base relative width to halve.
 319         :type relative_width: float
 320         :returns: The relative width of half logarithmic size.
 321         :rtype: float
 322         """
 323         return 1.0 - math.sqrt(1.0 - relative_width)
 324
 325     @staticmethod
 326     def half_step_up(relative_width, current_bound):
 327         """Return rate of half logarithmic width above.
 328
 329         :param relative_width: The base relative width to halve.
 330         :param current_bound: The current target transmit rate to move [pps].
 331         :type relative_width: float
 332         :type current_bound: float
 333         :returns: Transmit rate larger by logarithmically half width [pps].
 334         :rtype: float
 335         """
 336         return current_bound / (
 337             1.0 - OptimizedSearchAlgorithm.half_relative_width(relative_width))
 338
 339     def ndrpdr(self, state):
 340         """Pefrom trials for this phase. Return the new state when done.
 341
 342         :param state: State before this phase.
 343         :type state: ProgressState
 344         :returns: The updates state.
 345         :rtype: ProgressState
 346         :raises RuntimeError: If total duration is larger than timeout.
 347         """
 348         if state.phases > 0:
 349             # We need to finish preceding intermediate phases first.
 350             saved_phases = state.phases
 351             state.phases -= 1
 352             # Preceding phases have shorter duration.
 353             saved_duration = state.duration
 354             duration_multiplier = state.duration / self.initial_trial_duration
 355             phase_exponent = float(state.phases) / saved_phases
 356             state.duration = self.initial_trial_duration * math.pow(
 357                 duration_multiplier, phase_exponent)
 358             # Shorter durations do not need that narrow widths.
 359             saved_width = state.width_goal
 360             state.width_goal = self.double_relative_width(state.width_goal)
 361             # Recurse.
 362             state = self.ndrpdr(state)
 363             # Restore the state for current phase.
 364             state.duration = saved_duration
 365             state.width_goal = saved_width
 366             state.phases = saved_phases  # Not needed, but just in case.
 367         logging.info(
 368             "starting iterations with duration %s and relative width goal %s",
 369             state.duration, state.width_goal)
 370         start_time = time.time()
 371         while 1:
 372             if time.time() > start_time + self.timeout:
 373                 raise RuntimeError("Optimized search takes too long.")
 374             # Order of priorities: improper bounds (nl, pl, nh, ph),
 375             # then narrowing relative Tr widths.
 376             # Durations are not priorities yet,
 377             # they will settle on their own hopefully.
 378             ndr_lo = state.result.ndr_interval.measured_low
 379             ndr_hi = state.result.ndr_interval.measured_high
 380             pdr_lo = state.result.pdr_interval.measured_low
 381             pdr_hi = state.result.pdr_interval.measured_high
 382             ndr_rel_width = max(
 383                 state.width_goal, state.result.ndr_interval.rel_tr_width)
 384             pdr_rel_width = max(
 385                 state.width_goal, state.result.pdr_interval.rel_tr_width)
 386             # If we are hitting maximal or minimal rate, we cannot shift,
 387             # but we can re-measure.
 388             if ndr_lo.loss_fraction > 0.0:
 389                 if ndr_lo.target_tr > state.minimum_transmit_rate:
 390                     new_tr = max(
 391                         state.minimum_transmit_rate,
 392                         self.double_step_down(ndr_rel_width, ndr_lo.target_tr))
 393                     logging.info("ndr lo external %s", new_tr)
 394                     state = self._measure_and_update_state(state, new_tr)
 395                     continue
 396                 elif ndr_lo.duration < state.duration:
 397                     logging.info("ndr lo minimal re-measure")
 398                     state = self._measure_and_update_state(
 399                         state, state.minimum_transmit_rate)
 400                     continue
 401             if pdr_lo.loss_fraction > state.packet_loss_ratio:
 402                 if pdr_lo.target_tr > state.minimum_transmit_rate:
 403                     new_tr = max(
 404                         state.minimum_transmit_rate,
 405                         self.double_step_down(pdr_rel_width, pdr_lo.target_tr))
 406                     logging.info("pdr lo external %s", new_tr)
 407                     state = self._measure_and_update_state(state, new_tr)
 408                     continue
 409                 elif pdr_lo.duration < state.duration:
 410                     logging.info("pdr lo minimal re-measure")
 411                     state = self._measure_and_update_state(
 412                         state, state.minimum_transmit_rate)
 413                     continue
 414             if ndr_hi.loss_fraction <= 0.0:
 415                 if ndr_hi.target_tr < state.maximum_transmit_rate:
 416                     new_tr = min(
 417                         state.maximum_transmit_rate,
 418                         self.double_step_up(ndr_rel_width, ndr_hi.target_tr))
 419                     logging.info("ndr hi external %s", new_tr)
 420                     state = self._measure_and_update_state(state, new_tr)
 421                     continue
 422                 elif ndr_hi.duration < state.duration:
 423                     logging.info("ndr hi maximal re-measure")
 424                     state = self._measure_and_update_state(
 425                         state, state.maximum_transmit_rate)
 426                     continue
 427             if pdr_hi.loss_fraction <= state.packet_loss_ratio:
 428                 if pdr_hi.target_tr < state.maximum_transmit_rate:
 429                     new_tr = min(
 430                         state.maximum_transmit_rate,
 431                         self.double_step_up(pdr_rel_width, pdr_hi.target_tr))
 432                     logging.info("pdr hi external %s", new_tr)
 433                     state = self._measure_and_update_state(state, new_tr)
 434                     continue
 435                 elif pdr_hi.duration < state.duration:
 436                     logging.info("ndr hi maximal re-measure")
 437                     state = self._measure_and_update_state(
 438                         state, state.maximum_transmit_rate)
 439                     continue
 440             # If we are hitting maximum_transmit_rate,
 441             # it is still worth narrowing width,
 442             # hoping large enough Df will happen.
 443             # But if we are hitting the minimal rate (at current duration),
 444             # no additional measurement will help with that,
 445             # so we can stop narrowing in this phase.
 446             if (ndr_lo.target_tr <= state.minimum_transmit_rate
 447                     and ndr_lo.loss_fraction > 0.0):
 448                 ndr_rel_width = 0.0
 449             if (pdr_lo.target_tr <= state.minimum_transmit_rate
 450                     and pdr_lo.loss_fraction > state.packet_loss_ratio):
 451                 pdr_rel_width = 0.0
 452             if max(ndr_rel_width, pdr_rel_width) > state.width_goal:
 453                 # We have to narrow some width.
 454                 if ndr_rel_width >= pdr_rel_width:
 455                     new_tr = self.half_step_up(ndr_rel_width, ndr_lo.target_tr)
 456                     logging.info("Bisecting for NDR at %s", new_tr)
 457                     state = self._measure_and_update_state(state, new_tr)
 458                     continue
 459                 else:
 460                     new_tr = self.half_step_up(pdr_rel_width, pdr_lo.target_tr)
 461                     logging.info("Bisecting for PDR at %s", new_tr)
 462                     state = self._measure_and_update_state(state, new_tr)
 463                     continue
 464             # We do not need to improve width, but there still might be
 465             # some measurements with smaller duration.
 466             # We need to re-measure with full duration, possibly
 467             # creating invalid bounds to resolve (thus broadening width).
 468             if ndr_lo.duration < state.duration:
 469                 logging.info("re-measuring NDR lower bound")
 470                 self._measure_and_update_state(state, ndr_lo.target_tr)
 471                 continue
 472             if pdr_lo.duration < state.duration:
 473                 logging.info("re-measuring PDR lower bound")
 474                 self._measure_and_update_state(state, pdr_lo.target_tr)
 475                 continue
 476             # Except when lower bounds have high Df, in that case
 477             # we do not need to re-measure _upper_ bounds.
 478             if ndr_hi.duration < state.duration and ndr_rel_width > 0.0:
 479                 logging.info("re-measuring NDR upper bound")
 480                 self._measure_and_update_state(state, ndr_hi.target_tr)
 481                 continue
 482             if pdr_hi.duration < state.duration and pdr_rel_width > 0.0:
 483                 logging.info("re-measuring PDR upper bound")
 484                 self._measure_and_update_state(state, pdr_hi.target_tr)
 485                 continue
 486             # Widths are narrow (or lower bound minimal), bound measurements
 487             # are long enough, we can return.
 488             logging.info("phase done")
 489             break
 490         return state