Revert "CSIT-986: Use MLRsearch from pip"

This reverts commit 0c2c57d9965ab1db0d5404ad103871ac250339cb.

Reason for revert: unless you will fix this broken patch we have to revert this as it breaks several thing in the csit core ci/cd.

1) all tb are pypi offline this means no new pypi is automatically dowloaded. Everytime you change your version you have to update every tb. As this is not automated this will never work and put extreme overhead

2) this code is not pylint checked and not verified by any existing job breaking any kind of verificition mechanics in csit

3)there is no automation in terms of creating pypi (no job) this creates chicken egg problem that you cannot verify change unless new version is installed

Next time please think or consult with more seniored csit core developer
Unless above will be fixed i will revert on monday as now it breaks all jobs. I will set hard verification to framework setup (exception) so this will prevent next time merge.
Possible solution:
1)Move the directory back to resources and reference from csit directly not via pypi, leave the setup crap in dir and let users to create package on their own

Change-Id: Id530a9f19f668e45f73ffc9e7371bb453b59fd1b
Signed-off-by: Peter Mikus <pmikus@cisco.com>

8 files changed, 809 insertions, 3 deletions

diff --git a/resources/libraries/python/TrafficGenerator.py b/resources/libraries/python/TrafficGenerator.py
index b27260e8cd..ee65c1bf2a 100644
--- a/resources/libraries/python/TrafficGenerator.py
+++ b/resources/libraries/python/TrafficGenerator.py
@@ -22,9 +22,9 @@ from .ssh import SSH
 from .topology import NodeType
 from .topology import NodeSubTypeTG
 from .topology import Topology
-from MLRsearch.AbstractMeasurer import AbstractMeasurer
-from MLRsearch.MultipleLossRatioSearch import MultipleLossRatioSearch
-from MLRsearch.ReceiveRateMeasurement import ReceiveRateMeasurement
+from .search.AbstractMeasurer import AbstractMeasurer
+from .search.MultipleLossRatioSearch import MultipleLossRatioSearch
+from .search.ReceiveRateMeasurement import ReceiveRateMeasurement
 
 __all__ = ['TGDropRateSearchImpl', 'TrafficGenerator', 'OptimizedSearch']
 
