MLRsearch: Support other than just two ratios

+ Change some method names and argument types:
 + Do not mention NDR and PDR, except as examples.
 + Return list of ReceiveRateInterval instead of NdrPdrResult.
 + The resulting intervals can be degenerate when hitting min/max rate.
+ Rename quantity name parts from "fraction" to "ratio".
+ Intervals are no longer tracked for each target ratio.
 + They are found dynamically from known results.
+ Add effective_loss_ratio field to avoid loss inversion effects.
+ Move some functions to separate files.
 + Bound search logic moved to MeasurementDatabase.py
 + ProgressState moved to its file.
 + WidthArithmetics.py holds small computation functions.
+ Use parameter expansion_coefficient instead of "doublings".
+ Do uneven bisect to save time when width is not power of two times goal.
+ Timeout now correctly tracked for the whole search,
  not just the current phase.
+ Make logging (debug) function pluggable.
 + Added debug log messages for initial phase.
+ Do not mark as subclass if contructor signature differs.
+ Avoid re-measure on scale-limited (ASTF) profiles.
+ Remove outdated comments.
+ Bump copyright years.

Change-Id: I93f693b4f186f59030ee5ac21b78acc890109813
Signed-off-by: Vratko Polak <vrpolak@cisco.com>

1 files changed, 135 insertions, 0 deletions

diff --git a/resources/libraries/python/MLRsearch/WidthArithmetics.py b/resources/libraries/python/MLRsearch/WidthArithmetics.py
new file mode 100644
index 0000000000..81decfd12f
--- /dev/null
+++ b/resources/libraries/python/MLRsearch/WidthArithmetics.py
@@ -0,0 +1,135 @@
+# 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 = math.ceil(wig)
+    if wig <= 2.0 or cwig != math.ceil(wig * ROUNDING_CONSTANT):
+        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)