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