X-Git-Url: https://gerrit.fd.io/r/gitweb?a=blobdiff_plain;f=resources%2Flibraries%2Fpython%2FMLRsearch%2FMultipleLossRatioSearch.py;h=87dc784cbc33d85c91569925e9750d14b9c86ea7;hb=023fa41e51c966a1956bda6b915ffd894ff10e84;hp=be7ffba3a3179fca8b3fc75a18c8c41d95a3c24f;hpb=56fe9e512019d90a5647f4a244ffb8b6f6ff9c47;p=csit.git diff --git a/resources/libraries/python/MLRsearch/MultipleLossRatioSearch.py b/resources/libraries/python/MLRsearch/MultipleLossRatioSearch.py index be7ffba3a3..87dc784cbc 100644 --- a/resources/libraries/python/MLRsearch/MultipleLossRatioSearch.py +++ b/resources/libraries/python/MLRsearch/MultipleLossRatioSearch.py @@ -1,4 +1,4 @@ -# Copyright (c) 2018 Cisco and/or its affiliates. +# Copyright (c) 2020 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: @@ -17,9 +17,9 @@ import logging 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): @@ -79,7 +79,7 @@ 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__( @@ -113,9 +113,10 @@ class MultipleLossRatioSearch(AbstractSearchAlgorithm): 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. @@ -134,7 +135,7 @@ class MultipleLossRatioSearch(AbstractSearchAlgorithm): :type measurer: AbstractMeasurer.AbstractMeasurer :type final_relative_width: float :type final_trial_duration: float - :type initial_trial_duration: int + :type initial_trial_duration: float :type number_of_intermediate_phases: int :type timeout: float :type doublings: int @@ -147,7 +148,6 @@ class MultipleLossRatioSearch(AbstractSearchAlgorithm): self.timeout = float(timeout) self.doublings = int(doublings) - @staticmethod def double_relative_width(relative_width): """Return relative width corresponding to double logarithmic width. @@ -157,7 +157,7 @@ class MultipleLossRatioSearch(AbstractSearchAlgorithm): :returns: The relative width of double logarithmic size. :rtype: float """ - return 1.999 * relative_width - relative_width * relative_width + return 1.99999 * relative_width - relative_width * relative_width # The number should be 2.0, but we want to avoid rounding errors, # and ensure half of double is not larger than the original value. @@ -173,8 +173,8 @@ class MultipleLossRatioSearch(AbstractSearchAlgorithm): :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): @@ -191,7 +191,8 @@ class MultipleLossRatioSearch(AbstractSearchAlgorithm): """ for _ in range(doublings): relative_width = MultipleLossRatioSearch.double_relative_width( - relative_width) + relative_width + ) return current_bound * (1.0 - relative_width) @staticmethod @@ -206,8 +207,8 @@ class MultipleLossRatioSearch(AbstractSearchAlgorithm): :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): @@ -224,7 +225,8 @@ class MultipleLossRatioSearch(AbstractSearchAlgorithm): """ for _ in range(doublings): relative_width = MultipleLossRatioSearch.double_relative_width( - relative_width) + relative_width + ) return current_bound / (1.0 - relative_width) @staticmethod @@ -250,59 +252,59 @@ class MultipleLossRatioSearch(AbstractSearchAlgorithm): :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, - packet_loss_ratio): + def narrow_down_ndr_and_pdr(self, min_rate, max_rate, packet_loss_ratio): """Perform initial phase, create state object, proceed with next phases. - :param minimum_transmit_rate: Minimal target transmit rate [pps]. - :param maximum_transmit_rate: Maximal target transmit rate [pps]. + :param min_rate: Minimal target transmit rate [tps]. + :param max_rate: Maximal target transmit rate [tps]. :param packet_loss_ratio: Fraction of packets lost, for PDR [1]. - :type minimum_transmit_rate: float - :type maximum_transmit_rate: float + :type min_rate: float + :type max_rate: float :type packet_loss_ratio: float :returns: Structure containing narrowed down intervals and their measurements. :rtype: NdrPdrResult.NdrPdrResult :raises RuntimeError: If total duration is larger than timeout. """ - minimum_transmit_rate = float(minimum_transmit_rate) - maximum_transmit_rate = float(maximum_transmit_rate) + minimum_transmit_rate = float(min_rate) + maximum_transmit_rate = float(max_rate) packet_loss_ratio = float(packet_loss_ratio) - line_measurement = self.measurer.measure( + max_measurement = self.measurer.measure( self.initial_trial_duration, maximum_transmit_rate) initial_width_goal = self.final_relative_width for _ in range(self.number_of_intermediate_phases): 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)) + mrr = max(minimum_transmit_rate, min( + max_lo, max_measurement.relative_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) + mrr2 = min(max2_lo, mrr_measurement.relative_receive_rate) else: mrr2 = mrr / (1.0 - initial_width_goal) - if mrr2 > minimum_transmit_rate and mrr2 < maximum_transmit_rate: - line_measurement = mrr_measurement + if minimum_transmit_rate < mrr2 < maximum_transmit_rate: + max_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 + max_measurement, mrr_measurement = \ + (mrr_measurement, max_measurement) starting_interval = ReceiveRateInterval( - mrr_measurement, line_measurement) + mrr_measurement, max_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 @@ -318,15 +320,18 @@ class MultipleLossRatioSearch(AbstractSearchAlgorithm): """ # 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 @@ -344,51 +349,56 @@ class MultipleLossRatioSearch(AbstractSearchAlgorithm): :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 @@ -406,7 +416,8 @@ class MultipleLossRatioSearch(AbstractSearchAlgorithm): 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) @@ -416,12 +427,14 @@ class MultipleLossRatioSearch(AbstractSearchAlgorithm): 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, @@ -431,67 +444,22 @@ class MultipleLossRatioSearch(AbstractSearchAlgorithm): 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. @@ -504,43 +472,174 @@ class MultipleLossRatioSearch(AbstractSearchAlgorithm): 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, ndr_hi, pdr_lo, 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