aboutsummaryrefslogtreecommitdiffstats
path: root/resources/libraries/python/MLRsearch/WidthArithmetics.py
diff options
context:
space:
mode:
authorVratko Polak <vrpolak@cisco.com>2021-03-22 17:11:21 +0100
committerVratko Polak <vrpolak@cisco.com>2021-03-22 17:11:21 +0100
commitb6fbffad32515ccf94404680cb5280c2cb561af5 (patch)
tree6f16569781e3e3627589c6fff0d7a5be0410d3f3 /resources/libraries/python/MLRsearch/WidthArithmetics.py
parentadf5f13886e8bdd4fb224f12f10d731cadf698f3 (diff)
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>
Diffstat (limited to 'resources/libraries/python/MLRsearch/WidthArithmetics.py')
-rw-r--r--resources/libraries/python/MLRsearch/WidthArithmetics.py135
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)