X-Git-Url: https://gerrit.fd.io/r/gitweb?a=blobdiff_plain;f=resources%2Flibraries%2Fpython%2FMLRsearch%2FMultipleLossRatioSearch.py;h=1ecd42e7dd6378bd0e8c3413dda8b4482a6eb279;hb=891f932d2c0928038c7cb77f96ecad6e12c0e81f;hp=0eb1d7da4c97ceb1ca0c9f4c69cb4a086a93f5ae;hpb=ad27739cd87a75b172fd415fc20db08983ea4e13;p=csit.git

diff --git a/resources/libraries/python/MLRsearch/MultipleLossRatioSearch.py b/resources/libraries/python/MLRsearch/MultipleLossRatioSearch.py
index 0eb1d7da4c..1ecd42e7dd 100644
--- a/resources/libraries/python/MLRsearch/MultipleLossRatioSearch.py
+++ b/resources/libraries/python/MLRsearch/MultipleLossRatioSearch.py
@@ -17,9 +17,9 @@ import logging
 import math
 import time
 
-from AbstractSearchAlgorithm import AbstractSearchAlgorithm
-from NdrPdrResult import NdrPdrResult
-from ReceiveRateInterval import ReceiveRateInterval
+from .AbstractSearchAlgorithm import AbstractSearchAlgorithm
+from .NdrPdrResult import NdrPdrResult
+from .ReceiveRateInterval import ReceiveRateInterval
 
 
 class MultipleLossRatioSearch(AbstractSearchAlgorithm):
@@ -97,7 +97,7 @@ class MultipleLossRatioSearch(AbstractSearchAlgorithm):
                 for the current search [pps].
             :param maximum_transmit_rate: Maximum target transmit rate
                 for the current search [pps].
-            :type result: NdrPdrResult
+            :type result: NdrPdrResult.NdrPdrResult
             :type phases: int
             :type duration: float
             :type width_goal: float
@@ -115,7 +115,7 @@ class MultipleLossRatioSearch(AbstractSearchAlgorithm):
 
     def __init__(self, measurer, final_relative_width=0.005,
                  final_trial_duration=30.0, initial_trial_duration=1.0,
-                 number_of_intermediate_phases=2, timeout=600.0):
+                 number_of_intermediate_phases=2, timeout=600.0, doublings=1):
         """Store the measurer object and additional arguments.
 
         :param measurer: Rate provider to use by this search object.
@@ -128,12 +128,16 @@ class MultipleLossRatioSearch(AbstractSearchAlgorithm):
             to perform before the final phase [1].
         :param timeout: The search will fail itself when not finished
             before this overall time [s].
-        :type measurer: AbstractMeasurer
+        :param doublings: How many doublings to do in external search step.
+            Default 1 is suitable for fairly stable tests,
+            less stable tests might get better overal duration with 2 or more.
+        :type measurer: AbstractMeasurer.AbstractMeasurer
         :type final_relative_width: float
         :type final_trial_duration: float
         :type initial_trial_duration: int
         :type number_of_intermediate_phases: int
         :type timeout: float
+        :type doublings: int
         """
         super(MultipleLossRatioSearch, self).__init__(measurer)
         self.final_trial_duration = float(final_trial_duration)
@@ -141,6 +145,7 @@ class MultipleLossRatioSearch(AbstractSearchAlgorithm):
         self.number_of_intermediate_phases = int(number_of_intermediate_phases)
         self.initial_trial_duration = float(initial_trial_duration)
         self.timeout = float(timeout)
+        self.doublings = int(doublings)
 
 
     @staticmethod
@@ -171,6 +176,24 @@ class MultipleLossRatioSearch(AbstractSearchAlgorithm):
             1.0 - MultipleLossRatioSearch.double_relative_width(
                 relative_width))
 
