2.2. MLRsearch

2.2.1. AbstractMeasurer suite

Module defining AbstractMeasurer class.

class resources.libraries.python.MLRsearch.AbstractMeasurer.AbstractMeasurer

Bases: object

Abstract class defining common API for measurement providers.

abstract measure(duration, transmit_rate)

Perform trial measurement and return the result.

Parameters

  • duration (float) – Trial duration [s].

  • transmit_rate (float) – Target transmit rate [tps].

Returns

Structure containing the result of the measurement.

Return type

ReceiveRateMeasurement.ReceiveRateMeasurement

2.2.2. AbstractSearchAlgorithm suite

Module defining AbstractSearchAlgorithm class.

class resources.libraries.python.MLRsearch.AbstractSearchAlgorithm.AbstractSearchAlgorithm(measurer)

Bases: object

Abstract class defining common API for search algorithms.

abstract narrow_down_intervals(min_rate, max_rate, packet_loss_ratios)

Perform measurements to narrow down intervals, return them.

Parameters

  • min_rate (float) – Minimal target transmit rate [tps]. Usually, tests are set to fail if search reaches this or below.

  • max_rate (float) – Maximal target transmit rate [tps]. Usually computed from line rate and various other limits, to prevent failures or duration stretching in Traffic Generator.

  • packet_loss_ratios (Iterable[float]) – Ratios of packet loss to search for, e.g. [0.0, 0.005] for NDR and PDR.

Returns

Structure containing narrowed down intervals and their measurements.

Return type

List[ReceiveRateInterval.ReceiveRateInterval]

2.2.3. MeasurementDatabase suite

Module defining MeasurementDatabase class.

class resources.libraries.python.MLRsearch.MeasurementDatabase.MeasurementDatabase(measurements)

Bases: object

A structure holding measurement results.

The implementation uses a dict from duration values to PerDurationDatabase instances.

Several utility methods are added, accomplishing tasks useful for MLRsearch.

This class contains the “find tightest bounds” parts of logic required by MLRsearch. One exception is lack of any special handling for maximal or minimal rates.

add(measurement)

Add a measurement. Duration has to match the set one.

Parameters

measurement (ReceiveRateMeasurement) – Measurement result to add to the database.

get_bounds(ratio)

Return 6 bounds: lower/upper, current/previous, tightest/second.

Second tightest bounds are only returned for current duration. None instead of a measurement if there is no measurement of that type.

The result cotains bounds in this order: 1. Tightest lower bound for current duration. 2. Tightest upper bound for current duration. 3. Tightest lower bound for previous duration. 4. Tightest upper bound for previous duration. 5. Second tightest lower bound for current duration. 6. Second tightest upper bound for current duration.

Parameters

ratio (float) – Target ratio, valid has to be lower or equal.

Returns

Measurements acting as various bounds.

Return type

6-tuple of Optional[PerDurationDatabase]

get_results(ratio_list)

Return list of intervals for given ratios, from current duration.

Attempt to construct valid intervals. If a valid bound is missing, use smallest/biggest target_tr for lower/upper bound. This can result in degenerate intervals.

Parameters

ratio_list (Iterable[float]) – Ratios to create intervals for.

Returns

List of intervals.

Return type

List[ReceiveRateInterval]

set_current_duration(duration)

Remember what MLRsearch considers the current duration.

Setting the same duration is allowed, setting smaller is not allowed.

Parameters

duration (float) – Target trial duration of current phase, in seconds.

Raises

ValueError – If the duration is smaller than previous.

2.2.4. MultipleLossRatioSearch suite

Module defining MultipleLossRatioSearch class.

class resources.libraries.python.MLRsearch.MultipleLossRatioSearch.MultipleLossRatioSearch(measurer, final_relative_width=0.005, final_trial_duration=30.0, initial_trial_duration=1.0, number_of_intermediate_phases=2, timeout=600.0, debug=None, expansion_coefficient=2.0)

Bases: object

Optimized binary search algorithm for finding bounds for multiple ratios.

This is unofficially a subclass of AbstractSearchAlgorithm, but constructor signature is different.

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 multiple intervals at once. The intervals differ by the target loss ratio. Lower bound has to have equal or smaller loss ratio, upper bound has to have larger.

Next improvement is that the initial interval does not need to be valid. Imagine initial interval (10, 11) where loss at 11 is smaller than the searched ratio. 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 intervals of final phase is the result of the whole algorithm.

Each non-initial phase uses its own trial duration. Any non-initial phase stops searching (for all ratios independently) when minimum is not a valid lower bound (at current duration), or all of the following is true: Both bounds are valid, 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.

static improves(new_bound, lower_bound, upper_bound)

Return whether new bound improves upon old bounds.

To improve, new_bound has to be not None, and between the old bounds (where the bound is not None).

This piece of logic is commonly used, when we know old bounds from a primary source (e.g. current duration database) and new bound from a secondary source (e.g. previous duration database). Having a function allows “if improves(..):” construction to save space.

Parameters
Returns

Whether we can apply the new bound.

Return type

bool

narrow_down_intervals(min_rate, max_rate, packet_loss_ratios)

Perform initial phase, create state object, proceed with next phases.

The current implementation requires the ratios so be unique and sorted. Also non-empty.

Parameters

  • min_rate (float) – Minimal target transmit rate [tps].

  • max_rate (float) – Maximal target transmit rate [tps].

  • packet_loss_ratios (Iterable[float]) – Target ratios of packets loss to locate.

Returns

Structure containing narrowed down intervals and their measurements.

Return type

List[ReceiveRateInterval]

Raises

RuntimeError – If total duration is larger than timeout. Or if ratios list is (empty or) not sorted or unique.

ndrpdr()

Perform trials for this phase. State is updated in-place.

