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