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):
for the current search [pps].
:param maximum_transmit_rate: Maximum target transmit rate
for the current search [pps].
- :type result: NdrPdrResult
+ :type result: NdrPdrResult.NdrPdrResult
:type phases: int
:type duration: float
:type width_goal: float
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):
+ 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.
to perform before the final phase [1].
:param timeout: The search will fail itself when not finished
before this overall time [s].
- :type measurer: AbstractMeasurer
+ :param doublings: How many doublings to do in external search step.
+ Default 1 is suitable for fairly stable tests,
+ less stable tests might get better overal duration with 2 or more.
+ :type measurer: AbstractMeasurer.AbstractMeasurer
:type final_relative_width: float
:type final_trial_duration: float
:type initial_trial_duration: int
:type number_of_intermediate_phases: int
:type timeout: float
+ :type doublings: int
"""
super(MultipleLossRatioSearch, self).__init__(measurer)
self.final_trial_duration = float(final_trial_duration)
self.number_of_intermediate_phases = int(number_of_intermediate_phases)
self.initial_trial_duration = float(initial_trial_duration)
self.timeout = float(timeout)
+ self.doublings = int(doublings)
@staticmethod
1.0 - MultipleLossRatioSearch.double_relative_width(
relative_width))
+ @staticmethod
+ def expand_down(relative_width, doublings, current_bound):
+ """Return rate of expanded logarithmic width below.
+
+ :param relative_width: The base relative width to double.
+ :param doublings: How many doublings to do for expansion.
+ :param current_bound: The current target transmit rate to move [pps].
+ :type relative_width: float
+ :type doublings: int
+ :type current_bound: float
+ :returns: Transmit rate smaller by logarithmically double width [pps].
+ :rtype: float
+ """
+ for _ in range(doublings):
+ relative_width = MultipleLossRatioSearch.double_relative_width(
+ relative_width)
+ return current_bound * (1.0 - relative_width)
+
@staticmethod
def double_step_up(relative_width, current_bound):
"""Return rate of double logarithmic width above.
1.0 - MultipleLossRatioSearch.double_relative_width(
relative_width))
+ @staticmethod
+ def expand_up(relative_width, doublings, current_bound):
+ """Return rate of expanded logarithmic width above.
+
+ :param relative_width: The base relative width to double.
+ :param doublings: How many doublings to do for expansion.
+ :param current_bound: The current target transmit rate to move [pps].
+ :type relative_width: float
+ :type doublings: int
+ :type current_bound: float
+ :returns: Transmit rate smaller by logarithmically double width [pps].
+ :rtype: float
+ """
+ for _ in range(doublings):
+ relative_width = MultipleLossRatioSearch.double_relative_width(
+ relative_width)
+ return current_bound / (1.0 - relative_width)
+
@staticmethod
def half_relative_width(relative_width):
"""Return relative width corresponding to half logarithmic width.
:type packet_loss_ratio: float
:returns: Structure containing narrowed down intervals
and their measurements.
- :rtype: NdrPdrResult
+ :rtype: NdrPdrResult.NdrPdrResult
:raises RuntimeError: If total duration is larger than timeout.
"""
minimum_transmit_rate = float(minimum_transmit_rate)
:param old_interval: The current interval before the measurement.
:param measurement: The new meaqsurement to take into account.
:param packet_loss_ratio: Fraction for PDR (or zero for NDR).
- :type old_interval: ReceiveRateInterval
- :type measurement: ReceiveRateMeasurement
+ :type old_interval: ReceiveRateInterval.ReceiveRateInterval
+ :type measurement: ReceiveRateMeasurement.ReceiveRateMeasurement
:type packet_loss_ratio: float
:returns: The updated interval.
- :rtype: ReceiveRateInterval
+ :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.
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)
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.double_step_down(ndr_rel_width, 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.double_step_down(pdr_rel_width, 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.double_step_up(ndr_rel_width, 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.double_step_up(pdr_rel_width, 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")
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("ndr lo external %s", result)
+ elif ndr_lo.duration < state.duration:
+ result = state.minimum_transmit_rate
+ logging.info("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("pdr lo external %s", result)
+ elif pdr_lo.duration < state.duration:
+ result = state.minimum_transmit_rate
+ logging.info("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("ndr hi external %s", result)
+ elif ndr_hi.duration < state.duration:
+ result = state.maximum_transmit_rate
+ logging.info("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("pdr hi external %s", result)
+ elif pdr_hi.duration < state.duration:
+ result = state.maximum_transmit_rate
+ logging.info("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("Bisecting for NDR at %s", result)
+ elif pdr_rel_width > state.width_goal:
+ # PDR iternal search.
+ result = self.half_step_up(pdr_rel_width, pdr_lo.target_tr)
+ logging.info("Bisecting for PDR at %s", 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("re-measuring NDR lower bound")
+ elif pdr_lo.duration < state.duration:
+ result = pdr_lo.target_tr
+ logging.info("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("re-measuring NDR upper bound")
+ elif pdr_hi.duration < state.duration and pdr_rel_width > 0.0:
+ result = pdr_hi.target_tr
+ logging.info("re-measuring PDR upper bound")
+ else:
+ result = None
+ return result