Recursion to smaller durations is performed (if not performed yet).

Raises

RuntimeError – If total duration is larger than timeout.

2.2.5. PerDurationDatabase suite

Module defining PerDurationDatabase class.

class resources.libraries.python.MLRsearch.PerDurationDatabase.PerDurationDatabase(duration, measurements)

Bases: object

List-like structure holding measurement results for one duration.

This is a building block for MeasurementDatabase.

This class hold measurements for single target duration value only, so the logic is quite simple.

Several utility methods are added, accomplishing tasks useful for MLRsearch (to be called by MeasurementDatabase).

add(measurement)

Add measurement and normalize.

Parameters

measurement (ReceiveRateMeasurement) – Measurement result to add to the database.

get_valid_bounds(ratio)

Return None or a valid measurement for two tightest bounds.

The validity of a measurement to act as a bound is determined by comparing the argument ratio with measurement’s effective loss ratio.

Both lower and upper bounds are returned, both tightest and second tightest. If some value is not available, None is returned instead.

Parameters

ratio (float) – Target ratio, valid has to be lower or equal.

Returns

Tightest lower bound, tightest upper bound, second tightest lower bound, second tightest upper bound.

Return type

4-tuple of Optional[ReceiveRateMeasurement]

2.2.6. ProgressState suite

Module defining ProgressState class.

class resources.libraries.python.MLRsearch.ProgressState.ProgressState(database, phases, duration, width_goal, packet_loss_ratios, min_rate, max_rate, stop_time)

Bases: object

Structure containing data to be passed around in recursion.

This is basically a private class of MultipleRatioSearch, but keeping it in a separate file makes things more readable.

2.2.7. ReceiveRateInterval suite

Module defining ReceiveRateInterval class.

class resources.libraries.python.MLRsearch.ReceiveRateInterval.ReceiveRateInterval(measured_low, measured_high)

Bases: object

Structure defining two Rr measurements, and their relation.

abs_tr_width

Absolute width of target transmit rate. Upper minus lower.

rel_tr_width

Relative width of target transmit rate. Absolute divided by upper.

sort()

Sort bounds by target Tr, compute secondary quantities.

width_in_goals(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.

Parameters

relative_width_goal (float) – Upper bound times this is the goal difference between upper bound and lower bound.

Returns

Current width as logarithmic multiple of goal width [1].

Return type

float

2.2.8. ReceiveRateMeasurement suite

Module defining ReceiveRateMeasurement class.

class resources.libraries.python.MLRsearch.ReceiveRateMeasurement.ReceiveRateMeasurement(duration, target_tr, transmit_count, loss_count, approximated_duration=0.0, partial_transmit_count=0, effective_loss_ratio=None)

Bases: object

Structure defining the result of single Rr measurement.

2.2.9. WidthArithmetics suite

Module defining utility functions for manipulating intervals.

resources.libraries.python.MLRsearch.WidthArithmetics.half_step_up(current_bound, relative_width, goal_width)

Return rate of half logarithmic width above.

Parameters

  • relative_width (float) – The base relative width to halve.

  • current_bound (float) – The current target transmit rate to move [pps].

Returns

Transmit rate larger by logarithmically half width [pps].

Return type

float

resources.libraries.python.MLRsearch.WidthArithmetics.halve_relative_width(relative_width, goal_width)

Return relative width corresponding to half logarithmic width.

The logic attempts to save some halvings in future by performing uneven split. If rounding error risk is detected, even split is used.

Parameters

  • relative_width (float) – The base relative width to halve.

  • goal_width (float) – Width goal for final phase.

Returns

The relative width of half logarithmic size.

Return type

float

resources.libraries.python.MLRsearch.WidthArithmetics.multiple_step_down(current_bound, relative_width, coefficient)

Return rate of multiplied logarithmic width below.

The multiplication happens in logarithmic space, so the resulting applied relative width is always less than 1.

Parameters

  • relative_width (float) – The base relative width to double.

  • current_bound (float) – The current target transmit rate to move [pps].

  • coefficient (float) – Multiply by this in logarithmic space.

Returns

Transmit rate smaller by logarithmically multiplied width [pps].

Return type

float

resources.libraries.python.MLRsearch.WidthArithmetics.multiple_step_up(current_bound, relative_width, coefficient)

Return rate of double logarithmic width above.

The multiplication happens in logarithmic space, so the resulting applied relative width is always less than 1.

Parameters

  • current_bound (float) – The current target transmit rate to move [pps].

  • relative_width (float) – The base relative width to double.

  • coefficient (float) – Multiply by this in logarithmic space.

Returns

Transmit rate larger by logarithmically multiplied width [pps].

Return type

float

resources.libraries.python.MLRsearch.WidthArithmetics.multiply_relative_width(relative_width, coefficient)

Return relative width corresponding to multiplied logarithmic width.

The multiplication happens in logarithmic space, so the resulting relative width is always less than 1.

Parameters

  • relative_width (float) – The base relative width to multiply.

  • coefficient (float) – Multiply by this in logarithmic space.

Returns

The relative width of multiplied logarithmic size.

Return type

float

resources.libraries.python.MLRsearch.WidthArithmetics.step_down(current_bound, relative_width)

Return rate of logarithmic width below.

Parameters

  • current_bound (float) – The current target transmit rate to move [pps].

  • relative_width (float) – The base relative width to use.

Returns

Transmit rate smaller by relative width [pps].

Return type

float

resources.libraries.python.MLRsearch.WidthArithmetics.step_up(current_bound, relative_width)

Return rate of logarithmic width above.

Parameters

  • current_bound (float) – The current target transmit rate to move [pps].

  • relative_width (float) – The base relative width to use.

Returns

Transmit rate larger by logarithmically double width [pps].

Return type

float