+    @staticmethod
+    def expand_down(relative_width, doublings, current_bound):
+        """Return rate of expanded logarithmic width below.
+
+        :param relative_width: The base relative width to double.
+        :param doublings: How many doublings to do for expansion.
+        :param current_bound: The current target transmit rate to move [pps].
+        :type relative_width: float
+        :type doublings: int
+        :type current_bound: float
+        :returns: Transmit rate smaller by logarithmically double width [pps].
+        :rtype: float
+        """
+        for _ in range(doublings):
+            relative_width = MultipleLossRatioSearch.double_relative_width(
+                relative_width)
+        return current_bound * (1.0 - relative_width)
+
     @staticmethod
     def double_step_up(relative_width, current_bound):
         """Return rate of double logarithmic width above.
@@ -186,6 +209,24 @@ class MultipleLossRatioSearch(AbstractSearchAlgorithm):
             1.0 - MultipleLossRatioSearch.double_relative_width(
                 relative_width))
 
+    @staticmethod
+    def expand_up(relative_width, doublings, current_bound):
+        """Return rate of expanded logarithmic width above.
+
+        :param relative_width: The base relative width to double.
+        :param doublings: How many doublings to do for expansion.
+        :param current_bound: The current target transmit rate to move [pps].
+        :type relative_width: float
+        :type doublings: int
+        :type current_bound: float
+        :returns: Transmit rate smaller by logarithmically double width [pps].
+        :rtype: float
+        """
+        for _ in range(doublings):
+            relative_width = MultipleLossRatioSearch.double_relative_width(
+                relative_width)
+        return current_bound / (1.0 - relative_width)
+
     @staticmethod
     def half_relative_width(relative_width):
         """Return relative width corresponding to half logarithmic width.
@@ -224,7 +265,7 @@ class MultipleLossRatioSearch(AbstractSearchAlgorithm):
         :type packet_loss_ratio: float
         :returns: Structure containing narrowed down intervals
             and their measurements.
-        :rtype: NdrPdrResult
+        :rtype: NdrPdrResult.NdrPdrResult
         :raises RuntimeError: If total duration is larger than timeout.
         """
         minimum_transmit_rate = float(minimum_transmit_rate)
@@ -296,55 +337,58 @@ class MultipleLossRatioSearch(AbstractSearchAlgorithm):
         :param old_interval: The current interval before the measurement.
         :param measurement: The new meaqsurement to take into account.
         :param packet_loss_ratio: Fraction for PDR (or zero for NDR).
-        :type old_interval: ReceiveRateInterval
-        :type measurement: ReceiveRateMeasurement
+        :type old_interval: ReceiveRateInterval.ReceiveRateInterval
+        :type measurement: ReceiveRateMeasurement.ReceiveRateMeasurement
         :type packet_loss_ratio: float
         :returns: The updated interval.
-        :rtype: ReceiveRateInterval
+        :rtype: ReceiveRateInterval.ReceiveRateInterval
         """
         old_lo, old_hi = old_interval.measured_low, old_interval.measured_high
+        new_lo = new_hi = None
         # Priority zero: direct replace if the target Tr is the same.
         if measurement.target_tr in (old_lo.target_tr, old_hi.target_tr):
             if measurement.target_tr == old_lo.target_tr:
-                return ReceiveRateInterval(measurement, old_hi)
+                new_lo = measurement
             else:
-                return ReceiveRateInterval(old_lo, measurement)
+                new_hi = measurement
         # Priority one: invalid lower bound allows only one type of update.
-        if old_lo.loss_fraction > packet_loss_ratio:
+        elif old_lo.loss_fraction > packet_loss_ratio:
             # We can only expand down, old bound becomes valid upper one.
             if measurement.target_tr < old_lo.target_tr:
-                return ReceiveRateInterval(measurement, old_lo)
+                new_lo, new_hi = measurement, old_lo
             else:
                 return old_interval
+
         # Lower bound is now valid.
         # Next priorities depend on target Tr.
-        if measurement.target_tr < old_lo.target_tr:
+        elif measurement.target_tr < old_lo.target_tr:
             # Lower external measurement, relevant only
             # if the new measurement has high loss rate.
             if measurement.loss_fraction > packet_loss_ratio:
                 # Returning the broader interval as old_lo
                 # would be invalid upper bound.
-                return ReceiveRateInterval(measurement, old_hi)
+                new_lo = measurement
         elif measurement.target_tr > old_hi.target_tr:
             # Upper external measurement, only relevant for invalid upper bound.
             if old_hi.loss_fraction <= packet_loss_ratio:
                 # Old upper bound becomes valid new lower bound.
-                return ReceiveRateInterval(old_hi, measurement)
+                new_lo, new_hi = old_hi, measurement
         else:
             # Internal measurement, replaced boundary
             # depends on measured loss fraction.
             if measurement.loss_fraction > packet_loss_ratio:
                 # We have found a narrow valid interval,
                 # regardless of whether old upper bound was valid.
-                return ReceiveRateInterval(old_lo, measurement)
+                new_hi = measurement
             else:
                 # In ideal world, we would not want to shrink interval
                 # if upper bound is not valid.
                 # In the real world, we want to shrink it for
                 # "invalid upper bound at maximal rate" case.
