diff options
Diffstat (limited to 'resources/libraries/python/MLRsearch')
47 files changed, 4244 insertions, 1242 deletions
diff --git a/resources/libraries/python/MLRsearch/AbstractMeasurer.py b/resources/libraries/python/MLRsearch/AbstractMeasurer.py deleted file mode 100644 index da66b4e174..0000000000 --- a/resources/libraries/python/MLRsearch/AbstractMeasurer.py +++ /dev/null @@ -1,32 +0,0 @@ -# Copyright (c) 2021 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(metaclass=ABCMeta): - """Abstract class defining common API for measurement providers.""" - - @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 [tps]. - :type duration: float - :type transmit_rate: float - :returns: Structure containing the result of the measurement. - :rtype: ReceiveRateMeasurement.ReceiveRateMeasurement - """ diff --git a/resources/libraries/python/MLRsearch/AbstractSearchAlgorithm.py b/resources/libraries/python/MLRsearch/AbstractSearchAlgorithm.py deleted file mode 100644 index cca48ef798..0000000000 --- a/resources/libraries/python/MLRsearch/AbstractSearchAlgorithm.py +++ /dev/null @@ -1,48 +0,0 @@ -# Copyright (c) 2021 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 AbstractSearchAlgorithm class.""" - -from abc import ABCMeta, abstractmethod - - -class AbstractSearchAlgorithm(metaclass=ABCMeta): - """Abstract class defining common API for search algorithms.""" - - def __init__(self, measurer): - """Store the rate provider. - - :param measurer: Object able to perform trial or composite measurements. - :type measurer: AbstractMeasurer.AbstractMeasurer - """ - self.measurer = measurer - - @abstractmethod - def narrow_down_intervals( - self, min_rate, max_rate, packet_loss_ratios): - """Perform measurements to narrow down intervals, return them. - - :param min_rate: Minimal target transmit rate [tps]. - Usually, tests are set to fail if search reaches this or below. - :param max_rate: Maximal target transmit rate [tps]. - Usually computed from line rate and various other limits, - to prevent failures or duration stretching in Traffic Generator. - :param packet_loss_ratios: Ratios of packet loss to search for, - e.g. [0.0, 0.005] for NDR and PDR. - :type min_rate: float - :type max_rate: float - :type packet_loss_ratios: Iterable[float] - :returns: Structure containing narrowed down intervals - and their measurements. - :rtype: List[ReceiveRateInterval.ReceiveRateInterval] - """ diff --git a/resources/libraries/python/MLRsearch/MeasurementDatabase.py b/resources/libraries/python/MLRsearch/MeasurementDatabase.py deleted file mode 100644 index 2f601d6260..0000000000 --- a/resources/libraries/python/MLRsearch/MeasurementDatabase.py +++ /dev/null @@ -1,157 +0,0 @@ -# Copyright (c) 2021 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 MeasurementDatabase class.""" - -from .ReceiveRateInterval import ReceiveRateInterval -from .PerDurationDatabase import PerDurationDatabase - - -class MeasurementDatabase: - """A structure holding measurement results. - - The implementation uses a dict from duration values - to PerDurationDatabase instances. - - Several utility methods are added, accomplishing tasks useful for MLRsearch. - - This class contains the "find tightest bounds" parts of logic required - by MLRsearch. One exception is lack of any special handling for maximal - or minimal rates. - """ - - def __init__(self, measurements): - """Store measurement results in per-duration databases. - - TODO: Move processing to a factory method, - keep constructor only to store (presumably valid) values. - - If the measurements argument contains is a dict, - the constructor assumes it contains the processed databases. - - :param measurements: The measurement results to store. - :type measurements: Iterable[ReceiveRateMeasurement] - """ - if isinstance(measurements, dict): - self.data_for_duration = measurements - else: - self.data_for_duration = dict() - # TODO: There is overlap with add() code. Worth extracting? - for measurement in measurements: - duration = measurement.duration - if duration in self.data_for_duration: - self.data_for_duration[duration].add(measurement) - else: - self.data_for_duration[duration] = PerDurationDatabase( - duration, [measurement] - ) - durations = sorted(self.data_for_duration.keys()) - self.current_duration = durations[-1] if duration else None - self.previous_duration = durations[-2] if len(durations) > 1 else None - - def __repr__(self): - """Return string executable to get equivalent instance. - - :returns: Code to construct equivalent instance. - :rtype: str - """ - return f"MeasurementDatabase(measurements={self.data_for_duration!r})" - - def set_current_duration(self, duration): - """Remember what MLRsearch considers the current duration. - - Setting the same duration is allowed, setting smaller is not allowed. - - :param duration: Target trial duration of current phase, in seconds. - :type duration: float - :raises ValueError: If the duration is smaller than previous. - """ - if duration < self.current_duration: - raise ValueError( - f"Duration {duration} shorter than current duration" - f" {self.current_duration}" - ) - if duration > self.current_duration: - self.previous_duration = self.current_duration - self.current_duration = duration - self.data_for_duration[duration] = PerDurationDatabase( - duration, list() - ) - # Else no-op. - - def add(self, measurement): - """Add a measurement. Duration has to match the set one. - - :param measurement: Measurement result to add to the database. - :type measurement: ReceiveRateMeasurement - """ - duration = measurement.duration - if duration != self.current_duration: - raise ValueError( - f"{measurement!r} duration different than" - f" {self.current_duration}" - ) - self.data_for_duration[duration].add(measurement) - - def get_bounds(self, ratio): - """Return 6 bounds: lower/upper, current/previous, tightest/second. - - Second tightest bounds are only returned for current duration. - None instead of a measurement if there is no measurement of that type. - - The result cotains bounds in this order: - 1. Tightest lower bound for current duration. - 2. Tightest upper bound for current duration. - 3. Tightest lower bound for previous duration. - 4. Tightest upper bound for previous duration. - 5. Second tightest lower bound for current duration. - 6. Second tightest upper bound for current duration. - - :param ratio: Target ratio, valid has to be lower or equal. - :type ratio: float - :returns: Measurements acting as various bounds. - :rtype: 6-tuple of Optional[PerDurationDatabase] - """ - cur_lo1, cur_hi1, pre_lo, pre_hi, cur_lo2, cur_hi2 = [None] * 6 - duration = self.current_duration - if duration is not None: - data = self.data_for_duration[duration] - cur_lo1, cur_hi1, cur_lo2, cur_hi2 = data.get_valid_bounds(ratio) - duration = self.previous_duration - if duration is not None: - data = self.data_for_duration[duration] - pre_lo, pre_hi, _, _ = data.get_valid_bounds(ratio) - return cur_lo1, cur_hi1, pre_lo, pre_hi, cur_lo2, cur_hi2 - - def get_results(self, ratio_list): - """Return list of intervals for given ratios, from current duration. - - Attempt to construct valid intervals. If a valid bound is missing, - use smallest/biggest target_tr for lower/upper bound. - This can result in degenerate intervals. - - :param ratio_list: Ratios to create intervals for. - :type ratio_list: Iterable[float] - :returns: List of intervals. - :rtype: List[ReceiveRateInterval] - """ - ret_list = list() - current_data = self.data_for_duration[self.current_duration] - for ratio in ratio_list: - lower_bound, upper_bound, _, _, _, _ = self.get_bounds(ratio) - if lower_bound is None: - lower_bound = current_data.measurements[0] - if upper_bound is None: - upper_bound = current_data.measurements[-1] - ret_list.append(ReceiveRateInterval(lower_bound, upper_bound)) - return ret_list diff --git a/resources/libraries/python/MLRsearch/MultipleLossRatioSearch.py b/resources/libraries/python/MLRsearch/MultipleLossRatioSearch.py deleted file mode 100644 index 0e6c8cfa58..0000000000 --- a/resources/libraries/python/MLRsearch/MultipleLossRatioSearch.py +++ /dev/null @@ -1,485 +0,0 @@ -# Copyright (c) 2021 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 .MeasurementDatabase import MeasurementDatabase -from .ProgressState import ProgressState -from .ReceiveRateInterval import ReceiveRateInterval -from .WidthArithmetics import ( - multiply_relative_width, - step_down, - step_up, - multiple_step_down, - multiple_step_up, - half_step_up, -) - - -class MultipleLossRatioSearch: - """Optimized binary search algorithm for finding bounds for multiple ratios. - - This is unofficially a subclass of AbstractSearchAlgorithm, - but constructor signature is different. - - 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 multiple intervals at once. - The intervals differ by the target loss ratio. Lower bound - has to have equal or smaller loss ratio, upper bound has to have larger. - - Next improvement is that the initial interval does not need to be valid. - Imagine initial interval (10, 11) where loss at 11 is smaller - than the searched ratio. - 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 intervals of final phase is the result of the whole algorithm. - - Each non-initial phase uses its own trial duration. - Any non-initial phase stops searching (for all ratios independently) - when minimum is not a valid lower bound (at current duration), - or all of the following is true: - Both bounds are valid, 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. - """ - - 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, debug=None, - expansion_coefficient=2.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]. - :param debug: Callable to use instead of logging.debug(). - :param expansion_coefficient: External search multiplies width by this. - :type measurer: AbstractMeasurer.AbstractMeasurer - :type final_relative_width: float - :type final_trial_duration: float - :type initial_trial_duration: float - :type number_of_intermediate_phases: int - :type timeout: float - :type debug: Optional[Callable[[str], None]] - :type expansion_coefficient: float - """ - self.measurer = 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) - self.state = None - self.debug = logging.debug if debug is None else debug - self.expansion_coefficient = float(expansion_coefficient) - - def narrow_down_intervals(self, min_rate, max_rate, packet_loss_ratios): - """Perform initial phase, create state object, proceed with next phases. - - The current implementation requires the ratios so be unique and sorted. - Also non-empty. - - :param min_rate: Minimal target transmit rate [tps]. - :param max_rate: Maximal target transmit rate [tps]. - :param packet_loss_ratios: Target ratios of packets loss to locate. - :type min_rate: float - :type max_rate: float - :type packet_loss_ratios: Iterable[float] - :returns: Structure containing narrowed down intervals - and their measurements. - :rtype: List[ReceiveRateInterval] - :raises RuntimeError: If total duration is larger than timeout. - Or if ratios list is (empty or) not sorted or unique. - """ - min_rate = float(min_rate) - max_rate = float(max_rate) - packet_loss_ratios = [float(ratio) for ratio in packet_loss_ratios] - if len(packet_loss_ratios) < 1: - raise RuntimeError(u"At least one ratio is required!") - if packet_loss_ratios != sorted(set(packet_loss_ratios)): - raise RuntimeError(u"Input ratios have to be sorted and unique!") - measurements = list() - self.debug(f"First measurement at max rate: {max_rate}") - measured = self.measurer.measure( - duration=self.initial_trial_duration, - transmit_rate=max_rate, - ) - measurements.append(measured) - initial_width_goal = self.final_relative_width - for _ in range(self.number_of_intermediate_phases): - initial_width_goal = multiply_relative_width( - initial_width_goal, 2.0 - ) - max_lo = step_down(max_rate, initial_width_goal) - mrr = max(min_rate, min(max_lo, measured.relative_receive_rate)) - self.debug(f"Second measurement at mrr: {mrr}") - measured = self.measurer.measure( - duration=self.initial_trial_duration, - transmit_rate=mrr, - ) - measurements.append(measured) - # Attempt to get narrower width. - if measured.loss_ratio > packet_loss_ratios[0]: - max_lo = step_down(mrr, initial_width_goal) - mrr2 = min(max_lo, measured.relative_receive_rate) - else: - mrr2 = step_up(mrr, initial_width_goal) - if min_rate < mrr2 < max_rate: - self.debug(f"Third measurement at mrr2: {mrr2}") - measured = self.measurer.measure( - duration=self.initial_trial_duration, - transmit_rate=mrr2, - ) - measurements.append(measured) - # If mrr2 > mrr and mrr2 got zero loss, - # it is better to do external search from mrr2 up. - # To prevent bisection between mrr2 and max_rate, - # we simply remove the max_rate measurement. - # Similar logic applies to higher loss ratio goals. - # Overall, with mrr2 measurement done, we never need - # the first measurement done at max rate. - measurements = measurements[1:] - database = MeasurementDatabase(measurements) - stop_time = time.monotonic() + self.timeout - self.state = ProgressState( - database, self.number_of_intermediate_phases, - self.final_trial_duration, self.final_relative_width, - packet_loss_ratios, min_rate, max_rate, stop_time - ) - self.ndrpdr() - return self.state.database.get_results(ratio_list=packet_loss_ratios) - - def ndrpdr(self): - """Perform trials for this phase. State is updated in-place. - - Recursion to smaller durations is performed (if not performed yet). - - :raises RuntimeError: If total duration is larger than timeout. - """ - state = self.state - 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 = multiply_relative_width(saved_width, 2.0) - # Recurse. - self.ndrpdr() - # Restore the state for current phase. - state.width_goal = saved_width - state.duration = saved_duration - state.phases = saved_phases # Not needed, but just in case. - self.debug( - f"Starting phase with {state.duration} duration" - f" and {state.width_goal} relative width goal." - ) - failing_fast = False - database = state.database - database.set_current_duration(state.duration) - while time.monotonic() < state.stop_time: - for index, ratio in enumerate(state.packet_loss_ratios): - new_tr = self._select_for_ratio(ratio) - if new_tr is None: - # Either this ratio is fine, or min rate got invalid result. - # If fine, we will continue to handle next ratio. - if index > 0: - # First ratio passed, all next have a valid lower bound. - continue - lower_bound, _, _, _, _, _ = database.get_bounds(ratio) - if lower_bound is None: - failing_fast = True - self.debug(u"No valid lower bound for this iteration.") - break - # First ratio is fine. - continue - # We have transmit rate to measure at. - # We do not check duration versus stop_time here, - # as some measurers can be unpredictably faster - # than what duration suggests. - measurement = self.measurer.measure( - duration=state.duration, - transmit_rate=new_tr, - ) - database.add(measurement) - # Restart ratio handling on updated database. - break - else: - # No ratio needs measuring, we are done with this phase. - self.debug(u"Phase done.") - break - # We have broken out of the for loop. - if failing_fast: - # Abort the while loop early. - break - # Not failing fast but database got updated, restart the while loop. - else: - # Time is up. - raise RuntimeError(u"Optimized search takes too long.") - # Min rate is not valid, but returning what we have - # so next duration can recover. - - @staticmethod - def improves(new_bound, lower_bound, upper_bound): - """Return whether new bound improves upon old bounds. - - To improve, new_bound has to be not None, - and between the old bounds (where the bound is not None). - - This piece of logic is commonly used, when we know old bounds - from a primary source (e.g. current duration database) - and new bound from a secondary source (e.g. previous duration database). - Having a function allows "if improves(..):" construction to save space. - - :param new_bound: The bound we consider applying. - :param lower_bound: Known bound, new_bound has to be higher to apply. - :param upper_bound: Known bound, new_bound has to be lower to apply. - :type new_bound: Optional[ReceiveRateMeasurement] - :type lower_bound: Optional[ReceiveRateMeasurement] - :type upper_bound: Optional[ReceiveRateMeasurement] - :returns: Whether we can apply the new bound. - :rtype: bool - """ - if new_bound is None: - return False - if lower_bound is not None: - if new_bound.target_tr <= lower_bound.target_tr: - return False - if upper_bound is not None: - if new_bound.target_tr >= upper_bound.target_tr: - return False - return True - - def _select_for_ratio(self, ratio): - """Return None or new target_tr to measure at. - - Returning None means either we have narrow enough valid interval - for this ratio, or we are hitting min rate and should fail early. - - :param ratio: Loss ratio to ensure narrow valid bounds for. - :type ratio: float - :returns: The next target transmit rate to measure at. - :rtype: Optional[float] - :raises RuntimeError: If database inconsistency is detected. - """ - state = self.state - data = state.database - bounds = data.get_bounds(ratio) - cur_lo1, cur_hi1, pre_lo, pre_hi, cur_lo2, cur_hi2 = bounds - pre_lo_improves = self.improves(pre_lo, cur_lo1, cur_hi1) - pre_hi_improves = self.improves(pre_hi, cur_lo1, cur_hi1) - # TODO: Detect also the other case for initial bisect, see below. - if pre_lo_improves and pre_hi_improves: - # We allowed larger width for previous phase - # as single bisect here guarantees only one re-measurement. - new_tr = self._bisect(pre_lo, pre_hi) - if new_tr is not None: - self.debug(f"Initial bisect for {ratio}, tr: {new_tr}") - return new_tr - if pre_lo_improves: - new_tr = pre_lo.target_tr - self.debug(f"Re-measuring lower bound for {ratio}, tr: {new_tr}") - return new_tr - if pre_hi_improves: - # This can also happen when we did not do initial bisect - # for this ratio yet, but the previous duration lower bound - # for this ratio got already re-measured as previous duration - # upper bound for previous ratio. - new_tr = pre_hi.target_tr - self.debug(f"Re-measuring upper bound for {ratio}, tr: {new_tr}") - return new_tr - if cur_lo1 is None and cur_hi1 is None: - raise RuntimeError(u"No results found in databases!") - if cur_lo1 is None: - # Upper bound exists (cur_hi1). - # We already tried previous lower bound. - # So, we want to extend down. - new_tr = self._extend_down( - cur_hi1, cur_hi2, pre_hi, second_needed=False - ) - self.debug( - f"Extending down for {ratio}:" - f" old {cur_hi1.target_tr} new {new_tr}" - ) - return new_tr - if cur_hi1 is None: - # Lower bound exists (cur_lo1). - # We already tried previous upper bound. - # So, we want to extend up. - new_tr = self._extend_up(cur_lo1, cur_lo2, pre_lo) - self.debug( - f"Extending up for {ratio}:" - f" old {cur_lo1.target_tr} new {new_tr}" - ) - return new_tr - # Both bounds exist (cur_lo1 and cur_hi1). - # cur_lo1 might have been selected for this ratio (we are bisecting) - # or for previous ratio (we are extending down for this ratio). - # Compute both estimates and choose the higher value. - bisected_tr = self._bisect(cur_lo1, cur_hi1) - extended_tr = self._extend_down( - cur_hi1, cur_hi2, pre_hi, second_needed=True - ) - # Only if both are not None we need to decide. - if bisected_tr and extended_tr and extended_tr > bisected_tr: - self.debug( - f"Extending down for {ratio}:" - f" old {cur_hi1.target_tr} new {extended_tr}" - ) - new_tr = extended_tr - else: - self.debug( - f"Bisecting for {ratio}: lower {cur_lo1.target_tr}," - f" upper {cur_hi1.target_tr}, new {bisected_tr}" - ) - new_tr = bisected_tr - return new_tr - - def _extend_down(self, cur_hi1, cur_hi2, pre_hi, second_needed=False): - """Return extended width below, or None if hitting min rate. - - If no second tightest (nor previous) upper bound is available, - the behavior is governed by second_needed argument. - If true, return None. If false, start from width goal. - This is useful, as if a bisect is possible, - we want to give it a chance. - - :param cur_hi1: Tightest upper bound for current duration. Has to exist. - :param cur_hi2: Second tightest current upper bound, may not exist. - :param pre_hi: Tightest upper bound, previous duration, may not exist. - :param second_needed: Whether second tightest bound is required. - :type cur_hi1: ReceiveRateMeasurement - :type cur_hi2: Optional[ReceiveRateMeasurement] - :type pre_hi: Optional[ReceiveRateMeasurement] - :type second_needed: bool - :returns: The next target transmit rate to measure at. - :rtype: Optional[float] - """ - state = self.state - old_tr = cur_hi1.target_tr - if state.min_rate >= old_tr: - self.debug(u"Extend down hits min rate.") - return None - next_bound = cur_hi2 - if self.improves(pre_hi, cur_hi1, cur_hi2): - next_bound = pre_hi - if next_bound is None and second_needed: - return None - old_width = state.width_goal - if next_bound is not None: - old_width = ReceiveRateInterval(cur_hi1, next_bound).rel_tr_width - old_width = max(old_width, state.width_goal) - new_tr = multiple_step_down( - old_tr, old_width, self.expansion_coefficient - ) - new_tr = max(new_tr, state.min_rate) - return new_tr - - def _extend_up(self, cur_lo1, cur_lo2, pre_lo): - """Return extended width above, or None if hitting max rate. - - :param cur_lo1: Tightest lower bound for current duration. Has to exist. - :param cur_lo2: Second tightest current lower bound, may not exist. - :param pre_lo: Tightest lower bound, previous duration, may not exist. - :type cur_lo1: ReceiveRateMeasurement - :type cur_lo2: Optional[ReceiveRateMeasurement] - :type pre_lo: Optional[ReceiveRateMeasurement] - :returns: The next target transmit rate to measure at. - :rtype: Optional[float] - """ - state = self.state - old_tr = cur_lo1.target_tr - if state.max_rate <= old_tr: - self.debug(u"Extend up hits max rate.") - return None - next_bound = cur_lo2 - if self.improves(pre_lo, cur_lo2, cur_lo1): - next_bound = pre_lo - old_width = state.width_goal - if next_bound is not None: - old_width = ReceiveRateInterval(cur_lo1, next_bound).rel_tr_width - old_width = max(old_width, state.width_goal) - new_tr = multiple_step_up(old_tr, old_width, self.expansion_coefficient) - new_tr = min(new_tr, state.max_rate) - return new_tr - - def _bisect(self, lower_bound, upper_bound): - """Return middle rate or None if width is narrow enough. - - :param lower_bound: Measurement to use as a lower bound. Has to exist. - :param upper_bound: Measurement to use as an upper bound. Has to exist. - :type lower_bound: ReceiveRateMeasurement - :type upper_bound: ReceiveRateMeasurement - :returns: The next target transmit rate to measure at. - :rtype: Optional[float] - :raises RuntimeError: If database inconsistency is detected. - """ - state = self.state - width = ReceiveRateInterval(lower_bound, upper_bound).rel_tr_width - if width <= state.width_goal: - self.debug(u"No more bisects needed.") - return None - new_tr = half_step_up(lower_bound.target_tr, width, state.width_goal) - return new_tr diff --git a/resources/libraries/python/MLRsearch/PerDurationDatabase.py b/resources/libraries/python/MLRsearch/PerDurationDatabase.py deleted file mode 100644 index afdf48614b..0000000000 --- a/resources/libraries/python/MLRsearch/PerDurationDatabase.py +++ /dev/null @@ -1,123 +0,0 @@ -# Copyright (c) 2021 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 PerDurationDatabase class.""" - -import copy - - -class PerDurationDatabase: - """List-like structure holding measurement results for one duration. - - This is a building block for MeasurementDatabase. - - This class hold measurements for single target duration value only, - so the logic is quite simple. - - Several utility methods are added, accomplishing tasks useful for MLRsearch - (to be called by MeasurementDatabase). - """ - - def __init__(self, duration, measurements): - """Store (deep copy of) measurement results and normalize them. - - The results have to have the corresponding target duration, - and there should be no duplicate target_tr values. - Empty iterable (zero measurements) is an acceptable input. - - :param duration: All measurements have to have this target duration [s]. - :param measurements: The measurement results to store. - :type duration: float - :type measurements: Iterable[ReceiveRateMeasurement] - :raises ValueError: If duration does not match or if TR duplicity. - """ - self.duration = duration - self.measurements = [copy.deepcopy(meas) for meas in measurements] - self._normalize() - - def __repr__(self): - """Return string executable to get equivalent instance. - - :returns: Code to construct equivalent instance. - :rtype: str - """ - return ( - u"PerDurationDatabase(" - f"duration={self.duration!r}," - f"measurements={self.measurements!r})" - ) - - def _normalize(self): - """Sort by target_tr, fail on detecting duplicate target_tr. - - Also set effective loss ratios. - - :raises ValueError: If duration does not match or if TR duplicity. - """ - measurements = self.measurements - measurements.sort(key=lambda measurement: measurement.target_tr) - # Detect duplicated TRs. - previous_tr = None - for measurement in measurements: - current_tr = measurement.target_tr - if current_tr == previous_tr: - raise ValueError( - u"Transmit rate conflict:" - f" {measurement!r} {previous_tr!r}" - ) - previous_tr = current_tr - # Update effective ratios. - ratio_previous = None - for measurement in measurements: - if ratio_previous is None: - ratio_previous = measurement.loss_ratio - measurement.effective_loss_ratio = ratio_previous - continue - ratio_previous = max(ratio_previous, measurement.loss_ratio) - measurement.effective_loss_ratio = ratio_previous - - def add(self, measurement): - """Add measurement and normalize. - - :param measurement: Measurement result to add to the database. - :type measurement: ReceiveRateMeasurement - """ - # TODO: We should deepcopy either everywhere or nowhere. - self.measurements.append(measurement) - self._normalize() - - def get_valid_bounds(self, ratio): - """Return None or a valid measurement for two tightest bounds. - - The validity of a measurement to act as a bound is determined - by comparing the argument ratio with measurement's effective loss ratio. - - Both lower and upper bounds are returned, both tightest and second - tightest. If some value is not available, None is returned instead. - - :param ratio: Target ratio, valid has to be lower or equal. - :type ratio: float - :returns: Tightest lower bound, tightest upper bound, - second tightest lower bound, second tightest upper bound. - :rtype: 4-tuple of Optional[ReceiveRateMeasurement] - """ - lower_1, upper_1, lower_2, upper_2 = None, None, None, None - for measurement in self.measurements: - if measurement.effective_loss_ratio > ratio: - if upper_1 is None: - upper_1 = measurement - continue - upper_2 = measurement - break - lower_1, lower_2 = measurement, lower_1 - return lower_1, upper_1, lower_2, upper_2 diff --git a/resources/libraries/python/MLRsearch/ProgressState.py b/resources/libraries/python/MLRsearch/ProgressState.py deleted file mode 100644 index 3610638990..0000000000 --- a/resources/libraries/python/MLRsearch/ProgressState.py +++ /dev/null @@ -1,60 +0,0 @@ -# Copyright (c) 2021 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 ProgressState class.""" - - -class ProgressState: - """Structure containing data to be passed around in recursion. - - This is basically a private class of MultipleRatioSearch, - but keeping it in a separate file makes things more readable. - """ - - def __init__( - self, database, phases, duration, width_goal, packet_loss_ratios, - min_rate, max_rate, stop_time): - """Convert and store the argument values. - - Also initializa the stored width for external search. - - :param result: Structure containing measured results. - :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_ratios: List of ratios for the current search. - :param min_rate: Minimal target transmit rate available - for the current search [tps]. - :param max_rate: Maximal target transmit rate available - for the current search [tps]. - :param stop_time: Monotonic time [s] when we should fail on timeout. - :type result: MeasurementDatabase - :type phases: int - :type duration: float - :type width_goal: float - :type packet_loss_ratios: Iterable[float] - :type min_rate: float - :type max_rate: float - :type stop_time: float - """ - self.database = database - self.phases = int(phases) - self.duration = float(duration) - self.width_goal = float(width_goal) - self.packet_loss_ratios = [ - float(ratio) for ratio in packet_loss_ratios - ] - self.min_rate = float(min_rate) - self.max_rate = float(max_rate) - self.stop_time = float(stop_time) diff --git a/resources/libraries/python/MLRsearch/ReceiveRateInterval.py b/resources/libraries/python/MLRsearch/ReceiveRateInterval.py deleted file mode 100644 index 993561e396..0000000000 --- a/resources/libraries/python/MLRsearch/ReceiveRateInterval.py +++ /dev/null @@ -1,74 +0,0 @@ -# Copyright (c) 2021 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 ReceiveRateInterval class.""" - -import math - - -class ReceiveRateInterval: - """Structure defining two Rr measurements, and their relation.""" - - def __init__(self, measured_low, measured_high): - """Store the bound measurements and call sort. - - :param measured_low: Measurement for the lower bound. - :param measured_high: Measurement for the upper bound. - :type measured_low: ReceiveRateMeasurement.ReceiveRateMeasurement - :type measured_high: ReceiveRateMeasurement.ReceiveRateMeasurement - """ - self.measured_low = measured_low - self.measured_high = measured_high - # Declare secondary quantities to appease pylint. - 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. Absolute divided by upper.""" - self.sort() - - def sort(self): - """Sort bounds by target Tr, compute secondary quantities.""" - if self.measured_low.target_tr > self.measured_high.target_tr: - self.measured_low, self.measured_high = ( - self.measured_high, self.measured_low - ) - self.abs_tr_width = ( - self.measured_high.target_tr - self.measured_low.target_tr - ) - self.rel_tr_width = self.abs_tr_width / self.measured_high.target_tr - - def __str__(self): - """Return string as half-open interval.""" - return f"[{self.measured_low!s};{self.measured_high!s})" - - def __repr__(self): - """Return string evaluable as a constructor call.""" - return f"ReceiveRateInterval(measured_low={self.measured_low!r}," \ - f"measured_high={self.measured_high!r})" - - def width_in_goals(self, relative_width_goal): - """Return float value. - - Relative width goal is some (negative) value on logarithmic scale. - Current relative width is another logarithmic value. - Return the latter divided by the former. - This is useful when investigating how did surprising widths come to be. - - :param relative_width_goal: Upper bound times this is the goal - difference between upper bound and lower bound. - :type relative_width_goal: float - :returns: Current width as logarithmic multiple of goal width [1]. - :rtype: float - """ - return math.log(1.0 - self.rel_tr_width) / math.log( - 1.0 - relative_width_goal) diff --git a/resources/libraries/python/MLRsearch/ReceiveRateMeasurement.py b/resources/libraries/python/MLRsearch/ReceiveRateMeasurement.py deleted file mode 100644 index c52934530e..0000000000 --- a/resources/libraries/python/MLRsearch/ReceiveRateMeasurement.py +++ /dev/null @@ -1,125 +0,0 @@ -# Copyright (c) 2021 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 ReceiveRateMeasurement class.""" - - -class ReceiveRateMeasurement: - """Structure defining the result of single Rr measurement.""" - - def __init__( - self, duration, target_tr, transmit_count, loss_count, - approximated_duration=0.0, partial_transmit_count=0, - effective_loss_ratio=None): - """Constructor, normalize primary and compute secondary quantities. - - If approximated_duration is nonzero, it is stored. - If approximated_duration is zero, duration value is stored. - Either way, additional secondary quantities are computed - from the store value. - - If there is zero transmit_count, ratios are set to zero. - - In some cases, traffic generator does not attempt all the needed - transactions. In that case, nonzero partial_transmit_count - holds (an estimate of) count of the actually attempted transactions. - This is used to populate some secondary quantities. - - TODO: Use None instead of zero? - - Field effective_loss_ratio is specific for use in MLRsearch, - where measurements with lower loss ratio at higher target_tr - cannot be relied upon if there is a measurement with higher loss ratio - at lower target_tr. In this case, the higher loss ratio from - other measurement is stored as effective loss ratio in this measurement. - If None, the computed loss ratio of this measurement is used. - If not None, the computed ratio can still be apllied if it is larger. - - :param duration: Measurement duration [s]. - :param target_tr: Target transmit rate [pps]. - If bidirectional traffic is measured, this is bidirectional rate. - :param transmit_count: Number of packets transmitted [1]. - :param loss_count: Number of packets transmitted but not received [1]. - :param approximated_duration: Estimate of the actual time of the trial. - :param partial_transmit_count: Estimate count of actually attempted - transactions. - :param effective_loss_ratio: None or highest loss ratio so far. - :type duration: float - :type target_tr: float - :type transmit_count: int - :type loss_count: int - :type approximated_duration: float - :type partial_transmit_count: int - """ - self.duration = float(duration) - self.target_tr = float(target_tr) - self.transmit_count = int(transmit_count) - self.loss_count = int(loss_count) - self.receive_count = transmit_count - loss_count - self.transmit_rate = transmit_count / self.duration - self.loss_rate = loss_count / self.duration - self.receive_rate = self.receive_count / self.duration - self.loss_ratio = ( - float(self.loss_count) / self.transmit_count - if self.transmit_count > 0 else 1.0 - ) - self.effective_loss_ratio = self.loss_ratio - if effective_loss_ratio is not None: - if effective_loss_ratio > self.loss_ratio: - self.effective_loss_ratio = float(effective_loss_ratio) - self.receive_ratio = ( - float(self.receive_count) / self.transmit_count - if self.transmit_count > 0 else 0.0 - ) - self.approximated_duration = ( - float(approximated_duration) if approximated_duration - else self.duration - ) - self.approximated_receive_rate = ( - self.receive_count / self.approximated_duration - if self.approximated_duration > 0.0 else 0.0 - ) - # If the traffic generator is unreliable and sends less packets, - # the absolute receive rate might be too low for next target. - self.partial_transmit_count = ( - int(partial_transmit_count) if partial_transmit_count - else self.transmit_count - ) - self.partial_receive_ratio = ( - float(self.receive_count) / self.partial_transmit_count - if self.partial_transmit_count > 0 else 0.0 - ) - self.partial_receive_rate = ( - self.target_tr * self.partial_receive_ratio - ) - # We use relative packet ratios in order to support cases - # where target_tr is in transactions per second, - # but there are multiple packets per transaction. - self.relative_receive_rate = ( - self.target_tr * self.receive_count / self.transmit_count - ) - - def __str__(self): - """Return string reporting input and loss ratio.""" - return f"d={self.duration!s},Tr={self.target_tr!s}," \ - f"Df={self.loss_ratio!s}" - - def __repr__(self): - """Return string evaluable as a constructor call.""" - return f"ReceiveRateMeasurement(duration={self.duration!r}," \ - f"target_tr={self.target_tr!r}," \ - f"transmit_count={self.transmit_count!r}," \ - f"loss_count={self.loss_count!r}," \ - f"approximated_duration={self.approximated_duration!r}," \ - f"partial_transmit_count={self.partial_transmit_count!r}," \ - f"effective_loss_ratio={self.effective_loss_ratio!r})" diff --git a/resources/libraries/python/MLRsearch/WidthArithmetics.py b/resources/libraries/python/MLRsearch/WidthArithmetics.py deleted file mode 100644 index 21316c5441..0000000000 --- a/resources/libraries/python/MLRsearch/WidthArithmetics.py +++ /dev/null @@ -1,137 +0,0 @@ -# Copyright (c) 2021 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 utility functions for manipulating intervals.""" - -import math - - -ROUNDING_CONSTANT = 0.999999 - -def multiply_relative_width(relative_width, coefficient): - """Return relative width corresponding to multiplied logarithmic width. - - The multiplication happens in logarithmic space, - so the resulting relative width is always less than 1. - - :param relative_width: The base relative width to multiply. - :param coefficient: Multiply by this in logarithmic space. - :type relative_width: float - :type coefficient: float - :returns: The relative width of multiplied logarithmic size. - :rtype: float - """ - old_log_width = math.log(1.0 - relative_width) - # Slight decrease to prevent rounding errors from prolonging the search. - # TODO: Make the nines configurable. - new_log_width = old_log_width * coefficient * ROUNDING_CONSTANT - return 1.0 - math.exp(new_log_width) - -def halve_relative_width(relative_width, goal_width): - """Return relative width corresponding to half logarithmic width. - - The logic attempts to save some halvings in future by performing - uneven split. If rounding error risk is detected, - even split is used. - - :param relative_width: The base relative width to halve. - :param goal_width: Width goal for final phase. - :type relative_width: float - :type goal_width: float - :returns: The relative width of half logarithmic size. - :rtype: float - """ - fallback_width = 1.0 - math.sqrt(1.0 - relative_width) - # Wig means Width In Goals. - wig = math.log(1.0 - relative_width) / math.log(1.0 - goal_width) - cwig = 2.0 * math.ceil(wig / 2.0) - fwig = 2.0 * math.ceil(wig * ROUNDING_CONSTANT / 2.0) - if wig <= 2.0 or cwig != fwig: - # Avoid too uneven splits. - return fallback_width - coefficient = cwig / 2 - new_width = multiply_relative_width(goal_width, coefficient) - return new_width - -def step_down(current_bound, relative_width): - """Return rate of logarithmic width below. - - :param current_bound: The current target transmit rate to move [pps]. - :param relative_width: The base relative width to use. - :type current_bound: float - :type relative_width: float - :returns: Transmit rate smaller by relative width [pps]. - :rtype: float - """ - return current_bound * (1.0 - relative_width) - -def step_up(current_bound, relative_width): - """Return rate of logarithmic width above. - - :param current_bound: The current target transmit rate to move [pps]. - :param relative_width: The base relative width to use. - :type current_bound: float - :type relative_width: float - :returns: Transmit rate larger by logarithmically double width [pps]. - :rtype: float - """ - return current_bound / (1.0 - relative_width) - -def multiple_step_down(current_bound, relative_width, coefficient): - """Return rate of multiplied logarithmic width below. - - The multiplication happens in logarithmic space, - so the resulting applied relative width is always less than 1. - - :param relative_width: The base relative width to double. - :param current_bound: The current target transmit rate to move [pps]. - :param coefficient: Multiply by this in logarithmic space. - :type relative_width: float - :type current_bound: float - :type coefficient: float - :returns: Transmit rate smaller by logarithmically multiplied width [pps]. - :rtype: float - """ - new_width = multiply_relative_width(relative_width, coefficient) - return step_down(current_bound, new_width) - -def multiple_step_up(current_bound, relative_width, coefficient): - """Return rate of double logarithmic width above. - - The multiplication happens in logarithmic space, - so the resulting applied relative width is always less than 1. - - :param current_bound: The current target transmit rate to move [pps]. - :param relative_width: The base relative width to double. - :param coefficient: Multiply by this in logarithmic space. - :type current_bound: float - :type relative_width: float - :type coefficient: float - :returns: Transmit rate larger by logarithmically multiplied width [pps]. - :rtype: float - """ - new_width = multiply_relative_width(relative_width, coefficient) - return step_up(current_bound, new_width) - -def half_step_up(current_bound, relative_width, goal_width): - """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 - """ - new_width = halve_relative_width(relative_width, goal_width) - return step_up(current_bound, new_width) diff --git a/resources/libraries/python/MLRsearch/__init__.py b/resources/libraries/python/MLRsearch/__init__.py index 35ef812179..349a9a96b3 100644 --- a/resources/libraries/python/MLRsearch/__init__.py +++ b/resources/libraries/python/MLRsearch/__init__.py @@ -1,4 +1,4 @@ -# Copyright (c) 2021 Cisco and/or its affiliates. +# Copyright (c) 2023 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: @@ -14,3 +14,17 @@ """ __init__ file for Python package "MLRsearch". """ + +# TODO: Move submodules to separate modules. +# Not obvious how to do that from PyPI point of view +# without affecting the current CSIT global "resources" package root. +# Probably it can be done by specifying multiple directories +# in PYTHONPATH used throughout CSIT. + +# Import user-facing (API) stuff, so users do not need to know submodules. +from .config import Config +from .search_goal import SearchGoal +from .multiple_loss_ratio_search import MultipleLossRatioSearch +from .pep3140 import Pep3140Dict +from .trial_measurement import AbstractMeasurer, MeasurementResult +from .trimmed_stat import TrimmedStat diff --git a/resources/libraries/python/MLRsearch/candidate.py b/resources/libraries/python/MLRsearch/candidate.py new file mode 100644 index 0000000000..16bbe60bae --- /dev/null +++ b/resources/libraries/python/MLRsearch/candidate.py @@ -0,0 +1,153 @@ +# Copyright (c) 2023 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 Candidate class.""" + +from __future__ import annotations + +from dataclasses import dataclass +from functools import total_ordering +from typing import Optional + +from .discrete_load import DiscreteLoad +from .discrete_width import DiscreteWidth +from .selector import Selector + + +@total_ordering +@dataclass(frozen=True) +class Candidate: + """Class describing next trial inputs, as nominated by a selector. + + As each selector is notified by the controller when its nominated load + becomes the winner, a reference to the selector is also included here. + + The rest of the code focuses on defining the ordering between candidates. + When two instances are compared, the lesser has higher priority + for choosing which trial is actually performed next. + + As Python implicitly converts values to bool in many places + (e.g. in "if" statement), any instance is called "truthy" if it converts + to True, and "falsy" if it converts to False. + To make such places nice and readable, __bool__ method is implemented + in a way that a candidate instance is falsy if its load is None. + As a falsy candidate never gets measured, + other fields of a falsy instance are irrelevant. + """ + + load: Optional[DiscreteLoad] = None + """Measure at this intended load. None if no load nominated by selector.""" + duration: float = None + """Trial duration as chosen by the selector.""" + width: Optional[DiscreteWidth] = None + """Set the global width to this when this candidate becomes the winner.""" + selector: Selector = None + """Reference to the selector instance which nominated this candidate.""" + + def __str__(self) -> str: + """Convert trial inputs into a short human-readable string. + + :returns: The short string. + :rtype: str + """ + return f"d={self.duration},l={self.load}" + + def __eq__(self, other: Candidate) -> bool: + """Return wheter self is identical to the other candidate. + + This is just a pretense for total ordering wrapper to work. + In reality, MLRsearch shall never test equivalence, + so we save space by just raising RuntimeError if this is ever called. + + :param other: The other instance to compare to. + :type other: Candidate + :returns: True if the instances are equivalent. + :rtype: bool + :raises RuntimeError: Always, to prevent unintended usage. + """ + raise RuntimeError("Candidate equality comparison shall not be needed.") + + def __lt__(self, other: Candidate) -> bool: + """Return whether self should be measured before other. + + In the decreasing order of importance: + Non-None load is preferred. + Self is less than other when both loads are None. + Lower offered load is preferred. + Longer trial duration is preferred. + Non-none width is preferred. + Larger width is preferred. + Self is preferred. + + The logic comes from the desire to save time and being conservative. + + :param other: The other instance to compare to. + :type other: Candidate + :returns: True if self should be measured sooner. + :rtype: bool + """ + if not self.load: + if other.load: + return False + return True + if not other.load: + return True + if self.load < other.load: + return True + if self.load > other.load: + return False + if self.duration > other.duration: + return True + if self.duration < other.duration: + return False + if not self.width: + if other.width: + return False + return True + if not other.width: + return True + return self.width >= other.width + + def __bool__(self) -> bool: + """Does this candidate choose to perform any trial measurement? + + :returns: True if yes, it does choose to perform. + :rtype: bool + """ + return bool(self.load) + + @staticmethod + def nomination_from(selector: Selector) -> Candidate: + """Call nominate on selector, wrap into Candidate instance to return. + + We avoid dependency cycle while letting candidate depend on selector, + therefore selector cannot know how to wrap its nomination + into a full candidate instance. + This factory method finishes the wrapping. + + :param selector: Selector to call. + :type selector: Selector + :returns: Newly created Candidate instance with nominated trial inputs. + :rtype: Candidate + """ + load, duration, width = selector.nominate() + return Candidate( + load=load, + duration=duration, + width=width, + selector=selector, + ) + + def won(self) -> None: + """Inform selector its candidate became a winner.""" + self.selector.won(self.load) diff --git a/resources/libraries/python/MLRsearch/config.py b/resources/libraries/python/MLRsearch/config.py new file mode 100644 index 0000000000..7aa8ed75a8 --- /dev/null +++ b/resources/libraries/python/MLRsearch/config.py @@ -0,0 +1,179 @@ +# Copyright (c) 2023 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 Config class.""" + +from collections.abc import Iterable +from dataclasses import dataclass +from typing import Optional + +from .dataclass import DataclassProperty +from .search_goal import SearchGoal +from .search_goal_tuple import SearchGoalTuple + + +@dataclass +class Config: + """Structure containing several static config items. + + The main MLRsearch algorithm uses multiple customizable values. + Pylint complains if the values appear as long argument lists + or multiple local variables. + + This class offers a storage for values which do not contain + internally mutable state and are set at an unknown time + before the search starts. This way users can override only some values, + and do it over multiple calls. + All "official" user inputs are contained here. + + Properties are defined to enforce the requirements on allowed values. + All fields have default values, so instances can be created without any. + It is still recommended to set all values after instantiation, + as the defaults may change in the next version. + + As some relations between values of different fields are required, + users must take care to set them in the correct order. + + For example, min_load has to be set to a value smaller + than the current value of max_load. + """ + + # Externally visible "fields" (but in fact redefined as properties). + goals: SearchGoalTuple = SearchGoalTuple((SearchGoal(),)) + """Container holding search goals.""" + min_load: float = 9001.0 + """Each trial measurement must have intended load at least this [tps].""" + max_load: float = 1e9 + """Each trial measurement must have intended load at most this [tps].""" + search_duration_max: float = 1200.0 + """The search will end as a failure this long [s] after it is started.""" + warmup_duration: float = 1.0 + """If specified, one trial at max load and this duration is performed + before the usual search starts. None converts to zero and means no warmup. + The results of that one trial are ignored.""" + + @DataclassProperty + def goals(self) -> SearchGoalTuple: + """Return the reference to the current container of goals. + + :returns: The current container instance. + :rtype: SearchGoalTuple + """ + return self._goals + + @goals.setter + def goals(self, goals: Iterable[SearchGoal]) -> None: + """Create and store the goal container. + + :param goals: Search goals to add to the container to store. + :type goals: Iterable[SearchGoal] + :raises ValueError: If there are no goals. + :raises TypeError: If any of the goals is not a SearchGoal. + """ + self._goals = SearchGoalTuple(goals) + + @DataclassProperty + def min_load(self) -> float: + """Getter for min load, no logic here. + + :returns: Currently set minimal intended load [tps]. + :rtype: float + """ + return self._min_load + + @min_load.setter + def min_load(self, load: float) -> None: + """Set min load after converting type and checking value. + + :param load: Minimal intended load [tps] to set. + :type load: float + :raises ValueError: If the argument is found invalid. + """ + load = float(load) + if load <= 0.0: + raise ValueError(f"Min load {load} must be positive.") + # At the time init is first called, _max_load is not set yet. + if hasattr(self, "_max_load") and load >= self.max_load: + raise ValueError(f"Min load {load} must be smaller.") + self._min_load = load + + @DataclassProperty + def max_load(self) -> float: + """Getter for max load, no logic here. + + :returns: Currently set maximal intended load [tps]. + :rtype: float + """ + return self._max_load + + @max_load.setter + def max_load(self, load: float) -> None: + """Set max load after converting type and checking value. + + :param load: Minimal intended load [tps] to set. + :type load: float + :raises ValueError: If the argument is found invalid. + """ + load = float(load) + if load <= self.min_load: + raise ValueError(f"Max load {load} must be bigger.") + self._max_load = load + + @DataclassProperty + def search_duration_max(self) -> float: + """Getter for max search duration, no logic here. + + :returns: Currently set max search duration [s]. + :rtype: float + """ + return self._search_duration_max + + @search_duration_max.setter + def search_duration_max(self, duration: float) -> None: + """Set max search duration after converting and checking value. + + :param duration: Search duration maximum [s] to set. + :type duration: float + :raises ValueError: If the argument is found invalid. + """ + duration = float(duration) + if duration <= 0.0: + raise ValueError(f"Search duration max too small: {duration}") + self._search_duration_max = duration + + @DataclassProperty + def warmup_duration(self) -> float: + """Getter for warmup duration, no logic here. + + :returns: Currently set max search duration [s]. + :rtype: float + """ + return self._warmup_duration + + @warmup_duration.setter + def warmup_duration(self, duration: Optional[float]) -> None: + """Set warmup duration after converting and checking value. + + Zero duration is treated as None, meaning no warmup trial. + + :param duration: Warmup duration [s] to set. + :type duration: Optional(float) + :raises ValueError: If the argument is found invalid. + """ + if duration: + duration = float(duration) + if duration < 0.0: + raise ValueError(f"Warmup duration too small: {duration}") + else: + duration = 0.0 + self._warmup_duration = duration diff --git a/resources/libraries/python/MLRsearch/dataclass/__init__.py b/resources/libraries/python/MLRsearch/dataclass/__init__.py new file mode 100644 index 0000000000..e546b090c9 --- /dev/null +++ b/resources/libraries/python/MLRsearch/dataclass/__init__.py @@ -0,0 +1,19 @@ +# Copyright (c) 2023 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. + +""" +__init__ file for Python package "dataclass_property". +""" + +from .dc_property import DataclassProperty +from .field import secondary_field diff --git a/resources/libraries/python/MLRsearch/dataclass/dc_property.py b/resources/libraries/python/MLRsearch/dataclass/dc_property.py new file mode 100644 index 0000000000..7f3b49aeb8 --- /dev/null +++ b/resources/libraries/python/MLRsearch/dataclass/dc_property.py @@ -0,0 +1,173 @@ +# Copyright (c) 2023 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 DataclassProperty class. + +The main issue that needs support is dataclasses with properties +(including setters) and with (immutable) default values. + +First, this explains how property ends up passed as default constructor value: +https://florimond.dev/en/posts/2018/10/ +/reconciling-dataclasses-and-properties-in-python/ +TL;DR: By the time __init__ is generated, original class variable (type hint) +is replaced by property (method definition). + +Second, there are ways to deal with that: +https://stackoverflow.com/a/61480946 +TL;DR: It relies on the underscored field being replaced by the value. + +But that does not work for field which use default_factory (or no default) +(the underscored class field is deleted instead). +So another way is needed to cover those cases, +ideally without the need to define both original and underscored field. + +This implementation relies on a fact that decorators are executed +when the class fields do yet exist, and decorated function +does know its name, so the decorator can get the value stored in +the class field, and store it as an additional attribute of the getter function. +Then for setter, the property contains the getter (as an unbound function), +so it can access the additional attribute to get the value. + +This approach circumvents the precautions dataclasses take to prevent mishaps +when a single mutable object is shared between multiple instances. +So it is up to setters to create an appropriate copy of the default object +if the default value is mutable. + +The default value cannot be MISSING nor Field nor DataclassProperty, +otherwise the intended logic breaks. +""" + +from __future__ import annotations + +from dataclasses import Field, MISSING +from functools import wraps +from inspect import stack +from typing import Callable, Optional, TypeVar, Union + + +Self = TypeVar("Self") +"""Type for the dataclass instances being created using properties.""" +Value = TypeVar("Value") +"""Type for the value the property (getter, setter) handles.""" + + +def _calling_scope_variable(name: str) -> Value: + """Get a variable from a higher scope. + + This feels dirty, but without this the syntactic sugar + would not be sweet enough. + + The implementation is copied from https://stackoverflow.com/a/14694234 + with the difference of raising RuntimeError (instead of returning None) + if no variable of that name is found in any of the scopes. + + :param name: Name of the variable to access. + :type name: str + :returns: The value of the found variable. + :rtype: Value + :raises RuntimeError: If the variable is not found in any calling scope. + """ + frame = stack()[1][0] + while name not in frame.f_locals: + frame = frame.f_back + if frame is None: + raise RuntimeError(f"Field {name} value not found.") + return frame.f_locals[name] + + +class DataclassProperty(property): + """Subclass of property, handles default values for dataclass fields. + + If a dataclass field does not specify a default value (nor default_factory), + this is not needed, and in fact it will not work (so use built-in property). + + This implementation seemlessly finds and inserts the default value + (can be mutable) into a new attribute of the getter function. + Before calling a setter function in init (recognized by type), + the default value is retrieved and passed transparently to the setter. + It is the responsibilty of the setter to appropriately clone the value, + in order to prevent multiple instances sharing the same mutable value. + """ + + def __init__( + self, + fget: Optional[Callable[[], Value]] = None, + fset: Optional[Callable[[Self, Value], None]] = None, + fdel: Optional[Callable[[], None]] = None, + doc: Optional[str] = None, + ): + """Find and store the default value, construct the property. + + See this for how the superclass property works: + https://docs.python.org/3/howto/descriptor.html#properties + + :param fget: Getter (unbound) function to use, if any. + :param fset: Setter (unbound) function to use, if any. + :param fdel: Deleter (unbound) function to use, if any. + :param doc: Docstring to display when examining the property. + :type fget: Optional[Callable[[Self], Value]] + :type fset: Optional[Callable[[Self, Value], None]] + :type fdel: Optional[Callable[[Self], None]] + :type doc: Optional[str] + """ + variable_found = _calling_scope_variable(fget.__name__) + if not isinstance(variable_found, DataclassProperty): + if isinstance(variable_found, Field): + if variable_found.default is not MISSING: + fget.default_value = variable_found.default + # Else do not store any default value. + else: + fget.default_value = variable_found + # Else this is the second time init is called (when setting setter), + # in which case the default is already stored into fget. + super().__init__(fget=fget, fset=fset, fdel=fdel, doc=doc) + + def setter( + self, + fset: Optional[Callable[[Self, Value], None]], + ) -> DataclassProperty: + """Return new instance with a wrapped setter function set. + + If the argument is None, call superclass method. + + The wrapped function recognizes when it is called in init + (by the fact the value argument is of type DataclassProperty) + and in that case it extracts the stored default and passes that + to the user-defined setter function. + + :param fset: Setter function to wrap and apply. + :type fset: Optional[Callable[[Self, Value], None]] + :returns: New property instance with correct setter function set. + :rtype: DataclassProperty + """ + if fset is None: + return super().setter(fset) + + @wraps(fset) + def wrapped(sel_: Self, val: Union[Value, DataclassProperty]) -> None: + """Extract default from getter if needed, call the user setter. + + The sel_ parameter is listed explicitly, to signify + this is an unbound function, not a bounded method yet. + + :param sel_: Instance of dataclass (not of DataclassProperty) + to set the value on. + :param val: Set this value, or the default value stored there. + :type sel_: Self + :type val: Union[Value, DataclassProperty] + """ + if isinstance(val, DataclassProperty): + val = val.fget.default_value + fset(sel_, val) + + return super().setter(wrapped) diff --git a/resources/libraries/python/MLRsearch/dataclass/field.py b/resources/libraries/python/MLRsearch/dataclass/field.py new file mode 100644 index 0000000000..55d9d0879f --- /dev/null +++ b/resources/libraries/python/MLRsearch/dataclass/field.py @@ -0,0 +1,44 @@ +# Copyright (c) 2023 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 secondary_field function. + +Just a shrothand for frequently repeated expression. + +The main point is that this dataclass field is not used in init. +Maybe it is a derived value of a frozen dataclass. +Maybe it is a cache to help avoiding repeated computation. +Maybe it is a temporary value stored in one method and read in another method. +In any case, the caller does not need to know it is here, +so it is excluded from repr, hashing, ordering and similar. +""" + +from dataclasses import Field, field + + +def secondary_field() -> Field: + """Return newly created Field with non-default arguments + + In practice, it seems to be fine to reuse the resulting Field instance + when defining multiple dataclass fields, + but we keep this as a function to improve readability. + + :returns: A new Field instance useful for secondary fields. + :rtype: Field + """ + return field( + default=None, + init=False, + repr=False, + compare=False, + ) diff --git a/resources/libraries/python/MLRsearch/discrete_interval.py b/resources/libraries/python/MLRsearch/discrete_interval.py new file mode 100644 index 0000000000..0a3bf443a8 --- /dev/null +++ b/resources/libraries/python/MLRsearch/discrete_interval.py @@ -0,0 +1,140 @@ +# Copyright (c) 2023 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 DiscreteInterval class.""" + +from dataclasses import dataclass + +from .dataclass import secondary_field +from .discrete_load import DiscreteLoad +from .discrete_width import DiscreteWidth + + +# TODO: Can this be frozen? +@dataclass +class DiscreteInterval: + """Interval class with more computations available. + + Along discrete form of width, + a MLR specific way for halving the interval is also included. + + The two primary field values do not have to be valid relevant bounds, + but at the end of the search, they usually are. + + The load values must be round. + """ + + lower_bound: DiscreteLoad + """Value for the lower intended load (or load stats or similar).""" + upper_bound: DiscreteLoad + """Value for the higher intended load (or load stats or similar).""" + # Primary fields above, derived below. + discrete_width: DiscreteWidth = secondary_field() + """Discrete width between intended loads (upper_bound minus lower_bound).""" + + def __post_init__(self) -> None: + """Sort bounds by intended load, compute secondary quantities. + + :raises RuntimeError: If a result used non-rounded load. + """ + if not self.lower_bound.is_round: + raise RuntimeError(f"Non-round lower bound: {self.lower_bound!r}") + if not self.upper_bound.is_round: + raise RuntimeError(f"Non-round upper bound: {self.upper_bound!r}") + if self.lower_bound > self.upper_bound: + tmp = self.lower_bound + self.lower_bound = self.upper_bound + self.upper_bound = tmp + self.discrete_width = self.upper_bound - self.lower_bound + + def __str__(self) -> str: + """Convert to a short human-readable string. + + :returns: The short string. + :rtype: str + """ + return ( + f"lower_bound=({self.lower_bound}),upper_bound=({self.upper_bound})" + ) + + # TODO: Use "target" instad of "goal" in argument and variable names. + + def width_in_goals(self, goal: DiscreteWidth) -> float: + """Return relative width as a multiple of the given goal (int form). + + Integer forms are used for computation, safe as loads are rounded. + The result is a float, as self int may not be divisible by goal int. + + :param goal: A relative width amount to be used as a unit. + :type goal: DiscreteWidth + :returns: Self width in multiples of (integer form of) goal width. + :rtype: float + """ + return int(self.discrete_width) / int(goal) + + def middle(self, goal: DiscreteWidth) -> DiscreteLoad: + """Return new intended load (discrete form) in the middle. + + All calculations are based on int forms. + + One of the halfs is rounded to a power-of-two multiple of the goal. + The power that leads to most even split is used. + Lower width is the smaller one (if not exactly even). + + This approach prefers lower loads (to remain conservative) and can save + some measurements (when all middle measurements have high loss). + Note that when competing with external search from above, + that search is already likely to produce widths that are + power-of-two multiples of the target width. + + If the interval width is one goal (or less), RuntimeError is raised. + If the interval width is between one and two goals (not including), + a more even split is attempted (using half the goal value). + + :param goal: Target width goal to use for uneven halving. + :type goal: DiscreteWidth + :returns: New load to use for bisecting. + :rtype: DiscreteLoad + :raises RuntimeError: If an internal inconsistency is detected. + """ + int_self, int_goal = int(self.discrete_width), int(goal) + if int_self <= int_goal: + raise RuntimeError(f"Do not halve small enough interval: {self!r}") + if int_self == 2 * int_goal: + # Even split, return here simplifies the while loop below. + return self.lower_bound + goal + if int_self < 2 * int_goal: + # This can only happen when int_goal >= 2. + # In this case, we do not have good enough split at this width goal, + # but maybe this is not the final target, so we can attempt + # a split at half width goal. + if not int_goal % 2: + return self.middle(goal=goal.half_rounded_down()) + # Odd int_goal, so this must by the last phase. Do even split. + lo_width = self.discrete_width.half_rounded_down() + return self.lower_bound + lo_width + hi_width = goal + lo_width = self.discrete_width - hi_width + # We know lo_width > hi_width because we did not do the even split. + while 1: + hi2_width = hi_width * 2 + lo2_width = self.discrete_width - hi2_width + if lo2_width <= hi2_width: + break + hi_width, lo_width = hi2_width, lo2_width + # Which of the two options is more even? Product decides. + if int(hi_width) * int(lo_width) > int(hi2_width) * int(lo2_width): + # Previous attempt was more even, but hi_width was the smaller one. + lo2_width = hi_width + # Else lo2_width is more even and no larger than hi2_width. + return self.lower_bound + lo2_width diff --git a/resources/libraries/python/MLRsearch/discrete_load.py b/resources/libraries/python/MLRsearch/discrete_load.py new file mode 100644 index 0000000000..a75b4acf96 --- /dev/null +++ b/resources/libraries/python/MLRsearch/discrete_load.py @@ -0,0 +1,316 @@ +# Copyright (c) 2023 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 DiscreteLoad class.""" + +from __future__ import annotations + +from dataclasses import dataclass, field +from functools import total_ordering +from typing import Callable, Optional, Union + +from .load_rounding import LoadRounding +from .discrete_width import DiscreteWidth + + +@total_ordering +@dataclass +class DiscreteLoad: + """Structure to store load value together with its rounded integer form. + + LoadRounding instance is needed to enable conversion between two forms. + Conversion methods and factories are added for convenience. + + In general, the float form is allowed to differ from conversion from int. + + Comparisons are supported, acting on the float load component. + Additive operations are supported, acting on int form. + Multiplication by a float constant is supported, acting on float form. + + As for all user defined classes by default, all instances are truthy. + That is useful when dealing with Optional values, as None is falsy. + + This dataclass is effectively frozen, but cannot be marked as such + as that would prevent LoadStats from being its subclass. + """ + + # For most debugs, rounding in repr just takes space. + rounding: LoadRounding = field(repr=False, compare=False) + """Rounding instance to use for conversion.""" + float_load: float = None + """Float form of intended load [tps], usable for measurer.""" + int_load: int = field(compare=False, default=None) + """Integer form, usable for exact computations.""" + + def __post_init__(self) -> None: + """Ensure types, compute missing information. + + At this point, it is allowed for float load to differ from + conversion from int load. MLRsearch should round explicitly later, + based on its additional information. + + :raises RuntimeError: If both init arguments are None. + """ + if self.float_load is None and self.int_load is None: + raise RuntimeError("Float or int value is needed.") + if self.float_load is None: + self.int_load = int(self.int_load) + self.float_load = self.rounding.int2float(self.int_load) + else: + self.float_load = float(self.float_load) + self.int_load = self.rounding.float2int(self.float_load) + + def __str__(self) -> str: + """Convert to a short human-readable string. + + :returns: The short string. + :rtype: str + """ + return f"int_load={int(self)}" + + # Explicit comparison operators. + # Those generated with dataclass order=True do not allow subclass instances. + + def __eq__(self, other: Optional[DiscreteLoad]) -> bool: + """Return whether the other instance has the same float form. + + None is effectively considered to be an unequal instance. + + :param other: Other instance to compare to, or None. + :type other: Optional[DiscreteLoad] + :returns: True only if float forms are exactly equal. + :rtype: bool + """ + if other is None: + return False + return float(self) == float(other) + + def __lt__(self, other: DiscreteLoad) -> bool: + """Return whether self has smaller float form than the other instance. + + None is not supported, as MLRsearch does not need that + (so when None appears we want to raise). + + :param other: Other instance to compare to. + :type other: DiscreteLoad + :returns: True only if float forms of self is strictly smaller. + :rtype: bool + """ + return float(self) < float(other) + + def __hash__(self) -> int: + """Return a hash based on the float value. + + With this, the instance can be used as if it was immutable and hashable, + e.g. it can be a key in a dict. + + :returns: Hash value for this instance. + :rtype: int + """ + return hash(float(self)) + + @property + def is_round(self) -> bool: + """Return whether float load matches converted int load. + + :returns: False if float load is not rounded. + :rtype: bool + """ + expected = self.rounding.int2float(self.int_load) + return expected == self.float_load + + def __int__(self) -> int: + """Return the int value. + + :returns: The int field value. + :rtype: int + """ + return self.int_load + + def __float__(self) -> float: + """Return the float value. + + :returns: The float field value [tps]. + :rtype: float + """ + return self.float_load + + @staticmethod + def int_conver(rounding: LoadRounding) -> Callable[[int], DiscreteLoad]: + """Return a factory that turns an int load into a discrete load. + + :param rounding: Rounding instance needed. + :type rounding: LoadRounding + :returns: Factory to use when converting from int. + :rtype: Callable[[int], DiscreteLoad] + """ + + def factory_int(int_load: int) -> DiscreteLoad: + """Use rounding and int load to create discrete load. + + :param int_load: Intended load in integer form. + :type int_load: int + :returns: New discrete load instance matching the int load. + :rtype: DiscreteLoad + """ + return DiscreteLoad(rounding=rounding, int_load=int_load) + + return factory_int + + @staticmethod + def float_conver(rounding: LoadRounding) -> Callable[[float], DiscreteLoad]: + """Return a factory that turns a float load into a discrete load. + + :param rounding: Rounding instance needed. + :type rounding: LoadRounding + :returns: Factory to use when converting from float. + :rtype: Callable[[float], DiscreteLoad] + """ + + def factory_float(float_load: float) -> DiscreteLoad: + """Use rounding instance and float load to create discrete load. + + The float form is not rounded yet. + + :param int_load: Intended load in float form [tps]. + :type int_load: float + :returns: New discrete load instance matching the float load. + :rtype: DiscreteLoad + """ + return DiscreteLoad(rounding=rounding, float_load=float_load) + + return factory_float + + def rounded_down(self) -> DiscreteLoad: + """Create and return new instance with float form matching int. + + :returns: New instance with same int form and float form rounded down. + :rtype: DiscreteLoad + """ + return DiscreteLoad(rounding=self.rounding, int_load=int(self)) + + def hashable(self) -> DiscreteLoad: + """Return new equivalent instance. + + This is mainly useful for conversion from unhashable subclasses, + such as LoadStats. + Rounding instance (reference) is copied from self. + + :returns: New instance with values based on float form of self. + :rtype: DiscreteLoad + """ + return DiscreteLoad(rounding=self.rounding, float_load=float(self)) + + def __add__(self, width: DiscreteWidth) -> DiscreteLoad: + """Return newly constructed instance with width added to int load. + + Rounding instance (reference) is copied from self. + + Argument type is checked, to avoid caller adding two loads by mistake + (or adding int to load and similar). + + :param width: Value to add to int load. + :type width: DiscreteWidth + :returns: New instance. + :rtype: DiscreteLoad + :raises RuntimeError: When argument has unexpected type. + """ + if not isinstance(width, DiscreteWidth): + raise RuntimeError(f"Not width: {width!r}") + return DiscreteLoad( + rounding=self.rounding, + int_load=self.int_load + int(width), + ) + + def __sub__( + self, other: Union[DiscreteWidth, DiscreteLoad] + ) -> Union[DiscreteLoad, DiscreteWidth]: + """Return result based on the argument type. + + Load minus load is width, load minus width is load. + This allows the same operator to support both operations. + + Rounding instance (reference) is copied from self. + + :param other: Value to subtract from int load. + :type other: Union[DiscreteWidth, DiscreteLoad] + :returns: Resulting width or load. + :rtype: Union[DiscreteLoad, DiscreteWidth] + :raises RuntimeError: If the argument type is not supported. + """ + if isinstance(other, DiscreteWidth): + return self._minus_width(other) + if isinstance(other, DiscreteLoad): + return self._minus_load(other) + raise RuntimeError(f"Unsupported type {other!r}") + + def _minus_width(self, width: DiscreteWidth) -> DiscreteLoad: + """Return newly constructed instance, width subtracted from int load. + + Rounding instance (reference) is copied from self. + + :param width: Value to subtract from int load. + :type width: DiscreteWidth + :returns: New instance. + :rtype: DiscreteLoad + """ + return DiscreteLoad( + rounding=self.rounding, + int_load=self.int_load - int(width), + ) + + def _minus_load(self, other: DiscreteLoad) -> DiscreteWidth: + """Return newly constructed width instance, difference of int loads. + + Rounding instance (reference) is copied from self. + + :param other: Value to subtract from int load. + :type other: DiscreteLoad + :returns: New instance. + :rtype: DiscreteWidth + """ + return DiscreteWidth( + rounding=self.rounding, + int_width=self.int_load - int(other), + ) + + def __mul__(self, coefficient: float) -> DiscreteLoad: + """Return newly constructed instance, float load multiplied by argument. + + Rounding instance (reference) is copied from self. + + :param coefficient: Value to multiply float load with. + :type coefficient: float + :returns: New instance. + :rtype: DiscreteLoad + :raises RuntimeError: If argument is unsupported. + """ + if not isinstance(coefficient, float): + raise RuntimeError(f"Not float: {coefficient!r}") + if coefficient <= 0.0: + raise RuntimeError(f"Not positive: {coefficient!r}") + return DiscreteLoad( + rounding=self.rounding, + float_load=self.float_load * coefficient, + ) + + def __truediv__(self, coefficient: float) -> DiscreteLoad: + """Call multiplication with inverse argument. + + :param coefficient: Value to divide float load with. + :type coefficient: float + :returns: New instance. + :rtype: DiscreteLoad + :raises RuntimeError: If argument is unsupported. + """ + return self * (1.0 / coefficient) diff --git a/resources/libraries/python/MLRsearch/discrete_result.py b/resources/libraries/python/MLRsearch/discrete_result.py new file mode 100644 index 0000000000..882b6081c6 --- /dev/null +++ b/resources/libraries/python/MLRsearch/discrete_result.py @@ -0,0 +1,76 @@ +# Copyright (c) 2023 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 DiscreteResult class.""" + +from __future__ import annotations + +from dataclasses import dataclass + +from .discrete_load import DiscreteLoad +from .trial_measurement import MeasurementResult + + +@dataclass +class DiscreteResult(MeasurementResult): + """A measurement result where intended load is also given as discrete load. + + The discrete load has to be round and has to match the intended load. + """ + + # Must have default as superclass has fields with default values. + discrete_load: DiscreteLoad = None + """Intended load [tps]; discrete, round and equal to intended load.""" + + def __post_init__(self) -> None: + """Call super, verify intended and discrete loads are the same. + + :raises TypeError: If discrete load is not DiscreteLoad. + :raises ValueError: If the discrete load is not round. + :raises ValueError: If the load does not match intended load. + """ + super().__post_init__() + if not isinstance(self.discrete_load, DiscreteLoad): + raise TypeError(f"Not a discrete load: {self.discrete_load!r}") + if not self.discrete_load.is_round: + raise ValueError(f"Discrete load not round: {self.discrete_load!r}") + if float(self.discrete_load) != self.intended_load: + raise ValueError(f"Load mismatch: {self!r}") + + @staticmethod + def with_load( + result: MeasurementResult, load: DiscreteLoad + ) -> DiscreteResult: + """Return result with added load. + + :param result: A result, possibly without discrete load. + :param load: Discrete load to add. + :type result: MeasurementResult + :type load: DiscreteLoad + :returns: Equivalent result with matching discrete load. + :rtype: DiscreteResult + :raises TypeError: If discrete load is not DiscreteLoad. + :raises ValueError: If the discrete load is not round. + :raises ValueError: If the load does not match intended load. + """ + return DiscreteResult( + intended_duration=result.intended_duration, + intended_load=result.intended_load, + offered_count=result.offered_count, + loss_count=result.loss_count, + forwarding_count=result.forwarding_count, + offered_duration=result.offered_duration, + duration_with_overheads=result.duration_with_overheads, + intended_count=result.intended_count, + discrete_load=load, + ) diff --git a/resources/libraries/python/MLRsearch/discrete_width.py b/resources/libraries/python/MLRsearch/discrete_width.py new file mode 100644 index 0000000000..8a4845a83f --- /dev/null +++ b/resources/libraries/python/MLRsearch/discrete_width.py @@ -0,0 +1,197 @@ +# Copyright (c) 2023 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 DiscreteWidth class.""" + +from __future__ import annotations + +from dataclasses import dataclass, field + +from .load_rounding import LoadRounding + + +# TODO: Make properly frozen. +@dataclass(order=True) +class DiscreteWidth: + """Structure to store float width together with its rounded integer form. + + The width does not have to be positive, i.e. the computed integer width + does not have to be larger than zero. + + LoadRounding instance is needed to enable conversion between two forms. + + Conversion and arithmetic methods are added for convenience. + Division and non-integer multiplication are intentionally not supported, + as MLRsearch should not seek unround widths when round ones are available. + + The instance is effectively immutable, but not hashable as it refers + to the rounding instance, which is implemented as mutable + (although the mutations are not visible). + """ + + # For most debugs, rounding in repr just takes space. + rounding: LoadRounding = field(repr=False, compare=False) + """Rounding instance to use for conversion.""" + float_width: float = None + """Relative width of float intended load. + This is treated as a constructor argument, and does not need to match + the int width. Int width is computed to be no wider than this.""" + int_width: int = field(compare=False, default=None) + """Integer form, difference of integer loads. + This is the primary quantity used by most computations.""" + + def __post_init__(self) -> None: + """Ensure types, compute missing information. + + At this point, it is allowed for float width to be slightly larger + than the implied int width. + + If both forms are specified, the float form is taken as primary + (thus the integer form is recomputed to match). + + :raises RuntimeError: If both init arguments are None. + """ + if self.float_width is None and self.int_width is None: + raise RuntimeError("Float or int value is needed.") + if self.float_width is None: + self.int_width = int(self.int_width) + min_load = self.rounding.int2float(0) + increased_load = self.rounding.int2float(self.int_width) + self.float_width = (increased_load - min_load) / increased_load + return + self.float_width = float(self.float_width) + min_load = self.rounding.int2float(0) + increased_load = min_load / (1.0 - self.float_width) + int_load = self.rounding.float2int(increased_load) + verify_load = self.rounding.int2float(int_load) + if verify_load > increased_load: + int_load -= 1 + self.int_width = int_load + + def __str__(self) -> str: + """Convert into a short human-readable string. + + :returns: The short string. + :rtype: str + """ + return f"int_width={int(self)}" + + def __int__(self) -> int: + """Return the integer form. + + :returns: The int field value. + :rtype: int + """ + return self.int_width + + def __float__(self) -> float: + """Return the float form. + + :returns: The float field value. + :rtype: float + """ + return self.float_width + + def __hash__(self) -> int: + """Return a hash based on the float value. + + With this, the instance can be used as if it was immutable and hashable, + e.g. it can be a key in a dict. + + :returns: Hash value for this instance. + :rtype: int + """ + return hash(float(self)) + + def rounded_down(self) -> DiscreteWidth: + """Create and return new instance with float form matching int. + + :returns: New instance with same int form and float form rounded down. + :rtype: DiscreteWidth + """ + return DiscreteWidth(rounding=self.rounding, int_width=int(self)) + + def __add__(self, width: DiscreteWidth) -> DiscreteWidth: + """Return newly constructed instance with int widths added. + + Rounding instance (reference) is copied from self. + + Argument type is checked, to avoid caller adding something unsupported. + + :param width: Value to add to int width. + :type width: DiscreteWidth + :returns: New instance. + :rtype: DiscreteWidth + :raises RuntimeError: When argument has unexpected type. + """ + if not isinstance(width, DiscreteWidth): + raise RuntimeError(f"Not width: {width!r}") + return DiscreteWidth( + rounding=self.rounding, + int_width=self.int_width + int(width), + ) + + def __sub__(self, width: DiscreteWidth) -> DiscreteWidth: + """Return newly constructed instance with int widths subtracted. + + Rounding instance (reference) is copied from self. + + Argument type is checked, to avoid caller adding something unsupported. + Non-positive results are disallowed by constructor. + + :param width: Value to subtract to int width. + :type width: DiscreteWidth + :returns: New instance. + :rtype: DiscreteWidth + :raises RuntimeError: When argument has unexpected type. + """ + if not isinstance(width, DiscreteWidth): + raise RuntimeError(f"Not width: {type(width)}") + return DiscreteWidth( + rounding=self.rounding, + int_width=self.int_width - int(width), + ) + + def __mul__(self, coefficient: int) -> DiscreteWidth: + """Construct new instance with int value multiplied. + + Rounding instance (reference) is copied from self. + + :param coefficient: Constant to multiply int width with. + :type coefficient: int + :returns: New instance with multiplied int width. + :rtype: DiscreteWidth + :raises RuntimeError: If argument value does not meet requirements. + """ + if not isinstance(coefficient, int): + raise RuntimeError(f"Coefficient not int: {coefficient!r}") + if coefficient < 1: + raise RuntimeError(f"Coefficient not positive: {coefficient!r}") + return DiscreteWidth( + rounding=self.rounding, + int_width=self.int_width * coefficient, + ) + + def half_rounded_down(self) -> DiscreteWidth: + """Contruct new instance of half the integer width. + + If the current integer width is odd, round the half width down. + + :returns: New instance with half int width. + :rtype: DiscreteWidth + :raises RuntimeError: If the resulting integerl width is not positive. + """ + return DiscreteWidth( + rounding=self.rounding, + int_width=self.int_width // 2, + ) diff --git a/resources/libraries/python/MLRsearch/expander.py b/resources/libraries/python/MLRsearch/expander.py new file mode 100644 index 0000000000..0e6800477e --- /dev/null +++ b/resources/libraries/python/MLRsearch/expander.py @@ -0,0 +1,102 @@ +# Copyright (c) 2023 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 TargetExpander class.""" + + +from dataclasses import dataclass, field +from typing import Callable, Optional + +from .dataclass import secondary_field +from .discrete_load import DiscreteLoad +from .discrete_width import DiscreteWidth +from .global_width import GlobalWidth +from .limit_handler import LimitHandler +from .target_spec import TargetSpec + + +@dataclass +class TargetedExpander: + """Utility class to track expanding width during external search. + + One instance per selector but takes into consideration global current width. + + Generally, many strategies may limit next_width immediately, + but next_width expands only after measurement + when external search fails to find its bound (global width is also bumped). + See strategy classes for specific details on external and internal search. + """ + + target: TargetSpec + """The target this strategy is focusing on.""" + global_width: GlobalWidth + """Reference to the global width tracking instance.""" + initial_lower_load: Optional[DiscreteLoad] + """Smaller of the two loads distinguished at instance creation. + Can be None if initial upper bound is the min load.""" + initial_upper_load: Optional[DiscreteLoad] + """Larger of the two loads distinguished at instance creation. + Can be None if initial lower bound is the max load.""" + handler: LimitHandler = field(repr=False) + """Reference to the class used to avoid too narrow intervals.""" + debug: Callable[[str], None] = field(repr=False) + """Injectable function for debug logging.""" + # Primary above, derived below. + next_width: DiscreteWidth = secondary_field() + """This will be used in next search step if no strategy intervenes.""" + + def __post_init__(self) -> None: + """Prepare next width.""" + self.next_width = self.target.discrete_width + if self.initial_lower_load and self.initial_upper_load: + interval_width = self.initial_upper_load - self.initial_lower_load + self.next_width = max(self.next_width, interval_width) + self.expand(bump_global=False) + + def expand(self, bump_global: bool = True) -> None: + """Multiply next width by expansion coefficient. + + The global current width should be bumped when external search + is done but load is not the bound we were looking for. + + For global width shrinking, set the field directly. + + :param bump_global: False if called from limit or post init. + :type bump_global: bool + """ + self.next_width *= self.target.expansion_coefficient + if bump_global: + self.global_width.width = self.next_width + + def get_width(self) -> DiscreteWidth: + """Return next width corrected by global current width. + + :returns: The width to use, see GlobalWidth. + :rtype: DiscreteWidth + """ + return self.global_width.or_larger(self.next_width) + + def limit(self, last_width: DiscreteWidth) -> None: + """Decrease the prepared next width. + + This is called by other strategies when bounds are getting narrower. + + Global current width is not updated yet, + as the other strategy may not end up becoming the winner + and we want to avoid interfering with other selector strategies. + + :param last_width: As applied by other strategy, smaller of two halves. + :type last_width: DiscreteWidth + """ + self.next_width = max(last_width, self.target.discrete_width) + self.expand(bump_global=False) diff --git a/resources/libraries/python/MLRsearch/global_width.py b/resources/libraries/python/MLRsearch/global_width.py new file mode 100644 index 0000000000..6f7df8b894 --- /dev/null +++ b/resources/libraries/python/MLRsearch/global_width.py @@ -0,0 +1,70 @@ +# Copyright (c) 2023 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 GlobalWidth class.""" + + +from __future__ import annotations + +from dataclasses import dataclass + +from .discrete_load import DiscreteLoad +from .discrete_width import DiscreteWidth + + +@dataclass +class GlobalWidth: + """Primarily used to synchronize external search steps across selectors. + + The full name is global current width, but that is too long for identifiers. + + While each selector tracks its "local" (per goal) width using expander, + it is important we do not interleave upper external search for two goals. + That is why all selector instances refer to a singleton instance of this. + + In general, this value remains constant when main loop iterates over + selectors and when selector iterates over strategies. + After winner is measured, this width is set to winner width value + and for some strategies that width is expanded when external search says so. + + The two methods are not really worth creating a new class, + but the main reason is having a name for type hints + that distinguish this from various other "width" and "current" values. + """ + + width: DiscreteWidth + """Minimum width to apply at next external search step.""" + # TODO: Add a setter, so it is easier to add debug logging. + + @staticmethod + def from_loads(load0: DiscreteLoad, load1: DiscreteLoad) -> GlobalWidth: + """Initialize the value based on two loads from initial trials. + + :param load0: Lower (or equal) load from the two most recent trials. + :param load1: Higher (or equal) load from the two most recent trials. + :type load0: DiscreteLoad + :type load1: DiscreteLoad + :returns: Newly created instance with computed width. + :rtype: GlobalWidth + """ + return GlobalWidth(load1 - load0) + + def or_larger(self, width: DiscreteWidth) -> DiscreteWidth: + """Return width from argument or self, whichever is larger. + + :param width: A selector (strategy) asks if this width is large enough. + :type width: DiscreteWidth + :returns: Argument or current width. + :rtype: DiscreteWidth + """ + return width if width > self.width else self.width diff --git a/resources/libraries/python/MLRsearch/limit_handler.py b/resources/libraries/python/MLRsearch/limit_handler.py new file mode 100644 index 0000000000..5919f398f3 --- /dev/null +++ b/resources/libraries/python/MLRsearch/limit_handler.py @@ -0,0 +1,198 @@ +# Copyright (c) 2023 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 LimitHandler class.""" + +from dataclasses import dataclass +from typing import Callable, Optional + +from .dataclass import secondary_field +from .discrete_interval import DiscreteInterval +from .discrete_load import DiscreteLoad +from .discrete_width import DiscreteWidth +from .load_rounding import LoadRounding + + +@dataclass +class LimitHandler: + """Encapsulated methods for logic around handling limits. + + In multiple places within MLRsearch code, an intended load value + is only useful if it is far enough from possible known values. + All such places can be served with the handle method + with appropriate arguments. + """ + + rounding: LoadRounding + """Rounding instance to use.""" + debug: Callable[[str], None] + """Injectable logging function.""" + # The two fields below are derived, extracted from rounding as a shortcut. + min_load: DiscreteLoad = secondary_field() + """Minimal load, as prescribed by Config.""" + max_load: DiscreteLoad = secondary_field() + """Maximal load, as prescribed by Config.""" + + def __post_init__(self) -> None: + """Initialize derived quantities.""" + from_float = DiscreteLoad.float_conver(rounding=self.rounding) + self.min_load = from_float(self.rounding.min_load) + self.max_load = from_float(self.rounding.max_load) + + def handle( + self, + load: DiscreteLoad, + width: DiscreteWidth, + clo: Optional[DiscreteLoad], + chi: Optional[DiscreteLoad], + ) -> Optional[DiscreteLoad]: + """Return new intended load after considering limits and bounds. + + Not only we want to avoid measuring outside minmax interval, + we also want to avoid measuring too close to known limits and bounds. + We either round or return None, depending on hints from bound loads. + + When rounding away from hard limits, we may end up being + too close to an already measured bound. + In this case, pick a midpoint between the bound and the limit. + + The last two arguments are just loads (not full measurement results) + to allow callers to exclude some load without measuring them. + As a convenience, full results are also supported, + so that callers do not need to care about None when extracting load. + + :param load: Intended load candidate, initial or from a load selector. + :param width: Relative width goal, considered narrow enough for now. + :param clo: Intended load of current relevant lower bound. + :param chi: Intended load of current relevant upper bound. + :type load: DiscreteLoad + :type width: DiscreteWidth + :type clo: Optional[DiscreteLoad] + :type chi: Optional[DiscreteLoad] + :return: Adjusted load to measure at, or None if narrow enough already. + :rtype: Optional[DiscreteLoad] + :raises RuntimeError: If unsupported corner case is detected. + """ + if not load: + raise RuntimeError("Got None load to handle.") + load = load.rounded_down() + min_load, max_load = self.min_load, self.max_load + if clo and not clo.is_round: + raise RuntimeError(f"Clo {clo} should have been round.") + if chi and not chi.is_round: + raise RuntimeError(f"Chi {chi} should have been round.") + if not clo and not chi: + load = self._handle_load_with_excludes( + load, width, min_load, max_load, min_ex=False, max_ex=False + ) + # The "return load" lines are separate from load computation, + # so that logging can be added more easily when debugging. + return load + if chi and not clo: + if chi <= min_load: + # Expected when hitting the min load. + return None + if load >= chi: + # This can happen when mrr2 forward rate is rounded to mrr2. + return None + load = self._handle_load_with_excludes( + load, width, min_load, chi, min_ex=False, max_ex=True + ) + return load + if clo and not chi: + if clo >= max_load: + raise RuntimeError("Lower load expected.") + if load <= clo: + raise RuntimeError("Higher load expected.") + load = self._handle_load_with_excludes( + load, width, clo, max_load, min_ex=True, max_ex=False + ) + return load + # We have both clo and chi defined. + if not clo < load < chi: + # Happens when bisect compares with bounded extend. + return None + load = self._handle_load_with_excludes( + load, width, clo, chi, min_ex=True, max_ex=True + ) + return load + + def _handle_load_with_excludes( + self, + load: DiscreteLoad, + width: DiscreteWidth, + minimum: DiscreteLoad, + maximum: DiscreteLoad, + min_ex: bool, + max_ex: bool, + ) -> Optional[DiscreteLoad]: + """Adjust load if too close to limits, respecting exclusions. + + This is a reusable block. + Limits may come from previous bounds or from hard load limits. + When coming from bounds, rounding to that is not allowed. + When coming from hard limits, rounding to the limit value + is allowed in general (given by the setting the _ex flag). + + :param load: The candidate intended load before accounting for limits. + :param width: Relative width of area around the limits to avoid. + :param minimum: The lower limit to round around. + :param maximum: The upper limit to round around. + :param min_ex: If false, rounding to the minimum is allowed. + :param max_ex: If false, rounding to the maximum is allowed. + :type load: DiscreteLoad + :type width: DiscreteWidth + :type minimum: DiscreteLoad + :type maximum: DiscreteLoad + :type min_ex: bool + :type max_ex: bool + :returns: Adjusted load value, or None if narrow enough. + :rtype: Optional[DiscreteLoad] + :raises RuntimeError: If internal inconsistency is detected. + """ + if not minimum <= load <= maximum: + raise RuntimeError( + "Internal error: load outside limits:" + f" load {load} min {minimum} max {maximum}" + ) + max_width = maximum - minimum + if width >= max_width: + self.debug("Warning: Handling called with wide width.") + if not min_ex: + self.debug("Minimum not excluded, rounding to it.") + return minimum + if not max_ex: + self.debug("Maximum not excluded, rounding to it.") + return maximum + self.debug("Both limits excluded, narrow enough.") + return None + soft_min = minimum + width + soft_max = maximum - width + if soft_min > soft_max: + self.debug("Whole interval is less than two goals.") + middle = DiscreteInterval(minimum, maximum).middle(width) + soft_min = soft_max = middle + if load < soft_min: + if min_ex: + self.debug("Min excluded, rounding to soft min.") + return soft_min + self.debug("Min not excluded, rounding to minimum.") + return minimum + if load > soft_max: + if max_ex: + self.debug("Max excluded, rounding to soft max.") + return soft_max + self.debug("Max not excluded, rounding to maximum.") + return maximum + # Far enough from all limits, no additional adjustment is needed. + return load diff --git a/resources/libraries/python/MLRsearch/load_rounding.py b/resources/libraries/python/MLRsearch/load_rounding.py new file mode 100644 index 0000000000..0ac4487be9 --- /dev/null +++ b/resources/libraries/python/MLRsearch/load_rounding.py @@ -0,0 +1,205 @@ +# Copyright (c) 2023 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 LoadRounding class.""" + +import math + +from dataclasses import dataclass +from typing import List, Tuple + +from .dataclass import secondary_field + + +@dataclass +class LoadRounding: + """Class encapsulating stateful utilities that round intended load values. + + For MLRsearch algorithm logic to be correct, it is important that + interval width expansion and narrowing are exactly reversible, + which is not true in general for floating point number arithmetics. + + This class offers conversion to and from an integer quantity. + Operations in the integer realm are guaranteed to be reversible, + so the only risk is when converting between float and integer realm. + + Which relative width corresponds to the unit integer + is computed in initialization from width goals, + striking a balance between memory requirements and precision. + + There are two quality knobs. One restricts how far + can an integer be from the exact float value. + The other restrict how close it can be. That is to make sure + even with unpredictable rounding errors during the conversion, + the converted integer value is never bigger than the intended float value, + to ensure the intervals returned from MLRsearch will always + meet the relative width goal. + + An instance of this class is mutable only in the sense it contains + a growing cache of previously computed values. + """ + + # TODO: Hide the cache and present as frozen hashable object. + + min_load: float + """Minimal intended load [tps] to support, must be positive.""" + max_load: float + """Maximal intended load [tps] to support, must be bigger than min load.""" + float_goals: Tuple[float] + """Relative width goals to approximate, each must be positive + and smaller than one. Deduplicated and sorted in post init.""" + quality_lower: float = 0.99 + """Minimal multiple of each goal to be achievable.""" + quality_upper: float = 0.999999 + """Maximal multiple of each goal to be achievable.""" + # Primary fields above, computed fields below. + max_int_load: int = secondary_field() + """Integer for max load (min load int is zero).""" + _int2load: List[Tuple[int, float]] = secondary_field() + """Known int values (sorted) and their float equivalents.""" + + def __post_init__(self) -> None: + """Ensure types, perform checks, initialize conversion structures. + + :raises RuntimeError: If a requirement is not met. + """ + self.min_load = float(self.min_load) + self.max_load = float(self.max_load) + if not 0.0 < self.min_load < self.max_load: + raise RuntimeError("Load limits not supported: {self}") + self.quality_lower = float(self.quality_lower) + self.quality_upper = float(self.quality_upper) + if not 0.0 < self.quality_lower < self.quality_upper < 1.0: + raise RuntimeError("Qualities not supported: {self}") + goals = [] + for goal in self.float_goals: + goal = float(goal) + if not 0.0 < goal < 1.0: + raise RuntimeError(f"Goal width {goal} is not supported.") + goals.append(goal) + self.float_goals = tuple(sorted(set(goals))) + self.max_int_load = self._find_ints() + self._int2load = [] + self._int2load.append((0, self.min_load)) + self._int2load.append((self.max_int_load, self.max_load)) + + def _find_ints(self) -> int: + """Find and return value for max_int_load. + + Separated out of post init, as this is less conversion and checking, + and more math and searching. + + A dumb implementation would start with 1 and kept increasing by 1 + until all goals are within quality limits. + An actual implementation is smarter with the increment, + so it is expected to find the resulting values somewhat faster. + + :returns: Value to be stored as max_int_load. + :rtype: int + """ + minmax_log_width = math.log(self.max_load) - math.log(self.min_load) + log_goals = [-math.log1p(-goal) for goal in self.float_goals] + candidate = 1 + while 1: + log_width_unit = minmax_log_width / candidate + # Fallback to increment by one if rounding errors make tries bad. + next_tries = [candidate + 1] + acceptable = True + for log_goal in log_goals: + units = log_goal / log_width_unit + int_units = math.floor(units) + quality = int_units / units + if not self.quality_lower <= quality <= self.quality_upper: + acceptable = False + target = (int_units + 1) / self.quality_upper + next_try = (target / units) * candidate + next_tries.append(next_try) + # Else quality acceptable, not bumping the candidate. + if acceptable: + return candidate + candidate = int(math.ceil(max(next_tries))) + + def int2float(self, int_load: int) -> float: + """Convert from int to float tps load. Expand internal table as needed. + + Too low or too high ints result in min or max load respectively. + + :param int_load: Integer quantity to turn back into float load. + :type int_load: int + :returns: Converted load in tps. + :rtype: float + :raises RuntimeError: If internal inconsistency is detected. + """ + if int_load <= 0: + return self.min_load + if int_load >= self.max_int_load: + return self.max_load + lo_index, hi_index = 0, len(self._int2load) + lo_int, hi_int = 0, self.max_int_load + lo_load, hi_load = self.min_load, self.max_load + while hi_int - lo_int >= 2: + mid_index = (hi_index + lo_index + 1) // 2 + if mid_index >= hi_index: + mid_int = (hi_int + lo_int) // 2 + log_coeff = math.log(hi_load) - math.log(lo_load) + log_coeff *= (mid_int - lo_int) / (hi_int - lo_int) + mid_load = lo_load * math.exp(log_coeff) + self._int2load.insert(mid_index, (mid_int, mid_load)) + hi_index += 1 + mid_int, mid_load = self._int2load[mid_index] + if mid_int < int_load: + lo_index, lo_int, lo_load = mid_index, mid_int, mid_load + continue + if mid_int > int_load: + hi_index, hi_int, hi_load = mid_index, mid_int, mid_load + continue + return mid_load + raise RuntimeError("Bisect in int2float failed.") + + def float2int(self, float_load: float) -> int: + """Convert and round from tps load to int. Maybe expand internal table. + + Too low or too high load result in zero or max int respectively. + + Result value is rounded down to an integer. + + :param float_load: Tps quantity to convert into int. + :type float_load: float + :returns: Converted integer value suitable for halving. + :rtype: int + """ + if float_load <= self.min_load: + return 0 + if float_load >= self.max_load: + return self.max_int_load + lo_index, hi_index = 0, len(self._int2load) + lo_int, hi_int = 0, self.max_int_load + lo_load, hi_load = self.min_load, self.max_load + while hi_int - lo_int >= 2: + mid_index = (hi_index + lo_index + 1) // 2 + if mid_index >= hi_index: + mid_int = (hi_int + lo_int) // 2 + log_coeff = math.log(hi_load) - math.log(lo_load) + log_coeff *= (mid_int - lo_int) / (hi_int - lo_int) + mid_load = lo_load * math.exp(log_coeff) + self._int2load.insert(mid_index, (mid_int, mid_load)) + hi_index += 1 + mid_int, mid_load = self._int2load[mid_index] + if mid_load < float_load: + lo_index, lo_int, lo_load = mid_index, mid_int, mid_load + continue + if mid_load > float_load: + hi_index, hi_int, hi_load = mid_index, mid_int, mid_load + continue + return mid_int + return lo_int diff --git a/resources/libraries/python/MLRsearch/load_stats.py b/resources/libraries/python/MLRsearch/load_stats.py new file mode 100644 index 0000000000..5f4757f488 --- /dev/null +++ b/resources/libraries/python/MLRsearch/load_stats.py @@ -0,0 +1,112 @@ +# Copyright (c) 2023 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 LoadStats class.""" + +from __future__ import annotations + +from dataclasses import dataclass +from typing import Dict, Tuple + +from .target_spec import TargetSpec +from .target_stat import TargetStat +from .discrete_load import DiscreteLoad +from .discrete_result import DiscreteResult + + +# The eq=False part is needed to make sure comparison is inherited properly. +@dataclass(eq=False) +class LoadStats(DiscreteLoad): + """An offered load together with stats for all possible targets. + + As LoadStats is frequently passed instead of plan DiscreteLoad, + equality and ordering is dictated by the float load. + """ + + target_to_stat: Dict[TargetSpec, TargetStat] = None + """Mapping from target specification to its current stat for this load.""" + + def __post_init__(self) -> None: + """Initialize load value and check there are targets to track.""" + super().__post_init__() + if not self.target_to_stat: + raise ValueError(f"No targets: {self.target_to_stat!r}") + + def __str__(self) -> str: + """Convert into a short human-readable string. + + This works well only for trimmed stats, + as only the stat for the first target present is shown. + + :returns: The short string. + :rtype: str + """ + return ( + f"fl={self.float_load}" + f",s=({next(iter(self.target_to_stat.values()))})" + ) + + def __hash__(self) -> int: + """Raise as stats are mutable by definition. + + :returns: Hash value for this instance if possible. + :rtype: int + :raises TypeError: Not immutable. + """ + raise TypeError("Loadstats are mutable so constant hash is impossible.") + + def add(self, result: DiscreteResult) -> None: + """Take into account one more trial measurement result. + + :param result: The result to take into account. + :type result: DiscreteResult + :raises RuntimeError: If result load does is not equal to the self load. + """ + if result.intended_load != float(self): + raise RuntimeError( + f"Attempting to add load {result.intended_load}" + f" to result set for {float(self)}" + ) + for stat in self.target_to_stat.values(): + stat.add(result) + + @staticmethod + def new_empty(load: DiscreteLoad, targets: Tuple[TargetSpec]) -> LoadStats: + """Factory method to initialize mapping for given targets. + + :param load: The intended load value for the new instance. + :param targets: The target specifications to track stats for. + :type load: DiscreteLoad + :type targets: Tuple[TargetSpec] + :returns: New instance with empty stats initialized. + :rtype: LoadStats + :raise ValueError: Is the load is not rounded. + """ + if not load.is_round: + raise ValueError(f"Not round: {load!r}") + return LoadStats( + rounding=load.rounding, + int_load=int(load), + target_to_stat={target: TargetStat(target) for target in targets}, + ) + + def estimates(self, target: TargetSpec) -> Tuple[bool, bool]: + """Classify this load according to given target. + + :param target: According to which target this should be classified. + :type target: TargetSpec + :returns: Tuple of two estimates whether load can be lower bound. + (True, False) means target is not reached yet. + :rtype: Tuple[bool, bool] + """ + return self.target_to_stat[target].estimates() diff --git a/resources/libraries/python/MLRsearch/measurement_database.py b/resources/libraries/python/MLRsearch/measurement_database.py new file mode 100644 index 0000000000..7a6618c0da --- /dev/null +++ b/resources/libraries/python/MLRsearch/measurement_database.py @@ -0,0 +1,126 @@ +# Copyright (c) 2023 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 MeasurementDatabase class.""" + +from dataclasses import dataclass +from typing import Dict, Tuple + +from .discrete_load import DiscreteLoad +from .discrete_result import DiscreteResult +from .load_stats import LoadStats +from .relevant_bounds import RelevantBounds +from .target_spec import TargetSpec +from .trimmed_stat import TrimmedStat + + +@dataclass +class MeasurementDatabase: + """Structure holding measurement results for multiple durations and loads. + + Several utility methods are added, accomplishing tasks useful for MLRsearch. + + While TargetStats can decide when a single load is a lower bound (or upper), + it does not deal with loss inversion (higher load with less load). + + This class introduces the concept of relevant bounds. + Relevant upper bound is simply the lowest load classified as an upper bound. + But relevant lower bound is only chosen from lower bound loads + strictly smaller than the relevant upper bound. + This way any higher loads with good results are ignored, + so relevant bound give conservative estimate of SUT true performance. + """ + + targets: Tuple[TargetSpec] = None + """Targets to track stats for.""" + load_to_stats: Dict[DiscreteLoad, LoadStats] = None + """Mapping from loads to stats.""" + + def __post_init__(self) -> None: + """Check and sort initial values. + + If no stats yet, initialize empty ones. + + :raises ValueError: If there are no targets. + """ + if not self.targets: + raise ValueError(f"Database needs targets: {self.targets!r}") + if not self.load_to_stats: + self.load_to_stats = {} + self._sort() + + def _sort(self) -> None: + """Sort keys from low to high load.""" + self.load_to_stats = dict(sorted(self.load_to_stats.items())) + + def __getitem__(self, key: DiscreteLoad) -> LoadStats: + """Allow access to stats as if self was load_to_stats. + + This also accepts LoadStats as key, so callers do not need + to care about hashability. + + :param key: The load to get stats for. + :type key: DiscreteLoad + :returns: Stats for the given load. + :rtype LoadStats: + """ + return self.load_to_stats[key.hashable()] + + def add(self, result: DiscreteResult) -> None: + """Incorporate given trial measurement result. + + :param result: Measurement result to add to the database. + :type result: DiscreteResult + """ + discrete_load = result.discrete_load.hashable() + if not discrete_load.is_round: + raise ValueError(f"Not round load: {discrete_load!r}") + if discrete_load not in self.load_to_stats: + self.load_to_stats[discrete_load] = LoadStats.new_empty( + load=discrete_load, + targets=self.targets, + ) + self._sort() + self.load_to_stats[discrete_load].add(result) + + def get_relevant_bounds(self, target: TargetSpec) -> RelevantBounds: + """Return None or a valid trimmed stat, for the two relevant bounds. + + A load is valid only if both optimistic and pessimistic estimates agree. + + If some value is not available, None is returned instead. + The returned stats are trimmed to the argument target. + + The implementation starts from low loads + and the search stops at lowest upper bound, + thus conforming to the conservative definition of relevant bounds. + + :param target: Target to classify loads when finding bounds. + :type target: TargetSpec + :returns: Relevant lower bound, relevant upper bound. + :rtype: RelevantBounds + """ + lower_bound, upper_bound = None, None + for load_stats in self.load_to_stats.values(): + opt, pes = load_stats.estimates(target) + if opt != pes: + continue + if not opt: + upper_bound = load_stats + break + lower_bound = load_stats + if lower_bound: + lower_bound = TrimmedStat.for_target(lower_bound, target) + if upper_bound: + upper_bound = TrimmedStat.for_target(upper_bound, target) + return RelevantBounds(clo=lower_bound, chi=upper_bound) diff --git a/resources/libraries/python/MLRsearch/multiple_loss_ratio_search.py b/resources/libraries/python/MLRsearch/multiple_loss_ratio_search.py new file mode 100644 index 0000000000..b48e2e7547 --- /dev/null +++ b/resources/libraries/python/MLRsearch/multiple_loss_ratio_search.py @@ -0,0 +1,314 @@ +# Copyright (c) 2023 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 time + +from dataclasses import dataclass +from typing import Callable, Optional, Tuple + +from .candidate import Candidate +from .config import Config +from .dataclass import secondary_field +from .discrete_load import DiscreteLoad +from .discrete_result import DiscreteResult +from .expander import GlobalWidth +from .limit_handler import LimitHandler +from .load_rounding import LoadRounding +from .measurement_database import MeasurementDatabase +from .pep3140 import Pep3140Dict +from .search_goal import SearchGoal +from .selector import Selector +from .target_scaling import TargetScaling +from .trial_measurement import AbstractMeasurer +from .trimmed_stat import TrimmedStat + + +@dataclass +class MultipleLossRatioSearch: + """Optimized binary search algorithm for finding conditional throughputs. + + Traditional binary search algorithm needs initial interval + (lower and upper bound), and returns final narrow bounds + (related to its search goal) 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 in this class contains several improvements + aimed to reduce overall search time. + + One improvement is searching for bounds for multiple search goals at once. + Specifically, the trial measurement results influence bounds for all goals, + even though the selection of trial inputs for next measurement + focuses only on one goal. The focus can switch between goals frequently. + + Next improvement is that results of trial measurements + with small trial duration can be used to find a reasonable starting interval + for full trial duration search. + This results in more trials performed, but smaller overall duration + in general. + Internally, such shorter trials come from "preceding targets", + handled in a same way as a search goal "final target". + Related improvement is that the "current" interval does not need to be valid + (e.g. one of the bounds is missing). + In that case, this algorithm will move and expand the interval, + in a process called external search. Only when both bounds are found, + the interval bisection (called internal search) starts making it narrow. + + Next improvement is bisecting in logarithmic quantities, + so that target relative width is independent of measurement units. + + Next improvement is basing the initial interval on forwarding rates + of few initial measurements, starting at max load and using forwarding rates + seen so far. + + Next improvement is to allow the use of multiple shorter trials + instead one big trial, allowing a percentage of trials + to exceed the loss ratio target. + This makes the result more stable in practice. + Conservative behavior (single long trial, zero exceed ratio) + is still available using corresponding goal definitions. + + Final improvement is exiting early if the minimal load + is not a valid lower bound (at final duration) + and also exiting if the overall search duration is too long. + + There are also subtle optimizations related to candidate selection + and uneven splitting of intervals, too numerous to list here. + """ + + config: Config + """Arguments required at construction time.""" + # End of fields required at intance creation. + measurer: AbstractMeasurer = secondary_field() + """Measurer to use, set at calling search().""" + debug: Callable[[str], None] = secondary_field() + """Object to call for logging, None means logging.debug.""" + # Fields below are computed from data above + rounding: LoadRounding = secondary_field() + """Derived from goals. Instance to use for intended load rounding.""" + from_float: Callable[[float], DiscreteLoad] = secondary_field() + """Conversion method from float [tps] intended load values.""" + limit_handler: LimitHandler = secondary_field() + """Load post-processing utility based on config and rounding.""" + scaling: TargetScaling = secondary_field() + """Utility for creating target chains for search goals.""" + database: MeasurementDatabase = secondary_field() + """Storage for (stats of) measurement results so far.""" + stop_time: float = secondary_field() + """Monotonic time value at which the search should end with failure.""" + + def search( + self, + measurer: AbstractMeasurer, + debug: Optional[Callable[[str], None]] = None, + ) -> Pep3140Dict[SearchGoal, Optional[TrimmedStat]]: + """Perform initial trials, create state object, proceed with main loop. + + Stateful arguments (measurer and debug) are stored. + Derived objects are constructed from config. + + :param measurer: Measurement provider to use by this search object. + :param debug: Callable to optionally use instead of logging.debug(). + :returns: Structure containing conditional throughputs and other stats, + one for each search goal. + :type measurer: AbstractMeasurer + :type debug: Optional[Callable[[str], None]] + :returns: Mapping from goal to lower bound (none if min load is hit). + :rtype: Pep3140Dict[SearchGoal, Optional[TrimmedStat]] + :raises RuntimeError: If total duration is larger than timeout, + or if min load becomes an upper bound for a search goal + that has fail fast true. + """ + self.measurer = measurer + self.debug = logging.debug if debug is None else debug + self.rounding = LoadRounding( + min_load=self.config.min_load, + max_load=self.config.max_load, + float_goals=[goal.relative_width for goal in self.config.goals], + ) + self.from_float = DiscreteLoad.float_conver(rounding=self.rounding) + self.limit_handler = LimitHandler( + rounding=self.rounding, + debug=self.debug, + ) + self.scaling = TargetScaling( + goals=self.config.goals, + rounding=self.rounding, + ) + self.database = MeasurementDatabase(self.scaling.targets) + self.stop_time = time.monotonic() + self.config.search_duration_max + result0, result1 = self.run_initial_trials() + self.main_loop(result0.discrete_load, result1.discrete_load) + ret_dict = Pep3140Dict() + for goal in self.config.goals: + target = self.scaling.goal_to_final_target[goal] + bounds = self.database.get_relevant_bounds(target=target) + ret_dict[goal] = bounds.clo + return ret_dict + + def measure(self, duration: float, load: DiscreteLoad) -> DiscreteResult: + """Call measurer and put the result to appropriate form in database. + + Also check the argument types and load roundness, + and return the result to the caller. + + :param duration: Intended duration for the trial measurement. + :param load: Intended load for the trial measurement: + :type duration: float + :type load: DiscreteLoad + :returns: The trial results. + :rtype: DiscreteResult + :raises RuntimeError: If an argument doed not have the required type. + """ + if not isinstance(duration, float): + raise RuntimeError(f"Duration has to be float: {duration!r}") + if not isinstance(load, DiscreteLoad): + raise RuntimeError(f"Load has to be discrete: {load!r}") + if not load.is_round: + raise RuntimeError(f"Told to measure unrounded: {load!r}") + self.debug(f"Measuring at d={duration},il={int(load)}") + result = self.measurer.measure( + intended_duration=duration, + intended_load=float(load), + ) + self.debug(f"Measured lr={result.loss_ratio}") + result = DiscreteResult.with_load(result=result, load=load) + self.database.add(result) + return result + + def run_initial_trials(self) -> Tuple[DiscreteResult, DiscreteResult]: + """Perform trials to get enough data to start the selectors. + + Measurements are done with all initial targets in mind, + based on smallest target loss ratio, largest initial trial duration, + and largest initial target width. + + Forwarding rate is used as a hint for next intended load. + The relative quantity is used, as load can use different units. + When the smallest target loss ratio is non-zero, a correction is needed + (forwarding rate is only a good hint for zero loss ratio load). + The correction is conservative (all increase in load turns to losses). + + Also, warmup trial (if configured) is performed, + all other trials are added to the database. + + This could return the initial width, but from implementation perspective + it is easier to return two measurements (or the same one twice) here + and compute width later. The "one value twice" happens when max load + has small loss, or when min load has big loss. + + :returns: Two last measured values, in any order. Or one value twice. + :rtype: Tuple[DiscreteResult, DiscreteResult] + """ + max_load = self.limit_handler.max_load + ratio, duration, width = None, None, None + for target in self.scaling.targets: + if target.preceding: + continue + if ratio is None or ratio > target.loss_ratio: + ratio = target.loss_ratio + if not duration or duration < target.trial_duration: + duration = target.trial_duration + if not width or width < target.discrete_width: + width = target.discrete_width + self.debug(f"Init ratio {ratio} duration {duration} width {width}") + if self.config.warmup_duration: + self.debug("Warmup trial.") + self.measure(self.config.warmup_duration, max_load) + # Warmup should not affect the real results, reset the database. + self.database = MeasurementDatabase(self.scaling.targets) + self.debug(f"First trial at max rate: {max_load}") + result0 = self.measure(duration, max_load) + rfr = result0.relative_forwarding_rate + corrected_rfr = (self.from_float(rfr) / (1.0 - ratio)).rounded_down() + if corrected_rfr >= max_load: + self.debug("Small loss, no other initial trials are needed.") + return result0, result0 + mrr = self.limit_handler.handle(corrected_rfr, width, None, max_load) + self.debug(f"Second trial at (corrected) mrr: {mrr}") + result1 = self.measure(duration, mrr) + # Attempt to get narrower width. + result_ratio = result1.loss_ratio + if result_ratio > ratio: + rfr2 = result1.relative_forwarding_rate + crfr2 = (self.from_float(rfr2) / (1.0 - ratio)).rounded_down() + mrr2 = self.limit_handler.handle(crfr2, width, None, mrr) + else: + mrr2 = mrr + width + mrr2 = self.limit_handler.handle(mrr2, width, mrr, max_load) + if not mrr2: + self.debug("Close enough, measuring at mrr2 is not needed.") + return result1, result1 + self.debug(f"Third trial at (corrected) mrr2: {mrr2}") + result2 = self.measure(duration, mrr2) + return result1, result2 + + def main_loop(self, load0: DiscreteLoad, load1: DiscreteLoad) -> None: + """Initialize selectors and keep measuring the winning candidate. + + Selectors are created, the two input loads are useful starting points. + + The search ends when no selector nominates any candidate, + or if the search takes too long (or if a selector raises). + + Winner is selected according to ordering defined in Candidate class. + In case of a tie, selectors for earlier goals are preferred. + + As a selector is only allowed to update current width as the winner, + the update is done here explicitly. + + :param load0: Discrete load of one of results from run_initial_trials. + :param load1: Discrete load of other of results from run_initial_trials. + :type load0: DiscreteLoad + :type load1: DiscreteLoad + :raises RuntimeError: If the search takes too long, + or if min load becomes an upper bound for any search goal + """ + if load1 < load0: + load0, load1 = load1, load0 + global_width = GlobalWidth.from_loads(load0, load1) + selectors = [] + for target in self.scaling.goal_to_final_target.values(): + selector = Selector( + final_target=target, + global_width=global_width, + initial_lower_load=load0, + initial_upper_load=load1, + database=self.database, + handler=self.limit_handler, + debug=self.debug, + ) + selectors.append(selector) + while time.monotonic() < self.stop_time: + winner = Candidate() + for selector in selectors: + # Order of arguments is important + # when two targets nominate the same candidate. + winner = min(Candidate.nomination_from(selector), winner) + if not winner: + break + # We do not check duration versus stop_time here, + # as some measurers can be unpredictably faster + # than their intended duration suggests. + self.measure(duration=winner.duration, load=winner.load) + # Delayed updates. + if winner.width: + global_width.width = winner.width + winner.won() + else: + raise RuntimeError("Optimized search takes too long.") + self.debug("Search done.") diff --git a/resources/libraries/python/MLRsearch/pep3140/__init__.py b/resources/libraries/python/MLRsearch/pep3140/__init__.py new file mode 100644 index 0000000000..f8e2ffaa8f --- /dev/null +++ b/resources/libraries/python/MLRsearch/pep3140/__init__.py @@ -0,0 +1,24 @@ +# Copyright (c) 2023 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. + +""" +__init__ file for Python package "pep3140". +""" + +# TODO: Move submodules to separate modules. +# Not obvious how to do that from PyPI point of view +# without affecting the current CSIT global "resources" package root. +# Probably it can be done by specifying multiple directories +# in PYTHONPATH used throughout CSIT. + +from .classes import Pep3140Dict diff --git a/resources/libraries/python/MLRsearch/pep3140/classes.py b/resources/libraries/python/MLRsearch/pep3140/classes.py new file mode 100644 index 0000000000..9ab6e25c7c --- /dev/null +++ b/resources/libraries/python/MLRsearch/pep3140/classes.py @@ -0,0 +1,34 @@ +# Copyright (c) 2023 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 a subclass of dict with an alternative str method.""" + + +class Pep3140Dict(dict): + """A dict with str support as proposed in PEP 3140. + + Python implemented str acting on dict such that the resulting string + shows both keys and values in their repr form. + Therefore, str() of a dict gives the same result as repr(). + + This class shows both keys and values their str form instead. + """ + + def __str__(self) -> str: + """Return comma+space separated str of items in curly brackets. + + :returns: PEP 3140 string form of the dict data. + :rtype: str + """ + body = ", ".join(f"{key}: {value}" for key, value in self.items()) + return f"{{{body}}}" diff --git a/resources/libraries/python/MLRsearch/relevant_bounds.py b/resources/libraries/python/MLRsearch/relevant_bounds.py new file mode 100644 index 0000000000..4bc6796f71 --- /dev/null +++ b/resources/libraries/python/MLRsearch/relevant_bounds.py @@ -0,0 +1,56 @@ +# Copyright (c) 2023 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 RelevantBounds class.""" + +from __future__ import annotations + +from dataclasses import dataclass +from typing import Optional + +from .trimmed_stat import TrimmedStat + + +@dataclass +class RelevantBounds: + """Container for the pair of relevant bounds for a target. + + If there is no valid bound, None is used. + + Relevant upper bound is smallest load acting as an upper bound. + Relevant lower bound acts as a lower bound, has to be strictly smaller + than the relevant upper bound, and is largest among such loads. + + The short names "clo" and "chi" are also commonly used + in logging and technical comments. + + Trimming could be done here, but it needs to known the target explicitly, + so it is done in MeasurementDatabase instead. + """ + + clo: Optional[TrimmedStat] + """The relevant lower bound (trimmed) for the current target.""" + chi: Optional[TrimmedStat] + """The relevant upper bound (trimmed) for the current target.""" + + # TODO: Check types in post init? + + def __str__(self) -> str: + """Convert into a short human-readable string. + + :returns: The short string. + :rtype: str + """ + clo = int(self.clo) if self.clo else None + chi = int(self.chi) if self.chi else None + return f"clo={clo},chi={chi}" diff --git a/resources/libraries/python/MLRsearch/search_goal.py b/resources/libraries/python/MLRsearch/search_goal.py new file mode 100644 index 0000000000..7d7fd69841 --- /dev/null +++ b/resources/libraries/python/MLRsearch/search_goal.py @@ -0,0 +1,117 @@ +# Copyright (c) 2023 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 SearchGoal class.""" + +from dataclasses import dataclass + + +@dataclass(frozen=True, eq=True) +class SearchGoal: + """This is the part of controller inputs that can be repeated + with different values. MLRsearch saves time by searching + for conditional throughput for each goal at the same time, + compared to repeated calls with separate goals. + + Most fields (called attributes) of this composite + are relevant to the definition of conditional throughput. + The rest does not, but can affect the overal search time. + """ + + loss_ratio: float = 0.0 + """The goal loss ratio. + A trial can satisfy the goal only when its trial loss ratio is not higher + than this. See MeasurementResult.loss_ratio for details. + A trial that does not satisfy this goal is called a bad trial.""" + exceed_ratio: float = 0.5 + """What portion of the duration sum can consist of bad trial seconds + while still being classified as lower bound (assuming no short trials).""" + relative_width: float = 0.005 + """Target is achieved when the relevant lower bound + is no more than this (in units of the tightest upper bound) far + from the relevant upper bound.""" + initial_trial_duration: float = 1.0 + """Shortest trial duration employed when searching for this goal.""" + final_trial_duration: float = 1.0 + """Longest trial duration employed when searching for this goal.""" + duration_sum: float = 20.0 + """Minimal sum of durations of relevant trials sufficient to declare a load + to be upper or lower bound for this goal.""" + preceding_targets: int = 2 + """Number of increasingly coarser search targets to insert, + hoping to speed up searching for the final target of this goal.""" + expansion_coefficient: int = 2 + """External search multiplies width (in logarithmic space) by this.""" + fail_fast: bool = True + """If true and min load is not an upper bound, raise. + If false, search will return None instead of lower bound.""" + + def __post_init__(self) -> None: + """Convert fields to correct types and call validate.""" + super().__setattr__("loss_ratio", float(self.loss_ratio)) + super().__setattr__("exceed_ratio", float(self.exceed_ratio)) + super().__setattr__("relative_width", float(self.relative_width)) + super().__setattr__( + "final_trial_duration", float(self.final_trial_duration) + ) + super().__setattr__( + "initial_trial_duration", float(self.initial_trial_duration) + ) + super().__setattr__("duration_sum", float(self.duration_sum)) + super().__setattr__("preceding_targets", int(self.preceding_targets)) + super().__setattr__( + "expansion_coefficient", int(self.expansion_coefficient) + ) + super().__setattr__("fail_fast", bool(self.fail_fast)) + self.validate() + + def validate(self) -> None: + """Make sure the initialized values conform to requirements. + + :raises ValueError: If a field value is outside allowed bounds. + """ + if self.loss_ratio < 0.0: + raise ValueError(f"Loss ratio cannot be negative: {self}") + if self.loss_ratio >= 1.0: + raise ValueError(f"Loss ratio must be lower than 1: {self}") + if self.exceed_ratio < 0.0: + raise ValueError(f"Exceed ratio cannot be negative: {self}") + if self.exceed_ratio >= 1.0: + raise ValueError(f"Exceed ratio must be lower than 1: {self}") + if self.relative_width <= 0.0: + raise ValueError(f"Relative width must be positive: {self}") + if self.relative_width >= 1.0: + raise ValueError(f"Relative width must be less than 1: {self}") + if self.initial_trial_duration <= 0.0: + raise ValueError(f"Initial trial duration must be positive: {self}") + if self.final_trial_duration < self.initial_trial_duration: + raise ValueError( + f"Single duration max must be at least initial: {self}" + ) + if self.duration_sum < self.final_trial_duration: + raise ValueError( + "Min duration sum cannot be smaller" + f" than final trial duration: {self}" + ) + if self.expansion_coefficient <= 1: + raise ValueError(f"Expansion coefficient is too small: {self}") + too_small = False + if self.preceding_targets < 0: + too_small = True + elif self.preceding_targets < 1: + if self.initial_trial_duration < self.duration_sum: + too_small = True + if too_small: + raise ValueError( + f"Number of preceding targets is too small: {self}" + ) diff --git a/resources/libraries/python/MLRsearch/search_goal_tuple.py b/resources/libraries/python/MLRsearch/search_goal_tuple.py new file mode 100644 index 0000000000..d40ba99b4b --- /dev/null +++ b/resources/libraries/python/MLRsearch/search_goal_tuple.py @@ -0,0 +1,60 @@ +# Copyright (c) 2023 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 SearchGoalTuple class.""" + +from collections.abc import Iterator +from dataclasses import dataclass +from typing import Tuple + +from .search_goal import SearchGoal + + +@dataclass(frozen=True) +class SearchGoalTuple: + """Container class holding multiple search goals. + + Just a convenience for checking their number and types. + """ + + goals: Tuple[SearchGoal, ...] + """Goals extracted from user-provided Iterable of search goals.""" + + def __post_init__(self) -> None: + """Check type and number of search goals. + + :raises ValueError: If there are no goals. + :raises TypeError: If a goal is not a SearchGoal. + """ + super().__setattr__("goals", tuple(self.goals)) + if not self.goals: + raise ValueError(f"Cannot be empty: {self.goals}") + for goal in self.goals: + if not isinstance(goal, SearchGoal): + raise TypeError(f"Must be a SearchGoal instance: {goal}") + copied = list(self.goals) + deduplicated = set(self.goals) + for goal in copied: + if goal not in deduplicated: + raise ValueError(f"Duplicate goal: {goal}") + deduplicated.remove(goal) + if deduplicated: + raise ValueError(f"Error processing goals: {deduplicated}") + + def __iter__(self) -> Iterator[SearchGoal]: + """Enable itertion over goals. + + :returns: Iterator iteratinc over contained goals. + :rtype: Iterator[SearchGoal] + """ + return iter(self.goals) diff --git a/resources/libraries/python/MLRsearch/selector.py b/resources/libraries/python/MLRsearch/selector.py new file mode 100644 index 0000000000..4a6d2e2574 --- /dev/null +++ b/resources/libraries/python/MLRsearch/selector.py @@ -0,0 +1,183 @@ +# Copyright (c) 2023 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 Selector class.""" + + +from dataclasses import dataclass, field +from typing import Callable, List, Optional, Tuple + +from .dataclass import secondary_field +from .discrete_load import DiscreteLoad +from .discrete_width import DiscreteWidth +from .expander import TargetedExpander +from .global_width import GlobalWidth +from .limit_handler import LimitHandler +from .measurement_database import MeasurementDatabase +from .relevant_bounds import RelevantBounds +from .target_spec import TargetSpec +from .strategy import StrategyBase, STRATEGY_CLASSES + + +@dataclass +class Selector: + """A selector is an abstraction that focuses on only one of search goals. + + While lower-level logic is hidden in strategy classes, + the code in this class is responsible for initializing strategies + and shifting targets towards the final target. + + While the public methods have the same names and meaning as the ones + in strategy classes, their signature is different. + Selector adds the current target trial duration to the output of nominate(), + and adds the current bounds to the input of won(). + + The nominate method does not return a complete Candidate instance, + as we need to avoid circular dependencies + (candidate will refer to selector). + """ + + final_target: TargetSpec + """The target this selector is trying to ultimately achieve.""" + global_width: GlobalWidth + """Reference to the global width tracking instance.""" + initial_lower_load: DiscreteLoad + """Smaller of the two loads distinguished at instance creation. + During operation, this field is reused to store preceding target bound.""" + initial_upper_load: DiscreteLoad + """Larger of the two loads distinguished at instance creation. + During operation, this field is reused to store preceding target bound.""" + database: MeasurementDatabase = field(repr=False) + """Reference to the common database used by all selectors.""" + handler: LimitHandler = field(repr=False) + """Reference to the class used to avoid too narrow intervals.""" + debug: Callable[[str], None] = field(repr=False) + """Injectable function for debug logging.""" + # Primary above, derived below. + current_target: TargetSpec = secondary_field() + """The target the selector is focusing on currently.""" + target_stack: List[TargetSpec] = secondary_field() + """Stack of targets. When current target is achieved, next is popped.""" + strategies: Tuple[StrategyBase] = secondary_field() + """Instances implementing particular selection strategies.""" + current_strategy: Optional[StrategyBase] = secondary_field() + """Reference to strategy used for last nomination, needed for won().""" + # Cache. + bounds: RelevantBounds = secondary_field() + """New relevant bounds for this round of candidate selection.""" + + def __post_init__(self) -> None: + """Initialize derived values.""" + self.target_stack = [self.final_target] + while preceding_target := self.target_stack[-1].preceding: + self.target_stack.append(preceding_target) + self.current_target = self.target_stack.pop() + self._recreate_strategies() + + def _recreate_strategies(self) -> None: + """Recreate strategies after current target has changed. + + Width expander is recreated as target width is now smaller. + For convenience, strategies get injectable debug + which prints also the current target. + """ + expander = TargetedExpander( + target=self.current_target, + global_width=self.global_width, + initial_lower_load=self.initial_lower_load, + initial_upper_load=self.initial_upper_load, + handler=self.handler, + debug=self.debug, + ) + + def wrapped_debug(text: str) -> None: + """Call self debug with current target info prepended. + + :param text: Message to log at debug level. + :type text: str + """ + self.debug(f"Target {self.current_target}: {text}") + + self.strategies = tuple( + cls( + target=self.current_target, + expander=expander, + initial_lower_load=self.initial_lower_load, + initial_upper_load=self.initial_upper_load, + handler=self.handler, + debug=wrapped_debug, + ) + for cls in STRATEGY_CLASSES + ) + self.current_strategy = None + self.debug(f"Created strategies for: {self.current_target}") + + def _update_bounds(self) -> None: + """Before each iteration, call this to update bounds cache.""" + self.bounds = self.database.get_relevant_bounds(self.current_target) + + def nominate( + self, + ) -> Tuple[Optional[DiscreteLoad], float, Optional[DiscreteWidth]]: + """Find first strategy that wants to nominate, return trial inputs. + + Returned load is None if no strategy wants to nominate. + + Current target is shifted when (now preceding) target is reached. + As each strategy never becomes done before at least one + bound relevant to the current target becomes available, + it is never needed to revert to the preceding target after the shift. + + As the initial trials had inputs relevant to all initial targets, + the only way for this not to nominate a load + is when the final target is reached (including hitting min or max load). + The case of hitting min load raises, so search fails early. + + :returns: Nominated load, duration, and global width to set if winning. + :rtype: Tuple[Optional[DiscreteLoad], float, Optional[DiscreteWidth]] + :raises RuntimeError: If internal inconsistency is detected, + or if min load becomes an upper bound. + """ + self._update_bounds() + self.current_strategy = None + while 1: + for strategy in self.strategies: + load, width = strategy.nominate(self.bounds) + if load: + self.current_strategy = strategy + return load, self.current_target.trial_duration, width + if not self.bounds.clo and not self.bounds.chi: + raise RuntimeError("Internal error: no clo nor chi.") + if not self.target_stack: + if not self.bounds.clo and self.current_target.fail_fast: + raise RuntimeError(f"No lower bound: {self.bounds.chi!r}") + self.debug(f"Goal {self.current_target} reached: {self.bounds}") + return None, self.current_target.trial_duration, None + # Everything is ready for next target in the chain. + self.current_target = self.target_stack.pop() + # Debug logs look better if we forget bounds are TrimmedStat. + # Abuse rounding (if not None) to convert to pure DiscreteLoad. + clo, chi = self.bounds.clo, self.bounds.chi + self.initial_lower_load = clo.rounded_down() if clo else clo + self.initial_upper_load = chi.rounded_down() if chi else chi + self._update_bounds() + self._recreate_strategies() + + def won(self, load: DiscreteLoad) -> None: + """Update any private info when candidate became a winner. + + :param load: The load previously nominated by current strategy. + :type load: DiscreteLoad + """ + self._update_bounds() + self.current_strategy.won(bounds=self.bounds, load=load) diff --git a/resources/libraries/python/MLRsearch/strategy/__init__.py b/resources/libraries/python/MLRsearch/strategy/__init__.py new file mode 100644 index 0000000000..a1e0225a17 --- /dev/null +++ b/resources/libraries/python/MLRsearch/strategy/__init__.py @@ -0,0 +1,35 @@ +# Copyright (c) 2023 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. + +""" +__init__ file for Python package "strategy". +""" + +from .base import StrategyBase +from .bisect import BisectStrategy +from .extend_hi import ExtendHiStrategy +from .extend_lo import ExtendLoStrategy +from .halve import HalveStrategy +from .refine_hi import RefineHiStrategy +from .refine_lo import RefineLoStrategy + + +STRATEGY_CLASSES = ( + HalveStrategy, + RefineLoStrategy, + RefineHiStrategy, + ExtendLoStrategy, + ExtendHiStrategy, + BisectStrategy, +) +"""Tuple of strategy constructors, in order of priority decreasing.""" diff --git a/resources/libraries/python/MLRsearch/strategy/base.py b/resources/libraries/python/MLRsearch/strategy/base.py new file mode 100644 index 0000000000..0724f882bf --- /dev/null +++ b/resources/libraries/python/MLRsearch/strategy/base.py @@ -0,0 +1,132 @@ +# Copyright (c) 2023 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 StrategyBase class.""" + + +from abc import ABC, abstractmethod +from dataclasses import dataclass, field +from typing import Callable, Optional, Tuple + +from ..discrete_interval import DiscreteInterval +from ..discrete_load import DiscreteLoad +from ..discrete_width import DiscreteWidth +from ..expander import TargetedExpander +from ..limit_handler import LimitHandler +from ..relevant_bounds import RelevantBounds +from ..target_spec import TargetSpec + + +@dataclass +class StrategyBase(ABC): + """Abstract class encompassing data common to most strategies. + + A strategy is one piece of logic a selector may use + when nominating a candidate according to its current target. + + The two initial bound arguments may not be bounds at all. + For initial targets, the two values are usually mrr and mrr2. + For subsequent targets, the initial values are usually + the relevant bounds of the preceding target, + but one of them may be None if hitting min or max load. + + The initial values are mainly used as stable alternatives + to relevant bounds of preceding target, + because those bounds may have been unpredictably altered + by nominations from unrelated search goals. + This greatly simplifies reasoning about strategies making progress. + """ + + target: TargetSpec + """The target this strategy is focusing on.""" + expander: TargetedExpander + """Instance to track width expansion during search (if applicable).""" + initial_lower_load: Optional[DiscreteLoad] + """Smaller of the two loads distinguished at instance creation. + Can be None if upper bound is the min load.""" + initial_upper_load: Optional[DiscreteLoad] + """Larger of the two loads distinguished at instance creation. + Can be None if lower bound is the max load.""" + handler: LimitHandler = field(repr=False) + """Reference to the limit handler instance.""" + debug: Callable[[str], None] = field(repr=False) + """Injectable function for debug logging.""" + + @abstractmethod + def nominate( + self, bounds: RelevantBounds + ) -> Tuple[Optional[DiscreteLoad], Optional[DiscreteWidth]]: + """Nominate a load candidate if the conditions activate this strategy. + + A complete candidate refers also to the nominating selector. + To prevent circular dependence (selector refers to nominating strategy), + this function returns only duration and width. + + Width should only be non-None if global current width should be updated + when the candidate based on this becomes winner. + But currently all strategies return non-None width + if they return non-None load. + + :param bounds: Freshly updated bounds relevant for current target. + :type bounds: RelevantBounds + :returns: Two nones or candidate intended load and duration. + :rtype: Tuple[Optional[DiscreteLoad], Optional[DiscreteWidth]] + """ + return None, None + + def won(self, bounds: RelevantBounds, load: DiscreteLoad) -> None: + """Notify the strategy its candidate became the winner. + + Most strategies have no use for this information, + but some strategies may need to update their private information. + + :param bounds: Freshly updated bounds relevant for current target. + :param load: The current load, so strategy does not need to remember. + :type bounds: RelevantBounds + :type load: DiscreteLoad + """ + return + + def not_worth(self, bounds: RelevantBounds, load: DiscreteLoad) -> bool: + """A check on bounds common for multiple strategies. + + The load is worth measuring only if it can create or improve + either relevant bound. + + Each strategy is designed to create a relevant bound for current target, + which is only needed if that (or better) bound does not exist yet. + Conversely, if a strategy does not nominate, it is because + the load it would nominate (if any) is found not worth by this method. + + :param bounds: Current relevant bounds. + :param load: Load of a possible candidate. + :type bounds: RelevantBounds + :type load: DiscreteLoad + :returns: True if the load should NOT be nominated. + :rtype: bool + """ + if bounds.clo and bounds.clo >= load: + return True + if bounds.chi and bounds.chi <= load: + return True + if bounds.clo and bounds.chi: + # We are not hitting min nor max load. + # Measuring at this load will create or improve clo or chi. + # The only reason not to nominate is if interval is narrow already. + wig = DiscreteInterval( + lower_bound=bounds.clo, + upper_bound=bounds.chi, + ).width_in_goals(self.target.discrete_width) + if wig <= 1.0: + return True + return False diff --git a/resources/libraries/python/MLRsearch/strategy/bisect.py b/resources/libraries/python/MLRsearch/strategy/bisect.py new file mode 100644 index 0000000000..894544695e --- /dev/null +++ b/resources/libraries/python/MLRsearch/strategy/bisect.py @@ -0,0 +1,193 @@ +# Copyright (c) 2023 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 BisectStrategy class.""" + + +from dataclasses import dataclass +from typing import Optional, Tuple + +from ..discrete_interval import DiscreteInterval +from ..discrete_load import DiscreteLoad +from ..discrete_width import DiscreteWidth +from ..relevant_bounds import RelevantBounds +from .base import StrategyBase + + +@dataclass +class BisectStrategy(StrategyBase): + """Strategy to use when both bounds relevant to curent target are present. + + Primarily, this strategy is there to perform internal search. + As powers of two are fiendly to binary search, + this strategy relies on the splitting logic described in DiscreteInterval. + + The main reason why this class is so long is that a mere existence + of a valid bound for the current target does not imply + that bound is a good approximation of the final conditional throughput. + The bound might become valid due to efforts of a strategy + focusing on an entirely different search goal. + + On the other hand, initial bounds may be better approximations, + but they also may be bad approximations (for example + when SUT behavior strongly depends on trial duration). + + Based on comparison of existing current bounds to intial bounds, + this strategy also mimics what would external search do + (if the one current bound was missing and other initial bound was current). + In case that load value is closer to appropriate inital bound + (compared to how far the simple bisect between current bounds is), + that load is nominated. + + It turns out those "conditional" external search nominations + are quite different from unconditional ones, + at least when it comes to handling limits + and tracking when width expansion should be applied. + That is why that logic is here + and not in some generic external search class. + """ + + expand_on_clo: bool = False + """If extending up, width should be expanded when load becomes clo.""" + expand_on_chi: bool = False + """If extending down, width should be expanded when load becomes chi.""" + + def nominate( + self, bounds: RelevantBounds + ) -> Tuple[Optional[DiscreteLoad], Optional[DiscreteWidth]]: + """Nominate a load candidate between bounds or extending from them. + + The external search logic is offloaded into private methods. + If they return a truthy load, that is returned from here as well. + + Only if the actual bisect is selected, + the per-selector expander is limited to the (smaller) new width. + + :param bounds: Freshly updated bounds relevant for current target. + :type bounds: RelevantBounds + :returns: Two nones or candidate intended load and duration. + :rtype: Tuple[Optional[DiscreteLoad], Optional[DiscreteWidth]] + """ + if not bounds.clo or bounds.clo >= self.handler.max_load: + return None, None + if not bounds.chi or bounds.chi <= self.handler.min_load: + return None, None + interval = DiscreteInterval(bounds.clo, bounds.chi) + if interval.width_in_goals(self.target.discrete_width) <= 1.0: + return None, None + bisect_load = interval.middle(self.target.discrete_width) + load, width = self._extend_lo(bounds, bisect_load) + if load: + self.expand_on_clo, self.expand_on_chi = False, True + self.debug(f"Preferring to extend down: {load}") + return load, width + load, width = self._extend_hi(bounds, bisect_load) + if load: + self.expand_on_clo, self.expand_on_chi = True, False + self.debug(f"Preferring to extend up: {load}") + return load, width + load = bisect_load + if self.not_worth(bounds=bounds, load=load): + return None, None + self.expand_on_clo, self.expand_on_chi = False, False + self.debug(f"Preferring to bisect: {load}") + width_lo = DiscreteInterval(bounds.clo, load).discrete_width + width_hi = DiscreteInterval(load, bounds.chi).discrete_width + width = min(width_lo, width_hi) + self.expander.limit(width) + return load, width + + def _extend_lo( + self, bounds: RelevantBounds, bisect_load: DiscreteLoad + ) -> Tuple[Optional[DiscreteLoad], Optional[DiscreteWidth]]: + """Compute load as if extending down, return it if preferred. + + :param bounds: Freshly updated bounds relevant for current target. + :param bisect_load: Load when bisection is preferred. + :type bounds: RelevantBounds + :type bisect_load: DiscreteLoad + :returns: Two nones or candidate intended load and duration. + :rtype: Tuple[Optional[DiscreteLoad], Optional[DiscreteWidth]] + :raises RuntimeError: If an internal inconsistency is detected. + """ + # TODO: Simplify all the conditions or explain them better. + if not self.initial_upper_load: + return None, None + if bisect_load >= self.initial_upper_load: + return None, None + width = self.expander.get_width() + load = bounds.chi - width + load = self.handler.handle( + load=load, + width=self.target.discrete_width, + clo=bounds.clo, + chi=bounds.chi, + ) + if not load: + return None, None + if load <= bisect_load: + return None, None + if load >= self.initial_upper_load: + return None, None + if self.not_worth(bounds=bounds, load=load): + raise RuntimeError(f"Load not worth: {load}") + return load, width + + def _extend_hi( + self, bounds: RelevantBounds, bisect_load: DiscreteLoad + ) -> Tuple[Optional[DiscreteLoad], Optional[DiscreteWidth]]: + """Compute load as if extending up, return it if preferred. + + :param bounds: Freshly updated bounds relevant for current target. + :param bisect_load: Load when bisection is preferred. + :type bounds: RelevantBounds + :type bisect_load: DiscreteLoad + :returns: Two nones or candidate intended load and duration. + :rtype: Tuple[Optional[DiscreteLoad], Optional[DiscreteWidth]] + :raises RuntimeError: If an internal inconsistency is detected. + """ + # TODO: Simplify all the conditions or explain them better. + if not self.initial_lower_load: + return None, None + if bisect_load <= self.initial_lower_load: + return None, None + width = self.expander.get_width() + load = bounds.clo + width + load = self.handler.handle( + load=load, + width=self.target.discrete_width, + clo=bounds.clo, + chi=bounds.chi, + ) + if not load: + return None, None + if load >= bisect_load: + return None, None + if load <= self.initial_lower_load: + return None, None + if self.not_worth(bounds=bounds, load=load): + raise RuntimeError(f"Load not worth: {load}") + return load, width + + def won(self, bounds: RelevantBounds, load: DiscreteLoad) -> None: + """Expand width when appropriate. + + :param bounds: Freshly updated bounds relevant for current target. + :param load: The current load, so strategy does not need to remember. + :type bounds: RelevantBounds + :type load: DiscreteLoad + """ + if self.expand_on_clo and load == bounds.clo: + self.expander.expand() + elif self.expand_on_chi and load == bounds.chi: + self.expander.expand() diff --git a/resources/libraries/python/MLRsearch/strategy/extend_hi.py b/resources/libraries/python/MLRsearch/strategy/extend_hi.py new file mode 100644 index 0000000000..79c4ad7cf2 --- /dev/null +++ b/resources/libraries/python/MLRsearch/strategy/extend_hi.py @@ -0,0 +1,76 @@ +# Copyright (c) 2023 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 ExtendHiStrategy class.""" + + +from dataclasses import dataclass +from typing import Optional, Tuple + +from ..discrete_load import DiscreteLoad +from ..discrete_width import DiscreteWidth +from ..relevant_bounds import RelevantBounds +from .base import StrategyBase + + +@dataclass +class ExtendHiStrategy(StrategyBase): + """This strategy is applied when there is no relevant upper bound. + + Typically this is needed after RefineHiStrategy turned initial upper bound + into a current relevant lower bound. + """ + + def nominate( + self, bounds: RelevantBounds + ) -> Tuple[Optional[DiscreteLoad], Optional[DiscreteWidth]]: + """Nominate current relevant lower bound plus expander width. + + This performs external search in upwards direction, + until a valid upper bound for the current target is found, + or until max load is hit. + Limit handling is used to avoid nominating too close + (or above) the max rate. + + Width expansion is only applied if the candidate becomes a lower bound, + so that is detected in done method. + + :param bounds: Freshly updated bounds relevant for current target. + :type bounds: RelevantBounds + :returns: Two nones or candidate intended load and duration. + :rtype: Tuple[Optional[DiscreteLoad], Optional[DiscreteWidth]] + """ + if bounds.chi or not bounds.clo or bounds.clo >= self.handler.max_load: + return None, None + width = self.expander.get_width() + load = self.handler.handle( + load=bounds.clo + width, + width=self.target.discrete_width, + clo=bounds.clo, + chi=bounds.chi, + ) + if self.not_worth(bounds=bounds, load=load): + return None, None + self.debug(f"No chi, extending up: {load}") + return load, width + + def won(self, bounds: RelevantBounds, load: DiscreteLoad) -> None: + """Expand width if the load became the new lower bound. + + :param bounds: Freshly updated bounds relevant for current target. + :param load: The current load, so strategy does not need to remember. + :type bounds: RelevantBounds + :type load: DiscreteLoad + """ + if load == bounds.clo: + self.expander.expand() diff --git a/resources/libraries/python/MLRsearch/strategy/extend_lo.py b/resources/libraries/python/MLRsearch/strategy/extend_lo.py new file mode 100644 index 0000000000..68d20b6a6a --- /dev/null +++ b/resources/libraries/python/MLRsearch/strategy/extend_lo.py @@ -0,0 +1,76 @@ +# Copyright (c) 2023 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 ExtendLoStrategy class.""" + + +from dataclasses import dataclass +from typing import Optional, Tuple + +from ..discrete_load import DiscreteLoad +from ..discrete_width import DiscreteWidth +from ..relevant_bounds import RelevantBounds +from .base import StrategyBase + + +@dataclass +class ExtendLoStrategy(StrategyBase): + """This strategy is applied when there is no relevant lower bound. + + Typically this is needed after RefineLoStrategy turned initial lower bound + into a current relevant upper bound. + """ + + def nominate( + self, bounds: RelevantBounds + ) -> Tuple[Optional[DiscreteLoad], Optional[DiscreteWidth]]: + """Nominate current relevant upper bound minus expander width. + + This performs external search in downwards direction, + until a valid lower bound for the current target is found, + or until min load is hit. + Limit handling is used to avoid nominating too close + (or below) the min rate. + + Width expansion is only applied if the candidate becomes an upper bound, + so that is detected in done method. + + :param bounds: Freshly updated bounds relevant for current target. + :type bounds: RelevantBounds + :returns: Two nones or candidate intended load and duration. + :rtype: Tuple[Optional[DiscreteLoad], Optional[DiscreteWidth]] + """ + if bounds.clo or not bounds.chi or bounds.chi <= self.handler.min_load: + return None, None + width = self.expander.get_width() + load = self.handler.handle( + load=bounds.chi - width, + width=self.target.discrete_width, + clo=bounds.clo, + chi=bounds.chi, + ) + if self.not_worth(bounds=bounds, load=load): + return None, None + self.debug(f"No clo, extending down: {load}") + return load, width + + def won(self, bounds: RelevantBounds, load: DiscreteLoad) -> None: + """Expand width if the load became new upper bound. + + :param bounds: Freshly updated bounds relevant for current target. + :param load: The current load, so strategy does not need to remember. + :type bounds: RelevantBounds + :type load: DiscreteLoad + """ + if load == bounds.chi: + self.expander.expand() diff --git a/resources/libraries/python/MLRsearch/strategy/halve.py b/resources/libraries/python/MLRsearch/strategy/halve.py new file mode 100644 index 0000000000..3188a041c6 --- /dev/null +++ b/resources/libraries/python/MLRsearch/strategy/halve.py @@ -0,0 +1,83 @@ +# Copyright (c) 2023 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 HalveStrategy class.""" + + +from dataclasses import dataclass +from typing import Optional, Tuple + +from ..discrete_interval import DiscreteInterval +from ..discrete_load import DiscreteLoad +from ..discrete_width import DiscreteWidth +from ..relevant_bounds import RelevantBounds +from .base import StrategyBase + + +@dataclass +class HalveStrategy(StrategyBase): + """First strategy to apply for a new current target. + + Pick a load between initial lower bound and initial upper bound, + nominate it if it is (still) worth it. + + In a sense, this can be viewed as an extension of preceding target's + bisect strategy. But as the current target may require a different + trial duration, it is better to do it for the new target. + + Alternatively, this is a way to save one application + of subsequent refine strategy, thus avoiding reducing risk of triggering + an external search (slight time saver for highly unstable SUTs). + Either way, minor time save is achieved by preceding target + only needing to reach double of current target width. + + If the distance between initial bounds is already at or below + current target width, the middle point is not nominated. + The reasoning is that in this case external search is likely + to get triggered by the subsequent refine strategies, + so attaining a relevant bound here is not as likely to help. + """ + + def nominate( + self, bounds: RelevantBounds + ) -> Tuple[Optional[DiscreteLoad], Optional[DiscreteWidth]]: + """Nominate the middle between initial lower and upper bound. + + The returned width is the target width, even if initial bounds + happened to be closer together. + + :param bounds: Freshly updated bounds relevant for current target. + :type bounds: RelevantBounds + :returns: Two nones or candidate intended load and duration. + :rtype: Tuple[Optional[DiscreteLoad], Optional[DiscreteWidth]] + """ + if not self.initial_lower_load or not self.initial_upper_load: + return None, None + interval = DiscreteInterval( + lower_bound=self.initial_lower_load, + upper_bound=self.initial_upper_load, + ) + wig = interval.width_in_goals(self.target.discrete_width) + if wig > 2.0: + # Can happen for initial target. + return None, None + if wig <= 1.0: + # Already was narrow enough, refinements shall be sufficient. + return None, None + load = interval.middle(self.target.discrete_width) + if self.not_worth(bounds, load): + return None, None + self.debug(f"Halving available: {load}") + # TODO: Report possibly smaller width? + self.expander.limit(self.target.discrete_width) + return load, self.target.discrete_width diff --git a/resources/libraries/python/MLRsearch/strategy/refine_hi.py b/resources/libraries/python/MLRsearch/strategy/refine_hi.py new file mode 100644 index 0000000000..caa8fc4a7d --- /dev/null +++ b/resources/libraries/python/MLRsearch/strategy/refine_hi.py @@ -0,0 +1,55 @@ +# Copyright (c) 2023 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 RefineHiStrategy class.""" + + +from dataclasses import dataclass +from typing import Optional, Tuple + +from ..discrete_load import DiscreteLoad +from ..discrete_width import DiscreteWidth +from ..relevant_bounds import RelevantBounds +from .base import StrategyBase + + +@dataclass +class RefineHiStrategy(StrategyBase): + """If initial upper bound is still worth it, nominate it. + + This usually happens when halving resulted in relevant lower bound, + or if there was no halving (and RefineLoStrategy confirmed initial + lower bound became a relevant lower bound for the new current target). + + This either ensures a matching upper bound (target is achieved) + or moves the relevant lower bound higher (triggering external search). + """ + + def nominate( + self, bounds: RelevantBounds + ) -> Tuple[Optional[DiscreteLoad], Optional[DiscreteWidth]]: + """Nominate the initial upper bound. + + :param bounds: Freshly updated bounds relevant for current target. + :type bounds: RelevantBounds + :returns: Two nones or candidate intended load and duration. + :rtype: Tuple[Optional[DiscreteLoad], Optional[DiscreteWidth]] + """ + if not (load := self.initial_upper_load): + return None, None + if self.not_worth(bounds=bounds, load=load): + return None, None + self.debug(f"Upperbound refinement available: {load}") + # TODO: Limit to possibly smaller than target width? + self.expander.limit(self.target.discrete_width) + return load, self.target.discrete_width diff --git a/resources/libraries/python/MLRsearch/strategy/refine_lo.py b/resources/libraries/python/MLRsearch/strategy/refine_lo.py new file mode 100644 index 0000000000..7927798505 --- /dev/null +++ b/resources/libraries/python/MLRsearch/strategy/refine_lo.py @@ -0,0 +1,53 @@ +# Copyright (c) 2023 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 RefineLoStrategy class.""" + + +from dataclasses import dataclass +from typing import Optional, Tuple + +from ..discrete_load import DiscreteLoad +from ..discrete_width import DiscreteWidth +from ..relevant_bounds import RelevantBounds +from .base import StrategyBase + + +@dataclass +class RefineLoStrategy(StrategyBase): + """If initial lower bound is still worth it, nominate it. + + This usually happens when halving resulted in relevant upper bound, + or if there was no halving. + This ensures a relevant bound (upper or lower) for the current target + exists. + """ + + def nominate( + self, bounds: RelevantBounds + ) -> Tuple[Optional[DiscreteLoad], Optional[DiscreteWidth]]: + """Nominate the initial lower bound. + + :param bounds: Freshly updated bounds relevant for current target. + :type bounds: RelevantBounds + :returns: Two nones or candidate intended load and duration. + :rtype: Tuple[Optional[DiscreteLoad], Optional[DiscreteWidth]] + """ + if not (load := self.initial_lower_load): + return None, None + if self.not_worth(bounds=bounds, load=load): + return None, None + self.debug(f"Lowerbound refinement available: {load}") + # TODO: Limit to possibly smaller than target width? + self.expander.limit(self.target.discrete_width) + return load, self.target.discrete_width diff --git a/resources/libraries/python/MLRsearch/target_scaling.py b/resources/libraries/python/MLRsearch/target_scaling.py new file mode 100644 index 0000000000..25114c311c --- /dev/null +++ b/resources/libraries/python/MLRsearch/target_scaling.py @@ -0,0 +1,103 @@ +# Copyright (c) 2023 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 TargetScaling class.""" + +from dataclasses import dataclass +from typing import Dict, Tuple + +from .dataclass import secondary_field +from .discrete_width import DiscreteWidth +from .load_rounding import LoadRounding +from .search_goal import SearchGoal +from .search_goal_tuple import SearchGoalTuple +from .target_spec import TargetSpec + + +@dataclass +class TargetScaling: + """Encapsulate targets derived from goals. + + No default values for primaries, contructor call has to specify everything. + """ + + goals: SearchGoalTuple + """Set of goals to generate targets for.""" + rounding: LoadRounding + """Rounding instance to use (targets have discrete width).""" + # Derived quantities. + targets: Tuple[TargetSpec] = secondary_field() + """The generated targets, linked into chains.""" + goal_to_final_target: Dict[SearchGoal, TargetSpec] = secondary_field() + """Mapping from a goal to its corresponding final target.""" + + def __post_init__(self) -> None: + """For each goal create final, and non-final targets and link them.""" + linked_targets = [] + self.goal_to_final_target = {} + for goal in self.goals: + standalone_targets = [] + # Final target. + width = DiscreteWidth( + rounding=self.rounding, + float_width=goal.relative_width, + ).rounded_down() + duration_sum = goal.duration_sum + target = TargetSpec( + loss_ratio=goal.loss_ratio, + exceed_ratio=goal.exceed_ratio, + discrete_width=width, + trial_duration=goal.final_trial_duration, + duration_sum=duration_sum, + expansion_coefficient=goal.expansion_coefficient, + fail_fast=goal.fail_fast, + preceding=None, + ) + standalone_targets.append(target) + # Non-final targets. + preceding_targets = goal.preceding_targets + multiplier = ( + pow( + goal.initial_trial_duration / duration_sum, + 1.0 / preceding_targets, + ) + if preceding_targets + else 1.0 + ) + for count in range(preceding_targets): + preceding_sum = duration_sum * pow(multiplier, count + 1) + if count + 1 >= preceding_targets: + preceding_sum = goal.initial_trial_duration + trial_duration = min(goal.final_trial_duration, preceding_sum) + width *= 2 + target = TargetSpec( + loss_ratio=goal.loss_ratio, + exceed_ratio=goal.exceed_ratio, + discrete_width=width, + trial_duration=trial_duration, + duration_sum=preceding_sum, + expansion_coefficient=goal.expansion_coefficient, + fail_fast=False, + preceding=None, + ) + standalone_targets.append(target) + # Link preceding targets. + preceding_target = None + for target in reversed(standalone_targets): + linked_target = target.with_preceding(preceding_target) + linked_targets.append(linked_target) + preceding_target = linked_target + # Associate final target to the goal. + self.goal_to_final_target[goal] = linked_targets[-1] + # Store all targets as a tuple. + self.targets = tuple(linked_targets) diff --git a/resources/libraries/python/MLRsearch/target_spec.py b/resources/libraries/python/MLRsearch/target_spec.py new file mode 100644 index 0000000000..5279ba00a1 --- /dev/null +++ b/resources/libraries/python/MLRsearch/target_spec.py @@ -0,0 +1,95 @@ +# Copyright (c) 2023 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 TargetSpec class.""" + +from __future__ import annotations + +from dataclasses import dataclass, field +from typing import Optional + +from .discrete_width import DiscreteWidth + + +@dataclass(frozen=True, eq=True) +class TargetSpec: + """Composite object holding attributes specifying one search target. + + Abstractly, this has several similar meanings. + With discrete_width attribute this specifies when a selector is Done. + With expansion_coefficient attribute it tells selector how quickly + should it expand interval in external search. + With "preceding" attribute it helps selector, so it does not need to point + to preceding target separately from its current target. + Without those three attributes this object is still sufficient + for LoadStats to classify loads as lower bound, upper bound, or unknown. + """ + + loss_ratio: float + """Target loss ratio. Equal and directly analogous to goal loss ratio, + but applicable also for non-final targets.""" + exceed_ratio: float + """Target exceed ratio. Equal and directly analogous to goal exceed ratio, + but applicable also for non-final targets.""" + discrete_width: DiscreteWidth + """Target relative width. Analogous to goal relative width, + but coarser for non-final targets.""" + trial_duration: float + """Duration to use for trials for this target. Shorter trials have lesser + (and more complicated) impact when determining upper and lower bounds.""" + duration_sum: float + """Sum of trial durations sufficient to classify a load + as an upper or lower bound. + For non-final targets, this is shorter than goal duration_sum.""" + expansion_coefficient: int = field(repr=False) + """Equal and directly analogous to goal expansion coefficient, + but applicable also for non-final targets.""" + fail_fast: bool = field(repr=False) + """Copied from goal. If true and min load is not an upper bound, raise.""" + preceding: Optional[TargetSpec] = field(repr=False) + """Reference to next coarser target (if any) belonging to the same goal.""" + + # No conversions or validations, as this is an internal structure. + + def __str__(self) -> str: + """Convert into a short human-readable string. + + :returns: The short string. + :rtype: str + """ + return ( + f"lr={self.loss_ratio},er={self.exceed_ratio}" + f",ds={self.duration_sum}" + ) + + def with_preceding(self, preceding: Optional[TargetSpec]) -> TargetSpec: + """Create an equivalent instance but with different preceding field. + + This is useful in initialization. Create semi-initialized targets + starting from final one, than add references in reversed order. + + :param preceding: New value for preceding field, cannot be None. + :type preceding: Optional[TargetSpec] + :returns: Instance with the new value applied. + :rtype: TargetSpec + """ + return TargetSpec( + loss_ratio=self.loss_ratio, + exceed_ratio=self.exceed_ratio, + discrete_width=self.discrete_width, + trial_duration=self.trial_duration, + duration_sum=self.duration_sum, + expansion_coefficient=self.expansion_coefficient, + fail_fast=self.fail_fast, + preceding=preceding, + ) diff --git a/resources/libraries/python/MLRsearch/target_stat.py b/resources/libraries/python/MLRsearch/target_stat.py new file mode 100644 index 0000000000..9d30d51b9c --- /dev/null +++ b/resources/libraries/python/MLRsearch/target_stat.py @@ -0,0 +1,117 @@ +# Copyright (c) 2023 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 LoadStat class.""" + +from dataclasses import dataclass, field +from typing import Tuple + +from .target_spec import TargetSpec +from .discrete_result import DiscreteResult + + +@dataclass +class TargetStat: + """Class for aggregating trial results for a single load and target. + + Reference to the target is included for convenience. + + The main usage is for load classification, done in estimates method. + If both estimates agree, the load is classified as either a lower bound + or an upper bound. For additional logic for dealing with loss inversion + see MeasurementDatabase. + + Besides the duration sums needed for determining upper and lower bound, + a field useful for computing the conditional throughput is also included. + The conditional throughput is average of the (relative) forwarding rates + of good long trials weighted by gool long trial durations. + As the intended load is stored elsewhere, the one additional field here + has a peculiar unit, it is a sum of products of seconds and loss ratios. + """ + + target: TargetSpec = field(repr=False) + """The target for which this instance is aggregating results.""" + good_long: float = 0.0 + """Sum of durations of long enough trials satisfying target loss ratio.""" + bad_long: float = 0.0 + """Sum of durations of long trials not satisfying target loss ratio.""" + good_short: float = 0.0 + """Sum of durations of shorter trials satisfying target loss ratio.""" + bad_short: float = 0.0 + """Sum of durations of shorter trials not satisfying target loss ratio.""" + dur_rat_sum: float = 0.0 + """Sum over good long trials, of duration multiplied by loss ratio.""" + + def __str__(self) -> str: + """Convert into a short human-readable string. + + :returns: The short string. + :rtype: str + """ + return ( + f"gl={self.good_long},bl={self.bad_long}" + f",gs={self.good_short},bs={self.bad_short}" + ) + + def add(self, result: DiscreteResult) -> None: + """Take into account one more trial result. + + Use intended duration for deciding between long and short trials, + but use offered duation (with overheads) to increase the duration sums. + + :param result: The trial result to add to the stats. + :type result: DiscreteResult + """ + dwo = result.duration_with_overheads + if result.intended_duration >= self.target.trial_duration: + if result.loss_ratio > self.target.loss_ratio: + self.bad_long += dwo + else: + self.good_long += dwo + self.dur_rat_sum += dwo * result.loss_ratio + else: + if result.loss_ratio > self.target.loss_ratio: + self.bad_short += dwo + else: + self.good_short += dwo + + def estimates(self) -> Tuple[bool, bool]: + """Return whether this load can become a lower bound. + + This returns two estimates, hence the weird nonverb name of this method. + One estimate assumes all following results will satisfy the loss ratio, + the other assumes all results will not satisfy the loss ratio. + The sum of durations of the assumed results + is the minimum to reach target duration sum, or zero if already reached. + + If both estimates are the same, it means the load is a definite bound. + This may happen even when the sum of durations of already + measured trials is less than the target, when the missing measurements + cannot change the classification. + + :returns: Tuple of two estimates whether the load can be a lower bound. + (True, False) means more trial results are needed. + :rtype: Tuple[bool, bool] + """ + coeff = self.target.exceed_ratio + decrease = self.good_short * coeff / (1.0 - coeff) + short_excess = self.bad_short - decrease + effective_excess = self.bad_long + max(0.0, short_excess) + effective_dursum = max( + self.good_long + effective_excess, + self.target.duration_sum, + ) + limit_dursum = effective_dursum * self.target.exceed_ratio + optimistic = effective_excess <= limit_dursum + pessimistic = (effective_dursum - self.good_long) <= limit_dursum + return optimistic, pessimistic diff --git a/resources/libraries/python/MLRsearch/trial_measurement/__init__.py b/resources/libraries/python/MLRsearch/trial_measurement/__init__.py new file mode 100644 index 0000000000..034ae41819 --- /dev/null +++ b/resources/libraries/python/MLRsearch/trial_measurement/__init__.py @@ -0,0 +1,19 @@ +# Copyright (c) 2023 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. + +""" +__init__ file for Python package "trial_measurement". +""" + +from .abstract_measurer import AbstractMeasurer +from .measurement_result import MeasurementResult diff --git a/resources/libraries/python/MLRsearch/trial_measurement/abstract_measurer.py b/resources/libraries/python/MLRsearch/trial_measurement/abstract_measurer.py new file mode 100644 index 0000000000..6fab79c8dc --- /dev/null +++ b/resources/libraries/python/MLRsearch/trial_measurement/abstract_measurer.py @@ -0,0 +1,55 @@ +# Copyright (c) 2023 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 + +from .measurement_result import MeasurementResult as Result + + +class AbstractMeasurer(metaclass=ABCMeta): + """Abstract class defining common API for trial measurement providers. + + The original use of this class was in the realm of + RFC 2544 Throughput search, which explains the teminology + related to networks, frames, packets, offered load, forwarding rate + and similar. + + But the same logic can be used in higher level networking scenarios + (e.g. https requests) or even outside networking (database transactions). + + The current code uses language from packet forwarding, + docstring sometimes mention transactions as an alternative view. + """ + + @abstractmethod + def measure(self, intended_duration: float, intended_load: float) -> Result: + """Perform trial measurement and return the result. + + It is assumed the measurer got already configured with anything else + needed to perform the measurement (e.g. traffic profile + or transaction limit). + + Duration and load are the only values expected to vary + during the search. + + :param intended_duration: Intended trial duration [s]. + :param intended_load: Intended rate of transactions (packets) [tps]. + It is a per-port rate, e.g. uni-directional for SUTs + with two ports. + :type intended_duration: float + :type intended_load: float + :returns: Structure detailing the result of the measurement. + :rtype: measurement_result.MeasurementResult + """ diff --git a/resources/libraries/python/MLRsearch/trial_measurement/measurement_result.py b/resources/libraries/python/MLRsearch/trial_measurement/measurement_result.py new file mode 100644 index 0000000000..9dc1ccf5f1 --- /dev/null +++ b/resources/libraries/python/MLRsearch/trial_measurement/measurement_result.py @@ -0,0 +1,161 @@ +# Copyright (c) 2023 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 MeasurementResult class.""" + +from dataclasses import dataclass + + +@dataclass +class MeasurementResult: + """Structure defining the result of a single trial measurement. + + There are few primary (required) quantities. Various secondary (derived) + quantities are calculated and can be queried. + + The constructor allows broader argument types, + the post init function converts to the stricter types. + + Integer quantities (counts) are preferred, as float values + can suffer from rounding errors, and sometimes they are measured + at unknown (possibly very limited) precision and accuracy. + + There are relations between the counts (e.g. offered count + should be equal to a sum of forwarding count and loss count). + This implementation does not perform consistency checks, but uses them + for computing quantities the caller left unspecified. + + In some cases, the units of intended load are different from units + of loss count (e.g. load in transactions but loss in packets). + Quantities with relative_ prefix can be used to get load candidates + from forwarding results. + + Sometimes, the measurement provider is unable to reach the intended load, + and it can react by spending longer than intended duration + to reach its intended count. To signal irregular situations like this, + several optional fields can be given, and various secondary quantities + are populated, so the measurement consumer can query the quantity + it wants to rely on in these irregular situations. + + The current implementation intentionally limits the secondary quantities + to the few that proved useful in practice. + """ + + # Required primary quantities. + intended_duration: float + """Intended trial measurement duration [s].""" + intended_load: float + """Intended load [tps]. If bidirectional (or multi-port) traffic is used, + most users will put unidirectional (single-port) value here, + as bandwidth and pps limits are usually per-port.""" + # Two of the next three primary quantities are required. + offered_count: int = None + """Number of packets actually transmitted (transactions attempted). + This should be the aggregate (bidirectional, multi-port) value, + so that asymmetric trafic profiles are supported.""" + loss_count: int = None + """Number of packets transmitted but not received (transactions failed).""" + forwarding_count: int = None + """Number of packets successfully forwarded (transactions succeeded).""" + # Optional primary quantities. + offered_duration: float = None + """Estimate of the time [s] the trial was actually transmitting traffic.""" + duration_with_overheads: float = None + """Estimate of the time [s] it took to get the trial result + since the measurement started.""" + intended_count: int = None + """Expected number of packets to transmit. If not known, + the value of offered_count is used.""" + + def __post_init__(self) -> None: + """Convert types, compute missing values. + + Current caveats: + A failing assumption looks like a conversion error. + Negative counts are allowed, which can lead to errors later. + """ + self.intended_duration = float(self.intended_duration) + if self.offered_duration is None: + self.offered_duration = self.intended_duration + else: + self.offered_duration = float(self.offered_duration) + if self.duration_with_overheads is None: + self.duration_with_overheads = self.offered_duration + else: + self.duration_with_overheads = float(self.duration_with_overheads) + self.intended_load = float(self.intended_load) + if self.forwarding_count is None: + self.forwarding_count = int(self.offered_count) - int( + self.loss_count + ) + else: + self.forwarding_count = int(self.forwarding_count) + if self.offered_count is None: + self.offered_count = self.forwarding_count + int(self.loss_count) + else: + self.offered_count = int(self.offered_count) + if self.loss_count is None: + self.loss_count = self.offered_count - self.forwarding_count + else: + self.loss_count = int(self.loss_count) + if self.intended_count is None: + self.intended_count = self.offered_count + else: + self.intended_count = int(self.intended_count) + # TODO: Handle (somehow) situations where offered > intended? + + @property + def unsent_count(self) -> int: + """How many packets were not transmitted (transactions not started). + + :return: Intended count minus offered count. + :rtype: int + """ + return self.intended_count - self.offered_count + + @property + def loss_ratio(self) -> float: + """Bad count divided by overall count, zero if the latter is zero. + + The bad count includes not only loss count, but also unsent count. + If unsent count is negative, its absolute value is used. + The overall count is intended count or offered count, + whichever is bigger. + + Together, the resulting formula tends to increase loss ratio + (but not above 100%) in irregular situations, + thus guiding search algorithms towards lower loads + where there should be less irregularities. + The zero default is there to prevent search algorithms from + getting stuck on a too low intended load. + + :returns: Bad count divided by overall count. + :rtype: float + """ + overall = max(self.offered_count, self.intended_count) + bad = abs(self.loss_count) + abs(self.unsent_count) + return bad / overall if overall else 0.0 + + @property + def relative_forwarding_rate(self) -> float: + """Forwarding rate in load units as if duration and load was intended. + + The result is based purely on intended load and loss ratio. + While the resulting value may be far from what really happened, + it has nice behavior with respect to common assumptions + of search algorithms. + + :returns: Forwarding rate in load units estimated from loss ratio. + :rtype: float + """ + return self.intended_load * (1.0 - self.loss_ratio) diff --git a/resources/libraries/python/MLRsearch/trimmed_stat.py b/resources/libraries/python/MLRsearch/trimmed_stat.py new file mode 100644 index 0000000000..0076644aa3 --- /dev/null +++ b/resources/libraries/python/MLRsearch/trimmed_stat.py @@ -0,0 +1,78 @@ +# Copyright (c) 2023 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 TrimmedStat class.""" + +from __future__ import annotations + +from dataclasses import dataclass +from typing import Optional + +from .discrete_load import DiscreteLoad +from .load_stats import LoadStats +from .target_spec import TargetSpec + + +@dataclass +class TrimmedStat(LoadStats): + """Load stats trimmed to a single target. + + Useful mainly for reporting the overall results. + """ + + def __post_init__(self) -> None: + """Initialize load value and check there is one target to track.""" + super().__post_init__() + if len(self.target_to_stat) != 1: + raise ValueError(f"No single target: {self.target_to_stat!r}") + + @staticmethod + def for_target(stats: LoadStats, target: TargetSpec) -> TrimmedStat: + """Return new instance with only one target in the mapping. + + :param stats: The load stats instance to trim. + :param target: The one target which should remain in the mapping. + :type stats: LoadStats + :type target: TargetSpec + :return: Newly created instance. + :rtype: TrimmedStat + """ + return TrimmedStat( + rounding=stats.rounding, + int_load=stats.int_load, + target_to_stat={target: stats.target_to_stat[target]}, + ) + + @property + def conditional_throughput(self) -> Optional[DiscreteLoad]: + """Compute conditional throughput from the load. + + Target stat has dur_rat_sum and good_long. + The code here adds intended load and handles the case min load is hit. + If min load is not a lower bound, None is returned. + + :return: Conditional throughput assuming self is a relevant lower bound. + :rtype: Optional[DiscreteLoad] + :raises RuntimeError: If target is unclear or load is spurious. + """ + target = list(self.target_to_stat.keys())[0] + _, pes = self.estimates(target) + if not pes: + if int(self): + raise RuntimeError(f"Not a lower bound: {self}") + return None + # TODO: Verify self is really the clo? + stat = self.target_to_stat[target] + loss_ratio = stat.dur_rat_sum / stat.good_long + ret = self * (1.0 - loss_ratio) + return ret |