diff --git a/resources/libraries/python/search/AbstractMeasurer.py b/resources/libraries/python/search/AbstractMeasurer.py
new file mode 100644
index 0000000000..b972c4eb18
--- /dev/null
+++ b/resources/libraries/python/search/AbstractMeasurer.py
@@ -0,0 +1,35 @@
+# Copyright (c) 2018 Cisco and/or its affiliates.
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at:
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+"""Module defining AbstractMeasurer class."""
+
+from abc import ABCMeta, abstractmethod
+
+
+class AbstractMeasurer(object):
+    """Abstract class defining common API for measurement providers."""
+
+    __metaclass__ = ABCMeta
+
+    @abstractmethod
+    def measure(self, duration, transmit_rate):
+        """Perform trial measurement and return the result.
+
+        :param duration: Trial duration [s].
+        :param transmit_rate: Target transmit rate [pps].
+        :type duration: float
+        :type transmit_rate: float
+        :returns: Structure containing the result of the measurement.
+        :rtype: ReceiveRateMeasurement
+        """
+        pass
diff --git a/resources/libraries/python/search/AbstractSearchAlgorithm.py b/resources/libraries/python/search/AbstractSearchAlgorithm.py
new file mode 100644
index 0000000000..538322a42c
--- /dev/null
+++ b/resources/libraries/python/search/AbstractSearchAlgorithm.py
@@ -0,0 +1,51 @@
+# Copyright (c) 2018 Cisco and/or its affiliates.
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at:
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+"""Module defining AbstractSearchAlgorithm class."""
+
+from abc import ABCMeta, abstractmethod
+
+
+class AbstractSearchAlgorithm(object):
+    """Abstract class defining common API for search algorithms."""
+
+    __metaclass__ = ABCMeta
+
+    def __init__(self, measurer):
+        """Store the rate provider.
+
+        :param measurer: Object able to perform trial or composite measurements.
+        :type measurer: AbstractMeasurer
+        """
+        # TODO: Type check for AbstractMeasurer?
+        self.measurer = measurer
+
+    @abstractmethod
+    def narrow_down_ndr_and_pdr(
+            self, fail_rate, line_rate, packet_loss_ratio):
+        """Perform measurements to narrow down intervals, return them.
+
+        This will be renamed when custom loss ratio lists are supported.
+
+        :param fail_rate: Minimal target transmit rate [pps].
+        :param line_rate: Maximal target transmit rate [pps].
+        :param packet_loss_ratio: Fraction of packets lost, for PDR [1].
+        :type fail_rate: float
+        :type line_rate: float
+        :type packet_loss_ratio: float
+        :returns: Structure containing narrowed down intervals
+            and their measurements.
+        :rtype: NdrPdrResult
+        """
+        # TODO: Do we agree on arguments related to precision or trial duration?
+        pass
diff --git a/resources/libraries/python/search/MultipleLossRatioSearch.py b/resources/libraries/python/search/MultipleLossRatioSearch.py
new file mode 100644
index 0000000000..0eb1d7da4c
--- /dev/null
+++ b/resources/libraries/python/search/MultipleLossRatioSearch.py
@@ -0,0 +1,501 @@
+# Copyright (c) 2018 Cisco and/or its affiliates.
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at:
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+"""Module defining MultipleLossRatioSearch class."""
+
+import logging
+import math
+import time
+
+from AbstractSearchAlgorithm import AbstractSearchAlgorithm
+from NdrPdrResult import NdrPdrResult
+from ReceiveRateInterval import ReceiveRateInterval
+
+
+class MultipleLossRatioSearch(AbstractSearchAlgorithm):
+    """Optimized binary search algorithm for finding NDR and PDR bounds.
+
+    Traditional binary search algorithm needs initial interval
+    (lower and upper bound), and returns final interval after bisecting
+    (until some exit condition is met).
+    The exit condition is usually related to the interval width,
+    (upper bound value minus lower bound value).
+
+    The optimized algorithm contains several improvements
+    aimed to reduce overall search time.
+
+    One improvement is searching for two intervals at once.
+    The intervals are for NDR (No Drop Rate) and PDR (Partial Drop Rate).
+
+    Next improvement is that the initial interval does not need to be valid.
+    Imagine initial interval (10, 11) where 11 is smaller
+    than the searched value.
+    The algorithm will try (11, 13) interval next, and if 13 is still smaller,
+    (13, 17) and so on, doubling width until the upper bound is valid.
+    The part when interval expands is called external search,
+    the part when interval is bisected is called internal search.
+
+    Next improvement is that trial measurements at small trial duration
+    can be used to find a reasonable interval for full trial duration search.
+    This results in more trials performed, but smaller overall duration
+    in general.
+
+    Next improvement is bisecting in logarithmic quantities,
+    so that exit criteria can be independent of measurement units.
+
+    Next improvement is basing the initial interval on receive rates.
+
+    Final improvement is exiting early if the minimal value
+    is not a valid lower bound.
+
+    The complete search consist of several phases,
+    each phase performing several trial measurements.
+    Initial phase creates initial interval based on receive rates
+    at maximum rate and at maximum receive rate (MRR).
+    Final phase and preceding intermediate phases are performing
+    external and internal search steps,
+    each resulting interval is the starting point for the next phase.
+    The resulting interval of final phase is the result of the whole algorithm.
+
+    Each non-initial phase uses its own trial duration and width goal.
+    Any non-initial phase stops searching (for NDR or PDR independently)
+    when minimum is not a valid lower bound (at current duration),
+    or all of the following is true:
+    Both bounds are valid, bound bounds are measured at the current phase
+    trial duration, interval width is less than the width goal
+    for current phase.
+
+    TODO: Review and update this docstring according to rst docs.
+    TODO: Support configurable number of Packet Loss Ratios.
+    """
+
+    class ProgressState(object):
+        """Structure containing data to be passed around in recursion."""
+
+        def __init__(
+                self, result, phases, duration, width_goal, packet_loss_ratio,
+                minimum_transmit_rate, maximum_transmit_rate):
+            """Convert and store the argument values.
+
+            :param result: Current measured NDR and PDR intervals.
+            :param phases: How many intermediate phases to perform
+                before the current one.
+            :param duration: Trial duration to use in the current phase [s].
+            :param width_goal: The goal relative width for the curreent phase.
+            :param packet_loss_ratio: PDR fraction for the current search.
+            :param minimum_transmit_rate: Minimum target transmit rate
+                for the current search [pps].
+            :param maximum_transmit_rate: Maximum target transmit rate
+                for the current search [pps].
+            :type result: NdrPdrResult
+            :type phases: int
+            :type duration: float
+            :type width_goal: float
+            :type packet_loss_ratio: float
+            :type minimum_transmit_rate: float
+            :type maximum_transmit_rate: float
+            """
+            self.result = result
+            self.phases = int(phases)
+            self.duration = float(duration)
+            self.width_goal = float(width_goal)
+            self.packet_loss_ratio = float(packet_loss_ratio)
+            self.minimum_transmit_rate = float(minimum_transmit_rate)
+            self.maximum_transmit_rate = float(maximum_transmit_rate)
+
+    def __init__(self, measurer, final_relative_width=0.005,
+                 final_trial_duration=30.0, initial_trial_duration=1.0,
+                 number_of_intermediate_phases=2, timeout=600.0):
+        """Store the measurer object and additional arguments.
+
+        :param measurer: Rate provider to use by this search object.
+        :param final_relative_width: Final lower bound transmit rate
+            cannot be more distant that this multiple of upper bound [1].
+        :param final_trial_duration: Trial duration for the final phase [s].
+        :param initial_trial_duration: Trial duration for the initial phase
+            and also for the first intermediate phase [s].
+        :param number_of_intermediate_phases: Number of intermediate phases
+            to perform before the final phase [1].
+        :param timeout: The search will fail itself when not finished
+            before this overall time [s].
+        :type measurer: AbstractMeasurer
+        :type final_relative_width: float
+        :type final_trial_duration: float
+        :type initial_trial_duration: int
+        :type number_of_intermediate_phases: int
+        :type timeout: float
+        """
+        super(MultipleLossRatioSearch, self).__init__(measurer)
+        self.final_trial_duration = float(final_trial_duration)
+        self.final_relative_width = float(final_relative_width)
+        self.number_of_intermediate_phases = int(number_of_intermediate_phases)
+        self.initial_trial_duration = float(initial_trial_duration)
+        self.timeout = float(timeout)
+
+
+    @staticmethod
+    def double_relative_width(relative_width):
+        """Return relative width corresponding to double logarithmic width.
+
+        :param relative_width: The base relative width to double.
+        :type relative_width: float
+        :returns: The relative width of double logarithmic size.
+        :rtype: float
+        """
+        return 1.999 * relative_width - relative_width * relative_width
+        # The number should be 2.0, but we want to avoid rounding errors,
+        # and ensure half of double is not larger than the original value.
+
+    @staticmethod
+    def double_step_down(relative_width, current_bound):
+        """Return rate of double logarithmic width below.
+
+        :param relative_width: The base relative width to double.
+        :param current_bound: The current target transmit rate to move [pps].
+        :type relative_width: float
+        :type current_bound: float
+        :returns: Transmit rate smaller by logarithmically double width [pps].
+        :rtype: float
+        """
+        return current_bound * (
+            1.0 - MultipleLossRatioSearch.double_relative_width(
+                relative_width))
+
+    @staticmethod
+    def double_step_up(relative_width, current_bound):
+        """Return rate of double logarithmic width above.
+
+        :param relative_width: The base relative width to double.
+        :param current_bound: The current target transmit rate to move [pps].
+        :type relative_width: float
+        :type current_bound: float
+        :returns: Transmit rate larger by logarithmically double width [pps].
+        :rtype: float
+        """
+        return current_bound / (
+            1.0 - MultipleLossRatioSearch.double_relative_width(
+                relative_width))
+
+    @staticmethod
+    def half_relative_width(relative_width):
+        """Return relative width corresponding to half logarithmic width.
+
+        :param relative_width: The base relative width to halve.
+        :type relative_width: float
+        :returns: The relative width of half logarithmic size.
+        :rtype: float
+        """
+        return 1.0 - math.sqrt(1.0 - relative_width)
+
+    @staticmethod
+    def half_step_up(relative_width, current_bound):
+        """Return rate of half logarithmic width above.
+
+        :param relative_width: The base relative width to halve.
+        :param current_bound: The current target transmit rate to move [pps].
+        :type relative_width: float
+        :type current_bound: float
+        :returns: Transmit rate larger by logarithmically half width [pps].
+        :rtype: float
+        """
+        return current_bound / (
+            1.0 - MultipleLossRatioSearch.half_relative_width(relative_width))
+
+    def narrow_down_ndr_and_pdr(
+            self, minimum_transmit_rate, maximum_transmit_rate,
+            packet_loss_ratio):
+        """Perform initial phase, create state object, proceed with next phases.
+
+        :param minimum_transmit_rate: Minimal target transmit rate [pps].
+        :param maximum_transmit_rate: Maximal target transmit rate [pps].
+        :param packet_loss_ratio: Fraction of packets lost, for PDR [1].
+        :type minimum_transmit_rate: float
+        :type maximum_transmit_rate: float
+        :type packet_loss_ratio: float
+        :returns: Structure containing narrowed down intervals
+            and their measurements.
+        :rtype: NdrPdrResult
+        :raises RuntimeError: If total duration is larger than timeout.
+        """
+        minimum_transmit_rate = float(minimum_transmit_rate)
+        maximum_transmit_rate = float(maximum_transmit_rate)
+        packet_loss_ratio = float(packet_loss_ratio)
+        line_measurement = self.measurer.measure(
+            self.initial_trial_duration, maximum_transmit_rate)
+        initial_width_goal = self.final_relative_width
+        for _ in range(self.number_of_intermediate_phases):
+            initial_width_goal = self.double_relative_width(initial_width_goal)
+        max_lo = maximum_transmit_rate * (1.0 - initial_width_goal)
+        mrr = max(
+            minimum_transmit_rate,
+            min(max_lo, line_measurement.receive_rate))
+        mrr_measurement = self.measurer.measure(
+            self.initial_trial_duration, mrr)
+        # Attempt to get narrower width.
+        if mrr_measurement.loss_fraction > 0.0:
+            max2_lo = mrr * (1.0 - initial_width_goal)
+            mrr2 = min(max2_lo, mrr_measurement.receive_rate)
+        else:
+            mrr2 = mrr / (1.0 - initial_width_goal)
+        if mrr2 > minimum_transmit_rate and mrr2 < maximum_transmit_rate:
+            line_measurement = mrr_measurement
+            mrr_measurement = self.measurer.measure(
+                self.initial_trial_duration, mrr2)
+            if mrr2 > mrr:
+                buf = line_measurement
+                line_measurement = mrr_measurement
+                mrr_measurement = buf
+        starting_interval = ReceiveRateInterval(
+            mrr_measurement, line_measurement)
+        starting_result = NdrPdrResult(starting_interval, starting_interval)
+        state = self.ProgressState(
+            starting_result, self.number_of_intermediate_phases,
+            self.final_trial_duration, self.final_relative_width,
+            packet_loss_ratio, minimum_transmit_rate, maximum_transmit_rate)
+        state = self.ndrpdr(state)
+        return state.result
+
+    def _measure_and_update_state(self, state, transmit_rate):
+        """Perform trial measurement, update bounds, return new state.
+
+        :param state: State before this measurement.
+        :param transmit_rate: Target transmit rate for this measurement [pps].
+        :type state: ProgressState
+        :type transmit_rate: float
+        :returns: State after the measurement.
+        :rtype: ProgressState
+        """
+        # TODO: Implement https://stackoverflow.com/a/24683360
+        # to avoid the string manipulation if log verbosity is too low.
+        logging.info("result before update: %s", state.result)
+        logging.debug(
+            "relative widths in goals: %s", state.result.width_in_goals(
+                self.final_relative_width))
+        measurement = self.measurer.measure(state.duration, transmit_rate)
+        ndr_interval = self._new_interval(
+            state.result.ndr_interval, measurement, 0.0)
+        pdr_interval = self._new_interval(
+            state.result.pdr_interval, measurement, state.packet_loss_ratio)
+        state.result = NdrPdrResult(ndr_interval, pdr_interval)
+        return state
+
+    @staticmethod
+    def _new_interval(old_interval, measurement, packet_loss_ratio):
+        """Return new interval with bounds updated according to the measurement.
+
+        :param old_interval: The current interval before the measurement.
+        :param measurement: The new meaqsurement to take into account.
+        :param packet_loss_ratio: Fraction for PDR (or zero for NDR).
+        :type old_interval: ReceiveRateInterval
+        :type measurement: ReceiveRateMeasurement
+        :type packet_loss_ratio: float
+        :returns: The updated interval.
+        :rtype: ReceiveRateInterval
+        """
+        old_lo, old_hi = old_interval.measured_low, old_interval.measured_high
+        # Priority zero: direct replace if the target Tr is the same.
+        if measurement.target_tr in (old_lo.target_tr, old_hi.target_tr):
+            if measurement.target_tr == old_lo.target_tr:
+                return ReceiveRateInterval(measurement, old_hi)
+            else:
+                return ReceiveRateInterval(old_lo, measurement)
+        # Priority one: invalid lower bound allows only one type of update.
+        if old_lo.loss_fraction > packet_loss_ratio:
+            # We can only expand down, old bound becomes valid upper one.
+            if measurement.target_tr < old_lo.target_tr:
+                return ReceiveRateInterval(measurement, old_lo)
+            else:
+                return old_interval
+        # Lower bound is now valid.
+        # Next priorities depend on target Tr.
+        if measurement.target_tr < old_lo.target_tr:
+            # Lower external measurement, relevant only
+            # if the new measurement has high loss rate.
+            if measurement.loss_fraction > packet_loss_ratio:
+                # Returning the broader interval as old_lo
+                # would be invalid upper bound.
+                return ReceiveRateInterval(measurement, old_hi)
+        elif measurement.target_tr > old_hi.target_tr:
+            # Upper external measurement, only relevant for invalid upper bound.
+            if old_hi.loss_fraction <= packet_loss_ratio:
+                # Old upper bound becomes valid new lower bound.
+                return ReceiveRateInterval(old_hi, measurement)
+        else:
+            # Internal measurement, replaced boundary
+            # depends on measured loss fraction.
+            if measurement.loss_fraction > packet_loss_ratio:
+                # We have found a narrow valid interval,
+                # regardless of whether old upper bound was valid.
+                return ReceiveRateInterval(old_lo, measurement)
+            else:
+                # In ideal world, we would not want to shrink interval
+                # if upper bound is not valid.
+                # In the real world, we want to shrink it for
+                # "invalid upper bound at maximal rate" case.
+                return ReceiveRateInterval(measurement, old_hi)
+        # Fallback, the interval is unchanged by the measurement.
+        return old_interval
+
+    def ndrpdr(self, state):
+        """Pefrom trials for this phase. Return the new state when done.
+
+        :param state: State before this phase.
+        :type state: ProgressState
+        :returns: The updated state.
+        :rtype: ProgressState
+        :raises RuntimeError: If total duration is larger than timeout.
+        """
+        start_time = time.time()
+        if state.phases > 0:
+            # We need to finish preceding intermediate phases first.
+            saved_phases = state.phases
+            state.phases -= 1
+            # Preceding phases have shorter duration.
+            saved_duration = state.duration
+            duration_multiplier = state.duration / self.initial_trial_duration
+            phase_exponent = float(state.phases) / saved_phases
+            state.duration = self.initial_trial_duration * math.pow(
+                duration_multiplier, phase_exponent)
+            # Shorter durations do not need that narrow widths.
+            saved_width = state.width_goal
+            state.width_goal = self.double_relative_width(state.width_goal)
+            # Recurse.
+            state = self.ndrpdr(state)
+            # Restore the state for current phase.
+            state.duration = saved_duration
+            state.width_goal = saved_width
+            state.phases = saved_phases  # Not needed, but just in case.
+        logging.info(
+            "starting iterations with duration %s and relative width goal %s",
+            state.duration, state.width_goal)
+        while 1:
+            if time.time() > start_time + self.timeout:
+                raise RuntimeError("Optimized search takes too long.")
+            # Order of priorities: invalid bounds (nl, pl, nh, ph),
+            # then narrowing relative Tr widths.
+            # Durations are not priorities yet,
+            # they will settle on their own hopefully.
+            ndr_lo = state.result.ndr_interval.measured_low
+            ndr_hi = state.result.ndr_interval.measured_high
+            pdr_lo = state.result.pdr_interval.measured_low
+            pdr_hi = state.result.pdr_interval.measured_high
+            ndr_rel_width = max(
+                state.width_goal, state.result.ndr_interval.rel_tr_width)
+            pdr_rel_width = max(
+                state.width_goal, state.result.pdr_interval.rel_tr_width)
+            # If we are hitting maximal or minimal rate, we cannot shift,
+            # but we can re-measure.
+            if ndr_lo.loss_fraction > 0.0:
+                if ndr_lo.target_tr > state.minimum_transmit_rate:
+                    new_tr = max(
+                        state.minimum_transmit_rate,
+                        self.double_step_down(ndr_rel_width, ndr_lo.target_tr))
+                    logging.info("ndr lo external %s", new_tr)
+                    state = self._measure_and_update_state(state, new_tr)
+                    continue
+                elif ndr_lo.duration < state.duration:
+                    logging.info("ndr lo minimal re-measure")
+                    state = self._measure_and_update_state(
+                        state, state.minimum_transmit_rate)
+                    continue
+            if pdr_lo.loss_fraction > state.packet_loss_ratio:
+                if pdr_lo.target_tr > state.minimum_transmit_rate:
+                    new_tr = max(
+                        state.minimum_transmit_rate,
+                        self.double_step_down(pdr_rel_width, pdr_lo.target_tr))
+                    logging.info("pdr lo external %s", new_tr)
+                    state = self._measure_and_update_state(state, new_tr)
+                    continue
+                elif pdr_lo.duration < state.duration:
+                    logging.info("pdr lo minimal re-measure")
+                    state = self._measure_and_update_state(
+                        state, state.minimum_transmit_rate)
+                    continue
+            if ndr_hi.loss_fraction <= 0.0:
+                if ndr_hi.target_tr < state.maximum_transmit_rate:
+                    new_tr = min(
+                        state.maximum_transmit_rate,
+                        self.double_step_up(ndr_rel_width, ndr_hi.target_tr))
+                    logging.info("ndr hi external %s", new_tr)
+                    state = self._measure_and_update_state(state, new_tr)
+                    continue
+                elif ndr_hi.duration < state.duration:
+                    logging.info("ndr hi maximal re-measure")
+                    state = self._measure_and_update_state(
+                        state, state.maximum_transmit_rate)
+                    continue
+            if pdr_hi.loss_fraction <= state.packet_loss_ratio:
+                if pdr_hi.target_tr < state.maximum_transmit_rate:
+                    new_tr = min(
+                        state.maximum_transmit_rate,
+                        self.double_step_up(pdr_rel_width, pdr_hi.target_tr))
+                    logging.info("pdr hi external %s", new_tr)
+                    state = self._measure_and_update_state(state, new_tr)
+                    continue
+                elif pdr_hi.duration < state.duration:
+                    logging.info("ndr hi maximal re-measure")
+                    state = self._measure_and_update_state(
+                        state, state.maximum_transmit_rate)
+                    continue
+            # If we are hitting maximum_transmit_rate,
+            # it is still worth narrowing width,
+            # hoping large enough loss fraction will happen.
+            # But if we are hitting the minimal rate (at current duration),
+            # no additional measurement will help with that,
+            # so we can stop narrowing in this phase.
+            if (ndr_lo.target_tr <= state.minimum_transmit_rate
+                    and ndr_lo.loss_fraction > 0.0):
+                ndr_rel_width = 0.0
+            if (pdr_lo.target_tr <= state.minimum_transmit_rate
+                    and pdr_lo.loss_fraction > state.packet_loss_ratio):
+                pdr_rel_width = 0.0
+            if ndr_rel_width > state.width_goal:
+                # We have to narrow NDR width first, as NDR internal search
+                # can invalidate PDR (but not vice versa).
+                new_tr = self.half_step_up(ndr_rel_width, ndr_lo.target_tr)
+                logging.info("Bisecting for NDR at %s", new_tr)
+                state = self._measure_and_update_state(state, new_tr)
+                continue
+            if pdr_rel_width > state.width_goal:
+                # PDR iternal search.
+                new_tr = self.half_step_up(pdr_rel_width, pdr_lo.target_tr)
+                logging.info("Bisecting for PDR at %s", new_tr)
+                state = self._measure_and_update_state(state, new_tr)
+                continue
+            # We do not need to improve width, but there still might be
+            # some measurements with smaller duration.
+            # We need to re-measure with full duration, possibly
+            # creating invalid bounds to resolve (thus broadening width).
+            if ndr_lo.duration < state.duration:
+                logging.info("re-measuring NDR lower bound")
+                self._measure_and_update_state(state, ndr_lo.target_tr)
+                continue
+            if pdr_lo.duration < state.duration:
+                logging.info("re-measuring PDR lower bound")
+                self._measure_and_update_state(state, pdr_lo.target_tr)
+                continue
+            # Except when lower bounds have high loss fraction, in that case
+            # we do not need to re-measure _upper_ bounds.
+            if ndr_hi.duration < state.duration and ndr_rel_width > 0.0:
+                logging.info("re-measuring NDR upper bound")
+                self._measure_and_update_state(state, ndr_hi.target_tr)
+                continue
+            if pdr_hi.duration < state.duration and pdr_rel_width > 0.0:
+                logging.info("re-measuring PDR upper bound")
+                self._measure_and_update_state(state, pdr_hi.target_tr)
+                continue
+            # Widths are narrow (or lower bound minimal), bound measurements
+            # are long enough, we can return.
+            logging.info("phase done")
+            break
+        return state
diff --git a/resources/libraries/python/search/NdrPdrResult.py b/resources/libraries/python/search/NdrPdrResult.py
new file mode 100644
index 0000000000..b69a57ecbe
--- /dev/null
+++ b/resources/libraries/python/search/NdrPdrResult.py
@@ -0,0 +1,65 @@
+# Copyright (c) 2018 Cisco and/or its affiliates.
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at:
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+"""Module defining NdrPdrResult class."""
+
+from ReceiveRateInterval import ReceiveRateInterval
+
+
+class NdrPdrResult(object):
+    """Two measurement intervals, return value of search algorithms.
+
+    Partial fraction is NOT part of the result. Pdr interval should be valid
+    for all partial fractions implied by the interval."""
+
+    def __init__(self, ndr_interval, pdr_interval):
+        """Store the measured intervals after checking argument types.
+
+        :param ndr_interval: Object containing data for NDR part of the result.
+        :param pdr_interval: Object containing data for PDR part of the result.
+        :type ndr_interval: ReceiveRateInterval
+        :type pdr_interval: ReceiveRateInterval
+        """
+        # TODO: Type checking is not very pythonic,
+        # perhaps users can fix wrong usage without it?
+        if not isinstance(ndr_interval, ReceiveRateInterval):
+            raise TypeError("ndr_interval, is not a ReceiveRateInterval: "
+                            "{ndr!r}".format(ndr=ndr_interval))
+        if not isinstance(pdr_interval, ReceiveRateInterval):
+            raise TypeError("pdr_interval, is not a ReceiveRateInterval: "
+                            "{pdr!r}".format(pdr=pdr_interval))
+        self.ndr_interval = ndr_interval
+        self.pdr_interval = pdr_interval
+
+    def width_in_goals(self, relative_width_goal):
+        """Return a debug string related to current widths in logarithmic scale.
+
+        :param relative_width_goal: Upper bound times this is the goal
+            difference between upper bound and lower bound.
+        :type relative_width_goal: float
+        :returns: Message containing NDR and PDR widths in goals.
+        :rtype: str
+        """
+        return "ndr {ndr_in_goals}; pdr {pdr_in_goals}".format(
+            ndr_in_goals=self.ndr_interval.width_in_goals(relative_width_goal),
+            pdr_in_goals=self.pdr_interval.width_in_goals(relative_width_goal))
+
+    def __str__(self):
+        """Return string as tuple of named values."""
+        return "NDR={ndr!s};PDR={pdr!s}".format(
+            ndr=self.ndr_interval, pdr=self.pdr_interval)
+
+    def __repr__(self):
+        """Return string evaluable as a constructor call."""
+        return "NdrPdrResult(ndr_interval={ndr!r},pdr_interval={pdr!r})".format(
+            ndr=self.ndr_interval, pdr=self.pdr_interval)
diff --git a/resources/libraries/python/search/ReceiveRateInterval.py b/resources/libraries/python/search/ReceiveRateInterval.py
new file mode 100644
index 0000000000..05e0f10013
--- /dev/null
+++ b/resources/libraries/python/search/ReceiveRateInterval.py
@@ -0,0 +1,84 @@
+# Copyright (c) 2018 Cisco and/or its affiliates.
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at:
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+"""Module defining ReceiveRateInterval class."""
+
+import math
+
+from ReceiveRateMeasurement import ReceiveRateMeasurement
+
+
+class ReceiveRateInterval(object):
+    """Structure defining two Rr measurements, and their relation."""
+
+    def __init__(self, measured_low, measured_high):
+        """Store the bound measurements after checking argument types.
+
+        :param measured_low: Measurement for the lower bound.
+        :param measured_high: Measurement for the upper bound.
+        :type measured_low: ReceiveRateMeasurement
+        :type measured_high: ReceiveRateMeasurement
+        """
+        # TODO: Type checking is not very pythonic,
+        # perhaps users can fix wrong usage without it?
+        if not isinstance(measured_low, ReceiveRateMeasurement):
+            raise TypeError("measured_low is not a ReceiveRateMeasurement: "
+                            "{low!r}".format(low=measured_low))
+        if not isinstance(measured_high, ReceiveRateMeasurement):
+            raise TypeError("measured_high is not a ReceiveRateMeasurement: "
+                            "{high!r}".format(high=measured_high))
+        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 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)
+
+    def __str__(self):
+        """Return string as half-open interval."""
+        return "[{low!s};{high!s})".format(
+            low=self.measured_low, high=self.measured_high)
+
+    def __repr__(self):
+        """Return string evaluable as a constructor call."""
+        return ("ReceiveRateInterval(measured_low={low!r}"
+                ",measured_high={high!r})".format(
+                    low=self.measured_low, high=self.measured_high))
diff --git a/resources/libraries/python/search/ReceiveRateMeasurement.py b/resources/libraries/python/search/ReceiveRateMeasurement.py
new file mode 100644
index 0000000000..d052ebd3bf
--- /dev/null
+++ b/resources/libraries/python/search/ReceiveRateMeasurement.py
@@ -0,0 +1,54 @@
+# Copyright (c) 2018 Cisco and/or its affiliates.
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at:
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+"""Module defining ReceiveRateMeasurement class."""
+
+
+class ReceiveRateMeasurement(object):
+    """Structure defining the result of single Rr measurement."""
+
+    def __init__(self, duration, target_tr, transmit_count, loss_count):
+        """Constructor, normalize primary and compute secondary quantities.
+
+        :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].
+        :type duration: float
+        :type target_tr: float
+        :type transmit_count: int
+        :type loss_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_fraction = float(self.loss_count) / self.transmit_count
+        # TODO: Do we want to store also the real time (duration + overhead)?
+
+    def __str__(self):
+        """Return string reporting input and loss fraction."""
+        return "d={dur!s},Tr={rate!s},Df={frac!s}".format(
+            dur=self.duration, rate=self.target_tr, frac=self.loss_fraction)
+
+    def __repr__(self):
+        """Return string evaluable as a constructor call."""
+        return ("ReceiveRateMeasurement(duration={dur!r},target_tr={rate!r}"
+                ",transmit_count={trans!r},loss_count={loss!r})".format(
+                    dur=self.duration, rate=self.target_tr,
+                    trans=self.transmit_count, loss=self.loss_count))
diff --git a/resources/libraries/python/search/__init__.py b/resources/libraries/python/search/__init__.py
new file mode 100644
index 0000000000..4cc8158397
--- /dev/null
+++ b/resources/libraries/python/search/__init__.py
@@ -0,0 +1,16 @@
+# Copyright (c) 2018 Cisco and/or its affiliates.
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at:
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+"""
+__init__ file for Python package "MLRsearch"
+"""