+++ /dev/null
----
-title: Multiple Loss Ratio Search
-abbrev: MLRsearch
-docname: draft-ietf-bmwg-mlrsearch-04
-date: 2023-07-10
-
-ipr: trust200902
-area: ops
-wg: Benchmarking Working Group
-kw: Internet-Draft
-cat: info
-
-coding: us-ascii
-pi: # can use array (if all yes) or hash here
- toc: yes
- sortrefs: # defaults to yes
- symrefs: yes
-
-author:
- -
- ins: M. Konstantynowicz
- name: Maciek Konstantynowicz
- org: Cisco Systems
- email: mkonstan@cisco.com
- -
- ins: V. Polak
- name: Vratko Polak
- org: Cisco Systems
- email: vrpolak@cisco.com
-
-normative:
- RFC1242:
- RFC2285:
- RFC2544:
- RFC9004:
-
-informative:
- TST009:
- target: https://www.etsi.org/deliver/etsi_gs/NFV-TST/001_099/009/03.04.01_60/gs_NFV-TST009v030401p.pdf
- title: "TST 009"
- FDio-CSIT-MLRsearch:
- target: https://csit.fd.io/cdocs/methodology/measurements/data_plane_throughput/mlr_search/
- title: "FD.io CSIT Test Methodology - MLRsearch"
- date: 2022-11
- PyPI-MLRsearch:
- target: https://pypi.org/project/MLRsearch/0.4.0/
- title: "MLRsearch 0.4.0, Python Package Index"
- date: 2021-04
-
---- abstract
-
-This document proposes improvements to [RFC2544] throughput search by
-defining a new methodology called Multiple Loss Ratio search
-(MLRsearch). The main objectives for MLRsearch are to minimize the
-total test duration, search for multiple loss ratios and improve
-results repeatibility and comparability.
-
-The main motivation behind MLRsearch is the new set of challenges and
-requirements posed by testing Network Function Virtualization
-(NFV) systems and other software based network data planes.
-
-MLRsearch offers several ways to address these challenges, giving user
-configuration options to select their preferred way.
-
---- middle
-
-{::comment}
- As we use kramdown to convert from markdown,
- we use this way of marking comments not to be visible in rendered draft.
- https://stackoverflow.com/a/42323390
- If other engine is used, convert to this way:
- https://stackoverflow.com/a/20885980
-{:/comment}
-
-# Purpose and Scope
-
-The purpose of this document is to describe Multiple Loss Ratio search
-(MLRsearch), a throughput search methodology optimized for software
-DUTs.
-
-Applying vanilla [RFC2544] throughput bisection to software DUTs
-results in a number of problems:
-
-- Binary search takes too long as most of trials are done far from the
- eventually found throughput.
-- The required final trial duration (and pauses between trials) also
- prolong the overall search duration.
-- Software DUTs show noisy trial results (noisy neighbor problem),
- leading to big spread of possible discovered throughput values.
-- Throughput requires loss of exactly zero packets, but the industry
- frequently allows for small but non-zero losses.
-- The definition of throughput is not clear when trial results are
- inconsistent.
-
-MLRsearch aims to address these problems by applying the following set
-of enhancements:
-
-- Allow searching for multiple search goals, with differing goal loss ratios.
- - Each trial result can affect any search goal in principle
- (trial reuse).
-- Multiple preceding targets for each search goal, earlier ones need
- to spend less time on trials.
- - Earlier targets also aim at lesser precision.
- - Use Forwarding Rate (FR) at maximum offered load
- [RFC2285] (section 3.6.2) to initialize the initial targets.
-- Take care when dealing with inconsistent trial results.
- - Loss ratios goals are handled in an order that minimizes the chance
- of interference from later trials to earlier goals.
-- Apply several load selection heuristics to save even more time
- by trying hard to avoid unnecessarily narrow bounds.
-
-MLRsearch configuration options are flexible enough to
-support both conservative settings (unconditionally compliant with [RFC2544],
-but longer search duration and worse repeatability) and aggressive
-settings (shorter search duration and better repeatability but not
-compliant with [RFC2544]).
-
-No part of [RFC2544] is intended to be obsoleted by this document.
-
-# Terminology
-
-When a subsection is defining a term, the first paragraph
-acts as a definition. Other paragraphs are treated as a description,
-they provide additional details without being needed to define the term.
-
-Definitions should form a directed acyclic graph of dependencies.
-If a section contains subsections, the section definition
-may depend on the subsection definitions.
-Otherwise, any definition may depend on preceding definitions.
-In other words, if the section definition were to come after subsections,
-there would be no forward dependencies for people reading just definitions
-from start to finish.
-
-Descriptions provide motivations and explanations,
-they frequently reference terms defined only later.
-Motivations in section descriptions are the reason
-why section text comes before subsection text.
-
-## General notions
-
-General notions are the terms defined in this section.
-
-It is useful to define the following notions
-before delving into MLRsearch architecture,
-as the notions appear in multiple places
-with no place being special enough to host definition.
-
-### General and specific quantities
-
-General quantity is a quantity that may appear multiple times
-in MLRsearch specification, perhaps each time in a different role.
-The quantity when appearing in a single role is called
-a specific quantity.
-
-It is useful to define the general quantity,
-so definitions of specific quantities may refer to it.
-We say a specific quantity is based on a general quantity,
-if the specific quantity definition refers to and
-relies on the general quantity definition.
-
-It is natural to name specific quantities by adding an adjective
-(or a noun) to the name of the general quantity.
-But existing RFCs typically explicitly define a term acting
-in a specific role, so the RFC name directly refers to a specific
-quantity, while the corresponding general quantity
-is defined only implicitly.
-Therefore this documents defines general quantities explicitly,
-even if the same term already appears in an RFC.
-
-In practice, it is required to know which unit of measurement
-is used to accompany a numeric value of each quantity.
-The choice of a particular unit of measurement is not important
-for MLRsearch specification though, so specific units
-mentioned in this document are just examples or recommendations,
-not requirements.
-
-When reporting, it is REQUIRED to state the units used.
-
-### Composite
-
-A composite is a set of named attributes.
-Each attribute is either a specific quantity or a composite.
-
-MLRsearch specification frequently groups multiple specific quantities
-into a composite. Description of such a composite brings an insight
-to motivations why this or other terms are defined as they are.
-Such insight will be harder to communicate
-with the specific quantities alone.
-
-Also, it simplifies naming of specific quantities, as they usually can
-share a noun or adjective referring to their common composite.
-Most of relations between composites and their specific quantities
-can be described using plain English.
-
-Perhaps the only exception involves referring to specific quantities
-as attributes. For example if there is a composite called 'target',
-and one of its specific quantities is 'target width' defined using
-a general quantity 'width', we can say 'width is one of target attributes'.
-
-### SUT
-
-As defined in RFC 2285:
-The collective set of network devices to which stimulus is offered
-as a single entity and response measured.
-
-While RFC 2544 mostly refers to DUT as a single
-(network interconnecting) device, section 19 makes it clear
-multiple DUTs can be treated as a single system,
-so most of RFC 2544 also applies to testing SUT.
-
-MLRsearch specification only refers to SUT (not DUT),
-even if it consists of just a single device.
-
-### Trial
-
-A trial is the part of test described in RFC 2544 section 23.
-
-When traffic has been sent and SUT response has been observed,
-we say the trial has been performed, or the trial has been measured.
-Before that happens, multiple possibilities for upcoming trial
-may be under consideration.
-
-### Load
-
-Intended, constant load for a trial, usually in frames per second.
-
-Load is the general quantity implied by Constant Load of RFC 1242,
-Data Rate of RFC 2544 and Intended Load of RFC 2285.
-All three specify this value applies to one (input or output) interface,
-so we can talk about unidirectional load also
-when bidirectional or multi-port traffic is applied.
-
-MLRsearch does not rely on this distinction, it works also if
-the load values correspond to an aggregate rate
-(sum over all SUT tested input or output interface unidirectional loads),
-as long as all loads share the same semantics.
-
-Several RFCs define useful quantities based on Offered Load
-(instead of Intended Load), but MLRsearch specification
-works only with (intended) load. Those useful quantities
-still serve as motivations for few specific quantities used in MLRsearch
-specification.
-
-MLRsearch assumes most load values are positive.
-For some (but not all) specific quantities based on load,
-zero may also be a valid value.
-
-### Duration
-
-Intended duration of the traffic for a trial, usually in seconds.
-
-This general quantity does not include any preparation nor waiting
-described in section 23 of RFC 2544.
-Section 24 of RFC 2544 places additional restrictions on duration,
-but those restriction apply only to some of the specific quantities based
-on duration.
-
-Duration is always positive in MLRsearch.
-
-### Duration sum
-
-For a specific set of trials, this is the sum of their durations.
-
-Some of specific quantities based on duration sum are derived quantities,
-without a specific set of trials to sum their durations.
-
-Duration sum is never negative in MLRsearch.
-
-### Width
-
-General quantity defined for an ordered pair (lower and higher)
-of load values, which describes a distance between the two values.
-
-The motivation for the name comes from binary search.
-The binary search tries to approximate an unknown value
-by repeatedly bisecting an interval of possible values,
-until the interval becomes narrow enough.
-Width of the interval is a specific quantity
-and the termination condition compares that
-to another specific quantity acting as the threshold.
-The threshold value does not have a specific interval associated,
-but corresponds to a 'size' of the compared interval.
-As size is a word already used in definition of frame size,
-a more natural word describing interval is width.
-
-The MLRsearch specification does use (analogues of) upper bound
-and lower bound, but does not actually need to talk about intervals.
-Still, the intervals are implicitly there, so width is the natural name.
-
-Actually, there are two popular options for defining width.
-Absolute width is based on load, the value is the higher load
-minus the lower load.
-Relative width is dimensionless, the value is the absolute width
-divided by the higher load. As intended loads for trials are positive,
-relative width is between 0.0 (including) and 1.0 (excluding).
-
-Relative width as a threshold value may be useful for users
-who do not presume what is the typical performance of SUT,
-but absolute width may be a more familiar concept.
-
-MLRsearch specification does not prescribe which width has to be used,
-but widths MUST be either all absolute or all relative,
-and it MUST be clear from report which option was used
-(it is implied from the unit of measurement of any width value).
-
-### Loss ratio
-
-The loss ratio is a general quantity, dimensionless floating point value
-assumed to be between 0.0 and 1.0, both including.
-It is computed as the number of frames forwarded by SUT, divided by
-the number of frames that should have been forwarded during the trial.
-
-If the number of frames that should have been forwarded is zero,
-the loss ratio is considered to be zero
-(but it is better to use high enough loads to prevent this).
-
-Loss ratio is basically the same quantity as Frame Loss Rate of RFC 1242,
-just not expressed in percents.
-
-RFC1242 Frame Loss Rate:
-Percentage of frames that should have been forwarded
-by a network device under steady state (constant)
-load that were not forwarded due to lack of
-resources.
-
-(RFC2544 restricts Frame Loss Rate to a type of benchmark,
-for loads 100% of 'maximum rate', 90% and so on.)
-
-### Exceed ratio
-
-This general quantity is a dimensionless floating point value,
-defined using two duration sum quantities.
-One duration sum is referred to as the good duration sum,
-the other is referred to as the bad duration sum.
-The exceed ratio value is computed as the bad duration sum value
-divided by the sum of the two sums. If both sums are zero,
-the exceed ratio is undefined.
-
-As there are no negative duration sums in MLRsearch,
-exceed ratio values are between 0.0 and 1.0 (both including).
-
-## Architecture
-
-MLRsearch architecture consists of three main components:
-the manager, the controller and the measurer.
-
-The search algorithm is implemented in the controller,
-and it is the main focus of this document.
-
-Most implementation details of the manager and the measurer are
-out of scope of this document, except when describing
-how do those components interface with the controller.
-
-### Manager
-
-The manager is the component that initializes SUT, traffic generator
-(called tester in RFC 2544), the measurer and the controller
-with intended configurations. It then handles the execution
-to the controller and receives its result.
-
-Managers can range from simple CLI utilities to complex
-Continuous Integration systems. From the controller point of view
-it is important that no additional configuration (nor warmup)
-is needed for SUT and the measurer to perform trials.
-
-The interface between the manager and the controller
-is defined in the controller section.
-
-One execution of the controller is called a search.
-Some benchmarks may execute multiple searches on the same SUT
-(for example when confirming the performance is stable over time),
-but in this document only one invocation is concerned
-(others may be understood as the part of SUT preparation).
-
-Creation of reports of appropriate format can also be understood
-as the responsibility of the manager. This document places requirements
-on which information has to be reported.
-
-### Measurer
-
-The measurer is the component which performs one trial
-as described in RFC 2544 section 23, when requested by the controller.
-
-From the controller point of view, it is a function that accepts
-trial input and returns trial output.
-
-This is the only way the controller can interact with SUT.
-In practice, the measurer has to do subtle decisions
-when converting the observed SUT behavior into a single
-trial loss ratio value. For example how to deal with
-out of order frames or duplicate frames.
-
-On software implementation level, the measurer is a callable,
-injected by the manager into the controller instance.
-
-The act of performing one trial (act of turning trial input
-to trial output) is called a measurement, or trial measurement.
-This way we can talk about trials that were measured already
-and trials that are merely planned (not measured yet).
-
-#### Trial input
-
-The load and duration to use in an upcoming trial.
-
-This is a composite.
-
-Other quantities needed by the measurer are assumed to be constant
-and set up by the manager before search starts (see traffic profile),
-so they do not count as trial input attributes.
-
-##### Trial load
-
-Trial load is the intended load for the trial.
-
-This is a specific quantity based on load,
-directly corresponding to RFC 2285 intended load.
-
-##### Trial duration
-
-Trial duration is the intended duration for the trial.
-
-This is a specific quantity based on duration, so it specifies
-only the traffic part of the trial, not the waiting parts.
-
-#### Traffic profile
-
-Any other configuration values needed by the measurer to perform a trial.
-
-The measurer needs both trial input and traffic profile to perform the trial.
-As trial input contains the only values that vary during one the search,
-traffic profile remains constant during the search.
-
-Traffic profile when understood as a composite is REQUIRED by RFC 2544
-to contain some specific quantities (for example frame size).
-Several more specific quantities may be RECOMMENDED.
-
-Depending on SUT configuration (e.g. when testing specific protocols),
-additional values need to be included in the traffic profile
-and in the test report. (See other IETF documents.)
-
-#### Trial ouput
-
-A composite consisting of trial loss ratio
-and trial forwarding rate.
-
-Those are the only two specific quantities (among other quantities
-possibly measured in the trial, for example offered load)
-that are important for MLRsearch.
-
-##### Trial loss ratio
-
-Trial loss ratio is a specific quantity based on loss ratio.
-The value is related to a particular measured trial,
-as measured by the measurer.
-
-##### Trial forwarding rate
-
-Trial forwarding rate is a derived quantity.
-It is computed as one minus trial loss ratio,
-that multiplied by trial load.
-
-Despite the name, the general quantity this specific quantity
-corresponds to is load (not rate).
-The name is inspired by RFC 2285, which defines Forwarding Rate
-specific to one output interface.
-
-As the definition of loss ratio is not neccessarily per-interface
-(one of details left for the measurer), using the definition above
-(instead of RFC 2285) makes sure trial forwarding rate
-is always between zero and the trial load (both including).
-
-#### Trial result
-
-Trial result is a composite consisting of trial input attributes
-and trial output attributes.
-
-Those are all specific quantites related to a measured trial MLRsearch needs.
-
-While distinction between trial input and output is important
-when defining the interface between the controller and the measurer,
-it is easier to talk about trial result
-when describing how measured trials influence the controller behavior.
-
-### Controller
-
-The component of MLRsearch architecture that calls the measurer
-and returns conditional throughputs to the manager.
-
-This component implements the search algorithm,
-the main content of this document.
-
-Contrary to Throughput as defined in RFC 1242,
-the definition of conditional throughput is quite sensitive
-to the controller input (as provided by the manager),
-and its full definition needs several terms
-which would otherwise be hidden as internals of the controller
-implementation.
-
-The ability of conditional throughput to be less sensitive
-to performance variance, and the ability of the controller
-to find conditional throughputs for multiple search goals
-within one search (and in short overall search time)
-are strong enough motivations for the need of increased complexity.
-
-### Controller input
-
-A composite of max load, min load, and a set of search goals.
-
-The search goals (as elements of the set of search goals)
-are usually not named and unordered.
-
-It is fine if all search goals of the set have the same value
-of a particular attribute. In that case, the common value
-may be treated as a global attribute (similarly to max and min load).
-
-The set of search goals MUST NOT be empty.
-Two search goals within the set MUST differ in at least one attribute.
-The manager MAY avoid both issues by presenting empty report
-or de-duplicating the search goals, but it is RECOMMENDED
-for the manager to raise an error to its caller,
-as the two conditions suggest the test is improperly configured.
-
-#### Max load
-
-Max load is a specific quantity based on load.
-No trial load is ever higher than this value.
-
-RFC 2544 section 20 defines maximum frame rate
-based on theoretical maximum rate for the frame size on the media.
-RFC 2285 section 3.5.3 specifies Maximum offered load (MOL)
-which may be lower than maximum frame rate.
-There may be other limitations preventing high loads,
-for examples resources available to traffic generator.
-
-The manager is expected to provide a value that is not greater
-than any known limitation. Alternatively, the measurer
-is expected to work at max load, possibly reporting as lost
-any frames that were not able to leave Traffic Generator.
-
-From the controller point of view, this is merely a global upper limit
-for any trial load candidates.
-
-#### Min load
-
-Min load is a specific quantity based on load.
-No trial load is ever lower than this value.
-
-The motivation of this quantity is to prevent trials
-with too few frames sent to SUT.
-
-Also, practically if a SUT is able to reach only very small
-forwarding rates (min load indirectly serves as a threshold for how small),
-it may be considered faulty (or perhaps the test is misconfigured).
-
-#### Search goal
-
-A composite of 7 attributes (see subsections).
-
-If not otherwise specified, 'goal' always refers to a search goal
-in this document.
-
-The controller input may contain multiple search goals.
-The name Multiple Loss Ratio search was created back when
-goal loss ratio was the only attribute allowed to vary between goals.
-
-Each goal will get its conditional throughput discovered
-and reported at the end of the search.
-
-The definitions of the 7 attributes are not very informative by themselves.
-Their motivation (and naming) becomes more clear
-from the impact they have on conditional throughput.
-
-##### Goal loss ratio
-
-A specific quantity based on loss ratio.
-A threshold value for trial loss ratios.
-MUST be lower than one.
-
-Trial loss ratio values will be compared to this value,
-a trial will be considered bad if its loss ratio is higher than this.
-
-For example, RFC 2544 throughput has goal loss ratio of zero,
-a trial is bad once a sigle frame is lost.
-
-Loss ratio of one would classify each trial as good (regardless of loss),
-which is not useful.
-
-##### Goal initial trial duration
-
-A specific quantity based on duration.
-A threshold value for trial durations.
-MUST be positive.
-
-MLRsearch is allowed to use trials as short as this when focusing
-on this goal.
-The conditional throughput may be influenced by shorter trials,
-(measured when focusing on other search goals).
-
-{::comment}
- FIXME: Should shorter trials be explicitly ignored?
-{:/comment}
-
-##### Goal final trial duration
-
-A specific quantity based on duration.
-A threshold value for trial durations.
-MUST be no smaller than goal initial trial duration.
-
-MLRsearch is allowed to use trials as long as this when focusing
-on this goal. If more data is needed, repeated trials
-at the same load and duration are requested by the controller.
-
-##### Goal min duration sum
-
-A specific quantity based on duration sum.
-A threshold value for a particular duration sum.
-
-MLRsearch requires at least this amount of (effective) trials
-for a particular load to become part of MLRsearch outputs.
-
-It is possible (though maybe not prectical) for goal min duration sum
-to be smaller than goal final trial duration.
-
-In practice, the sum of durations actually spent on trial measurement
-can be smaller (when trial results are quite one-sided) or even larger
-(in presence of shorter-than-final trial duration results at the same load).
-
-If the sum of all (good and bad) long trials is at least this,
-and there are no short trials, then the load is guaranteed
-to be classified as either an upper or a lower bound.
-
-In some cases, the classification is known sooner,
-when the 'missing' trials cannot change the outcome.
-
-When short trials are present, the logic is more complicated.
-
-##### Goal exceed ratio
-
-A specific quantity based on exceed ratio.
-A threshold value for particulat sets of trials.
-
-An attribute used for classifying loads into upper and lower bounds.
-
-If the duration sum of all (current duration) trials is at least
-min duration sum, and more than this percentage of the duration sum
-comes from bad trials, this load is an upper bound.
-
-If there are shorter duration trials, the logic is more complicated.
-
-##### Goal width
-
-A specific quantity based on width.
-A threshold value for a particular width.
-MUST be positive.
-
-This defines the exit condition for this search goal.
-
-Relevant bounds (of the final target) need to be this close
-before conditional throughput can be reported.
-
-##### Preceding targets
-
-A non-negative integer affecting the behavior of the controller.
-
-How many additional non-final targets to add.
-Each next preceding target has double width
-and min duration sum geometrically closer to initial trial duration.
-
-The usage of preceding targets is an important source
-of MLRsearch time savings (compared to simpler search algorithms).
-
-Having this value configurable lets the manager
-tweak the overall search duration based on presumed knowledge
-of SUT performance stability.
-
-### Controller internals
-
-Terms not directly corresponding to the controller's input nor output,
-but needed indirectly as dependencies of the conditional throughput
-definition.
-
-Following these definitions specifies virtually all of the controller
-(MLRsearch algorithm) logic.
-
-#### Pre-initial trials
-
-Up to three special trials executed at the start of the search.
-The first trial load is max load,
-subsequent trial load are computed from preceding trial
-forwarding rate.
-
-The main loop of the controller logic needs at least one trial result,
-and time is saved if the trial results are close to future conditional
-throughput values.
-
-The exact way to compute load for second and third trial
-(and whether even measure second or third trial)
-are not specified here, as the implementation details
-have negligible effect on the reported conditional throughput.
-
-{::comment}
- TODO: Still, recommend something like this:
- Loads need to fit several different initial targets at once.
- Duration is the largest among initial trial durations,
- loads are computed from forwarding rate an smallest loss ratio goal.
- Also, the initial target current width is set based on these.
-{:/comment}
-
-#### Search target
-
-A composite of 5 specific quantites (see subsections).
-Frequently called just target.
-
-Similar to (but distinct from) the search goal.
-
-Each search goal prescribes a final target,
-probably with a chain of preceding targets.
-
-More details in the Derived targets section.
-
-##### Target loss ratio
-
-Same as loss ratio of the corresponding goal.
-
-##### Target exceed ratio
-
-Same as exceed ratio of the corresponding goal.
-
-##### Target width
-
-Similar to goal width attribute.
-Doubled from goal width for each level of preceding target.
-
-##### Target min duration sum
-
-Similar to goal min duration sum attribute.
-Geometrically interpolated between
-initial target duration and goal min duration sum.
-
-##### Target trial duration
-
-When MLRsearch focuses on this target, it measures trials
-with this duration.
-The value is equal to the minimum of goal final trial duration
-and target min duration sum.
-
-Also, this value is used to classify trial results
-as short (if trial duration is shorter than this) or long.
-
-#### Derived targets
-
-After receiving the set of search goals,
-MLRsearch internally derives a set of search targets.
-
-The derived targets can be seen as forming a chain,
-from initial target to final target.
-The chain is linked by a reference from a target to its preceding
-(towarsds initial) target.
-
-The reference may be implemented as 6th attribute od target.
-
-##### Final target
-
-The final target is the target where the most of attribute values
-are directly copied from the coresponding search goal.
-Final target width is the same as goal width,
-final target trial duration is the same as goal final trial duration,
-and final target min duration sum is the same
-as the goal min duration sum.
-
-The conditional throughput is found when focusing on the final target.
-All non-final targets do not directly affect the conditional throughput,
-they are there just as an optimization.
-
-##### Preceding target
-
-Each target may have a preceding target.
-Goal attribute Preceding targets governs how many targets are created
-in addition to the final target corresponding to the search goal.
-
-Any preceding target has double width, meaning one balanced bisection
-is needed to reduce preceding target width to the next target width.
-
-Preceding target min duration sum is exponentially smaller,
-aiming for prescribed initial target min duration sum.
-
-Preceding target trial duration is either its min duration sum,
-or the corresponding goal's final trial duration, whichever is smaller.
-
-As the preceding min duration sum is shorter than the next duration sum,
-MLRsearch is able to achieve the preceding target width
-sooner (than with the next target min duration sum).
-
-This way an approximation of the conditional throughput is found,
-with the next target needing not as much time to improve the approximation
-(compared to not starting with the approximation).
-
-##### Initial target
-
-Initial target is a target without any other target preceding it.
-Initial target min duration sum is equal to the corresponding goal's
-initial trial duration.
-
-As a consequence, initial target trial duration is equal to its min duration sum.
-
-#### Trial classification
-
-Any trial result can be classified according to any target along two axes.
-
-The two classifications are independent.
-
-This classification is important for defining the conditional throughput.
-
-##### Short trial
-
-If the (measured) trial duration is shorter than
-the target trial duration, the trial is called long.
-
-##### Long trial
-
-If the (measured) trial duration is not shorter than
-the target trial duration, the trial is called long.
-
-##### Bad trial
-
-If the (measured) trial loss ratio is larger than the target loss ratio,
-the trial is called bad.
-
-For example, if the target loss ratio is zero,
-a trial is bad as soon as one frame was lost.
-
-##### Good trial
-
-If the (measured) trial loss ratio is not larger than the target loss ratio,
-the trial is called good.
-
-For example, if the target loss ratio is zero,
-a trial is good only when there were no frames lost.
-
-#### Load stat
-
-A composite of 8 quantities (see subsections)
-The quantites depend on a target and a load,
-and are computed from all trials measured at that load so far.
-
-The MLRsearch output is the conditional througput,
-which is a specific quantity based on load.
-As MLRsearch may measure multiple trials at the same load,
-and those trials may not have the same duration,
-we need a way to classify a set of trial results at the same load.
-
-As the logic is not as straightforward as in other parts
-of MLRsearch algorithm, it is best defined using the following
-derived quantities.
-
-Load stat is the composite for one load and one target.
-Set of load stats for one load an all targets is commonly called load stats.
-
-##### Long good duration sum
-
-Sum of durations of all long good trials
-(at this load, according to this target).
-
-##### Long bad duration sum
-
-Sum of durations of all long bad trials
-(at this load, according to this target).
-
-##### Short good duration sum
-
-Sum of durations of all short good trials
-(at this load, according to this target).
-
-##### Short bad duration sum
-
-Sum of durations of all short bad trials
-(at this load, according to this target).
-
-##### Effective bad duration sum
-
-One divided by tagret exceed ratio, that plus one.
-Short good duration sum divided by that.
-Short bad duration sum minus that, or zero if that would be negative.
-Long bad duration sum plus that is the effective bad duration sum.
-
-Effective bad duration sum is the long bad duration sum
-plus some fraction of short bad duration sum.
-The fraction is between zero and one (both possibly including).
-
-If there are no short good trials, effective bad duration sum
-becomes the duration sum of all bad trials (long or short).
-
-If an exceed ratio computed from short good duration sum
-and short bad duration sum is equal or smaller than the target exceed ratio,
-effective bad duration sum is equal to just long bad duration sum.
-
-Basically, short good trials can only lessen the impact
-of short bad trials, while short bad trials directly contribute
-(unless lessened).
-
-A typical example of why a goal needs higher final trial duration
-than initial trial duration is when SUT is expected to have large buffers,
-so a trial may be too short to see frame losses due to
-a buffer becoming full. So a short good trial does not give strong information.
-On the other hand, short bad trial is a strong hint SUT would lose many frames
-at that load and long duration.
-But if there is a mix of short bad and short good trials,
-MLRsearch should not cherry-pick only the short bad ones.
-
-The presented way of computing the effective bad duration sum
-aims to be a fair treatment of short good trials.
-
-If the target exceed ratio is zero, the given definition contains
-positive infinty as an intermediate value, but still simplifies
-to a finite result (long bad duration sum plus short bad duration sum).
-
-##### Missing duration sum
-
-The target min duration sum minus effective bad duration sum
-and minus long good duration sum, or zero if that would be negative.
-
-MLRsearch may need up to this duration sum of additional long trials
-before classifing the load.
-
-##### Optimistic exceed ratio
-
-The specific quantity based on exceed ratio, where bad duration sum is
-the effective bad duration sum, and good duration sum is
-the long good duration sum plus the missing duration sum.
-
-This is the value MLRsearch would compare to target exceed ratio
-assuming all of the missing duration sum ends up consisting of long good trials.
-
-If there was a bad long trial, optimistic exceed ratio
-becomes larger than zero.
-Additionally, if the target exceed ratio is zero, optimistic exceed ratio
-becomes larger than zero even on one short bad trial.
-
-##### Pessimistic exceed ratio
-
-The specific quantity based on exceed ratio, where bad duration sum is
-the effective bad duration sum plus the missing duration sum,
-and good duration sum is the long good duration sum.
-
-This is the value MLRsearch would compare to target exceed ratio
-assuming all of the missing duration sum ends up consisting of bad good trials.
-
-Note that if the missing duration sum is zero,
-optimistic exceed ratio becomes equal to pessimistic exceed ratio.
-
-This is the role target min duration sum has,
-it guarantees the two load exceed ratios eventually become the same.
-Otherwise, pessimistic exceed ratio
-is always bigger than the optimistic exceed ratio.
-
-Depending on trial results, the missing duration sum may not be large enough
-to change optimistic (or pessimistic) exceed ratio
-to move to the other side compared to target exceed ratio.
-In that case, MLRsearch does not need to measure more trials
-at this load when focusing on this target.
-
-#### Target bounds
-
-With respect to a target, some loads may be classified as upper or lower bound,
-and some of the bounds are treated as relevant.
-
-The subsequent parts of MLRsearch rely only on relevant bounds,
-without the need to classify other loads.
-
-##### Upper bound
-
-A load is classified as an upper bound for a target,
-if and only if both optimistic exceed ratio
-and pessimstic load exceed ratio are larger than the target exceed ratio.
-
-During the search, it is possible there is no upper bound,
-for example because every measured load still has too high
-missing duration sum.
-
-If the target exceed ratio is zero, and the load has at least one bad trial
-(short or long), the load becomes an upper bound.
-
-##### Lower bound
-
-A load is classified as a lower bound for a target,
-if and only if both optimistic exceed ratio
-and pessimstic load exceed ratio are no larger than the target exceed ratio.
-
-During the search, it is possible there is no lower bound,
-for example because every measured load still has too high
-missing duration sum.
-
-If the target exceed ratio is zero, all trials at the load of
-a lower bound must be good trials (short or long).
-
-Note that so far it is possible for a lower bound to be higher
-than an upper bound.
-
-##### Relevant upper bound
-
-For a target, a load is the relevant upper bound,
-if and only if it is an upper bound, and all other upper bounds
-are larger (as loads).
-
-In some cases, the max load when classified as a lower bound
-is also effectively treated as the relevant upper bound.
-(In that case both relevant bounds are equal.)
-
-If that happens for a final target at the end of the search,
-the controller output may contain max load as the relevant upper bound
-(even if the goal exceed ratio was not exceeded),
-signalling SUT performs well even at max load.
-
-If the target exceed ratio is zero, the relevant upper bound
-is the smallest load where a bad trial (short or long) has been measured.
-
-##### Relevant lower bound
-
-For a target, a load is the relevant lower bound if two conditions hold.
-Both optimistic exceed ratio and pessimstic load exceed ratio
-are no larger than the target exceed ratio,
-and there is no smaller load classified as an upper bound.
-
-This is a second place where MLRsearch is not symmetric
-(the first place was effective bad duration sum).
-
-While it is not likely for a MLRsearch to find a smaller upper bound
-and a larger load satisfying first condition for the lower bound,
-it still may happen and MLRsearch has to deal with it.
-The second condition makes sure the relevant lower bound
-is smaller than the relevant upper bound.
-
-In some cases, the min load when classified as an upper bound
-is also effectively treated as the relevant lower bound.
-(In that case both relevant bounds are equal.)
-
-If that happens for a final target at the end of the search,
-the controller output may contain min load as the relevant lower bound
-even if the exceed ratio was 'overstepped',
-signalizing the SUT does not even reach the minimal required performance.
-
-The manager has to make sure this is distingushed in report
-from cases where min rate is a legitimate conditional throughput
-(e.g. the exceed ratio was not overstepped at the min load).
-
-##### Relevant bounds
-
-The pair of the relevant lower bound and the relevant upper bound.
-
-Useful for determining the width of the relevant bounds.
-Any of the bounds may be the effective one (max load or min load).
-
-A goal is achieved (at the end of the search) when the final target's
-relevant bounds have width no larger than the goal width.
-
-#### Candidate selector
-
-A stateful object (a finite state machine)
-focusing on a single target, used to determine next trial input.
-
-Initialized for a pair of targets:
-the current target and its preceding target (if any).
-
-Private state (not shared with other selectors) consists of mode and flags.
-Public state (shared with all selectors) is the actual relevant bounds
-for both targets (current and precedinig).
-
-After accepting a trial result, each selector can nominate
-one candidate (or no candidate) for the next trial measurement.
-
-##### Current target
-
-This is the target this selector tries to achieve.
-
-##### Preceding target
-
-The target (if any) preceding to the current target.
-
-While this selector does not focus on the preceding target,
-the relevant bounds for the preceding target are used as hints
-when the current bound does not have enough of its relevant bounds.
-
-##### Candidate
-
-The trial input (if any) this selecor nominates.
-
-The trial duration attribute is always the current target trial duration.
-The trial load attribute depends on the selector state.
-
-Candidates have defined ordering, to simplify finding the winner.
-If load differs, the candidate with lower load is preferred.
-If load is the same but duration differs, the candidate
-with larger duration is preferred.
-
-##### Selector mode
-
-During its lifetime, selector proceeds through the following modes.
-In order, but some modes may be skipped or revisited.
-
-Each mode has its own strategy of determining the candidate load (if any).
-
-###### Waiting
-
-Not enough relevant bounds (even for the preceding target).
-In this mode, the selector abstains from nominating a candidate.
-
-This selector leaves this mode when preceding target's selector is done.
-
-###### Halving
-
-Candidate is in the middle of the relevant bounds of the preceding target.
-
-If the relevant bounds are narrow enough already, this mode is skipped.
-As the preceding target had double width, just one halving load
-needs to be measured.
-
-Selector uses a flag to avoid re-entering this mode
-once it finished measuring the halved load.
-
-###### Upgrading
-
-This mode activates when one relevant bound for the current target is present
-and there is a matching relevant bound of the preceding target
-within the current target width.
-Candidate is the load of the matching bound from the preceding target.
-
-At most one bound load is measured, depending on halving outcome.
-Private flags are used to avoid upgrading at later times
-once selector finished measuring the upgraded load.
-
-###### Extending
-
-Refined already but the other relevant bound for the current target
-is still missing.
-Nominate new candidate according to external search.
-Initial target selectors skip all previous modes.
-
-A private value is used to track the width to be used in next load extension
-(increasing geometrically).
-For initial target selectors, the starting width may be chosen
-based on pre-initial trial results.
-
-If both relevant bounds are present at the current load,
-but the lower bound is far away (compared to tracked width),
-the candidate from this mode is preferred (as long as the load
-is larger than the candidate load of bisecting mode).
-
-###### Bisecting
-
-Both relevant bounds for the current target are available, but they are too far
-from each other. Candidate is in the middle.
-
-Contrary to halving, the candidate load does not need to be at the exact middle.
-For example if the width of the current relevant bounds
-is three times as large as the target width,
-it is advantageous to split the interval in 1:2 ratio
-(choosing the lower candidate load), as it can save one bisect.
-
-###### Done
-
-Both relevant bounds for the current target are available,
-the width is no larger than the target width.
-No candidate.
-
-If a selector reaches the done state,
-it is still possible later trials invalidate its relevant lower bound
-(by proving a lower load is in fact a new uper bound),
-making the selector transition into extending or bisecting mode.
-
-##### Active selector
-
-Derived from a common goal, the earliest selector which nominates a candidate
-is considered to be the active selector for this goal.
-Candidates from other selectors of the same goal are ignored.
-
-It is quite possible selectors focusing on other goals
-have already found a lower bound relevant to multiple targets in a chain.
-In that case, we want the most-initial of the target selectors
-(not already in done mode) to have the nomination.
-
-Otherwise (when in extending mode and missun relevant upper bound)
-the closer-to-final selectors would nominate candidates
-at lower load but at too high duration sum,
-preventing some of the time savings.
-
-##### Winner
-
-If the candidate previously nominated by a selector was the one
-that got measured, the candidate is called a winner.
-
-A selector observing its previous candidate was a winer
-can use simplified logic when determining the mode,
-as it knows no other selectors may have changed the relevant loads unexpectedly.
-
-### Controller output
-
-The output object the controller returns to the manager
-is a mapping assigning each search goal its conditional output (if it exists).
-
-The controller MAY include more information (if manager accepts it),
-for example load stat at relevant bounds.
-
-There MAY be several ways how to communicate the fact a conditional output
-does not exist (e.g. min load is classified as an upper bound).
-The manager MUST NOT present min load as a conditional output in that case.
-
-If max load is a lower bound, it leads to a valid conditional output value.
-
-#### Conditional throughput
-
-The conditional throughput is the average of trial forwarding rates
-across long good trials measured at the (offered load classified as)
-relevant lower bound (for the goal, at the end of the search).
-The average is the weighted arithmetic mean, weighted by trial duration.
-
-If the goal exceed ratio is zero, the definition of the relevant bounds
-simplifies significantly.
-If additionally the goal loss ratio is zero,
-and the goal min duration sum is equal to goal final trial duration,
-conditional throughput becomes conditionally compliant with RFC 2544 throughput.
-If the goal final trial duration is at least 60 seconds,
-the conditional througput becomes unconditionally compliant
-with RFC 2544 throughput.
-
-# Problems
-
-## Long Test Duration
-
-Emergence of software DUTs, with frequent software updates and a
-number of different packet processing modes and configurations, drives
-the requirement of continuous test execution and bringing down the test
-execution time.
-
-In the context of characterising particular DUT's network performance, this
-calls for improving the time efficiency of throughput search.
-A vanilla bisection (at 60sec trial duration for unconditional [RFC2544]
-compliance) is slow, because most trials spend time quite far from the
-eventual throughput.
-
-[RFC2544] does not specify any stopping condition for throughput search,
-so users can trade-off between search duration and achieved precision.
-But, due to exponential behavior of bisection, small improvement
-in search duration needs relatively big sacrifice in the throughput precision.
-
-## DUT within SUT
-
-[RFC2285] defines:
-- *DUT* as
- - The network forwarding device to which stimulus is offered and
- response measured [RFC2285] (section 3.1.1).
-- *SUT* as
- - The collective set of network devices to which stimulus is offered
- as a single entity and response measured [RFC2285] (section 3.1.2).
-
-[RFC2544] specifies a test setup with an external tester stimulating the
-networking system, treating it either as a single DUT, or as a system
-of devices, an SUT.
-
-In case of software networking, the SUT consists of a software program
-processing packets (device of interest, the DUT),
-running on a server hardware and using operating system functions as appropriate,
-with server hardware resources shared across all programs
-and the operating system.
-
-DUT is effectively "nested" within SUT.
-
-Due to a shared multi-tenant nature of SUT, DUT is subject to
-interference (noise) coming from the operating system and any other
-software running on the same server. Some sources of noise can be
-eliminated (e.g. by pinning DUT program threads to specific CPU cores
-and isolating those cores to avoid context switching). But some
-noise remains after all such reasonable precautions are applied. This
-noise does negatively affect DUT's network performance. We refer to it
-as an *SUT noise*.
-
-DUT can also exhibit fluctuating performance itself, e.g. while performing
-some "stop the world" internal stateful processing. In many cases this
-may be an expected per-design behavior, as it would be observable even
-in a hypothetical scenario where all sources of SUT noise are
-eliminated. Such behavior affects trial results in a way similar to SUT
-noise. We use *noise* as a shorthand covering both *DUT fluctuations* and
-genuine SUT noise.
-
-A simple model of SUT performance consists of a baseline *noiseless performance*,
-and an additional noise. The baseline is assumed to be constant (enough).
-The noise varies in time, sometimes wildly. The noise can sometimes be negligible,
-but frequently it lowers the observed SUT performance in a trial.
-
-In this model, SUT does not have a single performance value, it has a spectrum.
-One end of the spectrum is the noiseless baseline,
-the other end is a *noiseful performance*. In practice, trial results
-close to the noiseful end of the spectrum happen only rarely.
-The worse performance, the more rarely it is seen in a trial.
-
-Focusing on DUT, the benchmarking effort should aim
-at eliminating only the SUT noise from SUT measurement.
-But that is not really possible, as there are no realistic enough models
-able to distinguish SUT noise from DUT fluctuations.
-
-However, assuming that a well-constructed SUT has the DUT as its
-performance bottleneck, the "DUT noiseless performance" can be defined
-as the noiseless end of SUT performance spectrum. (At least for
-throughput. For other quantities such as latency there will be an
-additive difference.) By this definition, DUT noiseless performance
-also minimizes the impact of DUT fluctuations.
-
-In this document, we reduce the "DUT within SUT" problem to estimating
-the noiseless end of SUT performance spectrum from a limited number of
-trial results.
-
-Any improvements to throughput search algorithm, aimed for better
-dealing with software networking SUT and DUT setup, should employ
-strategies recognizing the presence of SUT noise, and allow discovery of
-(proxies for) DUT noiseless performance
-at different levels of sensitivity to SUT noise.
-
-## Repeatability and Comparability
-
-[RFC2544] does not suggest to repeat throughput search. And from just one
-throughput value, it cannot be determined how repeatable that value is.
-In practice, poor repeatability is also the main cause of poor
-comparability, e.g. different benchmarking teams can test the same SUT
-but get different throughput values.
-
-[RFC2544] throughput requirements (60s trial, no tolerance to single frame loss)
-force the search to fluctuate close the noiseful end of SUT performance
-spectrum. As that end is affected by rare trials of significantly low
-performance, the resulting throughput repeatability is poor.
-
-The repeatability problem is the problem of defining a search procedure
-which reports more stable results
-(even if they can no longer be called "throughput" in [RFC2544] sense).
-According to baseline (noiseless) and noiseful model, better repeatability
-will be at the noiseless end of the spectrum.
-Therefore, solutions to the "DUT within SUT" problem
-will help also with the repeatability problem.
-
-Conversely, any alteration to [RFC2544] throughput search
-that improves repeatability should be considered
-as less dependent on the SUT noise.
-
-An alternative option is to simply run a search multiple times, and report some
-statistics (e.g. average and standard deviation). This can be used
-for "important" tests, but it makes the search duration problem even
-more pronounced.
-
-## Throughput with Non-Zero Loss
-
-[RFC1242] (section 3.17) defines throughput as:
- The maximum rate at which none of the offered frames
- are dropped by the device.
-
-and then it says:
- Since even the loss of one frame in a
- data stream can cause significant delays while
- waiting for the higher level protocols to time out,
- it is useful to know the actual maximum data
- rate that the device can support.
-
-Contrary to that, many benchmarking teams settle with non-zero
-(small) loss ratio as the goal for a "throughput rate".
-
-Motivations are many: modern protocols tolerate frame loss better;
-trials nowadays send way more frames within the same duration;
-impact of rare noise bursts is smaller as the baseline performance
-can compensate somewhat by keeping the loss ratio below the goal;
-if SUT noise with "ideal DUT" is known, it can be set as the loss ratio goal.
-
-Regardless of validity of any and all similar motivations,
-support for non-zero loss goals makes any search algorithm more user-friendly.
-[RFC2544] throughput is not friendly in this regard.
-
-Searching for multiple goal loss ratios also helps to describe the SUT
-performance better than a single goal result. Repeated wide gap between
-zero and non-zero loss conditional throughputs indicates
-the noise has a large impact on the overall SUT performance.
-
-It is easy to modify the vanilla bisection to find a lower bound
-for intended load that satisfies a non-zero-loss goal,
-but it is not that obvious how to search for multiple goals at once,
-hence the support for multiple loss goals remains a problem.
-
-## Inconsistent Trial Results
-
-While performing throughput search by executing a sequence of
-measurement trials, there is a risk of encountering inconsistencies
-between trial results.
-
-The plain bisection never encounters inconsistent trials.
-But [RFC2544] hints about possibility if inconsistent trial results in two places.
-The first place is section 24 where full trial durations are required, presumably
-because they can be inconsistent with results from shorter trial durations.
-The second place is section 26.3 where two successive zero-loss trials
-are recommended, presumably because after one zero-loss trial
-there can be subsequent inconsistent non-zero-loss trial.
-
-Examples include:
-
-- a trial at the same load (same or different trial duration) results
- in a different packet loss ratio.
-- a trial at higher load (same or different trial duration) results
- in a smaller packet loss ratio.
-
-Any robust throughput search algorithm needs to decide how to continue
-the search in presence of such inconsistencies.
-Definitions of throughput in [RFC1242] and [RFC2544] are not specific enough
-to imply a unique way of handling such inconsistencies.
-
-Ideally, there will be a definition of a quantity which both generalizes
-throughput for non-zero-loss (and other possible repeatibility enhancements),
-while being precise enough to force a specific way to resolve trial
-inconsistencies.
-But until such definition is agreed upon, the correct way to handle
-inconsistent trial results remains an open problem.
-
-# How the problems are addressed
-
-Configurable loss ratio in MLRsearch search goals are there
-in direct support for non-zero-loss conditional throughput.
-In practice the conditional throughput results' stability
-increases with higher loss ratio goals.
-
-Multiple trials with noise tolerance enhancement,
-as implemented in MLRsearch using non-zero goal exceed ratio value,
-also indirectly increases the result stability.
-That allows MLRsearch to achieve all the benefits
-of Binary Search with Loss Verification,
-as recommended in [RFC9004] (section 6.2)
-and specified in [TST009] (section 12.3.3).
-
-The main factor improving the overall search time is the introduction
-of preceding targets. Less impactful time savings
-are achieved by pre-initial trials, halving mode
-and smart splitting in bisecting mode.
-
-In several places, MLRsearch is "conservative" when handling
-(potentially) inconsistent results. This includes the requirement
-for the relevant lower bound to be smaller than any upper bound,
-the unequal handling of good and bad short trials,
-and preference to lower load when choosing the winner among candidates.
-
-While this does no guarantee good search stability
-(goals focusing on higher loads may still invalidate existing bounds
-simply by requiring larger min duration sums),
-it lowers the change of SUT having an area of poorer performance
-below the reported conditional througput loads.
-In any case, the definition of conditional throughput
-is precise enough to dictate "conservative" handling
-of trial inconsistencies.
-
-# IANA Considerations
-
-No requests of IANA.
-
-# Security Considerations
-
-Benchmarking activities as described in this memo are limited to
-technology characterization of a DUT/SUT using controlled stimuli in a
-laboratory environment, with dedicated address space and the constraints
-specified in the sections above.
-
-The benchmarking network topology will be an independent test setup and
-MUST NOT be connected to devices that may forward the test traffic into
-a production network or misroute traffic to the test management network.
-
-Further, benchmarking is performed on a "black-box" basis, relying
-solely on measurements observable external to the DUT/SUT.
-
-Special capabilities SHOULD NOT exist in the DUT/SUT specifically for
-benchmarking purposes. Any implications for network security arising
-from the DUT/SUT SHOULD be identical in the lab and in production
-networks.
-
-# Acknowledgements
-
-Many thanks to Alec Hothan of OPNFV NFVbench project for thorough
-review and numerous useful comments and suggestions.
-
---- back
--- /dev/null
+---
+title: Multiple Loss Ratio Search
+abbrev: MLRsearch
+docname: draft-ietf-bmwg-mlrsearch-05
+date: 2023-10-23
+
+ipr: trust200902
+area: ops
+wg: Benchmarking Working Group
+kw: Internet-Draft
+cat: info
+
+coding: us-ascii
+pi: # can use array (if all yes) or hash here
+ toc: yes
+ sortrefs: # defaults to yes
+ symrefs: yes
+
+author:
+ -
+ ins: M. Konstantynowicz
+ name: Maciek Konstantynowicz
+ org: Cisco Systems
+ email: mkonstan@cisco.com
+ -
+ ins: V. Polak
+ name: Vratko Polak
+ org: Cisco Systems
+ email: vrpolak@cisco.com
+
+normative:
+ RFC1242:
+ RFC2285:
+ RFC2544:
+ RFC9004:
+
+informative:
+ TST009:
+ target: https://www.etsi.org/deliver/etsi_gs/NFV-TST/001_099/009/03.04.01_60/gs_NFV-TST009v030401p.pdf
+ title: "TST 009"
+ FDio-CSIT-MLRsearch:
+ target: https://csit.fd.io/cdocs/methodology/measurements/data_plane_throughput/mlr_search/
+ title: "FD.io CSIT Test Methodology - MLRsearch"
+ date: 2023-10
+ PyPI-MLRsearch:
+ target: https://pypi.org/project/MLRsearch/0.4.1/
+ title: "MLRsearch 0.4.1, Python Package Index"
+ date: 2021-07
+
+--- abstract
+
+This document proposes extensions to [RFC2544] throughput search by
+defining a new methodology called Multiple Loss Ratio search
+(MLRsearch). The main objectives of MLRsearch are to minimize the
+total search duration, to support searching for multiple loss ratios
+and to improve results repeatability and comparability.
+
+The main motivation behind extending [RFC2544] is the new set of challenges
+and requirements posed by evaluating and testing software based networking
+systems, specifically their data planes.
+
+MLRsearch offers several ways to address these challenges, giving user
+configuration options to select their preferred way.
+
+--- middle
+
+{::comment}
+ As we use kramdown to convert from markdown,
+ we use this way of marking comments not to be visible in rendered draft.
+ https://stackoverflow.com/a/42323390
+ If other engine is used, convert to this way:
+ https://stackoverflow.com/a/20885980
+{:/comment}
+
+# Purpose and Scope
+
+The purpose of this document is to describe Multiple Loss Ratio search
+(MLRsearch), a data plane throughput search methodology optimized for software
+networking DUTs.
+
+Applying vanilla [RFC2544] throughput bisection to software DUTs
+results in a number of problems:
+
+- Binary search takes too long as most of trials are done far from the
+ eventually found throughput.
+- The required final trial duration and pauses between trials
+ prolong the overall search duration.
+- Software DUTs show noisy trial results,
+ leading to a big spread of possible discovered throughput values.
+- Throughput requires loss of exactly zero frames, but the industry
+ frequently allows for small but non-zero losses.
+- The definition of throughput is not clear when trial results are inconsistent.
+
+MLRsearch library aims to address these problems by applying the following set
+of enhancements:
+
+- Allow multiple shorter trials instead of one big trial per load.
+ - Optionally, tolerate a percentage of trial result with higher loss.
+- Allow searching for multiple search goals, with differing loss ratios.
+ - Any trial result can affect each search goal in principle.
+- Insert multiple coarse targets for each search goal, earlier ones need
+ to spend less time on trials.
+ - Earlier targets also aim for lesser precision.
+ - Use Forwarding Rate (FR) at maximum offered load
+ [RFC2285] (section 3.6.2) to initialize the initial targets.
+- Take care when dealing with inconsistent trial results.
+ - Reported throughput is smaller than smallest load with high loss.
+ - Smaller load candidates are measured first.
+- Apply several load selection heuristics to save even more time
+ by trying hard to avoid unnecessarily narrow bounds.
+
+Some of these enhancements are formalized as MLRsearch specification,
+the remaining enhancements are treated as implementation details,
+thus achieving high comparability without limiting future improvements.
+
+MLRsearch configuration options are flexible enough to
+support both conservative settings and aggressive settings.
+Where the conservative settings lead to results
+unconditionally compliant with [RFC2544],
+but longer search duration and worse repeatability.
+Conversely, aggressive settings lead to shorter search duration
+and better repeatability, but the results are not compliant with [RFC2544].
+
+No part of [RFC2544] is intended to be obsoleted by this document.
+
+# Identified Problems
+
+This chapter describes the problems affecting usability
+of various preformance testing methodologies,
+mainly a binary search for [RFC2544] unconditionally compliant throughput.
+
+The last chapter will summarize how the problems are addressed,
+the middle chapters provide explanations and definitions needed for that.
+
+## Long Search Duration
+
+Emergence of software DUTs, with frequent software updates and a
+number of different frame processing modes and configurations,
+has increased both the number of performance tests requred to verify DUT update
+and the frequency of running those tests.
+This makes the overall test execution time even more important than before.
+
+In the context of characterising particular DUT's network performance,
+this calls for improving the time efficiency of throughput search.
+A vanilla bisection (at 60sec trial duration for unconditional [RFC2544]
+compliance) is slow, because most trials spend time quite far from the
+eventual throughput.
+
+[RFC2544] does not specify any stopping condition for throughput search,
+so users can trade-off between search duration and achieved precision.
+But, due to logarithmic nature of bisection, even small improvement
+in search duration needs relatively big sacrifice in the precision of the
+discovered throughput.
+
+## DUT in SUT
+
+[RFC2285] defines:
+- DUT as
+ - The network forwarding device to which stimulus is offered and
+ response measured [RFC2285] (section 3.1.1).
+- SUT as
+ - The collective set of network devices to which stimulus is offered
+ as a single entity and response measured [RFC2285] (section 3.1.2).
+
+[RFC2544] specifies a test setup with an external tester stimulating the
+networking system, treating it either as a single DUT, or as a system
+of devices, an SUT.
+
+In case of software networking, the SUT consists nt only of the DUT
+as a software program processing frames, but also of
+a server hardware and operating system functions,
+with server hardware resources shared across all programs
+and the operating system running on the same server.
+
+The DUT is effectively nested within the rest of the SUT.
+
+Due to a shared multi-tenant nature of SUT, DUT is subject to
+possible interference coming from the operating system and any other
+software running on the same server. Some sources of such interference
+can be to some degree eliminated, e.g. by pinning DUT program threads
+to specific CPU cores and isolating those cores to avoid context switching.
+But some level of adverse effects may remain even after
+all such reasonable precautions are applied.
+These effects affect DUT's network performance negatively.
+As the effects are hard to predict in general, they have impact similar to
+what other engineering disciplines define as a noise.
+Thus, all such effects are called an SUT noise.
+
+DUT can also exhibit fluctuating performance itself, for reasons
+not related to the rest of SUT, for example due to pauses in execution
+as needed for internal stateful processing. In many cases this
+may be an expected per-design behavior, as it would be observable even
+in a hypothetical scenario where all sources of SUT noise are eliminated.
+Such behavior affects trial results in a way similar to SUT noise.
+As the two phenomenons are hard to destinguish,
+this document uses the word noise as a shorthand covering both
+this internal DUT performance fluctuations and genuine SUT noise.
+
+A simple model of SUT performance consists of an idealized noiseless performance,
+and additional noise effects. The noiseless performance is assumed to be constant,
+all observed performance variations are due to noise.
+The impact of the noise can vary in time, sometimes wildly,
+even within a single trial.
+The noise can sometimes be negligible, but frequently
+it lowers the observed SUT performance as observed in trial results.
+
+In this model, SUT does not have a single performance value, it has a spectrum.
+One end of the spectrum is the idealized noiseless performance value,
+the other end can be called a noiseful performance. In practice, trial results
+close to the noiseful end of the spectrum happen only rarely.
+The worse the performance value is, the more rarely it is seen in a trial.
+Therefore, the extreme noiseful end of SUT spectrum is not really observable
+among trial results. Also, the extreme noiseless end of SUT spectrum
+is unlikely to be observable, this time because some small noise effects
+are likely to occur multiple times during a trial.
+
+Unless specified otherwise, this document talks about potentially observable
+ends of the SUT performance spectrum, not about the extreme ones.
+
+Focusing on DUT, the benchmarking effort should aim
+at eliminating only the SUT noise from SUT measurements.
+In practice that is not really possible, as based on authors experience
+and available literature, there are no realistic enough models
+able to distinguish SUT noise from DUT fluctuations.
+
+However, assuming that a well-constructed SUT has the DUT as its
+performance bottleneck, the DUT ideal noiseless performance can be defined
+as the noiseless end of SUT performance spectrum. At least for
+throughput. For other performance quantities such as latency there may be an
+additive difference.
+
+Note that by this definition, DUT noiseless performance
+also minimizes the impact of DUT fluctuations, as much as realistically possible
+for a given trial duration.
+
+In this document, we reduce the DUT in SUT problem to estimating
+the noiseless end of SUT performance spectrum from a limited number of
+trial results.
+
+Any improvements to throughput search algorithm, aimed for better
+dealing with software networking SUT and DUT setup, should employ
+strategies recognizing the presence of SUT noise, and allow discovery of
+(proxies for) DUT noiseless performance
+at different levels of sensitivity to SUT noise.
+
+## Repeatability and Comparability
+
+[RFC2544] does not suggest to repeat throughput search. And from just one
+discovered throughput value, it cannot be determined how repeatable that value is.
+In practice, poor repeatability is also the main cause of poor
+comparability, that is different benchmarking teams can test the same SUT
+but get throughput values differing more than expected from search precision.
+
+[RFC2544] throughput requirements (60 seconds trial and
+no tolerance of a single frame loss) affect the throughput results
+in the following way.
+The SUT behavior close to the noiseful end of its performance spectrum
+consists of rare occasions of significantly low performance,
+but the long trial duration makes those occasions not so rare on the trial level.
+Therefore, the binary search results tend to wander away from the noiseless end
+of SUT performance spectrum, more frequently and more widely than shorter
+trials would, thus resulting in poor throughput repeatability.
+
+The repeatability problem can be addressed by defining a search procedure
+which reports more stable results,
+even if they can no longer be called throughput in [RFC2544] sense.
+According to the SUT performance spectrum model, better repeatability
+will be at the noiseless end of the spectrum.
+Therefore, solutions to the DUT in SUT problem
+will help also with the repeatability problem.
+
+Conversely, any alteration to [RFC2544] throughput search
+that improves repeatability should be considered
+as less dependent on the SUT noise.
+
+An alternative option is to simply run a search multiple times, and report some
+statistics (e.g. average and standard deviation). This can be used
+for a subset of tests deemed more important,
+but it makes the search duration problem even more pronounced.
+
+## Throughput with Non-Zero Loss
+
+[RFC1242] (section 3.17) defines throughput as:
+ The maximum rate at which none of the offered frames
+ are dropped by the device.
+
+Then, it says:
+ Since even the loss of one frame in a
+ data stream can cause significant delays while
+ waiting for the higher level protocols to time out,
+ it is useful to know the actual maximum data
+ rate that the device can support.
+
+Contrary to that, many benchmarking teams settle with small, non-zero
+loss ratio as the goal for a their load search.
+
+Motivations are many:
+
+- Modern protocols tolerate frame loss better,
+ compared to the time when [RFC1242] and [RFC2544] were specified.
+
+- Trials nowadays send way more frames within the same duration,
+ increasing the chance small SUT performance fluctuatios
+ is enough to cause frame loss.
+
+- Small bursts of frame loss caused by noise have otherwise smaller impact
+ on the average frame loss ratio ovserved in the trial,
+ as during other parts of the same trial the SUT may work mroe closely
+ to its noiseless performance, thus perhaps lowering the trial loss ratio
+ below the goal loss ratio value.
+
+- If an approximation of the SUT noise impact on the trial loss ratio is known,
+ it can be set as the goal loss ratio.
+
+Regardless of validity of any and all similar motivations,
+support for non-zero loss goals makes any search algorithm more user friendly.
+[RFC2544] throughput is not user friendly in this regard.
+
+Assuming users are allowed to specify the goal loss ratio value,
+the usefulness is enhanced even more if users can specify multiple
+loss ratio values, especially when a single search can find all relevant bounds.
+
+Searching for multiple search goals also helps to describe the SUT performance
+spectrum better than a single search goal result.
+For example, repeated wide gap between zero and non-zero loss loads
+indicates the noise has a large impact on the observed performance,
+which is not evident from a single goal load search procedure result.
+
+It is easy to modify the vanilla bisection to find a lower bound
+for intended load that satisfies a non-zero goal loss ratio.
+But it is not that obvious how to search for multiple goals at once,
+hence the support for multiple search goals remains a problem.
+
+## Inconsistent Trial Results
+
+While performing throughput search by executing a sequence of
+measurement trials, there is a risk of encountering inconsistencies
+between trial results.
+
+The plain bisection never encounters inconsistent trials.
+But [RFC2544] hints about possibility of inconsistent trial results,
+in two places in its text.
+The first place is section 24, where full trial durations are required,
+presumably because they can be inconsistent with results
+from shorter trial durations.
+The second place is section 26.3, where two successive zero-loss trials
+are recommended, presumably because after one zero-loss trial
+there can be subsequent inconsistent non-zero-loss trial.
+
+Examples include:
+
+- A trial at the same load (same or different trial duration) results
+ in a different trial loss ratio.
+- A trial at higher load (same or different trial duration) results
+ in a smaller trial loss ratio.
+
+Any robust throughput search algorithm needs to decide how to continue
+the search in presence of such inconsistencies.
+Definitions of throughput in [RFC1242] and [RFC2544] are not specific enough
+to imply a unique way of handling such inconsistencies.
+
+Ideally, there will be a definition of a new quantity which both generalizes
+throughput for non-zero-loss (and other possible repeatibility enhancements),
+while being precise enough to force a specific way to resolve trial result
+inconsistencies.
+But until such definition is agreed upon, the correct way to handle
+inconsistent trial results remains an open problem.
+
+# MLRsearch Specification
+
+This chapter focuses on technical definitions needed for evaluating
+whether a particular test procedure adheres to MLRsearch specification.
+
+For motivations, explanations, and other comments see other chapters.
+
+## MLRsearch Architecture
+
+MLRsearch architecture consists of three main components:
+the manager, the controller and the measurer.
+Presence of other components (mainly the SUT) is also implied.
+
+While the manager and the measurer can be seen a abstractions
+present in any testing procedure, the behavior of the controller
+is what distinguishes MLRsearch algorithms from other search procedures.
+
+### Measurer
+
+The measurer is the component which performs one trial
+as described in [RFC2544] section 23, when requested by the controller.
+
+Specifically, one call to the measurer accepts a trial load value
+and trial duration value, performs the trial, and returns
+the measured trial loss ratio, and optionally a different duration value.
+
+It is responsibility of the measurer to uphold any requirements
+and assumptions present in MLRsearch specification
+(e.g. trial forwarding ratio not being larger than one).
+Implementers have some freedom, for example in the way they deal with
+duplicated frames, or what to return if tester sent zero frames towards SUT.
+Implementations are RECOMMENDED to document their behavior
+related to such freedoms in as detailed way as possible
+
+Implemenations MUST document any deviations from RFC documents,
+for example if the wait time around traffic
+is shorter than what [RFC2544] section 23 specifies.
+
+### Controller
+
+The controller is the component of MLRsearch architecture
+that is called by the manager (just once), calls the measurer
+(usually multiple times in succession),
+and returns the result of the search to the manager.
+
+The only required argument in the call to the controller
+is a list of search goals. For the structure of the search result,
+see subsection Search Result.
+
+### Manager
+
+The manager is the component that initializes SUT, traffic generator
+(tester in [RFC2544]), the measurer and the controller
+with intended configurations. It then hands over the execution
+to the controller and receives its result.
+
+Creation of reports of appropriate format can also be understood
+as the responsibility of the manager.
+
+## Units
+
+The specification deals with physical quantities, so it is assumed
+each numeric value is accompanied by an appropriate physical unit.
+
+The specification does not state which unit is appropriate,
+but implementations MUST make it explicit which unit is used
+for each value provided or received by the user.
+
+For example, load quantities (including the conditional throughput)
+returned by the controller are defined to be based on single-interface
+(unidirectional) loads. For bidirectional traffic, users are likely
+to expect bidirectional throughput quantities, so the manager is responsible
+for making its report clear.
+
+## SUT
+
+As defined in [RFC2285]:
+The collective set of network devices to which stimulus is offered
+as a single entity and response measured.
+
+## Trial
+
+A trial is the part of test described in [RFC2544] section 23.
+
+### Trial Load
+
+Trial load is the intended constant load for a trial.
+
+Load is the quantity implied by Constant Load of [RFC1242],
+Data Rate of [RFC2544] and Intended Load of [RFC2285].
+All three specify this value applies to one (input or output) interface.
+
+### Trial Duration
+
+Trial duration is the intended duration of the traffic for a trial.
+
+In general, this general quantity does not include any preparation nor waiting
+described in section 23 of [RFC2544].
+
+However, the measurer MAY return a duration value different
+from the intended duration. This may be useful for users
+who want to control the overal search duration, not just the traffic part of it.
+The manager MUST report how does the measurer computes the returned duration
+values in that case.
+
+### Trial Forwarding Ratio
+
+Trial forwarding ratio is dimensionless floating point value,
+assumed to be between 0.0 and 1.0, both including.
+It is computed as the number of frames forwarded by SUT, divided by
+the number of frames that should have been forwarded during the trial.
+
+Note that, contrary to load, frame counts used to compute
+trial forwarding ratio are aggregates over all SUT ports.
+
+Questions around what is the correct number of frames
+that should have been forwarded it outside of the scope of this document.
+E.g. what should the measurer return when it detects
+that the offered load differs significantly from the intended load.
+
+It is RECOMMENDED implementations return an irregular goal result
+if they detect questionable (in comparability sense) trial results
+affecting their goal result.
+
+### Trial Loss Ratio
+
+Trial loss ratio is equal to one minus the trial forwarding ratio.
+
+### Trial Forwarding Rate
+
+The trial forwarding rate is the trial load multiplied by
+the trial forwarding ratio.
+
+Note that this is very similar, but not identical to Forwarding Rate
+as defined in [RFC2285] section 3.6.1, as that definition
+is specific to one output interface, while trial forwarding ratio
+is based on frame counts aggregated over all SUT interfaces.
+
+## Traffic profile
+
+Any other specifics (besides trial load and trial duration)
+the measurer needs to perform the trial are understood as a composite
+called the traffic profile.
+All its attributes are assumed to be constant during the search,
+and the composite is configured on the measurer by the manager
+before the search starts.
+
+Traffic profile is REQUIRED by [RFC2544] to contain some specific quantities,
+for example frame size.
+Several more specific quantities may be RECOMMENDED.
+
+Depending on SUT configuration, e.g. when testing specific protocols,
+additional values need to be included in the traffic profile
+and in the test report. See other IETF documents.
+
+## Search Goal
+
+A search goal is one item of the list required as an argument
+when the manager calls the controller.
+
+Each search goal is composite consisting of several attributes,
+some of them are required.
+Implementations are free to add their own attributes.
+
+Subsections list all required attributes and one recommended attribute.
+
+The meaning of the attributes is formally given only by their effect
+on the computation of the attributes of the goal result.
+The subsections do contain a short informal description,
+but see other chapters for more in-depth explanations.
+
+### Goal Final Trial Duration
+
+A threshold value for trial durations.
+REQUIRED attribute, MUST be positive.
+
+Informally, the conditional throughput for this goal will be computed
+only from trial results from trials as long as this.
+
+### Goal Duration Sum
+
+A threshold value for a particular sum of trial durations.
+REQUIRED attribute, MUST be positive.
+
+This uses the duration values returned by the measurer,
+in case it returns something else than the intended durations
+for the traffic part of the search.
+
+Informally, even at looking only at trials done at this goal's
+final trial duration, MLRsearch may spend up to this time measuring
+the same load value.
+
+### Goal Loss Ratio
+
+A threshold value for trial loss ratios.
+REQUIRED attribute, MUST be non-negative and smaller than one.
+
+Informally, if a load causes too many trials with trial results larger than this,
+the conditional throughput for this goal will be smaller than that load.
+
+### Goal Exceed Ratio
+
+A threshold value for particular ratio of duration sums.
+REQUIRED attribute, MUST be non-negative and smaller than one.
+
+This uses the duration values returned by the measurer,
+in case it returns something else than the intended durations
+for the traffic part of the search.
+
+Informally, this acts as the q-value for a quantile when selecting
+the forwarding rate of which trial result becomes the conditional throughput.
+For example, when the goal exceed ratio is 0.5 and MLRsearch
+happened to use the whole goal duration sum when determining conditional
+throughput, it means the conditional throughput is the median
+of trial forwarding rates.
+In practice, MLRsearch may stop measuring a load before the goal duration sum
+is reached, and the conditional throughput in that case frequently
+is the worst trial still not exceeding the goal loss ratio.
+If the goal duration sum is no larger than the goal fina trial duration,
+MLRsearch performs only one trial per load (unless other goals need more)
+and the goal exceed ratio has no effect on the search result.
+
+### Goal Width
+
+A value used as a threshold for telling when two trial load values
+are close enough.
+
+RECOMMENDED attribute, positive. Implementations without this attribute
+MUST give the manager other ways to control the search exit condition.
+
+Absolute load difference and relative load difference are two popular choices,
+but implementations may choose a different way to specify width.
+
+Informally, this acts as a stopping condition, controling the precision
+of the search. The search stops if every goal has reached its precision.
+
+## Search Result
+
+Search result is a single composite object returned from the controller
+to the manager.
+It is a mapping from the search goals (see section Search Goal) into goal results
+(see section Goal Result).
+The mapping MUST map from all the search goals present in the controller input.
+
+Each search goal instance is mapped to a goal result instance.
+Multiple search goal instances may map to the same goal result instance.
+
+## Goal Result
+
+Goal result is a composite object consisting of several attributes.
+All attributes are related to the same search goal, the one search goal instance
+the Search Result is mapping into this instance of the Goal Result.
+
+Some of the attributes are required, some are recommended,
+implementations are free to add their own.
+
+The subsections define attributes for regular goal result.
+Implementations are free to define their own irregular goal results,
+but the manager MUST report them clearly as not regular according to this section.
+
+A typical irregular result is when all trials at maximum offered load
+have zero loss, as the relevant upper bound does not exist in that case.
+
+### Relevant Upper Bound
+
+Relevant upper bound is the intended load value that is classified
+at the end of the search as the relevant upper bound (see Appendix A)
+for this goal.
+This is a REQUIRED attribute.
+
+Informally, this is the smallest intended load that failed to uphold
+all the requirements of this search goal, mainly the goal loss ratio
+in combination with the goal exceed ratio.
+
+### Relevant Lower Bound
+
+Relevant lower bound is the intended load value that got classified
+(after all trials) as the relevant lower bound (see Appendix A) for this goal.
+This is a REQUIRED attribute.
+
+The distance between the relevant lower bound and the relevant upper bound
+MUST NOT be larger than the goal width, for a regular goal result,
+if the implementation offers width as a goal attribute.
+
+Informally, this is the smallest intended load that managed to uphold
+all the requirements of this search goal, mainly the goal loss ratio
+in combination with the goal exceed ratio, while not being larger
+than the relevant upper bound.
+
+### Conditional Throughput
+
+The conditional throughput (see Appendix B) as evaluated
+at the relevant lower bound.
+This is a RECOMMENDED attribute.
+
+Informally, a typical forwarding rate expected to be seen
+at the relevant lower bound. But frequently just a conservative estimate thereof,
+as MLRsearch implementations tend to stop gathering more data
+as soon as they confirm this estimate cannot get worse within
+the goal duration sum.
+
+# MLRsearch Explanations
+
+This chapter focuses on intuitions and motivations
+and skips over some important details.
+
+Familiarity with the MLRsearch specification is not required here,
+so this chapter can act as an introduction.
+For example, this chapter start talking about tightest lower bounds
+before it is ready to talk about the relevant lower bound from the specification.
+
+## MLRsearch Versions
+
+The MLRsearch algorithm has been developed in a code-first approach,
+a Python library has been created, debugged and used in production
+before first descriptions (even informal) were published.
+In fact, multiple versions of the library were used in production
+over past few years, and later code was usually not compatible
+with earlier descriptions.
+
+The code in (any version of) MLRsearch library fully determines
+the search process (for given configuration parameters),
+leaving no space for deviations.
+MLRsearch as a name for a broad class of possible algorithms
+leaves plenty of space for future improvements, at the cost
+of poor comparability of results of different MLRsearch implementations.
+
+This document aspires to prescribe a MLRsearch specification
+in a way that restricts the important parts related to comparability,
+while leaving other parts vague enough so implementations can improve freely.
+
+## Exit Condition
+
+[RFC2544] prescribes that after performing one trial at a specific offered load,
+the next offered load should be larger or smaller, based on frame loss.
+
+The usual implementation uses binary search. Here a lossy trial becomes
+a new upper bound, a lossless trial becomes a new lower bound.
+The span of values between the tightest lower bound and the tightest upper bound
+forms an interval of possible results,
+and after each trial the width of that interval halves.
+
+Usually the binary search implementation tracks only the two tightest bounds,
+simply calling them bounds, but the old values still remain valid bounds,
+just not as tight as the new ones.
+
+After some number of trials, the tightest lower bound becomes the throughput.
+[RFC2544] does not specify when (if ever) should the search stop.
+
+MLRsearch library introduces a concept of goal width. The search stops
+when the distance between the tightest upper bound and the tightest lower bound
+is smaller than a user-configured value called goal width from now on.
+In other words, interval width has to be smaller than goal width
+at the end of the search.
+
+This goal width value therefore determines the precision of the result.
+As MLRsearch specification requires a particular structure of the result,
+the result itself does contain enough information to determine its precision,
+thus it is not required to report the goal width value.
+
+This allows MLRsearch implementations to use exit conditions
+different from goal width.
+The MLRsearch specification only REQUIRES the search procedure
+to always finish in a finite time, regardless of possible trial results.
+
+## Load Classification
+
+MLRsearch keeps the basic logic of binary search (tracking tightest bounds,
+measuring at the middle), perhaps with minor technical clarifications.
+The algorithm chooses an intended load (as opposed to offered load),
+the interval between bounds does not need to be split exactly in two equal halves,
+and the final reported structure specifies both bounds
+(optionally also the conditional throughput at the lower bound, defined later).
+
+The biggest difference is that in order to classify a load
+as an upper or lower bound, MLRsearch may need more than one trial
+(depending on configuration options) to be performed at the same intended load.
+
+As a consequence, even if a load already does have few trial results,
+it still may be classified as undecided, neither a lower bound nor an upper bound.
+
+Explanation of the classification logic is given in the next chatper,
+as it relies heavily on other sections of this chapter.
+
+For repeatability and comparability reasons, it is important that
+given a set of trial results, all implementations of MLRsearch
+classify the load in an equivalent way.
+
+## Loss Ratios
+
+Next difference is in goals of the search. [RFC2544] has a single goal,
+based on classifying full-length trials as either loss-less or lossy.
+
+As the name suggests, MLRsearch can seach for multiple goals, differing in their
+loss ratios. Precise definition of goal loss ratio will be given later.
+The [RFC2544] throughput goal then simply becomes a zero goal loss ratio.
+Different goals also may have different goal width.
+
+A set of trial results for one specific intended load value
+can classify the load as an upper bound for some goals, but a lower bound
+for some other goals, and undecided for the rest of the goals.
+
+Therefore, the load classification depends not only on ttrial results,
+but also on the goal. The overall search procedure becomes more complicated
+(compared to binary search with a single goal),
+but most of the complications do not affect the final result,
+except for one phenomenon, loss inversion.
+
+## Loss Inversion
+
+In [RFC2544] throuhput search using bisection, any load with lossy trial
+becomes a hard upper bound, meaning every subsequent trial has smaller
+intended load.
+
+But in MLRsearch, a load that is classified as an upper bound for one goal
+may still be a lower bound for another goal, and due to that other goal
+MLRsearch will probably perform trials at even higher loads.
+What to do when all such higher load trials happen to have zero loss?
+Does it mean the earlier upper bound was not real?
+Does it mean the later lossless trials are not considered a lower bound?
+Surely we do not want to have an upper bound at a load smaller than a lower bound.
+
+MLRsearch is conservative in these situations.
+The upper bound is considered real, and the lossless trials at higher loads
+are considered to be a coincidence, at least when computing the final result.
+
+This is formalized using new notions, the relevant upper bound and
+the relevant lower bound.
+Load classification is still based just on the set of trial results
+at a given intended load (trials at other loads are ignored),
+making it possible to have a lower load classified as an upper bound
+and a higher load classified as a lower bound (for the same goal).
+The relevant upper bound (for a goal) is the smallest load classified
+as an upper bound. But the relevant lower bound is not simply
+the largest among lower bounds. It is the largest load among loads
+that are lower bounds while also being smaller than the relevant upper bound.
+
+With these definitions, the relevant lower bound is always smaller
+than the relevant upper bound (if both exist), and the two relevant bounds
+are used analogously as the two tightest bounds in the binary search.
+When they are less than goal width apart, the relevant bounds are used in output.
+
+One consequence is that every trial result can have an impact on the search result.
+That means if your SUT (or your traffic generator) needs a warmup,
+be sure to warm it up before starting the search.
+
+## Exceed Ratio
+
+The idea of performing multiple trials at the same load comes from
+a model where some trial results (those with high loss) are affected
+by infrequent effects, causing poor repeatability of [RFC2544] throughput results.
+See the discussion about noiseful and noiseless ends of SUT performance spectrum.
+Stable results are closer to the noiseless end of SUT preformance spectrum,
+so MLRsearch may need to allow some frequency of high-loss trials
+to ignore the reare but big effects near the noisefull end.
+
+MLRsearch is able to do such trial result filtering, but it needs
+a configuration option to tell it how much frequent can the infrequent big loss be.
+This option is called exceed ratio. It tells MLRsearch what ratio of trials
+(more exactly what ratio of trial seconds) can have trial loss ratio
+larger than goal loss ratio and still be classified as a lower bound.
+Zero exceed ratio means all trials have to have trial loss ratio
+equal to or smaller than the goal loss ratio.
+
+For explainability reasons, the RECOMMENDED value for exceed ratio is 0.5,
+as it simplifies some later concepts by relating them to the concept of median.
+
+## Duration Sum
+
+When more than one trial is needed to classify a load,
+MLRsearch also needs something that controlls the number of trials needed.
+Therefore, each goal also has an attribute called duration sum.
+
+The meaning of a goal duration sum is that when a load has trials
+(at full trial duration, details later)
+whose trial durations when summed up give a value at least this,
+the load is guaranteed to be classified as an upper bound or a lower bound
+for the goal.
+
+As the duration sum has a big impact on the overall search duration,
+and [RFC2544] prescibes wait intervals around trial traffic,
+the MLRsearch algorithm may sum durations that are different
+from the actual trial traffic durations.
+
+## Short Trials
+
+Section 24 of [RFC2544] already anticipates possible time savings
+when short trials (shorter than full length trials) are used.
+
+MLRsearch requires each goal to specify its final trial duration.
+Full-length trial is the short name for a trial whose intended trial duration
+is equal to the goal final trial duration.
+
+Any MLRsearch implementation may include its own configuration options
+which control when and how MLRsearch chooses to use shorter trial durations.
+
+For explainability reasons, when exceed ratio of 0.5 is used,
+it is recommended for the goal duration sum to be an odd multiple
+of the full trial durations, so conditional throughput becomes identical to
+a median of a particular set of forwarding rates.
+
+Presence of shorter trial results complicates the load classification logic.
+Full details are given later. In short, results from short trials
+may cause a load to be classified as an upper bound.
+This may cause loss inversion, and thus lower the relevant lower bound
+(below what would classification say when considering full-length trials only).
+
+For explainability reasons, it is RECOMMENDED users use such configurations
+that guarantee all trials have the same length.
+Alas, such configurations are usually not compliant with [RFC2544] requirements,
+or not time-saving enough.
+
+## Conditional Throughput
+
+As testing equipment takes intended load as input parameter
+for a trial measurement, any load search algorithm needs to deal
+with intended load values internally.
+
+But in presence of goals with non-zero loss ratio, the intended load
+usually does not match the user intuition of what a throughput is.
+The forwarding rate (as defined in [RFC2285] section 3.6.1) is better,
+but it is not obvious how to generalize it
+for loads with multiple trial results,
+especially with non-zero goal exceed ratio.
+
+MLRsearch defines one such generalization, called the conditional throughput.
+It is the forwarding rate from one of the trials performed at the load
+in question. Specification of which trial exactly is quite technical.
+More detailed explanations are given in the next chapter.
+
+Conditional throughput is partially related to load classification.
+If a load is classified as a lower bound for a goal,
+the conditional throughpt can be calculated,
+and guaranteed to show effective loss ratio no larger than goal loss ratio.
+
+While the conditional throughput gives more intuitive-looking values
+than the relevant lower bound, especially for non-zero goal loss ratio values,
+the actual definition is more complicated than the definition of the relevant
+lower bound. In future, other intuitive values may become popular,
+but they are unlikely to supersede the definition of the relevant lower bound
+as the most fitting value for comparability purposes,
+therefore the relevant lower bound remains a required attribute
+of the goal result structure.
+
+Note that comparing best and worst case, the same relevant lower bound value
+may result in the conditional throughput differing up to the goal loss ratio.
+Therefore it is rarely needed to set the goal width (if expressed
+as relative difference of loads) below the goal loss ratio.
+In other words, setting the goal width below the goal loss ratio
+may cause the conditional throughput for a larger loss ratio to became smaller
+than a conditional throughput for a goal with a smaller goal loss ratio,
+which is counter-intuitive, considering they come from the same search.
+Therefore it is RECOMMENDED to set the goal width to a value no smaller
+than the goal loss ratio.
+
+## Search Time
+
+The main motivation for MLRsearch was to have an algorithm that spends less time
+finding a throughput, either the [RFC2544] compliant one,
+or some generalization thereof. The art of achieving short search times
+is mainly in smart selection of intended loads (and intended durations)
+for the next trial to perform.
+
+While there is an indirect impact of the load selection on the reported values,
+in practice such impact tends to be small,
+even for SUTs with quite broad performance spectrum.
+
+A typical example of two approaches to load selection leading to different
+relevant lower bounds is when the interval is split in a very uneven way.
+An implementation chosing loads very close to the current relevant lower bound
+are quite likely to eventually stumble upon a trial result
+with poor performance (due to SUT noise).
+For an implementation chosing load very close to the current relevant upper bound
+this is unlikely, as it examines more loads that can see a performance
+close to the noiseless end of the SUT performance spectrum.
+The reason why it is unlikely to have two MLRsearch implementation showing
+this kind of preference in load selection is precisely
+in the desire to have short searches.
+Even splits are the best way to achive the desired precision,
+so the more optimized a search algorithm is for the overall search duration,
+the better the repeatability and comparability
+of its results will be, assuming the user configuration remains the same.
+
+Therefore, this document remains quite vague on load selection
+and other optimisation details, and configuration attributes related to them.
+Assuming users prefer libreries that achieve short overall search time,
+the definition of the relevant lower bound
+should be strict enough to ensure result repeatability
+and comparability between different implementations,
+while not restricting future implementations much.
+
+Sadly, different implementations may exhibit their sweet spot of
+best repeatability at given search duration at different goals attribute values,
+especially with respect to optional goal attributes
+such as initial trial duration.
+Thus, this document does not comment much on which configurations
+are good for comparability between different implementations.
+For comparability between different SUTs using the same implementation,
+refer to configurations recommended by that particular implementation.
+
+## [RFC2544] compliance
+
+The following search goal ensures unconditional compliance with
+[RFC2544] throughput search procedure:
+
+- Goal loss ratio: zero.
+
+- Goal final trial duration: 60 seconds.
+
+- Goal duration sum: 60 seconds.
+
+- Goal exceed ratio: zero.
+
+Presence of other search goals does not affect compliance of this goal result.
+The relevant lower bound and the conditional throughput are in this case
+equal to each other, and the value is the [RFC2544] throughput.
+
+If the 60 second quantity is replaced by a smaller quantity in both attributes,
+the conditional throughput is still conditionally compliant with
+[RFC2544] throughput.
+
+# Selected Functional Details
+
+This chapter continues with explanations,
+but this time more precise definitions are needed
+for readers to follow the explanations.
+The definitions here are wordy, implementers can look into the next chapter
+for more concise definitions.
+
+The two areas of focus in this chapter are the load classification
+and the conditional throughput, starting with the latter.
+
+## Performance Spectrum
+
+There are several equivalent ways to define the conditional throughput computation.
+One of the ways relies on an object called the performance spectrum.
+First, two heavy definitions are needed.
+
+Take an intended load value, and a finite set of trial results, all trials
+measured at that load value. The performance spectrum is the function that maps
+any non-negative real number into a sum of trial durations among all trials
+in the set that have that number as their forwarding rate,
+e.g. map to zero if no trial has that particular forwarding rate.
+
+A related function, defined if there is at least one trial in the set,
+is the performance spectrum divided by sum of durations of all trials in the set.
+That function is called the performance probability function, as it satisfies
+all the requirements for probability mass function function
+of a discrete probability distribution,
+the one-dimensional random variable being the trial forwarding rate.
+
+These functions are related to the SUT performance spectrum,
+as sampled by the trials in the set.
+
+As for any other probability function, we can talk about percentiles,
+of the performance probability function, and bout other quantiles
+such as the median. The conditional throughput will be
+one such quantile value for a specifically chosen set of trials.
+
+Take a set of all full-length trials performed at the load in question.
+The sum of durations of those trials may be less than goal duration sum, or not.
+If it is less, add an imaginary trial result with zero forwarding rate
+such that the new sum of durations is equal to the goal duration sum.
+This is the set of trials to use. The q-value for the quantile
+is the goal exceed ratio. If the quantile touches two trials,
+the larger forwarding rate is used.
+
+First example. For zero exceed ratio when goal duration sum
+has been reached. The conditional throughput is the smallest forwarding
+rate among the trials.
+
+Second example. For zero exceed ratio when goal duration sum
+has not been reached yet. Due to the missing duration sum,
+the worst case may still happen, so the conditional througput
+is zero. This is not reported to the user, as this load
+cannot become the relevant lower bound yet.
+
+Third example. Exceed ratio 50%, goal duration sum two seconds,
+one trial present with duration one second and zero loss.
+An imaginary trial is added with duration one second and zero forwarding rate.
+Median would touch both trials, so the conditional throughput
+is the forwarding rate of the one non-imaginary trial.
+As that had zero loss, the value is equal to the offered load.
+
+The classification does not need the whole performance spectrum,
+only few duration sums.
+
+A trial is called bad (according to a goal) if its trial loss ratio
+is larger than the goal loss ratio. Trial that is not bad is called good.
+
+## Single Trial Duration
+
+When goal attributes are chosen in such a way that every trial has the same
+intended duration, the load classification is sipler.
+
+The following description looks technical, but it follows the motivation
+of goal loss ratio, goal exceed ratio and goal duration sum.
+If sum of durations of all trials (at given load) is less than the goal
+duration sum, imagine best case scenario (all subsequent trials having zero loss)
+and worst case scenario (all subsequent trials having 100% loss).
+Here we assume there is as many subsequent trials as needed
+to make the sum of all trials to become equal to the goal duration sum.
+As the exceed ratio is defined just using sums of durations
+(number of trials does not matter), it does not matter whether
+the "subsequent trials" can consist of integer number of full-length trials.
+
+If even in the best case scenario the load exceed ratio would be larger
+than the goal exceed ratio, the load is an upper bound.
+If even in the worst case scenario the load exceed ratio would not be larger
+than the goal exceed ratio, the load is a lower bound.
+
+Even more specifically.
+Take all trials measured at a given load.
+Sum of durations of all bad full-length trials is called the bad sum.
+Sum of durations of all good full-length trials is called the good sum.
+The result of adding bad sum plus the good sum is called the measured sum.
+The larger of the measured sum and the goal duration sum is called the whole sum.
+The whole sum minus the measured sum is called the missing sum.
+Optimistic exceed ratio is the bad sum divided by the whole sum.
+Pessimistic exceed ratio is the bad sum plus the missing sum, that divided by
+the whole sum.
+If optimistic exceed ratio is larger than the goal exceed ratio,
+the load is classified as an upper bound.
+If pessimistic exceed ratio is not larger than the goal exceed ratio,
+the load is classified as a lower bound.
+Else, the load is classified as undecided.
+
+The definition of pessimistic exceed ratio matches the logic in
+the conditional throughput computation, so a load is a lower bound
+if and only if the conditional throughput effective loss ratio
+is not larger than the goal loss ratio.
+If it is larger, the load is either an upper bound or undecided.
+
+## Short Trial Scenarios
+
+Trials with intended duration smaller than the goal final trial duration
+are called short trials.
+The motivation for load classification logic in presence of short trials
+is based around a counter-factual case: What would the trial result be
+if a short trial has been measured as a full-length trial instead?
+
+There are three main scenarios where human intuition guides
+the intended behavior of load classification.
+
+Scenario one. The user had their reason for not configuring shorter goal
+final trial duration. Perhaps SUT has buffers that may get full at longer
+trial durations. Perhaps SUT shows periodic decreases of performance
+the user does not want to treat as noise. In any case, many good short trials
+may became bad full-length trial in the counter-factual case.
+In extreme case, there are no bad short trials.
+In this scenario, we want the load classification NOT to classify the load
+as a lower bound, despite the abundance of good short trials.
+Effectively, we want the good short trials to be ignored, so they
+do not contribute to comparisons with the goal duration sum.
+
+Scenario two. When there is a frame loss in a short trial,
+the counter-factual full-length trial is expected to lose at least as many
+frames. And in practice, bad short trials are rarely turning into
+good full-length trials. In extreme case, there are no good short trials.
+In this scenario, we want the load classification
+to classify the load as an upper bound just based on abundance
+of short bad trials. Effectively we want the bad short trials
+to contribute to comparisons with the goal duration sum,
+so the load can be classified sooner.
+
+Scenario three. Some SUTs are quite indifferent to trial duration.
+Performance probability function constructed from short trial results
+is likely to be similar to performance probability function constructed
+from full-length trial results (perhaps with smaller dispersion,
+but overall without big impact on the median quantiles).
+For moderate goal exceed ratio values, this may mean there are both
+good short trials and bad short trials.
+This scenario is there just to invalidate a simple heuristic
+of always ignoring good short trials and never ignoring bad short trials.
+That simple heuristic would be too biased. Yes, the short bad trials
+are likely to turn into full-length bad trials in the counter-factual case,
+but there is no information on what would the good short trials turn into.
+The only way to decide is to do more trials at full length,
+the same as in scenario one.
+
+## Short Trial Logic
+
+MLRsearch picks a particular logic for load classification
+in presence of short trials, but it is still RECOMMENDED to use configurations
+that imply no short trials, so the possible inefficiencies in that logic
+do not affect the result, and the result has better explainability.
+
+With thas said, the logic differs from the single trial duration case
+only in different definition of bad sum.
+Good sum is still the sum across all good full-length trials.
+
+Few more notions are needed for definig the new bad sum.
+Sum of durations of all bad full-length trials is called the bad long sum.
+Sum of durations of all bad short trials is called the bad short sum.
+Sum of durations of all good short trials is called the good short sum.
+One minus the goal exceed ratio is called the inceed ratio.
+The goal exceed ratio divided by the inceed ratio is called the exceed coefficient.
+The good short sum multiplied by the exceed coefficient is called the balancing sum.
+The bad short sum minus the balancing sum is called the excess sum.
+If the excess sum is negative, the bad sum is equal to the bad long sum.
+Else, the bad sum is equal to the bad long sum plus the excess sum.
+
+Here is how the new definition of the bad sum fares in the three scenarios,
+where the load is close to what would relevant bounds be
+if only full-length trials were used for the search.
+
+Scenario one. If duration is too short, we expect to see higher frequency
+of good short trials. This could lead to negative excess sum,
+which has no impact, hence the load classification is given just by
+full-length trials.
+Thus, MLRsearch using too short trials has no detrimental effect
+on result comparability in this scenario.
+But also using short trials does not help with overall search duration,
+proably making it worse.
+
+Scenario two. Settings with small exceed ratio have small exceed coefficient,
+so the impact of good short sum is small and the bad short sum
+is almost wholly converted into excess sum, thus bad short trials
+have almost as big impact as full-length bad trials.
+The same conclusion applies for moderate exceed ratio values
+when the good short sum is small.
+Thus, short trials can cause a load to get classified as an upper bound earlier
+bringing time savings (while not affecting comparability).
+
+Scenario three. Here excess sum is small in absolute value, as balancing sum
+is expected to be be similar to the bad short sum.
+Once again, full-length trials are needed for final load classification,
+but usage of short trials probably means MLRsearch needed shorter search time
+before selecting this load for measurement, bringing time savings
+(while not affecting comparability).
+
+## Longer Trial Durations
+
+If there are trial results with intended duration larger
+than the goal trial duration, the classification logic is intentionally undefined.
+
+The implementations MAY treat such longer trials as if they were full-length.
+In any case, presence of such longer trials in either the relevant lower bound
+or the relevant upper bound SHOULD be mentioned, as for sume SUTs
+it is likely to affect comparability.
+
+
+TODO: Here will be a chapter summarizing how MLRsearch library
+adresses the problems from the Identified Problems chapter.
+
+{::comment}
+
+ # Problems after MLRsearch
+
+ Now when MLRsearch is clearly specified and explained,
+ it is possible to summarize how does MLRsearch specification help with problems.
+
+ Here, "multiple trials" is a shorthand for having the goal final trial duration
+ significantly smaller than the goal duration sum.
+ This results in MLRsearch performing multiple trials at the same load,
+ which may not be the case with other configurations.
+
+ ## Long Test Duration
+
+ As shortening the overall search duration is the main motivation
+ of MLRsearch library development, the library implements
+ multiple improvements on this front, both big and small.
+ Most of implementation details are not part of the MLRsearch specification,
+ so that future implementations may keep shortening the search duration even more.
+
+ TODO: The rest is about attributes.
+
+ From the required goal attributes, the goal duration sum
+ remains the best way to get even shorter searches.
+
+ Usage of multiple trials can also save time,
+ depending on wait times around trial traffic.
+
+ The farther the goal exceed ratio is from 0.5 towards either side,
+ the less predictable the overal search duration becomes in practice.
+
+ Width parameter does not change search duration much in practice
+ (compared to other, mainly optional goal attributes).
+
+ ## DUT in SUT
+
+ Practice shows big improvements when multiple trials
+ and moderate exceed ratios are used. Mainly when it comes to result
+ repeatability, as sometimes it is not easy to distinguish
+ SUT noise from DUT instability.
+
+ Conditional throughput has intuitive meaning when described
+ using the performance spectrum, so this is an improvement,
+ especially when compared to search procedures which use non-zero
+ goal loss ratio but return only the intended load at a lower bound.
+
+ Multiple trials can save time also when the noisy end of
+ the preformance spectrum needs to be examined, e.g. for [RFC9004].
+
+ Under some circumstances, testing the same DUT and SUT setup with different
+ DUT configurations can give some hints on what part of noise us SUT noise
+ and what part is DUT performance fluctuations.
+ In practice, both types of noise tend to be too complicated for that analysis.
+ MLRsearch does not offer additional tools in this regard,
+ apart of giving users ability to search for more goals,
+ hoping to get more insight at the cost of longer overall search time.
+
+ ## Repeatability and Comparability
+
+ Multiple trials improve repeatability, depending on exceed ratio.
+
+ In practice, 1s goal final trial duration with exceed ratio 0.5
+ is good enough for modern SUTs (but that usually requires
+ smaller wait times around the traffic part of the trial,
+ otherwise too much search time is wasted waiting).
+
+ It is not clear whether exceed ratios higher than 0.5 are better
+ for repeatability.
+ The 0.5 value is still preferred due to explainability using median.
+ TODO: Stress single value is for comparability, which one is due explainability.
+
+ It is possible that the conditional throughput values (with non-zero
+ goal loss ratio) are better for repeatability than the relevant
+ lower bound values, especially for implementations
+ which pick load from a small set of discrete values.
+
+ Implementations focusing on shortening the overall search time
+ are automatically forced to avoid comparability issues
+ due to load selection, as they must prefer even splits wherever possible.
+ But this conclusion only holds when the same goals are used.
+ Larger adoption is needed before any further claims on comparability
+ between MLRsearch implementations can be made.
+
+ ## Throughput with Non-Zero Loss
+
+ Suported by the goal loss ratio attribute.
+ Improves repeatability as expected.
+
+ ## Inconsistent Trial Results
+
+ MLRsearch is conservative wherever possible,
+ this is built into the definition of conditional throughput,
+ and into the treatment of short trial results for load classification.
+
+ This is consistent with [RFC2544] zero loss tolerance motivation.
+
+ If the very best (noiseless) part of the SUT performance spectrum
+ is of interest, it should be enough to set small value for
+ the goal final trial duration, and perhaps also a large value
+ for the goal exceed ratio.
+
+ Implementations may offer other (optional) configuration attributes
+ (and optional goal result attributes)
+ to become less conservative, but currently it is not clear
+ what impact would that have on repeatability.
+
+{:/comment}
+
+# IANA Considerations
+
+No requests of IANA.
+
+# Security Considerations
+
+Benchmarking activities as described in this memo are limited to
+technology characterization of a DUT/SUT using controlled stimuli in a
+laboratory environment, with dedicated address space and the constraints
+specified in the sections above.
+
+The benchmarking network topology will be an independent test setup and
+MUST NOT be connected to devices that may forward the test traffic into
+a production network or misroute traffic to the test management network.
+
+Further, benchmarking is performed on a "black-box" basis, relying
+solely on measurements observable external to the DUT/SUT.
+
+Special capabilities SHOULD NOT exist in the DUT/SUT specifically for
+benchmarking purposes. Any implications for network security arising
+from the DUT/SUT SHOULD be identical in the lab and in production
+networks.
+
+# Acknowledgements
+
+Many thanks to Alec Hothan of OPNFV NFVbench project for thorough
+review and numerous useful comments and suggestions.
+
+Special wholehearted gratitude and thanks to late Al Morton for his
+thorough reviews filled with very specific feedback and constructive
+guidelines. Thank you Al for the close collaboration over the years,
+for your continuous unwavering encouragements full of empathy and
+positive attitude.
+Al, you are dearly missed.
+
+# Appendix A
+
+This is a specification of load classification.
+
+The block at the end of this appendix holds pseudocode
+which computes two values, stored in variables named optimistic and pessimistic.
+The pseudocode happens to be a valid Python code.
+
+If both values are computed to be true, the load in question
+is classified as a lower bound according to the goal in question.
+If both values are false, the load is classified as an upper bound.
+Otherwise, the load is classifies as undecided.
+
+The pseudocole expects the following variables hold values as follows:
+
+- goal_duration_sum: The goal duration sum value.
+
+- goal_exceed_ratio: The goal exceed ratio value.
+
+- good_long_sum: Sum of durations across trials with trial duration
+ at least equal to the goal final trial duration and with trial loss ratio
+ not higher than the goal loss ratio.
+
+- bad_long_sum: Sum of durations across trials with trial duration
+ at least equal to the goal final trial duration and with trial loss ratio
+ higher than the goal loss ratio.
+
+- good_short_sum: Sum of durations across trials with trial duration
+ shorter than the goal final trial duration and with trial loss ratio
+ not higher than the goal loss ratio.
+
+- bad_short_sum: Sum of durations across trials with trial duration
+ shorter than the goal final trial duration and with trial loss ratio
+ higher than the goal loss ratio.
+
+Here the implicit set of available trial results consists of all trials
+measured at given intended load at the end of search.
+
+The code works correctly also when there are no trial results at given load.
+
+```
+balancing_sum = good_short_sum * goal_exceed_ratio / (1.0 - goal_exceed_ratio)
+effective_bad_sum = bad_long_sum + max(0.0, bad_short_sum - balancing_sum)
+effective_whole_sum = max(good_long_sum + effective_bad_sum, goal_duration_sum)
+quantile_duration_sum = effective_whole_sum * goal_exceed_ratio
+optimistic = effective_bad_sum <= quantile_duration_sum
+pessimistic = (effective_whole_sum - good_long_sum) <= quantile_duration_sum
+```
+
+# Appendix B
+
+This is a specification of conditional throughput.
+
+The block at the end of this appendix holds pseudocode
+which computes a value stored as variable conditional_throughput.
+The pseudocode happens to be a valid Python code.
+
+The pseudocole expects the following variables hold values as follows:
+
+- goal_duration_sum: The goal duration sum value.
+
+- goal_exceed_ratio: The goal exceed ratio value.
+
+- good_long_sum: Sum of durations across trials with trial duration
+ at least equal to the goal final trial duration and with trial loss ratio
+ not higher than the goal loss ratio.
+
+- bad_long_sum: Sum of durations across trials with trial duration
+ at least equal to the goal final trial duration and with trial loss ratio
+ higher than the goal loss ratio.
+
+- long_trials: An iterable of all trial results from trials with trial duration
+ at least equal to the goal final trial duration,
+ sorted by increasing trial loss ratio.
+ A trial result is a composite with the following two attributes available:
+
+ - trial.loss_ratio: The trial loss ratio as measured for this trial.
+
+ - trial.duration: The trial duration of this trial.
+
+Here the implicit set of available trial results consists of all trials
+measured at given intended load at the end of search.
+
+The code works correctly only when there if there is at leas one
+trial result measured at given load.
+
+```
+all_long_sum = max(goal_duration_sum, good_long_sum + bad_long_sum)
+remaining = all_long_sum * (1.0 - goal_exceed_ratio)
+quantile_loss_ratio = None
+for trial in long_trials:
+ if quantile_loss_ratio is None or remaining > 0.0:
+ quantile_loss_ratio = trial.loss_ratio
+ remaining -= trial.duration
+ else:
+ break
+else:
+ if remaining > 0.0:
+ quantile_loss_ratio = 1.0
+
+conditional_throughput = intended_load * (1.0 - quantile_loss_ratio)
+```
+
+--- back
Code Review / csit.git / commitdiff