feat(ietf): replace MLRsearch draft to new version

Change-Id: Id2136d7a6cc95708ee641ca01247a3db50d2c8bf
Signed-off-by: Vratko Polak <vrpolak@cisco.com>
Signed-off-by: Maciek Konstantynowicz <mkonstan@cisco.com>

1 files changed, 501 insertions, 0 deletions

diff --git a/docs/ietf/draft-ietf-bmwg-mlrsearch-03.md b/docs/ietf/draft-ietf-bmwg-mlrsearch-03.md
new file mode 100644
index 0000000000..40180dc55b
--- /dev/null
+++ b/docs/ietf/draft-ietf-bmwg-mlrsearch-03.md
@@ -0,0 +1,501 @@
+---
+title: Multiple Loss Ratio Search
+abbrev: MLRsearch
+docname: draft-ietf-bmwg-mlrsearch-03
+date: 2022-11-09
+
+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://s3-docs.fd.io/csit/rls2110/report/introduction/methodology_data_plane_throughput/methodology_data_plane_throughput.html#mlrsearch-tests
+    title: "FD.io CSIT Test Methodology - MLRsearch"
+    date: 2021-11
+  PyPI-MLRsearch:
+    target: https://pypi.org/project/MLRsearch/0.3.0/
+    title: "MLRsearch 0.3.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 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 with multiple loss ratio goals.
+  - Each trial result can affect any search goal in principle
+    (trial reuse).
+- Multiple phases within one loss ratio goal search, middle ones need
+  to spend less time on trials.
+  - Middle phases also aim at lesser precision.
+  - Use Forwarding Rate (FR) at maximum offered load
+    [RFC2285] (section 3.6.2) to initialize the first middle phase.
+- Take care when dealing with inconsistent trial results.
+  - Loss ratios goals are handled in an order that precludes any
+    interference from later trials to earlier goals.
+- Apply several load selection heuristics to save even more time
+  by trying hard to avoid unnecessarily narrow intervals.
+
+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.
+
+# 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 precision goal.
+But, due to exponential behavior of bisection, small improvement
+in search duration needs relatively big sacrifice in the result 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.
+
+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 DUT
+but get different throughput values.
+
+[RFC2544] throughput requirements (60s trial, no tolerance to single frame loss)
+force the search to converge around 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
+bigger.
+
+## 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 loss ratio goals also helps to describe the SUT
+performance better than a single goal result. Repeated wide gap between
+zero and non-zero loss loads 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.
+
+# MLRsearch Approach
+
+The following description intentionally leaves out some important implementation
+details. This is both to hide complexity that is not important for overall
+understanding, and to allow future improvements in the implementation.
+
+## Terminology
+
+- *trial duration*: Amount of time over which frames are transmitted
+  towards SUT and DUT in a single measurement step.
+  - **MLRsearch input parameter** for final MLRsearch measurements.
+- *loss ratio*: Ratio of the count of frames lost to the count of frames
+  transmitted over a trial duration, a.k.a. packet loss ratio. Related
+  to packet loss rate [RFC1242] (section 3.6).
+  In MLRsearch loss ratio can mean either a trial result or a goal:
+  - *trial loss ratio*: Loss ratio measured during a trial.
+  - *loss ratio goal*: **MLRsearch input parameter**.
+    - If *trial loss ratio* is smaller or equal to this,
+      the trial **satisfies** the loss ratio goal.
+- *load*: Constant offered load stimulating the SUT and DUT. Consistent
+  with offered load [RFC2285] (section 3.5.2).
+  - MLRsearch works with intended load instead, as it cannot deal with
+    situations where the offered load is considerably different than
+    intended load.
+- *throughput*: The maximum load at which none of the offered frames are
+  dropped by the SUT and DUT. Consistent with [RFC1242] (section 3.17).
+- *conditional throughput*: The forwarding rate measured at the maximum
+  load at which a list of specified conditions are met i.e. loss ratio
+  goal and trial duration.
+  - Throughput is then a special case of conditional throughput
+    for zero loss ratio goal and long enough trial duration.
+  - Conditional throughput is aligned with forwarding rate (FR)
+    [RFC2285] (section 3.6.1), adding trial duration to offered load
+    required when reporting FR.
+- *lower bound*: One of values tracked by MLRsearch during the search runtime.
+  It is specific to the current trial duration and current loss ratio goal.
+  It represents a load value with at least one trial result available.
+  If the trial satisfies the current loss ratio goal,
+  it is a *valid* bound (else *invalid*).
+- *upper bound*: One of values tracked by MLRsearch during the search runtime.
+  It is specific to the current trial duration and current loss ratio goal.
+  It represents a load value with at least one trial result available.
+  If the trial satisfies the current loss ratio goal,
+  it is an *invalid* bound (else *valid*).
+- *interval*: The span between lower and upper bound loads.
+- *precision goal*: **MLRsearch input parameter**, acting as a search
+  stop condition, given as either absolute or relative width goal. An
+  interval meets precision goal if:
+  - The difference of upper and lower bound loads (in pps)
+    is not more than the absolute width goal.
+  - The difference as above, divided by upper bound load (in pps)
+    is not more than the relative width goal.
+
+## Description
+
+The MLRsearch approach to address the identified problems is based
+on the following main strategies:
+
+- MLRsearch main inputs include the following search goals and parameters:
+  - One or more **loss ratio goals**.
+    - e.g. a zero-loss goal and one (or more) non-zero-loss goals.
+  - **Target trial duration** condition governing required trial duration
+    for final measurements.
+  - **Target precision** condition governing how close final lower and
+    upper bound load values must be to each other for final
+    measurements.
+- Search is executed as a sequence of phases:
+  - *Initial phase* initializes bounds for the first middle phase.
+  - *Middle phase*s narrow down the bounds, using shorter trial
+    durations and lower precision goals. Several middle phases can
+    precede each final phase.
+  - *Final phase* (one per loss ratio goal) finds bounds matching input
+    goals and parameters to serve as the overal search output.
+- Each search phase produces its *ending* upper bound and lower bound:
+  - Initial phase may produce invalid bounds.
+  - Middle and final phases produce valid bounds.
+  - Middle or final phases needs at least two values to act as 
+    *starting* bounds (may be invalid).
+  - Each phase may perform several trial measurements, until phase's
+    ending conditions are all met.
+  - Trial results from previous phases may be re-used.
+- Initial phase establishes the starting values for bounds, using
+  forwarding rates (FR) [RFC2285] (section 3.6.1)
+  from a few trials of minimal duration, as follows:
+  - 1st trial is done at *maximum offered load (MOL)* [RFC2285] (section 3.5.3),
+    resulting in Forwarding rate at maximum offered load (FRMOL)
+    [RFC2285] (section 3.6.2).
+  - 2nd trial is done at *FRMOL*, resulting in forwarding rate at FRMOL (FRFRMOL),
+    newly defined here.
+  - 3rd trial is done at *FRFRMOL*, so its results are available for the next phase.
+  - By default, FRMOL is used as an upper bound, FRFRMOL as a lower bound.
+    - Adjustments may apply here for some cases e.g. when 2nd trial got
+      zero loss or if FRFRMOL is too close to FRMOL.
+- Middle phases are producing ending bounds by improving upon starting bounds:
+  - Each middle phase uses the same loss ratio goal as the final phase it precedes.
+    - Called *current loss ratio goal* for upper and lower bound purposes.
+  - Each middle phase has its own *current trial duration*
+    and *current precision goal* parameters, computed from
+    MLRsearch input parameters.
+    As phases progress, these parameters approach MLRsearch main input values.
+    - Current trial duration starts from a configurable minimum (e.g. 1 sec)
+      and increases in a geometric sequence.
+    - Current precision goal always allows twice as wide intervals
+      as the following phase.
+  - The starting bounds are usually the ending bounds from the preceding phase.
+    - Unless there are many previous trial results that are more promising.
+  - Each middle phase operates in a sequence of four actions:
+    1. Perform trial at the load between the starting bounds.
+      - Depending on the trial result this becomes the first
+        new valid upper or lower bound for current phase.
+    2. Re-measure at the remaining starting lower or upper (respectively) bound.
+    3. If that did not result in a valid bound, start an *external search*.
+      - That is a variant of exponential search.
+        - The "growth" is given by input parameter *expansion_coefficient*.
+      - This action ends when a new valid bound is found.
+        - Or if an already existing valid bound becomes close enough.
+    4. Repeatedly bisect the current interval until the bounds are close enough.
+- Final search phase operates in exactly the same way as middle phases.
+  There are two reasons why it is named differently:
+  - The current trial duration and current precision goal within the phase
+    are equal to the target trial duration and target precision input parameters.
+  - The forwarding rates of the ending bounds become the output of MLRsearch.
+    - Specifically, the forwarding rates of the final lower bounds
+      are the conditional throughput values per given loss ratio goals.
+
+## Enhancement: Multiple trials per load
+
+An enhancement of MLRsearch is to introduce a *noise tolerance* input parameter.
+The idea is to perform several medium-length trials (instead of a single long trial)
+and tolerate a configurable fraction of them to not-satisfy the loss ratio goal.
+
+MLRsearch implementation with this enhancement exists in FD.io CSIT project
+and test results of VPP and DPDK (testpmd, l3fwd) DUTs look promising.
+
+This enhancement would make the description of MLRsearch approach
+considerably more complicated, so this document version only describes
+MLRsearch without this enhancement.
+
+# How the problems are addressed
+
+Configurable loss ratio goals are in direct support for non-zero-loss conditional througput.
+In practice the conditional throughput results' stability
+increases with higher loss ratio goals.
+
+Multiple trials with noise tolerance enhancement will also indirectly
+increase result stability and it will allow MLRsearch
+to add 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 middle phases. The full implementation can bring a large number of
+heuristics related to how exactly should the next trial load be chosen,
+but the impact of those is not as big.
+
+The Description subsection lacks any details on how to handle inconsistent
+trial results. In practice, there tend to be a three-way trade-off
+between i) short overall search time, ii) result stability
+and iii) how simple the definition of the returned conditional throughput can be.
+The third one is important for comparability between different MLRsearch
+implementations.
+
+# 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