From a9f251c649a5dea7428a43dc24380077a72dacba Mon Sep 17 00:00:00 2001 From: Vratko Polak Date: Mon, 28 May 2018 11:53:45 +0200 Subject: CSIT-986: Implement proposed MDR improvements + Use first intermediate with goal in initial phase. + Measure above MRR if that got zero loss. + Always prioritizes NDR in internal search. + Rename classes. + Copy code for standalone PyPI publishing. - Original files will be deleted after publish. Change-Id: I5169d602d1e5e35a1894645cd52e70d791871608 Signed-off-by: Vratko Polak --- resources/libraries/python/TrafficGenerator.py | 12 +- .../libraries/python/search/AbstractMeasurer.py | 35 ++ .../python/search/AbstractRateProvider.py | 35 -- .../python/search/AbstractSearchAlgorithm.py | 12 +- .../python/search/MultipleLossRatioSearch.py | 501 +++++++++++++++++++++ resources/libraries/python/search/NdrPdrResult.py | 2 +- .../python/search/OptimizedSearchAlgorithm.py | 497 -------------------- .../libraries/python/search/ReceiveRateInterval.py | 4 +- resources/libraries/python/search/__init__.py | 2 +- 9 files changed, 553 insertions(+), 547 deletions(-) create mode 100644 resources/libraries/python/search/AbstractMeasurer.py delete mode 100644 resources/libraries/python/search/AbstractRateProvider.py create mode 100644 resources/libraries/python/search/MultipleLossRatioSearch.py delete mode 100644 resources/libraries/python/search/OptimizedSearchAlgorithm.py (limited to 'resources') diff --git a/resources/libraries/python/TrafficGenerator.py b/resources/libraries/python/TrafficGenerator.py index 816b946381..ee65c1bf2a 100644 --- a/resources/libraries/python/TrafficGenerator.py +++ b/resources/libraries/python/TrafficGenerator.py @@ -22,8 +22,8 @@ from .ssh import SSH from .topology import NodeType from .topology import NodeSubTypeTG from .topology import Topology -from .search.AbstractRateProvider import AbstractRateProvider -from .search.OptimizedSearchAlgorithm import OptimizedSearchAlgorithm +from .search.AbstractMeasurer import AbstractMeasurer +from .search.MultipleLossRatioSearch import MultipleLossRatioSearch from .search.ReceiveRateMeasurement import ReceiveRateMeasurement __all__ = ['TGDropRateSearchImpl', 'TrafficGenerator', 'OptimizedSearch'] @@ -101,7 +101,7 @@ class TGDropRateSearchImpl(DropRateSearch): return tg_instance.get_latency_int() -class TrafficGenerator(AbstractRateProvider): +class TrafficGenerator(AbstractMeasurer): """Traffic Generator. FIXME: Describe API.""" @@ -643,7 +643,7 @@ class OptimizedSearch(object): :type initial_trial_duration: float :type number_of_intermediate_phases: int :type timeout: float - :returns: Structure containing narrowed down intervals + :returns: Structure containing narrowed down NDR and PDR intervals and their measurements. :rtype: NdrPdrResult :raises RuntimeError: If total duration is larger than timeout. @@ -653,8 +653,8 @@ class OptimizedSearch(object): tg_instance = BuiltIn().get_library_instance( 'resources.libraries.python.TrafficGenerator') tg_instance.set_rate_provider_defaults(frame_size, traffic_type) - algorithm = OptimizedSearchAlgorithm( - tg_instance, final_trial_duration=final_trial_duration, + algorithm = MultipleLossRatioSearch( + measurer=tg_instance, final_trial_duration=final_trial_duration, final_relative_width=final_relative_width, number_of_intermediate_phases=number_of_intermediate_phases, initial_trial_duration=initial_trial_duration, timeout=timeout) diff --git a/resources/libraries/python/search/AbstractMeasurer.py b/resources/libraries/python/search/AbstractMeasurer.py new file mode 100644 index 0000000000..b972c4eb18 --- /dev/null +++ b/resources/libraries/python/search/AbstractMeasurer.py @@ -0,0 +1,35 @@ +# Copyright (c) 2018 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: +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +"""Module defining AbstractMeasurer class.""" + +from abc import ABCMeta, abstractmethod + + +class AbstractMeasurer(object): + """Abstract class defining common API for measurement providers.""" + + __metaclass__ = ABCMeta + + @abstractmethod + def measure(self, duration, transmit_rate): + """Perform trial measurement and return the result. + + :param duration: Trial duration [s]. + :param transmit_rate: Target transmit rate [pps]. + :type duration: float + :type transmit_rate: float + :returns: Structure containing the result of the measurement. + :rtype: ReceiveRateMeasurement + """ + pass diff --git a/resources/libraries/python/search/AbstractRateProvider.py b/resources/libraries/python/search/AbstractRateProvider.py deleted file mode 100644 index 125c2af8cc..0000000000 --- a/resources/libraries/python/search/AbstractRateProvider.py +++ /dev/null @@ -1,35 +0,0 @@ -# Copyright (c) 2018 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: -# -# http://www.apache.org/licenses/LICENSE-2.0 -# -# Unless required by applicable law or agreed to in writing, software -# distributed under the License is distributed on an "AS IS" BASIS, -# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -# See the License for the specific language governing permissions and -# limitations under the License. - -"""Module defining AbstractRateProvider class.""" - -from abc import ABCMeta, abstractmethod - - -class AbstractRateProvider(object): - """Abstract class defining common API for rate providers.""" - - __metaclass__ = ABCMeta - - @abstractmethod - def measure(self, duration, transmit_rate): - """Perform trial measurement and return the result. - - :param duration: Trial duration [s]. - :param transmit_rate: Target transmit rate [pps]. - :type duration: float - :type transmit_rate: float - :returns: Structure containing the result of the measurement. - :rtype: ReceiveRateMeasurement - """ - pass diff --git a/resources/libraries/python/search/AbstractSearchAlgorithm.py b/resources/libraries/python/search/AbstractSearchAlgorithm.py index 08f3a6bebc..538322a42c 100644 --- a/resources/libraries/python/search/AbstractSearchAlgorithm.py +++ b/resources/libraries/python/search/AbstractSearchAlgorithm.py @@ -21,20 +21,22 @@ class AbstractSearchAlgorithm(object): __metaclass__ = ABCMeta - def __init__(self, rate_provider): + def __init__(self, measurer): """Store the rate provider. - :param rate_provider: Object able to perform trial measurements. - :type rate_provider: AbstractRateProvider + :param measurer: Object able to perform trial or composite measurements. + :type measurer: AbstractMeasurer """ - # TODO: Type check for AbstractRateProvider? - self.rate_provider = rate_provider + # TODO: Type check for AbstractMeasurer? + self.measurer = measurer @abstractmethod def narrow_down_ndr_and_pdr( self, fail_rate, line_rate, packet_loss_ratio): """Perform measurements to narrow down intervals, return them. + This will be renamed when custom loss ratio lists are supported. + :param fail_rate: Minimal target transmit rate [pps]. :param line_rate: Maximal target transmit rate [pps]. :param packet_loss_ratio: Fraction of packets lost, for PDR [1]. diff --git a/resources/libraries/python/search/MultipleLossRatioSearch.py b/resources/libraries/python/search/MultipleLossRatioSearch.py new file mode 100644 index 0000000000..0eb1d7da4c --- /dev/null +++ b/resources/libraries/python/search/MultipleLossRatioSearch.py @@ -0,0 +1,501 @@ +# Copyright (c) 2018 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: +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +"""Module defining MultipleLossRatioSearch class.""" + +import logging +import math +import time + +from AbstractSearchAlgorithm import AbstractSearchAlgorithm +from NdrPdrResult import NdrPdrResult +from ReceiveRateInterval import ReceiveRateInterval + + +class MultipleLossRatioSearch(AbstractSearchAlgorithm): + """Optimized binary search algorithm for finding NDR and PDR bounds. + + Traditional binary search algorithm needs initial interval + (lower and upper bound), and returns final interval after bisecting + (until some exit condition is met). + The exit condition is usually related to the interval width, + (upper bound value minus lower bound value). + + The optimized algorithm contains several improvements + aimed to reduce overall search time. + + One improvement is searching for two intervals at once. + The intervals are for NDR (No Drop Rate) and PDR (Partial Drop Rate). + + Next improvement is that the initial interval does not need to be valid. + Imagine initial interval (10, 11) where 11 is smaller + than the searched value. + The algorithm will try (11, 13) interval next, and if 13 is still smaller, + (13, 17) and so on, doubling width until the upper bound is valid. + The part when interval expands is called external search, + the part when interval is bisected is called internal search. + + Next improvement is that trial measurements at small trial duration + can be used to find a reasonable interval for full trial duration search. + This results in more trials performed, but smaller overall duration + in general. + + Next improvement is bisecting in logarithmic quantities, + so that exit criteria can be independent of measurement units. + + Next improvement is basing the initial interval on receive rates. + + Final improvement is exiting early if the minimal value + is not a valid lower bound. + + The complete search consist of several phases, + each phase performing several trial measurements. + Initial phase creates initial interval based on receive rates + at maximum rate and at maximum receive rate (MRR). + Final phase and preceding intermediate phases are performing + external and internal search steps, + each resulting interval is the starting point for the next phase. + The resulting interval of final phase is the result of the whole algorithm. + + Each non-initial phase uses its own trial duration and width goal. + Any non-initial phase stops searching (for NDR or PDR independently) + when minimum is not a valid lower bound (at current duration), + or all of the following is true: + Both bounds are valid, bound bounds are measured at the current phase + trial duration, interval width is less than the width goal + for current phase. + + TODO: Review and update this docstring according to rst docs. + TODO: Support configurable number of Packet Loss Ratios. + """ + + class ProgressState(object): + """Structure containing data to be passed around in recursion.""" + + def __init__( + self, result, phases, duration, width_goal, packet_loss_ratio, + minimum_transmit_rate, maximum_transmit_rate): + """Convert and store the argument values. + + :param result: Current measured NDR and PDR intervals. + :param phases: How many intermediate phases to perform + before the current one. + :param duration: Trial duration to use in the current phase [s]. + :param width_goal: The goal relative width for the curreent phase. + :param packet_loss_ratio: PDR fraction for the current search. + :param minimum_transmit_rate: Minimum target transmit rate + for the current search [pps]. + :param maximum_transmit_rate: Maximum target transmit rate + for the current search [pps]. + :type result: NdrPdrResult + :type phases: int + :type duration: float + :type width_goal: float + :type packet_loss_ratio: float + :type minimum_transmit_rate: float + :type maximum_transmit_rate: float + """ + self.result = result + self.phases = int(phases) + self.duration = float(duration) + self.width_goal = float(width_goal) + self.packet_loss_ratio = float(packet_loss_ratio) + 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): + """Store the measurer object and additional arguments. + + :param measurer: Rate provider to use by this search object. + :param final_relative_width: Final lower bound transmit rate + cannot be more distant that this multiple of upper bound [1]. + :param final_trial_duration: Trial duration for the final phase [s]. + :param initial_trial_duration: Trial duration for the initial phase + and also for the first intermediate phase [s]. + :param number_of_intermediate_phases: Number of intermediate phases + 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 + :type final_relative_width: float + :type final_trial_duration: float + :type initial_trial_duration: int + :type number_of_intermediate_phases: int + :type timeout: float + """ + super(MultipleLossRatioSearch, self).__init__(measurer) + self.final_trial_duration = float(final_trial_duration) + self.final_relative_width = float(final_relative_width) + self.number_of_intermediate_phases = int(number_of_intermediate_phases) + self.initial_trial_duration = float(initial_trial_duration) + self.timeout = float(timeout) + + + @staticmethod + def double_relative_width(relative_width): + """Return relative width corresponding to double logarithmic width. + + :param relative_width: The base relative width to double. + :type relative_width: float + :returns: The relative width of double logarithmic size. + :rtype: float + """ + return 1.999 * 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. + + @staticmethod + def double_step_down(relative_width, current_bound): + """Return rate of double logarithmic width below. + + :param relative_width: The base relative width to double. + :param current_bound: The current target transmit rate to move [pps]. + :type relative_width: float + :type current_bound: float + :returns: Transmit rate smaller by logarithmically double width [pps]. + :rtype: float + """ + return current_bound * ( + 1.0 - MultipleLossRatioSearch.double_relative_width( + relative_width)) + + @staticmethod + def double_step_up(relative_width, current_bound): + """Return rate of double logarithmic width above. + + :param relative_width: The base relative width to double. + :param current_bound: The current target transmit rate to move [pps]. + :type relative_width: float + :type current_bound: float + :returns: Transmit rate larger by logarithmically double width [pps]. + :rtype: float + """ + return current_bound / ( + 1.0 - MultipleLossRatioSearch.double_relative_width( + relative_width)) + + @staticmethod + def half_relative_width(relative_width): + """Return relative width corresponding to half logarithmic width. + + :param relative_width: The base relative width to halve. + :type relative_width: float + :returns: The relative width of half logarithmic size. + :rtype: float + """ + return 1.0 - math.sqrt(1.0 - relative_width) + + @staticmethod + def half_step_up(relative_width, current_bound): + """Return rate of half logarithmic width above. + + :param relative_width: The base relative width to halve. + :param current_bound: The current target transmit rate to move [pps]. + :type relative_width: float + :type current_bound: float + :returns: Transmit rate larger by logarithmically half width [pps]. + :rtype: float + """ + return current_bound / ( + 1.0 - MultipleLossRatioSearch.half_relative_width(relative_width)) + + def narrow_down_ndr_and_pdr( + self, minimum_transmit_rate, maximum_transmit_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 packet_loss_ratio: Fraction of packets lost, for PDR [1]. + :type minimum_transmit_rate: float + :type maximum_transmit_rate: float + :type packet_loss_ratio: float + :returns: Structure containing narrowed down intervals + and their measurements. + :rtype: NdrPdrResult + :raises RuntimeError: If total duration is larger than timeout. + """ + minimum_transmit_rate = float(minimum_transmit_rate) + maximum_transmit_rate = float(maximum_transmit_rate) + packet_loss_ratio = float(packet_loss_ratio) + line_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_measurement = self.measurer.measure( + 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: + 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 + 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) + state = self.ndrpdr(state) + return state.result + + def _measure_and_update_state(self, state, transmit_rate): + """Perform trial measurement, update bounds, return new state. + + :param state: State before this measurement. + :param transmit_rate: Target transmit rate for this measurement [pps]. + :type state: ProgressState + :type transmit_rate: float + :returns: State after the measurement. + :rtype: ProgressState + """ + # 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.debug( + "relative widths in goals: %s", 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) + pdr_interval = self._new_interval( + state.result.pdr_interval, measurement, state.packet_loss_ratio) + state.result = NdrPdrResult(ndr_interval, pdr_interval) + return state + + @staticmethod + def _new_interval(old_interval, measurement, packet_loss_ratio): + """Return new interval with bounds updated according to the measurement. + + :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 packet_loss_ratio: float + :returns: The updated interval. + :rtype: ReceiveRateInterval + """ + old_lo, old_hi = old_interval.measured_low, old_interval.measured_high + # 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) + else: + return ReceiveRateInterval(old_lo, measurement) + # Priority one: invalid lower bound allows only one type of update. + if 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) + else: + return old_interval + # Lower bound is now valid. + # Next priorities depend on target Tr. + if 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) + 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) + 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) + 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 + + def ndrpdr(self, state): + """Pefrom trials for this phase. Return the new state when done. + + :param state: State before this phase. + :type state: ProgressState + :returns: The updated state. + :rtype: ProgressState + :raises RuntimeError: If total duration is larger than timeout. + """ + start_time = time.time() + if state.phases > 0: + # We need to finish preceding intermediate phases first. + saved_phases = state.phases + state.phases -= 1 + # Preceding phases have shorter duration. + saved_duration = state.duration + 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) + # Shorter durations do not need that narrow widths. + saved_width = state.width_goal + state.width_goal = self.double_relative_width(state.width_goal) + # Recurse. + state = self.ndrpdr(state) + # Restore the state for current phase. + 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) + while 1: + if time.time() > start_time + self.timeout: + raise RuntimeError("Optimized search takes too long.") + # Order of priorities: invalid bounds (nl, pl, nh, ph), + # then narrowing relative Tr widths. + # Durations are not priorities yet, + # they will settle on their own hopefully. + ndr_lo = state.result.ndr_interval.measured_low + ndr_hi = state.result.ndr_interval.measured_high + 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) + pdr_rel_width = max( + 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 + # If we are hitting maximum_transmit_rate, + # it is still worth narrowing width, + # hoping large enough loss fraction will happen. + # But if we are hitting the minimal rate (at current duration), + # no additional measurement will help with that, + # so we can stop narrowing in this phase. + if (ndr_lo.target_tr <= state.minimum_transmit_rate + and ndr_lo.loss_fraction > 0.0): + ndr_rel_width = 0.0 + 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) + 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) + continue + # Widths are narrow (or lower bound minimal), bound measurements + # are long enough, we can return. + logging.info("phase done") + break + return state diff --git a/resources/libraries/python/search/NdrPdrResult.py b/resources/libraries/python/search/NdrPdrResult.py index 47fb757c07..b69a57ecbe 100644 --- a/resources/libraries/python/search/NdrPdrResult.py +++ b/resources/libraries/python/search/NdrPdrResult.py @@ -13,7 +13,7 @@ """Module defining NdrPdrResult class.""" -from .ReceiveRateInterval import ReceiveRateInterval +from ReceiveRateInterval import ReceiveRateInterval class NdrPdrResult(object): diff --git a/resources/libraries/python/search/OptimizedSearchAlgorithm.py b/resources/libraries/python/search/OptimizedSearchAlgorithm.py deleted file mode 100644 index f89acd56b2..0000000000 --- a/resources/libraries/python/search/OptimizedSearchAlgorithm.py +++ /dev/null @@ -1,497 +0,0 @@ -# Copyright (c) 2018 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: -# -# http://www.apache.org/licenses/LICENSE-2.0 -# -# Unless required by applicable law or agreed to in writing, software -# distributed under the License is distributed on an "AS IS" BASIS, -# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -# See the License for the specific language governing permissions and -# limitations under the License. - -"""Module defining OptimizedSearchAlgorithm class.""" - -import logging -import math -import time - -from .AbstractSearchAlgorithm import AbstractSearchAlgorithm -from .NdrPdrResult import NdrPdrResult -from .ReceiveRateInterval import ReceiveRateInterval - - -class OptimizedSearchAlgorithm(AbstractSearchAlgorithm): - """Optimized binary search algorithm for finding NDR and PDR bounds. - - Traditional binary search algorithm needs initial interval - (lower and upper bound), and returns final interval after bisecting - (until some exit condition is met). - The exit condition is usually related to the interval width, - (upper bound value minus lower bound value). - - The optimized algorithm contains several improvements - aimed to reduce overall search time. - - One improvement is searching for two intervals at once. - The intervals are for NDR (No Drop Rate) and PDR (Partial Drop Rate). - - Next improvement is that the initial interval does need to be valid. - Imagine initial interval (10, 11) where 11 is smaller - than the searched value. - The algorithm will try (11, 13) interval next, and if 13 is still smaller, - (13, 17) and so on, doubling width until the upper bound is valid. - The part when interval expands is called external search, - the part when interval is bisected is called internal search. - - Next improvement is that trial measurements at small trial duration - can be used to find a reasonable interval for full trial duration search. - This results in more trials performed, but smaller overall duration - in general. - - Next improvement is bisecting in logarithmic quantities, - so that exit criteria can be independent of measurement units. - - Next improvement is basing the initial interval on receive rates. - - Final improvement is exiting early if the minimal value - is not a valid lower bound. - - The complete search consist of several phases, - each phase performing several trial measurements. - Initial phase creates initial interval based on receive rates - at maximum rate and at maximum receive rate (MRR). - Final phase and preceding intermediate phases are performing - external and internal search steps, - each resulting interval is the starting point for the next phase. - The resulting interval of final phase is the result of the whole algorithm. - - Each non-initial phase uses its own trial duration and width goal. - Any non-initial phase stops searching (for NDR or PDR independently) - when minimum is not a valid lower bound (at current duration), - or all of the following is true: - Both bounds are valid, bound bounds are measured at the current phase - trial duration, interval width is less than the width goal - for current phase. - - TODO: Reviwew and update this docstring according to rst docs. - TODO: Initial phase: Larger min width and search up on zero. - TODO: Support configurable number of Packet Loss Ratios. - TODO: Rename to MultipleDropRateSearch (or MultipleLossRatioSearch). - """ - - class ProgressState(object): - """Structure containing data to be passed around in recursion.""" - - def __init__( - self, result, phases, duration, width_goal, packet_loss_ratio, - minimum_transmit_rate, maximum_transmit_rate): - """Convert and store the argument values. - - :param result: Current measured NDR and PDR intervals. - :param phases: How many intermediate phases to perform - before the current one. - :param duration: Trial duration to use in the current phase [s]. - :param width_goal: The goal relative width for the curreent phase. - :param packet_loss_ratio: PDR fraction for the current search. - :param minimum_transmit_rate: Minimum target transmit rate - for the current search [pps]. - :param maximum_transmit_rate: Maximum target transmit rate - for the current search [pps]. - :type result: NdrPdrResult - :type phases: int - :type duration: float - :type width_goal: float - :type packet_loss_ratio: float - :type minimum_transmit_rate: float - :type maximum_transmit_rate: float - """ - self.result = result - self.phases = int(phases) - self.duration = float(duration) - self.width_goal = float(width_goal) - self.packet_loss_ratio = float(packet_loss_ratio) - self.minimum_transmit_rate = float(minimum_transmit_rate) - self.maximum_transmit_rate = float(maximum_transmit_rate) - - def __init__(self, rate_provider, final_relative_width=0.005, - final_trial_duration=30.0, initial_trial_duration=1.0, - number_of_intermediate_phases=2, timeout=600.0): - """Store rate provider and additional arguments. - - :param rate_provider: Rate provider to use by this search object. - :param final_relative_width: Final lower bound transmit rate - cannot be more distant that this multiple of upper bound [1]. - :param final_trial_duration: Trial duration for the final phase [s]. - :param initial_trial_duration: Trial duration for the initial phase - and also for the first intermediate phase [s]. - :param number_of_intermediate_phases: Number of intermediate phases - to perform before the final phase [1]. - :param timeout: The search will fail itself when not finished - before this overall time [s]. - :type rate_provider: AbstractRateProvider - :type final_relative_width: float - :type final_trial_duration: float - :type initial_trial_duration: int - :type number_of_intermediate_phases: int - :type timeout: float - """ - super(OptimizedSearchAlgorithm, self).__init__(rate_provider) - self.final_trial_duration = float(final_trial_duration) - self.final_relative_width = float(final_relative_width) - self.number_of_intermediate_phases = int(number_of_intermediate_phases) - self.initial_trial_duration = float(initial_trial_duration) - self.timeout = float(timeout) - - def narrow_down_ndr_and_pdr( - self, minimum_transmit_rate, maximum_transmit_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 packet_loss_ratio: Fraction of packets lost, for PDR [1]. - :type minimum_transmit_rate: float - :type maximum_transmit_rate: float - :type packet_loss_ratio: float - :returns: Structure containing narrowed down intervals - and their measurements. - :rtype: NdrPdrResult - :raises RuntimeError: If total duration is larger than timeout. - """ - minimum_transmit_rate = float(minimum_transmit_rate) - maximum_transmit_rate = float(maximum_transmit_rate) - packet_loss_ratio = float(packet_loss_ratio) - line_measurement = self.rate_provider.measure( - self.initial_trial_duration, maximum_transmit_rate) - # 0.999 is to avoid rounding errors which make - # the subsequent logic think the width is too broad. - max_lo = max( - minimum_transmit_rate, - maximum_transmit_rate * (1.0 - 0.999 * self.final_relative_width)) - mrr = min( - max_lo, max(minimum_transmit_rate, line_measurement.receive_rate)) - mrr_measurement = self.rate_provider.measure( - self.initial_trial_duration, mrr) - # Attempt to get narrower width. - max2_lo = max( - minimum_transmit_rate, - mrr * (1.0 - 0.999 * self.final_relative_width)) - mrr2 = min(max2_lo, mrr_measurement.receive_rate) - if mrr2 > minimum_transmit_rate: - line_measurement = mrr_measurement - mrr_measurement = self.rate_provider.measure( - self.initial_trial_duration, mrr2) - 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) - state = self.ndrpdr(state) - return state.result - - def _measure_and_update_state(self, state, transmit_rate): - """Perform trial measurement, update bounds, return new state. - - :param state: State before this measurement. - :param transmit_rate: Target transmit rate for this measurement [pps]. - :type state: ProgressState - :type transmit_rate: float - :returns: State after the measurement. - :rtype: ProgressState - """ - # 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.debug( - "relative widths in goals: %s", state.result.width_in_goals( - self.final_relative_width)) - measurement = self.rate_provider.measure(state.duration, transmit_rate) - ndr_interval = self._new_interval( - state.result.ndr_interval, measurement, 0.0) - pdr_interval = self._new_interval( - state.result.pdr_interval, measurement, state.packet_loss_ratio) - state.result = NdrPdrResult(ndr_interval, pdr_interval) - return state - - @staticmethod - def _new_interval(old_interval, measurement, packet_loss_ratio): - """Return new interval with bounds updated according to the measurement. - - :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 packet_loss_ratio: float - :returns: The updated interval. - :rtype: ReceiveRateInterval - """ - old_lo, old_hi = old_interval.measured_low, old_interval.measured_high - # 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) - else: - return ReceiveRateInterval(old_lo, measurement) - # Priority one: invalid lower bound allows only one type of update. - if 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) - else: - return old_interval - # Lower bound is now valid. - # Next priorities depend on target Tr. - if 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) - 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) - 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) - 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 - - @staticmethod - def double_relative_width(relative_width): - """Return relative width corresponding to double logarithmic width. - - :param relative_width: The base relative width to double. - :type relative_width: float - :returns: The relative width of double logarithmic size. - :rtype: float - """ - return 1.999 * 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. - - @staticmethod - def double_step_down(relative_width, current_bound): - """Return rate of double logarithmic width below. - - :param relative_width: The base relative width to double. - :param current_bound: The current target transmit rate to move [pps]. - :type relative_width: float - :type current_bound: float - :returns: Transmit rate smaller by logarithmically double width [pps]. - :rtype: float - """ - return current_bound * ( - 1.0 - OptimizedSearchAlgorithm.double_relative_width( - relative_width)) - - @staticmethod - def double_step_up(relative_width, current_bound): - """Return rate of double logarithmic width above. - - :param relative_width: The base relative width to double. - :param current_bound: The current target transmit rate to move [pps]. - :type relative_width: float - :type current_bound: float - :returns: Transmit rate larger by logarithmically double width [pps]. - :rtype: float - """ - return current_bound / ( - 1.0 - OptimizedSearchAlgorithm.double_relative_width( - relative_width)) - - @staticmethod - def half_relative_width(relative_width): - """Return relative width corresponding to half logarithmic width. - - :param relative_width: The base relative width to halve. - :type relative_width: float - :returns: The relative width of half logarithmic size. - :rtype: float - """ - return 1.0 - math.sqrt(1.0 - relative_width) - - @staticmethod - def half_step_up(relative_width, current_bound): - """Return rate of half logarithmic width above. - - :param relative_width: The base relative width to halve. - :param current_bound: The current target transmit rate to move [pps]. - :type relative_width: float - :type current_bound: float - :returns: Transmit rate larger by logarithmically half width [pps]. - :rtype: float - """ - return current_bound / ( - 1.0 - OptimizedSearchAlgorithm.half_relative_width(relative_width)) - - def ndrpdr(self, state): - """Pefrom trials for this phase. Return the new state when done. - - :param state: State before this phase. - :type state: ProgressState - :returns: The updates state. - :rtype: ProgressState - :raises RuntimeError: If total duration is larger than timeout. - """ - if state.phases > 0: - # We need to finish preceding intermediate phases first. - saved_phases = state.phases - state.phases -= 1 - # Preceding phases have shorter duration. - saved_duration = state.duration - 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) - # Shorter durations do not need that narrow widths. - saved_width = state.width_goal - state.width_goal = self.double_relative_width(state.width_goal) - # Recurse. - state = self.ndrpdr(state) - # Restore the state for current phase. - 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) - start_time = time.time() - while 1: - if time.time() > start_time + self.timeout: - raise RuntimeError("Optimized search takes too long.") - # Order of priorities: improper bounds (nl, pl, nh, ph), - # then narrowing relative Tr widths. - # Durations are not priorities yet, - # they will settle on their own hopefully. - ndr_lo = state.result.ndr_interval.measured_low - ndr_hi = state.result.ndr_interval.measured_high - 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) - pdr_rel_width = max( - 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 - # If we are hitting maximum_transmit_rate, - # it is still worth narrowing width, - # hoping large enough loss fraction will happen. - # But if we are hitting the minimal rate (at current duration), - # no additional measurement will help with that, - # so we can stop narrowing in this phase. - if (ndr_lo.target_tr <= state.minimum_transmit_rate - and ndr_lo.loss_fraction > 0.0): - ndr_rel_width = 0.0 - if (pdr_lo.target_tr <= state.minimum_transmit_rate - and pdr_lo.loss_fraction > state.packet_loss_ratio): - pdr_rel_width = 0.0 - if max(ndr_rel_width, pdr_rel_width) > state.width_goal: - # We have to narrow some width. - # TODO: Prefer NDR, it could invalidate PDR (not vice versa). - if ndr_rel_width >= pdr_rel_width: - 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 - else: - new_tr = self.half_step_up(pdr_rel_width, pdr_lo.target_tr) - logging.info("Bisecting for PDR at %s", new_tr) - 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) - continue - # Widths are narrow (or lower bound minimal), bound measurements - # are long enough, we can return. - logging.info("phase done") - break - return state diff --git a/resources/libraries/python/search/ReceiveRateInterval.py b/resources/libraries/python/search/ReceiveRateInterval.py index 11f812d886..05e0f10013 100644 --- a/resources/libraries/python/search/ReceiveRateInterval.py +++ b/resources/libraries/python/search/ReceiveRateInterval.py @@ -15,7 +15,7 @@ import math -from .ReceiveRateMeasurement import ReceiveRateMeasurement +from ReceiveRateMeasurement import ReceiveRateMeasurement class ReceiveRateInterval(object): @@ -43,7 +43,7 @@ class ReceiveRateInterval(object): self.abs_tr_width = None """Absolute width of target transmit rate. Upper minus lower.""" self.rel_tr_width = None - """Relative width of target transmit rate. Ansolute divided by upper.""" + """Relative width of target transmit rate. Absolute divided by upper.""" self.sort() def sort(self): diff --git a/resources/libraries/python/search/__init__.py b/resources/libraries/python/search/__init__.py index 619c4c09c5..4cc8158397 100644 --- a/resources/libraries/python/search/__init__.py +++ b/resources/libraries/python/search/__init__.py @@ -12,5 +12,5 @@ # limitations under the License. """ -__init__ file for directory resources/libraries/python/search +__init__ file for Python package "MLRsearch" """ -- cgit 1.2.3-korg