-# Copyright (c) 2018 Cisco and/or its affiliates.
+# Copyright (c) 2019 Cisco and/or its affiliates.
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at:
import math
import time
-from AbstractSearchAlgorithm import AbstractSearchAlgorithm
-from NdrPdrResult import NdrPdrResult
-from ReceiveRateInterval import ReceiveRateInterval
+from .AbstractSearchAlgorithm import AbstractSearchAlgorithm
+from .NdrPdrResult import NdrPdrResult
+from .ReceiveRateInterval import ReceiveRateInterval
class MultipleLossRatioSearch(AbstractSearchAlgorithm):
TODO: Support configurable number of Packet Loss Ratios.
"""
- class ProgressState(object):
+ class ProgressState:
"""Structure containing data to be passed around in recursion."""
def __init__(
self.minimum_transmit_rate = float(minimum_transmit_rate)
self.maximum_transmit_rate = float(maximum_transmit_rate)
- def __init__(self, measurer, final_relative_width=0.005,
- final_trial_duration=30.0, initial_trial_duration=1.0,
- number_of_intermediate_phases=2, timeout=600.0, doublings=1):
+ def __init__(
+ self, measurer, final_relative_width=0.005,
+ final_trial_duration=30.0, initial_trial_duration=1.0,
+ number_of_intermediate_phases=2, timeout=600.0, doublings=1):
"""Store the measurer object and additional arguments.
:param measurer: Rate provider to use by this search object.
self.timeout = float(timeout)
self.doublings = int(doublings)
-
@staticmethod
def double_relative_width(relative_width):
"""Return relative width corresponding to double logarithmic width.
:rtype: float
"""
return current_bound * (
- 1.0 - MultipleLossRatioSearch.double_relative_width(
- relative_width))
+ 1.0 - MultipleLossRatioSearch.double_relative_width(relative_width)
+ )
@staticmethod
def expand_down(relative_width, doublings, current_bound):
"""
for _ in range(doublings):
relative_width = MultipleLossRatioSearch.double_relative_width(
- relative_width)
+ relative_width
+ )
return current_bound * (1.0 - relative_width)
@staticmethod
:rtype: float
"""
return current_bound / (
- 1.0 - MultipleLossRatioSearch.double_relative_width(
- relative_width))
+ 1.0 - MultipleLossRatioSearch.double_relative_width(relative_width)
+ )
@staticmethod
def expand_up(relative_width, doublings, current_bound):
"""
for _ in range(doublings):
relative_width = MultipleLossRatioSearch.double_relative_width(
- relative_width)
+ relative_width
+ )
return current_bound / (1.0 - relative_width)
@staticmethod
:rtype: float
"""
return current_bound / (
- 1.0 - MultipleLossRatioSearch.half_relative_width(relative_width))
+ 1.0 - MultipleLossRatioSearch.half_relative_width(relative_width)
+ )
def narrow_down_ndr_and_pdr(
self, minimum_transmit_rate, maximum_transmit_rate,
initial_width_goal = self.double_relative_width(initial_width_goal)
max_lo = maximum_transmit_rate * (1.0 - initial_width_goal)
mrr = max(
- minimum_transmit_rate,
- min(max_lo, line_measurement.receive_rate))
+ minimum_transmit_rate, min(max_lo, line_measurement.receive_rate)
+ )
mrr_measurement = self.measurer.measure(
- self.initial_trial_duration, mrr)
+ self.initial_trial_duration, mrr
+ )
# Attempt to get narrower width.
if mrr_measurement.loss_fraction > 0.0:
max2_lo = mrr * (1.0 - initial_width_goal)
mrr2 = min(max2_lo, mrr_measurement.receive_rate)
else:
mrr2 = mrr / (1.0 - initial_width_goal)
- if mrr2 > minimum_transmit_rate and mrr2 < maximum_transmit_rate:
+ if minimum_transmit_rate < mrr2 < maximum_transmit_rate:
line_measurement = mrr_measurement
mrr_measurement = self.measurer.measure(
self.initial_trial_duration, mrr2)
if mrr2 > mrr:
- buf = line_measurement
- line_measurement = mrr_measurement
- mrr_measurement = buf
+ line_measurement, mrr_measurement = \
+ (mrr_measurement, line_measurement)
starting_interval = ReceiveRateInterval(
mrr_measurement, line_measurement)
starting_result = NdrPdrResult(starting_interval, starting_interval)
state = self.ProgressState(
starting_result, self.number_of_intermediate_phases,
self.final_trial_duration, self.final_relative_width,
- packet_loss_ratio, minimum_transmit_rate, maximum_transmit_rate)
+ packet_loss_ratio, minimum_transmit_rate, maximum_transmit_rate
+ )
state = self.ndrpdr(state)
return state.result
"""
# TODO: Implement https://stackoverflow.com/a/24683360
# to avoid the string manipulation if log verbosity is too low.
- logging.info("result before update: %s", state.result)
+ logging.info(f"result before update: {state.result}")
logging.debug(
- "relative widths in goals: %s", state.result.width_in_goals(
- self.final_relative_width))
+ f"relative widths in goals: "
+ f"{state.result.width_in_goals(self.final_relative_width)}"
+ )
measurement = self.measurer.measure(state.duration, transmit_rate)
ndr_interval = self._new_interval(
- state.result.ndr_interval, measurement, 0.0)
+ state.result.ndr_interval, measurement, 0.0
+ )
pdr_interval = self._new_interval(
- state.result.pdr_interval, measurement, state.packet_loss_ratio)
+ state.result.pdr_interval, measurement, state.packet_loss_ratio
+ )
state.result = NdrPdrResult(ndr_interval, pdr_interval)
return state
:rtype: ReceiveRateInterval.ReceiveRateInterval
"""
old_lo, old_hi = old_interval.measured_low, old_interval.measured_high
+ new_lo = new_hi = None
# Priority zero: direct replace if the target Tr is the same.
if measurement.target_tr in (old_lo.target_tr, old_hi.target_tr):
if measurement.target_tr == old_lo.target_tr:
- return ReceiveRateInterval(measurement, old_hi)
+ new_lo = measurement
else:
- return ReceiveRateInterval(old_lo, measurement)
+ new_hi = measurement
# Priority one: invalid lower bound allows only one type of update.
- if old_lo.loss_fraction > packet_loss_ratio:
+ elif old_lo.loss_fraction > packet_loss_ratio:
# We can only expand down, old bound becomes valid upper one.
if measurement.target_tr < old_lo.target_tr:
- return ReceiveRateInterval(measurement, old_lo)
+ new_lo, new_hi = measurement, old_lo
else:
return old_interval
+
# Lower bound is now valid.
# Next priorities depend on target Tr.
- if measurement.target_tr < old_lo.target_tr:
+ elif measurement.target_tr < old_lo.target_tr:
# Lower external measurement, relevant only
# if the new measurement has high loss rate.
if measurement.loss_fraction > packet_loss_ratio:
# Returning the broader interval as old_lo
# would be invalid upper bound.
- return ReceiveRateInterval(measurement, old_hi)
+ new_lo = measurement
elif measurement.target_tr > old_hi.target_tr:
# Upper external measurement, only relevant for invalid upper bound.
if old_hi.loss_fraction <= packet_loss_ratio:
# Old upper bound becomes valid new lower bound.
- return ReceiveRateInterval(old_hi, measurement)
+ new_lo, new_hi = old_hi, measurement
else:
# Internal measurement, replaced boundary
# depends on measured loss fraction.
if measurement.loss_fraction > packet_loss_ratio:
# We have found a narrow valid interval,
# regardless of whether old upper bound was valid.
- return ReceiveRateInterval(old_lo, measurement)
+ new_hi = measurement
else:
# In ideal world, we would not want to shrink interval
# if upper bound is not valid.
# In the real world, we want to shrink it for
# "invalid upper bound at maximal rate" case.
- return ReceiveRateInterval(measurement, old_hi)
- # Fallback, the interval is unchanged by the measurement.
- return old_interval
+ new_lo = measurement
+
+ return ReceiveRateInterval(
+ old_lo if new_lo is None else new_lo,
+ old_hi if new_hi is None else new_hi
+ )
def ndrpdr(self, state):
- """Pefrom trials for this phase. Return the new state when done.
+ """Perform trials for this phase. Return the new state when done.
:param state: State before this phase.
:type state: ProgressState
duration_multiplier = state.duration / self.initial_trial_duration
phase_exponent = float(state.phases) / saved_phases
state.duration = self.initial_trial_duration * math.pow(
- duration_multiplier, phase_exponent)
+ duration_multiplier, phase_exponent
+ )
# Shorter durations do not need that narrow widths.
saved_width = state.width_goal
state.width_goal = self.double_relative_width(state.width_goal)
state.duration = saved_duration
state.width_goal = saved_width
state.phases = saved_phases # Not needed, but just in case.
+
logging.info(
- "starting iterations with duration %s and relative width goal %s",
- state.duration, state.width_goal)
+ f"starting iterations with duration {state.duration} and relative "
+ f"width goal {state.width_goal}"
+ )
while 1:
if time.time() > start_time + self.timeout:
- raise RuntimeError("Optimized search takes too long.")
+ raise RuntimeError(u"Optimized search takes too long.")
# Order of priorities: invalid bounds (nl, pl, nh, ph),
# then narrowing relative Tr widths.
# Durations are not priorities yet,
pdr_lo = state.result.pdr_interval.measured_low
pdr_hi = state.result.pdr_interval.measured_high
ndr_rel_width = max(
- state.width_goal, state.result.ndr_interval.rel_tr_width)
+ state.width_goal, state.result.ndr_interval.rel_tr_width
+ )
pdr_rel_width = max(
- state.width_goal, state.result.pdr_interval.rel_tr_width)
+ state.width_goal, state.result.pdr_interval.rel_tr_width
+ )
# If we are hitting maximal or minimal rate, we cannot shift,
# but we can re-measure.
- if ndr_lo.loss_fraction > 0.0:
- if ndr_lo.target_tr > state.minimum_transmit_rate:
- new_tr = max(
- state.minimum_transmit_rate,
- self.expand_down(
- ndr_rel_width, self.doublings, ndr_lo.target_tr))
- logging.info("ndr lo external %s", new_tr)
- state = self._measure_and_update_state(state, new_tr)
- continue
- elif ndr_lo.duration < state.duration:
- logging.info("ndr lo minimal re-measure")
- state = self._measure_and_update_state(
- state, state.minimum_transmit_rate)
- continue
- if pdr_lo.loss_fraction > state.packet_loss_ratio:
- if pdr_lo.target_tr > state.minimum_transmit_rate:
- new_tr = max(
- state.minimum_transmit_rate,
- self.expand_down(
- pdr_rel_width, self.doublings, pdr_lo.target_tr))
- logging.info("pdr lo external %s", new_tr)
- state = self._measure_and_update_state(state, new_tr)
- continue
- elif pdr_lo.duration < state.duration:
- logging.info("pdr lo minimal re-measure")
- state = self._measure_and_update_state(
- state, state.minimum_transmit_rate)
- continue
- if ndr_hi.loss_fraction <= 0.0:
- if ndr_hi.target_tr < state.maximum_transmit_rate:
- new_tr = min(
- state.maximum_transmit_rate,
- self.expand_up(
- ndr_rel_width, self.doublings, ndr_hi.target_tr))
- logging.info("ndr hi external %s", new_tr)
- state = self._measure_and_update_state(state, new_tr)
- continue
- elif ndr_hi.duration < state.duration:
- logging.info("ndr hi maximal re-measure")
- state = self._measure_and_update_state(
- state, state.maximum_transmit_rate)
- continue
- if pdr_hi.loss_fraction <= state.packet_loss_ratio:
- if pdr_hi.target_tr < state.maximum_transmit_rate:
- new_tr = min(
- state.maximum_transmit_rate,
- self.expand_up(
- pdr_rel_width, self.doublings, pdr_hi.target_tr))
- logging.info("pdr hi external %s", new_tr)
- state = self._measure_and_update_state(state, new_tr)
- continue
- elif pdr_hi.duration < state.duration:
- logging.info("ndr hi maximal re-measure")
- state = self._measure_and_update_state(
- state, state.maximum_transmit_rate)
- continue
+ new_tr = self._ndrpdr_loss_fraction(
+ state, ndr_lo, ndr_hi, pdr_lo, pdr_hi, ndr_rel_width,
+ pdr_rel_width
+ )
+
+ if new_tr is not None:
+ state = self._measure_and_update_state(state, new_tr)
+ continue
+
# If we are hitting maximum_transmit_rate,
# it is still worth narrowing width,
# hoping large enough loss fraction will happen.
if (pdr_lo.target_tr <= state.minimum_transmit_rate
and pdr_lo.loss_fraction > state.packet_loss_ratio):
pdr_rel_width = 0.0
- if ndr_rel_width > state.width_goal:
- # We have to narrow NDR width first, as NDR internal search
- # can invalidate PDR (but not vice versa).
- new_tr = self.half_step_up(ndr_rel_width, ndr_lo.target_tr)
- logging.info("Bisecting for NDR at %s", new_tr)
- state = self._measure_and_update_state(state, new_tr)
- continue
- if pdr_rel_width > state.width_goal:
- # PDR iternal search.
- new_tr = self.half_step_up(pdr_rel_width, pdr_lo.target_tr)
- logging.info("Bisecting for PDR at %s", new_tr)
+
+ new_tr = self._ndrpdr_width_goal(
+ state, ndr_lo, pdr_lo, ndr_rel_width, pdr_rel_width
+ )
+
+ if new_tr is not None:
state = self._measure_and_update_state(state, new_tr)
continue
+
# We do not need to improve width, but there still might be
# some measurements with smaller duration.
- # We need to re-measure with full duration, possibly
- # creating invalid bounds to resolve (thus broadening width).
- if ndr_lo.duration < state.duration:
- logging.info("re-measuring NDR lower bound")
- self._measure_and_update_state(state, ndr_lo.target_tr)
- continue
- if pdr_lo.duration < state.duration:
- logging.info("re-measuring PDR lower bound")
- self._measure_and_update_state(state, pdr_lo.target_tr)
- continue
- # Except when lower bounds have high loss fraction, in that case
- # we do not need to re-measure _upper_ bounds.
- if ndr_hi.duration < state.duration and ndr_rel_width > 0.0:
- logging.info("re-measuring NDR upper bound")
- self._measure_and_update_state(state, ndr_hi.target_tr)
- continue
- if pdr_hi.duration < state.duration and pdr_rel_width > 0.0:
- logging.info("re-measuring PDR upper bound")
- self._measure_and_update_state(state, pdr_hi.target_tr)
+ new_tr = self._ndrpdr_duration(
+ state, ndr_lo, ndr_hi, pdr_lo, pdr_hi, ndr_rel_width,
+ pdr_rel_width
+ )
+
+ if new_tr is not None:
+ state = self._measure_and_update_state(state, new_tr)
continue
+
# Widths are narrow (or lower bound minimal), bound measurements
# are long enough, we can return.
- logging.info("phase done")
+ logging.info(u"phase done")
break
return state
+
+ def _ndrpdr_loss_fraction(
+ self, state, ndr_lo, ndr_hi, pdr_lo, pdr_hi, ndr_rel_width,
+ pdr_rel_width):
+ """Perform loss_fraction-based trials within a ndrpdr phase
+
+ :param state: current state
+ :param ndr_lo: ndr interval measured low
+ :param ndr_hi: ndr interval measured high
+ :param pdr_lo: pdr interval measured low
+ :param pdr_hi: pdr interval measured high
+ :param ndr_rel_width: ndr interval relative width
+ :param pdr_rel_width: pdr interval relative width
+ :type state: ProgressState
+ :type ndr_lo: ReceiveRateMeasurement.ReceiveRateMeasurement
+ :type ndr_hi: ReceiveRateMeasurement.ReceiveRateMeasurement
+ :type pdr_lo: ReceiveRateMeasurement.ReceiveRateMeasurement
+ :type pdr_hi: ReceiveRateMeasurement.ReceiveRateMeasurement
+ :type ndr_rel_width: float
+ :type pdr_rel_width: float
+ :returns: a new transmit rate if one should be applied
+ :rtype: float
+ """
+ result = None
+ if ndr_lo.loss_fraction > 0.0:
+ if ndr_lo.target_tr > state.minimum_transmit_rate:
+ result = max(
+ state.minimum_transmit_rate, self.expand_down(
+ ndr_rel_width, self.doublings, ndr_lo.target_tr
+ )
+ )
+ logging.info(f"ndr lo external {result}")
+ elif ndr_lo.duration < state.duration:
+ result = state.minimum_transmit_rate
+ logging.info(u"ndr lo minimal re-measure")
+
+ if result is None and pdr_lo.loss_fraction > state.packet_loss_ratio:
+ if pdr_lo.target_tr > state.minimum_transmit_rate:
+ result = max(
+ state.minimum_transmit_rate, self.expand_down(
+ pdr_rel_width, self.doublings, pdr_lo.target_tr
+ )
+ )
+ logging.info(f"pdr lo external {result}")
+ elif pdr_lo.duration < state.duration:
+ result = state.minimum_transmit_rate
+ logging.info(u"pdr lo minimal re-measure")
+
+ if result is None and ndr_hi.loss_fraction <= 0.0:
+ if ndr_hi.target_tr < state.maximum_transmit_rate:
+ result = min(
+ state.maximum_transmit_rate, self.expand_up(
+ ndr_rel_width, self.doublings, ndr_hi.target_tr
+ )
+ )
+ logging.info(f"ndr hi external {result}")
+ elif ndr_hi.duration < state.duration:
+ result = state.maximum_transmit_rate
+ logging.info(u"ndr hi maximal re-measure")
+
+ if result is None and pdr_hi.loss_fraction <= state.packet_loss_ratio:
+ if pdr_hi.target_tr < state.maximum_transmit_rate:
+ result = min(
+ state.maximum_transmit_rate, self.expand_up(
+ pdr_rel_width, self.doublings, pdr_hi.target_tr
+ )
+ )
+ logging.info(f"pdr hi external {result}")
+ elif pdr_hi.duration < state.duration:
+ result = state.maximum_transmit_rate
+ logging.info(u"ndr hi maximal re-measure")
+ return result
+
+ def _ndrpdr_width_goal(
+ self, state, ndr_lo, pdr_lo, ndr_rel_width, pdr_rel_width):
+ """Perform width_goal-based trials within a ndrpdr phase
+
+ :param state: current state
+ :param ndr_lo: ndr interval measured low
+ :param pdr_lo: pdr interval measured low
+ :param ndr_rel_width: ndr interval relative width
+ :param pdr_rel_width: pdr interval relative width
+ :type state: ProgressState
+ :type ndr_lo: ReceiveRateMeasurement.ReceiveRateMeasurement
+ :type pdr_lo: ReceiveRateMeasurement.ReceiveRateMeasurement
+ :type ndr_rel_width: float
+ :type pdr_rel_width: float
+ :returns: a new transmit rate if one should be applied
+ :rtype: float
+ Return a new transmit rate if one should be applied.
+ """
+ if ndr_rel_width > state.width_goal:
+ # We have to narrow NDR width first, as NDR internal search
+ # can invalidate PDR (but not vice versa).
+ result = self.half_step_up(ndr_rel_width, ndr_lo.target_tr)
+ logging.info(f"Bisecting for NDR at {result}")
+ elif pdr_rel_width > state.width_goal:
+ # PDR internal search.
+ result = self.half_step_up(pdr_rel_width, pdr_lo.target_tr)
+ logging.info(f"Bisecting for PDR at {result}")
+ else:
+ result = None
+ return result
+
+ @staticmethod
+ def _ndrpdr_duration(
+ state, ndr_lo, pdr_lo, ndr_hi, pdr_hi, ndr_rel_width,
+ pdr_rel_width):
+ """Perform duration-based trials within a ndrpdr phase
+
+ :param state: current state
+ :param ndr_lo: ndr interval measured low
+ :param ndr_hi: ndr interval measured high
+ :param pdr_lo: pdr interval measured low
+ :param pdr_hi: pdr interval measured high
+ :param ndr_rel_width: ndr interval relative width
+ :param pdr_rel_width: pdr interval relative width
+ :type state: ProgressState
+ :type ndr_lo: ReceiveRateMeasurement.ReceiveRateMeasurement
+ :type ndr_hi: ReceiveRateMeasurement.ReceiveRateMeasurement
+ :type pdr_lo: ReceiveRateMeasurement.ReceiveRateMeasurement
+ :type pdr_hi: ReceiveRateMeasurement.ReceiveRateMeasurement
+ :type ndr_rel_width: float
+ :type pdr_rel_width: float
+ :returns: a new transmit rate if one should be applied
+ :rtype: float
+ """
+ # We need to re-measure with full duration, possibly
+ # creating invalid bounds to resolve (thus broadening width).
+ if ndr_lo.duration < state.duration:
+ result = ndr_lo.target_tr
+ logging.info(u"re-measuring NDR lower bound")
+ elif pdr_lo.duration < state.duration:
+ result = pdr_lo.target_tr
+ logging.info(u"re-measuring PDR lower bound")
+ # Except when lower bounds have high loss fraction, in that case
+ # we do not need to re-measure _upper_ bounds.
+ elif ndr_hi.duration < state.duration and ndr_rel_width > 0.0:
+ result = ndr_hi.target_tr
+ logging.info(u"re-measuring NDR upper bound")
+ elif pdr_hi.duration < state.duration and pdr_rel_width > 0.0:
+ result = pdr_hi.target_tr
+ logging.info(u"re-measuring PDR upper bound")
+ else:
+ result = None
+ return result
Code Review / csit.git / blobdiff