+ Use first intermediate with goal in initial phase.
+ Measure above MRR if that got zero loss.
+ Always prioritizes NDR in internal search.
+ Rename classes.
+ Copy code for standalone PyPI publishing.
- Original files will be deleted after publish.
Change-Id: I5169d602d1e5e35a1894645cd52e70d791871608
Signed-off-by: Vratko Polak <vrpolak@cisco.com>
--- /dev/null
+# Byte-compiled / optimized / DLL files
+__pycache__/
+*.py[cod]
+*$py.class
+
+# C extensions
+*.so
+
+# Distribution / packaging
+.Python
+build/
+develop-eggs/
+dist/
+downloads/
+eggs/
+.eggs/
+lib/
+lib64/
+parts/
+sdist/
+var/
+wheels/
+*.egg-info/
+.installed.cfg
+*.egg
+MANIFEST
+
+# PyInstaller
+# Usually these files are written by a python script from a template
+# before PyInstaller builds the exe, so as to inject date/other infos into it.
+*.manifest
+*.spec
+
+# Installer logs
+pip-log.txt
+pip-delete-this-directory.txt
+
+# Unit test / coverage reports
+htmlcov/
+.tox/
+.coverage
+.coverage.*
+.cache
+nosetests.xml
+coverage.xml
+*.cover
+.hypothesis/
+.pytest_cache/
+
+# Translations
+*.mo
+*.pot
+
+# Django stuff:
+*.log
+local_settings.py
+db.sqlite3
+
+# Flask stuff:
+instance/
+.webassets-cache
+
+# Scrapy stuff:
+.scrapy
+
+# Sphinx documentation
+docs/_build/
+
+# PyBuilder
+target/
+
+# Jupyter Notebook
+.ipynb_checkpoints
+
+# pyenv
+.python-version
+
+# celery beat schedule file
+celerybeat-schedule
+
+# SageMath parsed files
+*.sage.py
+
+# Environments
+.env
+.venv
+env/
+venv/
+ENV/
+env.bak/
+venv.bak/
+
+# Spyder project settings
+.spyderproject
+.spyproject
+
+# Rope project settings
+.ropeproject
+
+# mkdocs documentation
+/site
+
+# mypy
+.mypy_cache/
--- /dev/null
+ Apache License
+ Version 2.0, January 2004
+ http://www.apache.org/licenses/
+
+ TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
+
+ 1. Definitions.
+
+ "License" shall mean the terms and conditions for use, reproduction,
+ and distribution as defined by Sections 1 through 9 of this document.
+
+ "Licensor" shall mean the copyright owner or entity authorized by
+ the copyright owner that is granting the License.
+
+ "Legal Entity" shall mean the union of the acting entity and all
+ other entities that control, are controlled by, or are under common
+ control with that entity. For the purposes of this definition,
+ "control" means (i) the power, direct or indirect, to cause the
+ direction or management of such entity, whether by contract or
+ otherwise, or (ii) ownership of fifty percent (50%) or more of the
+ outstanding shares, or (iii) beneficial ownership of such entity.
+
+ "You" (or "Your") shall mean an individual or Legal Entity
+ exercising permissions granted by this License.
+
+ "Source" form shall mean the preferred form for making modifications,
+ including but not limited to software source code, documentation
+ source, and configuration files.
+
+ "Object" form shall mean any form resulting from mechanical
+ transformation or translation of a Source form, including but
+ not limited to compiled object code, generated documentation,
+ and conversions to other media types.
+
+ "Work" shall mean the work of authorship, whether in Source or
+ Object form, made available under the License, as indicated by a
+ copyright notice that is included in or attached to the work
+ (an example is provided in the Appendix below).
+
+ "Derivative Works" shall mean any work, whether in Source or Object
+ form, that is based on (or derived from) the Work and for which the
+ editorial revisions, annotations, elaborations, or other modifications
+ represent, as a whole, an original work of authorship. For the purposes
+ of this License, Derivative Works shall not include works that remain
+ separable from, or merely link (or bind by name) to the interfaces of,
+ the Work and Derivative Works thereof.
+
+ "Contribution" shall mean any work of authorship, including
+ the original version of the Work and any modifications or additions
+ to that Work or Derivative Works thereof, that is intentionally
+ submitted to Licensor for inclusion in the Work by the copyright owner
+ or by an individual or Legal Entity authorized to submit on behalf of
+ the copyright owner. For the purposes of this definition, "submitted"
+ means any form of electronic, verbal, or written communication sent
+ to the Licensor or its representatives, including but not limited to
+ communication on electronic mailing lists, source code control systems,
+ and issue tracking systems that are managed by, or on behalf of, the
+ Licensor for the purpose of discussing and improving the Work, but
+ excluding communication that is conspicuously marked or otherwise
+ designated in writing by the copyright owner as "Not a Contribution."
+
+ "Contributor" shall mean Licensor and any individual or Legal Entity
+ on behalf of whom a Contribution has been received by Licensor and
+ subsequently incorporated within the Work.
+
+ 2. Grant of Copyright License. Subject to the terms and conditions of
+ this License, each Contributor hereby grants to You a perpetual,
+ worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+ copyright license to reproduce, prepare Derivative Works of,
+ publicly display, publicly perform, sublicense, and distribute the
+ Work and such Derivative Works in Source or Object form.
+
+ 3. Grant of Patent License. Subject to the terms and conditions of
+ this License, each Contributor hereby grants to You a perpetual,
+ worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+ (except as stated in this section) patent license to make, have made,
+ use, offer to sell, sell, import, and otherwise transfer the Work,
+ where such license applies only to those patent claims licensable
+ by such Contributor that are necessarily infringed by their
+ Contribution(s) alone or by combination of their Contribution(s)
+ with the Work to which such Contribution(s) was submitted. If You
+ institute patent litigation against any entity (including a
+ cross-claim or counterclaim in a lawsuit) alleging that the Work
+ or a Contribution incorporated within the Work constitutes direct
+ or contributory patent infringement, then any patent licenses
+ granted to You under this License for that Work shall terminate
+ as of the date such litigation is filed.
+
+ 4. Redistribution. You may reproduce and distribute copies of the
+ Work or Derivative Works thereof in any medium, with or without
+ modifications, and in Source or Object form, provided that You
+ meet the following conditions:
+
+ (a) You must give any other recipients of the Work or
+ Derivative Works a copy of this License; and
+
+ (b) You must cause any modified files to carry prominent notices
+ stating that You changed the files; and
+
+ (c) You must retain, in the Source form of any Derivative Works
+ that You distribute, all copyright, patent, trademark, and
+ attribution notices from the Source form of the Work,
+ excluding those notices that do not pertain to any part of
+ the Derivative Works; and
+
+ (d) If the Work includes a "NOTICE" text file as part of its
+ distribution, then any Derivative Works that You distribute must
+ include a readable copy of the attribution notices contained
+ within such NOTICE file, excluding those notices that do not
+ pertain to any part of the Derivative Works, in at least one
+ of the following places: within a NOTICE text file distributed
+ as part of the Derivative Works; within the Source form or
+ documentation, if provided along with the Derivative Works; or,
+ within a display generated by the Derivative Works, if and
+ wherever such third-party notices normally appear. The contents
+ of the NOTICE file are for informational purposes only and
+ do not modify the License. You may add Your own attribution
+ notices within Derivative Works that You distribute, alongside
+ or as an addendum to the NOTICE text from the Work, provided
+ that such additional attribution notices cannot be construed
+ as modifying the License.
+
+ You may add Your own copyright statement to Your modifications and
+ may provide additional or different license terms and conditions
+ for use, reproduction, or distribution of Your modifications, or
+ for any such Derivative Works as a whole, provided Your use,
+ reproduction, and distribution of the Work otherwise complies with
+ the conditions stated in this License.
+
+ 5. Submission of Contributions. Unless You explicitly state otherwise,
+ any Contribution intentionally submitted for inclusion in the Work
+ by You to the Licensor shall be under the terms and conditions of
+ this License, without any additional terms or conditions.
+ Notwithstanding the above, nothing herein shall supersede or modify
+ the terms of any separate license agreement you may have executed
+ with Licensor regarding such Contributions.
+
+ 6. Trademarks. This License does not grant permission to use the trade
+ names, trademarks, service marks, or product names of the Licensor,
+ except as required for reasonable and customary use in describing the
+ origin of the Work and reproducing the content of the NOTICE file.
+
+ 7. Disclaimer of Warranty. Unless required by applicable law or
+ agreed to in writing, Licensor provides the Work (and each
+ Contributor provides its Contributions) on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+ implied, including, without limitation, any warranties or conditions
+ of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
+ PARTICULAR PURPOSE. You are solely responsible for determining the
+ appropriateness of using or redistributing the Work and assume any
+ risks associated with Your exercise of permissions under this License.
+
+ 8. Limitation of Liability. In no event and under no legal theory,
+ whether in tort (including negligence), contract, or otherwise,
+ unless required by applicable law (such as deliberate and grossly
+ negligent acts) or agreed to in writing, shall any Contributor be
+ liable to You for damages, including any direct, indirect, special,
+ incidental, or consequential damages of any character arising as a
+ result of this License or out of the use or inability to use the
+ Work (including but not limited to damages for loss of goodwill,
+ work stoppage, computer failure or malfunction, or any and all
+ other commercial damages or losses), even if such Contributor
+ has been advised of the possibility of such damages.
+
+ 9. Accepting Warranty or Additional Liability. While redistributing
+ the Work or Derivative Works thereof, You may choose to offer,
+ and charge a fee for, acceptance of support, warranty, indemnity,
+ or other liability obligations and/or rights consistent with this
+ License. However, in accepting such obligations, You may act only
+ on Your own behalf and on Your sole responsibility, not on behalf
+ of any other Contributor, and only if You agree to indemnify,
+ defend, and hold each Contributor harmless for any liability
+ incurred by, or claims asserted against, such Contributor by reason
+ of your accepting any such warranty or additional liability.
+
+ END OF TERMS AND CONDITIONS
+
+ APPENDIX: How to apply the Apache License to your work.
+
+ To apply the Apache License to your work, attach the following
+ boilerplate notice, with the fields enclosed by brackets "[]"
+ replaced with your own identifying information. (Don't include
+ the brackets!) The text should be enclosed in the appropriate
+ comment syntax for the file format. We also recommend that a
+ file or class name and description of purpose be included on the
+ same "printed page" as the copyright notice for easier
+ identification within third-party archives.
+
+ Copyright [yyyy] [name of copyright owner]
+
+ 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.
--- /dev/null
+
+# Include the README
+include README.rst
+
+# Include the license file
+include LICENSE.txt
# See the License for the specific language governing permissions and
# limitations under the License.
-"""Module defining AbstractRateProvider class."""
+"""Module defining AbstractMeasurer class."""
from abc import ABCMeta, abstractmethod
-class AbstractRateProvider(object):
- """Abstract class defining common API for rate providers."""
+class AbstractMeasurer(object):
+ """Abstract class defining common API for measurement providers."""
__metaclass__ = ABCMeta
--- /dev/null
+# 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
# See the License for the specific language governing permissions and
# limitations under the License.
-"""Module defining OptimizedSearchAlgorithm class."""
+"""Module defining MultipleLossRatioSearch class."""
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 OptimizedSearchAlgorithm(AbstractSearchAlgorithm):
+class MultipleLossRatioSearch(AbstractSearchAlgorithm):
"""Optimized binary search algorithm for finding NDR and PDR bounds.
Traditional binary search algorithm needs initial interval
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 need to be valid.
+ 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,
trial duration, interval width is less than the width goal
for current phase.
- TODO: Reviwew and update this docstring according to rst docs.
- TODO: Initial phase: Larger min width and search up on zero.
+ TODO: Review and update this docstring according to rst docs.
TODO: Support configurable number of Packet Loss Ratios.
- TODO: Rename to MultipleDropRateSearch (or MultipleLossRatioSearch).
"""
class ProgressState(object):
self.minimum_transmit_rate = float(minimum_transmit_rate)
self.maximum_transmit_rate = float(maximum_transmit_rate)
- def __init__(self, rate_provider, final_relative_width=0.005,
+ 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 rate provider and additional arguments.
+ """Store the measurer object and additional arguments.
- :param rate_provider: Rate provider to use by this search object.
+ :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].
to perform before the final phase [1].
:param timeout: The search will fail itself when not finished
before this overall time [s].
- :type rate_provider: AbstractRateProvider
+ :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(OptimizedSearchAlgorithm, self).__init__(rate_provider)
+ 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):
minimum_transmit_rate = float(minimum_transmit_rate)
maximum_transmit_rate = float(maximum_transmit_rate)
packet_loss_ratio = float(packet_loss_ratio)
- line_measurement = self.rate_provider.measure(
+ line_measurement = self.measurer.measure(
self.initial_trial_duration, maximum_transmit_rate)
- # 0.999 is to avoid rounding errors which make
- # the subsequent logic think the width is too broad.
- max_lo = max(
+ 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,
- maximum_transmit_rate * (1.0 - 0.999 * self.final_relative_width))
- mrr = min(
- max_lo, max(minimum_transmit_rate, line_measurement.receive_rate))
- mrr_measurement = self.rate_provider.measure(
+ min(max_lo, line_measurement.receive_rate))
+ mrr_measurement = self.measurer.measure(
self.initial_trial_duration, mrr)
# Attempt to get narrower width.
- max2_lo = max(
- minimum_transmit_rate,
- mrr * (1.0 - 0.999 * self.final_relative_width))
- mrr2 = min(max2_lo, mrr_measurement.receive_rate)
- if mrr2 > minimum_transmit_rate:
+ 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.rate_provider.measure(
+ 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)
logging.debug(
"relative widths in goals: %s", state.result.width_in_goals(
self.final_relative_width))
- measurement = self.rate_provider.measure(state.duration, transmit_rate)
+ 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(
# Fallback, the interval is unchanged by the measurement.
return old_interval
- @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 - OptimizedSearchAlgorithm.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 - OptimizedSearchAlgorithm.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 - OptimizedSearchAlgorithm.half_relative_width(relative_width))
-
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 updates state.
+ :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
logging.info(
"starting iterations with duration %s and relative width goal %s",
state.duration, state.width_goal)
- start_time = time.time()
while 1:
if time.time() > start_time + self.timeout:
raise RuntimeError("Optimized search takes too long.")
- # Order of priorities: improper bounds (nl, pl, nh, ph),
+ # 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.
if (pdr_lo.target_tr <= state.minimum_transmit_rate
and pdr_lo.loss_fraction > state.packet_loss_ratio):
pdr_rel_width = 0.0
- if max(ndr_rel_width, pdr_rel_width) > state.width_goal:
- # We have to narrow some width.
- # TODO: Prefer NDR, it could invalidate PDR (not vice versa).
- if ndr_rel_width >= pdr_rel_width:
- 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
- else:
- 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
+ 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
--- /dev/null
+# 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)
--- /dev/null
+# 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))
--- /dev/null
+# 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))
--- /dev/null
+# 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"
+"""
--- /dev/null
+Multiple Loss Ratio Search library
+==================================
+
+Origins
+-------
+
+This library was developed as a speedup for traditional binary search
+in CSIT_ (Continuous System and Integration Testing) project of fd.io_
+(Fast Data), one of LFN_ (Linux Foundation Networking) projects.
+
+In order to make this code available in PyPI_ (Python Package Index),
+the setuputils stuff has been added,
+and the code has been moved into a separate directory_,
+in order to not interfere with otherwise tightly coupled CSIT code.
+
+Usage
+-----
+
+TODO.
+
+Operation logic
+---------------
+
+TODO.
+
+.. _CSIT: https://wiki.fd.io/view/CSIT
+.. _fd.io: https://fd.io/
+.. _LFN: https://www.linuxfoundation.org/projects/networking/
+.. _PyPI: https://pypi.org/
+.. _directory: https://gerrit.fd.io/r/gitweb?p=csit.git;a=tree;f=PyPI/MLRsearch;hb=refs/heads/master
--- /dev/null
+[metadata]
+# This includes the license file in the wheel.
+license_file = LICENSE.txt
+
+[bdist_wheel]
+# TODO: Make the code work both on Python 2 and 3.
+universal=0
--- /dev/null
+"""A setup module for setuptools.
+
+See:
+https://packaging.python.org/en/latest/distributing.html
+"""
+
+from setuptools import setup, find_packages
+from os import path
+from io import open
+
+here = path.abspath(path.dirname(__file__))
+with open(path.join(here, "README.rst"), encoding="utf-8") as f:
+ long_description = f.read()
+
+setup(
+ name="MLRsearch",
+ version="0.1.1", # This is currently the only place listing the version.
+ description="Library for speeding up binary search using shorter measurements.",
+ long_description=long_description,
+ long_description_content_type="text/x-rst",
+ # TODO: Create a separate webpage for MLRsearch library.
+ url="https://gerrit.fd.io/r/gitweb?p=csit.git;a=tree;f=PyPI/MLRsearch;hb=refs/heads/master",
+ author="Cisco Systems Inc. and/or its affiliates",
+ author_email="csit-dev@lists.fd.io",
+ classifiers=[
+ "Development Status :: 3 - Alpha",
+ "Intended Audience :: Science/Research",
+ "Intended Audience :: Telecommunications Industry",
+ # Pick your license as you wish
+ "License :: OSI Approved :: Apache Software License",
+ # TODO: Test which Python versions is the code compatible with.
+ "Programming Language :: Python :: 2.7",
+ "Topic :: System :: Networking"
+ ],
+ keywords="binary search throughput networking",
+ packages=find_packages(exclude=[]),
+ # TODO: python_requires="~=2.7"
+ install_requires=[],
+ # TODO: Include simulator and tests.
+ extras_require={
+ },
+ package_data={
+ },
+ entry_points={
+ "console_scripts": [
+ ],
+ },
+ project_urls={
+ "Bug Reports": "https://jira.fd.io/projects/CSIT/issues",
+ "Source": "https://gerrit.fd.io/r/gitweb?p=csit.git;a=tree;f=PyPI/MLRsearch;hb=refs/heads/master",
+ },
+)
CSIT contributors, make sure each PyPI project
-has the following users listed as Owners:
+has the following users listed as Owners
+(both on pypi.org and on test.pypi.org if the project exists there):
+ vrpolakatcisco
+ tiborfrank
transmit rate had the loss lower or equal to PLR, then
the new transmit rate is PDR upper_bound
increased by two PDR interval widths.
- - Else, *if* NDR (or PDR) interval does not meet the current phase width goal,
- prepare for internal search. The new transmit rate is
- (lower bound + upper bound) / 2.
- It does not matter much which interval is investigated first.
- The current implementation starts with NDR, unless PDR interval is wider
- (but always preferring NDR is slightly better).
+ - If interval width is higher than the current phase goal:
+
+ - Else, *if* NDR interval does not meet the current phase width goal,
+ prepare for internal search. The new transmit rate is
+ (NDR lower bound + NDR upper bound) / 2.
+ - Else, *if* PDR interval does not meet the current phase width goal,
+ prepare for internal search. The new transmit rate is
+ (PDR lower bound + PDR upper bound) / 2.
- Else, *if* some bound has still only been measured at a lower duration,
prepare to re-measure at the current duration (and the same transmit rate).
The order of priorities is:
Narrow intervals make external search take more time to find a valid bound.
If the new transmit increased or decreased rate would result in width
less than the current goal, increase/decrease more.
- This can happen if measurement for the other interval
+ This can happen if the measurement for the other interval
makes the current interval too narrow.
Similarly, take care the measurements in the initial phase
create wide enough interval.
Tables
``````
+.. note:: The comparison was done for the MDR code
+ before https://gerrit.fd.io/r/12761
+
.. table:: Table 1. Search part of test duration.
==================== ========== =========== =========== ========== =========== ===========
from .topology import NodeType
from .topology import NodeSubTypeTG
from .topology import Topology
-from .search.AbstractRateProvider import AbstractRateProvider
-from .search.OptimizedSearchAlgorithm import OptimizedSearchAlgorithm
+from .search.AbstractMeasurer import AbstractMeasurer
+from .search.MultipleLossRatioSearch import MultipleLossRatioSearch
from .search.ReceiveRateMeasurement import ReceiveRateMeasurement
__all__ = ['TGDropRateSearchImpl', 'TrafficGenerator', 'OptimizedSearch']
return tg_instance.get_latency_int()
-class TrafficGenerator(AbstractRateProvider):
+class TrafficGenerator(AbstractMeasurer):
"""Traffic Generator.
FIXME: Describe API."""
:type initial_trial_duration: float
:type number_of_intermediate_phases: int
:type timeout: float
- :returns: Structure containing narrowed down intervals
+ :returns: Structure containing narrowed down NDR and PDR intervals
and their measurements.
:rtype: NdrPdrResult
:raises RuntimeError: If total duration is larger than timeout.
tg_instance = BuiltIn().get_library_instance(
'resources.libraries.python.TrafficGenerator')
tg_instance.set_rate_provider_defaults(frame_size, traffic_type)
- algorithm = OptimizedSearchAlgorithm(
- tg_instance, final_trial_duration=final_trial_duration,
+ algorithm = MultipleLossRatioSearch(
+ measurer=tg_instance, final_trial_duration=final_trial_duration,
final_relative_width=final_relative_width,
number_of_intermediate_phases=number_of_intermediate_phases,
initial_trial_duration=initial_trial_duration, timeout=timeout)
--- /dev/null
+# 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
__metaclass__ = ABCMeta
- def __init__(self, rate_provider):
+ def __init__(self, measurer):
"""Store the rate provider.
- :param rate_provider: Object able to perform trial measurements.
- :type rate_provider: AbstractRateProvider
+ :param measurer: Object able to perform trial or composite measurements.
+ :type measurer: AbstractMeasurer
"""
- # TODO: Type check for AbstractRateProvider?
- self.rate_provider = rate_provider
+ # 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].
--- /dev/null
+# 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
"""Module defining NdrPdrResult class."""
-from .ReceiveRateInterval import ReceiveRateInterval
+from ReceiveRateInterval import ReceiveRateInterval
class NdrPdrResult(object):
import math
-from .ReceiveRateMeasurement import ReceiveRateMeasurement
+from ReceiveRateMeasurement import ReceiveRateMeasurement
class ReceiveRateInterval(object):
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. Ansolute divided by upper."""
+ """Relative width of target transmit rate. Absolute divided by upper."""
self.sort()
def sort(self):
# limitations under the License.
"""
-__init__ file for directory resources/libraries/python/search
+__init__ file for Python package "MLRsearch"
"""
Code Review / csit.git / commitdiff