-                return ReceiveRateInterval(measurement, old_hi)
-        # Fallback, the interval is unchanged by the measurement.
-        return old_interval
+                new_lo = measurement
+
+        return ReceiveRateInterval(old_lo if new_lo is None else new_lo,
+                                   old_hi if new_hi is None else new_hi)
 
     def ndrpdr(self, state):
         """Pefrom trials for this phase. Return the new state when done.
@@ -375,6 +419,7 @@ class MultipleLossRatioSearch(AbstractSearchAlgorithm):
             state.duration = saved_duration
             state.width_goal = saved_width
             state.phases = saved_phases  # Not needed, but just in case.
+
         logging.info(
             "starting iterations with duration %s and relative width goal %s",
             state.duration, state.width_goal)
@@ -395,58 +440,14 @@ class MultipleLossRatioSearch(AbstractSearchAlgorithm):
                 state.width_goal, state.result.pdr_interval.rel_tr_width)
             # If we are hitting maximal or minimal rate, we cannot shift,
             # but we can re-measure.
-            if ndr_lo.loss_fraction > 0.0:
-                if ndr_lo.target_tr > state.minimum_transmit_rate:
-                    new_tr = max(
-                        state.minimum_transmit_rate,
-                        self.double_step_down(ndr_rel_width, ndr_lo.target_tr))
-                    logging.info("ndr lo external %s", new_tr)
-                    state = self._measure_and_update_state(state, new_tr)
-                    continue
-                elif ndr_lo.duration < state.duration:
-                    logging.info("ndr lo minimal re-measure")
-                    state = self._measure_and_update_state(
-                        state, state.minimum_transmit_rate)
-                    continue
-            if pdr_lo.loss_fraction > state.packet_loss_ratio:
-                if pdr_lo.target_tr > state.minimum_transmit_rate:
-                    new_tr = max(
-                        state.minimum_transmit_rate,
-                        self.double_step_down(pdr_rel_width, pdr_lo.target_tr))
-                    logging.info("pdr lo external %s", new_tr)
-                    state = self._measure_and_update_state(state, new_tr)
-                    continue
-                elif pdr_lo.duration < state.duration:
-                    logging.info("pdr lo minimal re-measure")
-                    state = self._measure_and_update_state(
-                        state, state.minimum_transmit_rate)
-                    continue
-            if ndr_hi.loss_fraction <= 0.0:
-                if ndr_hi.target_tr < state.maximum_transmit_rate:
-                    new_tr = min(
-                        state.maximum_transmit_rate,
-                        self.double_step_up(ndr_rel_width, ndr_hi.target_tr))
-                    logging.info("ndr hi external %s", new_tr)
-                    state = self._measure_and_update_state(state, new_tr)
-                    continue
-                elif ndr_hi.duration < state.duration:
-                    logging.info("ndr hi maximal re-measure")
-                    state = self._measure_and_update_state(
-                        state, state.maximum_transmit_rate)
-                    continue
-            if pdr_hi.loss_fraction <= state.packet_loss_ratio:
-                if pdr_hi.target_tr < state.maximum_transmit_rate:
-                    new_tr = min(
-                        state.maximum_transmit_rate,
-                        self.double_step_up(pdr_rel_width, pdr_hi.target_tr))
-                    logging.info("pdr hi external %s", new_tr)
-                    state = self._measure_and_update_state(state, new_tr)
-                    continue
-                elif pdr_hi.duration < state.duration:
-                    logging.info("ndr hi maximal re-measure")
-                    state = self._measure_and_update_state(
-                        state, state.maximum_transmit_rate)
-                    continue
+            new_tr = self._ndrpdr_loss_fraction(state,
+                                                ndr_lo, ndr_hi, pdr_lo, pdr_hi,
+                                                ndr_rel_width, pdr_rel_width)
+
+            if new_tr is not None:
+                state = self._measure_and_update_state(state, new_tr)
+                continue
+
             # If we are hitting maximum_transmit_rate,
             # it is still worth narrowing width,
             # hoping large enough loss fraction will happen.
@@ -459,43 +460,166 @@ class MultipleLossRatioSearch(AbstractSearchAlgorithm):
             if (pdr_lo.target_tr <= state.minimum_transmit_rate
                     and pdr_lo.loss_fraction > state.packet_loss_ratio):
                 pdr_rel_width = 0.0
-            if ndr_rel_width > state.width_goal:
-                # We have to narrow NDR width first, as NDR internal search
-                # can invalidate PDR (but not vice versa).
-                new_tr = self.half_step_up(ndr_rel_width, ndr_lo.target_tr)
-                logging.info("Bisecting for NDR at %s", new_tr)
-                state = self._measure_and_update_state(state, new_tr)
-                continue
-            if pdr_rel_width > state.width_goal:
-                # PDR iternal search.
-                new_tr = self.half_step_up(pdr_rel_width, pdr_lo.target_tr)
-                logging.info("Bisecting for PDR at %s", new_tr)
+
+            new_tr = self._ndrpdr_width_goal(state, ndr_lo, pdr_lo,
+                                             ndr_rel_width, pdr_rel_width)
+
+            if new_tr is not None:
                 state = self._measure_and_update_state(state, new_tr)
                 continue
+
             # We do not need to improve width, but there still might be
             # some measurements with smaller duration.
-            # We need to re-measure with full duration, possibly
-            # creating invalid bounds to resolve (thus broadening width).
-            if ndr_lo.duration < state.duration:
-                logging.info("re-measuring NDR lower bound")
-                self._measure_and_update_state(state, ndr_lo.target_tr)
-                continue
-            if pdr_lo.duration < state.duration:
-                logging.info("re-measuring PDR lower bound")
-                self._measure_and_update_state(state, pdr_lo.target_tr)
-                continue
-            # Except when lower bounds have high loss fraction, in that case
-            # we do not need to re-measure _upper_ bounds.
-            if ndr_hi.duration < state.duration and ndr_rel_width > 0.0:
-                logging.info("re-measuring NDR upper bound")
-                self._measure_and_update_state(state, ndr_hi.target_tr)
-                continue
-            if pdr_hi.duration < state.duration and pdr_rel_width > 0.0:
-                logging.info("re-measuring PDR upper bound")
-                self._measure_and_update_state(state, pdr_hi.target_tr)
+            new_tr = self._ndrpdr_duration(state,
+                                           ndr_lo, ndr_hi, pdr_lo, pdr_hi,
+                                           ndr_rel_width, pdr_rel_width)
+
+            if new_tr is not None:
+                state = self._measure_and_update_state(state, new_tr)
                 continue
+
             # Widths are narrow (or lower bound minimal), bound measurements
             # are long enough, we can return.
             logging.info("phase done")
             break
         return state
+
+    def _ndrpdr_loss_fraction(self, state, ndr_lo, ndr_hi, pdr_lo, pdr_hi,
+                              ndr_rel_width, pdr_rel_width):
+        """Perform loss_fraction-based trials within a ndrpdr phase
+
+        :param state: current state
+        :param ndr_lo: ndr interval measured low
+        :param ndr_hi: ndr interval measured high
+        :param pdr_lo: pdr interval measured low
+        :param pdr_hi: pdr interval measured high
+        :param ndr_rel_width: ndr interval relative width
+        :param pdr_rel_width: pdr interval relative width
+        :type state: ProgressState
+        :type ndr_lo: ReceiveRateMeasurement.ReceiveRateMeasurement
+        :type ndr_hi: ReceiveRateMeasurement.ReceiveRateMeasurement
+        :type pdr_lo: ReceiveRateMeasurement.ReceiveRateMeasurement
+        :type pdr_hi: ReceiveRateMeasurement.ReceiveRateMeasurement
+        :type ndr_rel_width: float
+        :type pdr_rel_width: float
+        :returns: a new transmit rate if one should be applied
+        :rtype: float
+        """
+        result = None
+        if ndr_lo.loss_fraction > 0.0:
+            if ndr_lo.target_tr > state.minimum_transmit_rate:
+                result = max(
+                    state.minimum_transmit_rate,
+                    self.expand_down(
+                        ndr_rel_width, self.doublings, ndr_lo.target_tr))
+                logging.info("ndr lo external %s", result)
+            elif ndr_lo.duration < state.duration:
+                result = state.minimum_transmit_rate
+                logging.info("ndr lo minimal re-measure")
+
+        if result is None and pdr_lo.loss_fraction > state.packet_loss_ratio:
+            if pdr_lo.target_tr > state.minimum_transmit_rate:
+                result = max(
+                    state.minimum_transmit_rate,
+                    self.expand_down(
+                        pdr_rel_width, self.doublings, pdr_lo.target_tr))
+                logging.info("pdr lo external %s", result)
+            elif pdr_lo.duration < state.duration:
+                result = state.minimum_transmit_rate
+                logging.info("pdr lo minimal re-measure")
+
+        if result is None and ndr_hi.loss_fraction <= 0.0:
+            if ndr_hi.target_tr < state.maximum_transmit_rate:
+                result = min(
+                    state.maximum_transmit_rate,
+                    self.expand_up(
+                        ndr_rel_width, self.doublings, ndr_hi.target_tr))
+                logging.info("ndr hi external %s", result)
+            elif ndr_hi.duration < state.duration:
+                result = state.maximum_transmit_rate
+                logging.info("ndr hi maximal re-measure")
+
+        if result is None and pdr_hi.loss_fraction <= state.packet_loss_ratio:
+            if pdr_hi.target_tr < state.maximum_transmit_rate:
+                result = min(
+                    state.maximum_transmit_rate,
+                    self.expand_up(
+                        pdr_rel_width, self.doublings, pdr_hi.target_tr))
+                logging.info("pdr hi external %s", result)
+            elif pdr_hi.duration < state.duration:
+                result = state.maximum_transmit_rate
+                logging.info("ndr hi maximal re-measure")
+        return result
+
+    def _ndrpdr_width_goal(self, state, ndr_lo, pdr_lo,
+                           ndr_rel_width, pdr_rel_width):
+        """Perform width_goal-based trials within a ndrpdr phase
+
+        :param state: current state
+        :param ndr_lo: ndr interval measured low
+        :param pdr_lo: pdr interval measured low
+        :param ndr_rel_width: ndr interval relative width
+        :param pdr_rel_width: pdr interval relative width
+        :type state: ProgressState
+        :type ndr_lo: ReceiveRateMeasurement.ReceiveRateMeasurement
+        :type pdr_lo: ReceiveRateMeasurement.ReceiveRateMeasurement
+        :type ndr_rel_width: float
+        :type pdr_rel_width: float
+        :returns: a new transmit rate if one should be applied
+        :rtype: float
+        Return a new transmit rate if one should be applied.
+        """
+        if ndr_rel_width > state.width_goal:
+            # We have to narrow NDR width first, as NDR internal search
+            # can invalidate PDR (but not vice versa).
+            result = self.half_step_up(ndr_rel_width, ndr_lo.target_tr)
+            logging.info("Bisecting for NDR at %s", result)
+        elif pdr_rel_width > state.width_goal:
+            # PDR iternal search.
+            result = self.half_step_up(pdr_rel_width, pdr_lo.target_tr)
+            logging.info("Bisecting for PDR at %s", result)
+        else:
+            result = None
+        return result
+
+    @staticmethod
+    def _ndrpdr_duration(state, ndr_lo, pdr_lo, ndr_hi, pdr_hi,
+                         ndr_rel_width, pdr_rel_width):
+        """Perform duration-based trials within a ndrpdr phase
+
+        :param state: current state
+        :param ndr_lo: ndr interval measured low
+        :param ndr_hi: ndr interval measured high
+        :param pdr_lo: pdr interval measured low
+        :param pdr_hi: pdr interval measured high
+        :param ndr_rel_width: ndr interval relative width
+        :param pdr_rel_width: pdr interval relative width
+        :type state: ProgressState
+        :type ndr_lo: ReceiveRateMeasurement.ReceiveRateMeasurement
+        :type ndr_hi: ReceiveRateMeasurement.ReceiveRateMeasurement
+        :type pdr_lo: ReceiveRateMeasurement.ReceiveRateMeasurement
+        :type pdr_hi: ReceiveRateMeasurement.ReceiveRateMeasurement
+        :type ndr_rel_width: float
+        :type pdr_rel_width: float
+        :returns: a new transmit rate if one should be applied
+        :rtype: float
+        """
+        # We need to re-measure with full duration, possibly
+        # creating invalid bounds to resolve (thus broadening width).
+        if ndr_lo.duration < state.duration:
+            result = ndr_lo.target_tr
+            logging.info("re-measuring NDR lower bound")
+        elif pdr_lo.duration < state.duration:
+            result = pdr_lo.target_tr
+            logging.info("re-measuring PDR lower bound")
+        # Except when lower bounds have high loss fraction, in that case
+        # we do not need to re-measure _upper_ bounds.
+        elif ndr_hi.duration < state.duration and ndr_rel_width > 0.0:
+            result = ndr_hi.target_tr
+            logging.info("re-measuring NDR upper bound")
+        elif pdr_hi.duration < state.duration and pdr_rel_width > 0.0:
+            result = pdr_hi.target_tr
+            logging.info("re-measuring PDR upper bound")
+        else:
+            result = None
+        return result