feat(ietf): replace MLRsearch draft to new version

[csit.git] / docs / ietf / draft-ietf-bmwg-mlrsearch-03.md

---
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