resources/libraries/python/MLRsearch/MultipleLossRatioSearch.py

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