< draft-vpolak-mkonstan-bmwg-mlrsearch-01.txt   draft-vpolak-mkonstan-bmwg-mlrsearch-02.txt >
Benchmarking Working Group M. Konstantynowicz, Ed. Benchmarking Working Group M. Konstantynowicz, Ed.
Internet-Draft V. Polak, Ed. Internet-Draft V. Polak, Ed.
Intended status: Informational Cisco Systems Intended status: Informational Cisco Systems
Expires: September 28, 2019 March 27, 2019 Expires: January 9, 2020 July 08, 2019
Multiple Loss Ratio Search for Packet Throughput (MLRsearch) Multiple Loss Ratio Search for Packet Throughput (MLRsearch)
draft-vpolak-mkonstan-bmwg-mlrsearch-01 draft-vpolak-mkonstan-bmwg-mlrsearch-02
Abstract Abstract
This document proposes changes to [RFC2544], specifically to packet This document proposes changes to [RFC2544], specifically to packet
throughput search methodology, by defining a new search algorithm throughput search methodology, by defining a new search algorithm
referred to as Multiple Loss Ratio search (MLRsearch for short). referred to as Multiple Loss Ratio search (MLRsearch for short).
Instead of relying on binary search with pre-set starting offered Instead of relying on binary search with pre-set starting offered
load, it proposes a novel approach discovering the starting point in load, it proposes a novel approach discovering the starting point in
the initial phase, and then searching for packet throughput based on the initial phase, and then searching for packet throughput based on
defined packet loss ratio (PLR) input criteria and defined final defined packet loss ratio (PLR) input criteria and defined final
skipping to change at page 2, line 4 skipping to change at page 2, line 4
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/. Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on September 28, 2019. This Internet-Draft will expire on January 9, 2020.
Copyright Notice Copyright Notice
Copyright (c) 2019 IETF Trust and the persons identified as the Copyright (c) 2019 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of (https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 2 1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 2
2. MLRsearch Background . . . . . . . . . . . . . . . . . . . . 3 2. MLRsearch Background . . . . . . . . . . . . . . . . . . . . 4
3. MLRsearch Overview . . . . . . . . . . . . . . . . . . . . . 3 3. MLRsearch Overview . . . . . . . . . . . . . . . . . . . . . 5
4. Sample Implementation . . . . . . . . . . . . . . . . . . . . 5 4. Sample Implementation . . . . . . . . . . . . . . . . . . . . 8
4.1. Input Parameters . . . . . . . . . . . . . . . . . . . . 6 4.1. Input Parameters . . . . . . . . . . . . . . . . . . . . 8
4.2. Initial phase . . . . . . . . . . . . . . . . . . . . . . 6 4.2. Initial Phase . . . . . . . . . . . . . . . . . . . . . . 9
4.3. Non-initial phases . . . . . . . . . . . . . . . . . . . 7 4.3. Non-Initial Phases . . . . . . . . . . . . . . . . . . . 10
5. Known Implementations . . . . . . . . . . . . . . . . . . . . 9 4.4. Sample MLRsearch Run . . . . . . . . . . . . . . . . . . 12
5.1. FD.io CSIT Implementation Deviations . . . . . . . . . . 9 5. Known Implementations . . . . . . . . . . . . . . . . . . . . 12
6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 5.1. FD.io CSIT Implementation Deviations . . . . . . . . . . 12
7. Security Considerations . . . . . . . . . . . . . . . . . . . 10 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 13
8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 10 7. Security Considerations . . . . . . . . . . . . . . . . . . . 14
9. Normative References . . . . . . . . . . . . . . . . . . . . 10 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 14
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 11 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 14
9.1. Normative References . . . . . . . . . . . . . . . . . . 14
9.2. Informative References . . . . . . . . . . . . . . . . . 14
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 15
1. Terminology 1. Terminology
o NDR - Non-Drop Rate, a packet throughput metric with Packet Loss o Frame size: size of an Ethernet Layer-2 frame on the wire,
Ratio equal zero (a zero packet loss), expressed in packets-per- including any VLAN tags (dot1q, dot1ad) and Ethernet FCS, but
second (pps). NDR packet throughput has an associated metric excluding Ethernet preamble and inter-frame gap. Measured in
oftentimes referred to as NDR bandwidth expressed in bits-per- bytes.
second (bps), and calculated as a product of:
* NDR packet rate for specific packet (frame) size, and o Packet size: same as frame size, both terms used interchangeably.
* Packet (L2 frame size) size in bits plus any associated L1 o Inner L2 size: for tunneled L2 frames only, size of an
overhead. encapsulated Ethernet Layer-2 frame, preceded with tunnel header,
and followed by tunnel trailer. Measured in Bytes.
o PLR - Packet Loss Ratio, a packet loss metric calculated as a o Inner IP size: for tunneled IP packets only, size of an
ratio of (packets_transmitted - packets_received) to encapsulated IPv4 or IPv6 packet, preceded with tunnel header, and
packets_transmitted, over the test trial duration. followed by tunnel trailer. Measured in Bytes.
o PDR - Partial-Drop Rate, a packet throughput metric with Packet o Device Under Test (DUT): In software networking, "device" denotes
Loss Ratio greater than zero (a non-zero packet loss), expressed a specific piece of software tasked with packet processing. Such
in packets-per-second (pps). PDR packet throughput has an device is surrounded with other software components (such as
associated metric oftentimes referred to as PDR bandwidth operating system kernel). It is not possible to run devices
expressed in bits-per- second (bps), and calculated as a product without also running the other components, and hardware resources
of: are shared between both. For purposes of testing, the whole set
of hardware and software components is called "system under test"
(SUT). As SUT is the part of the whole test setup performance of
which can be measured by [RFC2544] methods, this document uses SUT
instead of [RFC2544] DUT. Device under test (DUT) can be re-
introduced when analysing test results using whitebox techniques,
but this document sticks to blackbox testing.
* PDR packet rate for specific packet (frame) size, and o System Under Test (SUT): System under test (SUT) is a part of the
whole test setup whose performance is to be benchmarked. The
complete methodology contains other parts, whose performance is
either already established, or not affecting the benchmarking
result.
* Packet (L2 frame size) size in bits plus any associated L1 o Bi-directional throughput tests: involve packets/frames flowing in
overhead. both transmit and receive directions over every tested interface
of SUT/DUT. Packet flow metrics are measured per direction, and
can be reported as aggregate for both directions (i.e. throughput)
and/or separately for each measured direction (i.e. latency). In
most cases bi-directional tests use the same (symmetric) load in
both directions.
o Uni-directional throughput tests: involve packets/frames flowing
in only one direction, i.e. either transmit or receive direction,
over every tested interface of SUT/DUT. Packet flow metrics are
measured and are reported for measured direction.
o Packet Loss Ratio (PLR): ratio of packets received relative to
packets transmitted over the test trial duration, calculated using
formula: PLR = ( pkts_transmitted - pkts_received ) /
pkts_transmitted. For bi-directional throughput tests aggregate
PLR is calculated based on the aggregate number of packets
transmitted and received.
o Packet Throughput Rate: maximum packet offered load DUT/SUT
forwards within the specified Packet Loss Ratio (PLR). In many
cases the rate depends on the frame size processed by DUT/SUT.
Hence packet throughput rate MUST be quoted with specific frame
size as received by DUT/SUT during the measurement. For bi-
directional tests, packet throughput rate should be reported as
aggregate for both directions. Measured in packets-per-second
(pps) or frames-per-second (fps), equivalent metrics.
o Bandwidth Throughput Rate: a secondary metric calculated from
packet throughput rate using formula: bw_rate = pkt_rate *
(frame_size + L1_overhead) * 8, where L1_overhead for Ethernet
includes preamble (8 Bytes) and inter-frame gap (12 Bytes). For
bi-directional tests, bandwidth throughput rate should be reported
as aggregate for both directions. Expressed in bits-per-second
(bps).
o Non Drop Rate (NDR): maximum packet/bandwith throughput rate
sustained by DUT/SUT at PLR equal zero (zero packet loss) specific
to tested frame size(s). MUST be quoted with specific packet size
as received by DUT/SUT during the measurement. Packet NDR
measured in packets-per-second (or fps), bandwidth NDR expressed
in bits-per-second (bps).
o Partial Drop Rate (PDR): maximum packet/bandwith throughput rate
sustained by DUT/SUT at PLR greater than zero (non-zero packet
loss) specific to tested frame size(s). MUST be quoted with
specific packet size as received by DUT/SUT during the
measurement. Packet PDR measured in packets-per-second (or fps),
bandwidth PDR expressed in bits-per-second (bps).
o Maximum Receive Rate (MRR): packet/bandwidth rate regardless of
PLR sustained by DUT/SUT under specified Maximum Transmit Rate
(MTR) packet load offered by traffic generator. MUST be quoted
with both specific packet size and MTR as received by DUT/SUT
during the measurement. Packet MRR measured in packets-per-second
(or fps), bandwidth MRR expressed in bits-per-second (bps).
o Trial: a single measurement step.
o Trial duration: amount of time over which packets are transmitted
and received in a single throughput measurement step.
2. MLRsearch Background 2. MLRsearch Background
Multiple Loss Rate search (MLRsearch) is a packet throughput search Multiple Loss Ratio search (MLRsearch) is a packet throughput search
algorithm suitable for deterministic (as opposed to probabilistic) algorithm suitable for deterministic systems (as opposed to
systems. MLRsearch discovers multiple packet throughput rates in a probabilistic systems). MLRsearch discovers multiple packet
single search, each rate associated with a distinct Packet Loss Ratio throughput rates in a single search, with each rate associated with a
(PLR) criteria. distinct Packet Loss Ratio (PLR) criteria.
Two popular names for particular PLR criteria are Non-Drop Rate (NDR, For cases when multiple rates need to be found, this property makes
with PLR=0, zero packet loss) and Partial Drop Rate (PDR, with PLR>0, MLRsearch more efficient in terms of time execution, compared to
non-zero packet loss). MLRsearch discovers NDR and PDR in a single traditional throughput search algorithms that discover a single
search reducing required execution time compared to separate binary packet rate per defined search criteria (e.g. a binary search
searches for NDR and PDR. MLRsearch reduces execution time even specified by [RFC2544]). MLRsearch reduces execution time even
further by relying on shorter trial durations of intermediate steps, further by relying on shorter trial durations of intermediate steps,
with only the final measurements conducted at the specified final with only the final measurements conducted at the specified final
trial duration. This results in the shorter overall search execution trial duration. This results in the shorter overall search execution
time when compared to a standard NDR/PDR binary search, while time when compared to a traditional binary search, while guaranteeing
guaranteeing the same or similar results. (TODO: Specify "standard" the same results for deterministic systems.
in the previous sentence.)
If needed, MLRsearch can be easily adopted to discover more In practice two rates with distinct PLRs are commonly used for packet
throughput rates with different pre-defined PLRs. throughput measurements of NFV systems: Non Drop Rate (NDR) with
PLR=0 and Partial Drop Rate (PDR) with PLR>0. The rest of this
document describes MLRsearch for NDR and PDR. If needed, MLRsearch
can be easily adapted to discover more throughput rates with
different pre-defined PLRs.
Unless otherwise noted, all throughput rates are _always_ bi- Similarly to other throughput search approaches like binary search,
directional aggregates of two equal (symmetric) uni-directional MLRsearch is effective for SUTs/DUTs with PLR curve that is
packet rates received and reported by an external traffic generator. continuously flat or increasing with growing offered load. It may
not be as effective for SUTs/DUTs with abnormal PLR curves.
MLRsearch relies on traffic generator to qualify the received packet
stream as error-free, and invalidate the results if any disqualifying
errors are present e.g. out-of-sequence frames.
MLRsearch can be applied to both uni-directional and bi-directional
throughput tests.
For bi-directional tests, MLRsearch rates and ratios are aggregates
of both directions, based on the following assumptions:
o Packet rates transmitted by traffic generator and received by SUT/
DUT are the same in each direction, in other words the load is
symmetric.
o SUT/DUT packet processing capacity is the same in both directions,
resulting in the same packet loss under load.
3. MLRsearch Overview 3. MLRsearch Overview
The main properties of MLRsearch: The main properties of MLRsearch:
o MLRsearch is a duration aware multi-phase multi-rate search o MLRsearch is a duration aware multi-phase multi-rate search
algorithm. algorithm:
* Initial phase determines promising starting interval for the * Initial Phase determines promising starting interval for the
search. search.
* Intermediate phases progress towards defined final search * Intermediate Phases progress towards defined final search
criteria. criteria.
* Final phase executes measurements according to the final search * Final Phase executes measurements according to the final search
criteria. criteria.
o Initial phase: * Final search criteria is defined by following inputs:
* Uses link rate as a starting transmit rate and discovers the + PLRs associated with NDR and PDR.
Maximum Receive Rate (MRR) used as an input to the first
intermediate phase.
o Intermediate phases: + Final trial duration.
* Start with initial trial duration (in the first phase) and + Measurement resolution.
converge geometrically towards the final trial duration (in the
final phase).
* Track two values for NDR and two for PDR. o Initial Phase:
+ The values are called (NDR or PDR) lower_bound and * Measure MRR over initial trial duration.
upper_bound.
+ Each value comes from a specific trial measurement (most * Measured MRR is used as an input to the first intermediate
recent for that transmit rate), and as such the value is phase.
associated with that measurement's duration and loss.
+ A bound can be invalid, for example if NDR lower_bound has o Multiple Intermediate Phases:
been measured with nonzero loss.
+ Invalid bounds are not real boundaries for the searched * Trial duration:
value, but are needed to track interval widths.
+ Valid bounds are real boundaries for the searched value. + Start with initial trial duration in the first intermediate
phase.
+ Each non-initial phase ends with all bounds valid. + Converge geometrically towards the final trial duration.
* Start with a large (lower_bound, upper_bound) interval width * Track two values for NDR and two for PDR:
and geometrically converge towards the width goal (measurement
resolution) of the phase. Each phase halves the previous width
goal.
* Use internal and external searches: + The values are called lower_bound and upper_bound.
+ External search - measures at transmit rates outside the + Each value comes from a specific trial measurement:
(lower_bound, upper_bound) interval. Activated when a bound
is invalid, to search for a new valid bound by doubling the
interval width. It is a variant of "exponential search".
+ Internal search - "binary search", measures at transmit - Most recent for that transmit rate.
rates within the (lower_bound, upper_bound) valid interval,
halving the interval width.
o Final phase - As such the value is associated with that measurement's
duration and loss.
+ A bound can be valid or invalid:
- Valid lower_bound must conform with PLR search criteria.
- Valid upper_bound must not conform with PLR search
criteria.
- Example of invalid NDR lower_bound is if it has been
measured with non-zero loss.
- Invalid bounds are not real boundaries for the searched
value:
o They are needed to track interval widths.
- Valid bounds are real boundaries for the searched value.
- Each non-initial phase ends with all bounds valid.
- Bound can become invalid if it re-measured at longer
trial duration in sub-sequent phase.
* Search:
+ Start with a large (lower_bound, upper_bound) interval
width, that determines measurement resolution.
+ Geometrically converge towards the width goal of the phase.
+ Each phase halves the previous width goal.
* Use of internal and external searches:
+ External search:
- Measures at transmit rates outside the (lower_bound,
upper_bound) interval.
- Activated when a bound is invalid, to search for a new
valid bound by doubling the interval width.
- It is a variant of "exponential search".
+ Internal search:
- A "binary search" that measures at transmit rates within
the (lower_bound, upper_bound) valid interval, halving
the interval width.
o Final Phase:
* Executed with the final test trial duration, and the final * Executed with the final test trial duration, and the final
width goal that determines resolution of the overall search. width goal that determines resolution of the overall search.
o Intermediate phases together with the final phase are called non- o Intermediate Phases together with the Final Phase are called Non-
initial phases. Initial Phases.
The main benefits of MLRsearch vs. binary search include: The main benefits of MLRsearch vs. binary search include:
o In general MLRsearch is likely to execute more search trials o In general MLRsearch is likely to execute more trials overall, but
overall, but less trials at a set final duration. likely less trials at a set final trial duration.
o In well behaving cases it greatly reduces (>50%) the overall o In well behaving cases, e.g. when results do not depend on trial
duration compared to a single PDR (or NDR) binary search duration, duration, it greatly reduces (>50%) the overall duration compared
while finding multiple drop rates. to a single PDR (or NDR) binary search over duration, while
finding multiple drop rates.
o In all cases MLRsearch yields the same or similar results to o In all cases MLRsearch yields the same or similar results to
binary search. binary search.
o Note: both binary search and MLRsearch are susceptible to o Note: both binary search and MLRsearch are susceptible to
reporting non-repeatable results across multiple runs for very bad reporting non-repeatable results across multiple runs for very bad
behaving cases. behaving cases.
Caveats: Caveats:
skipping to change at page 6, line 7 skipping to change at page 8, line 43
4. Sample Implementation 4. Sample Implementation
Following is a brief description of a sample MLRsearch implementation Following is a brief description of a sample MLRsearch implementation
based on the open-source code running in FD.io CSIT project as part based on the open-source code running in FD.io CSIT project as part
of a Continuous Integration / Continuous Development (CI/CD) of a Continuous Integration / Continuous Development (CI/CD)
framework. framework.
4.1. Input Parameters 4.1. Input Parameters
1. *maximum_transmit_rate* - maximum packet transmit rate to be used 1. *maximum_transmit_rate* - Maximum Transmit Rate (MTR) of packets
by external traffic generator, limited by either the actual to be used by external traffic generator implementing MLRsearch,
Ethernet link rate or traffic generator NIC model capabilities. limited by the actual Ethernet link(s) rate, NIC model or traffic
Sample defaults: 2 * 14.88 Mpps for 64B 10GE link rate, 2 * 18.75 generator capabilities. Sample defaults: 2 * 14.88 Mpps for 64B
Mpps for 64B 40GE NIC maximum rate. 10GE link rate, 2 * 18.75 Mpps for 64B 40GE NIC (specific model)
maximum rate (lower than 2 * 59.52 Mpps 40GE link rate).
2. *minimum_transmit_rate* - minimum packet transmit rate to be used 2. *minimum_transmit_rate* - minimum packet transmit rate to be used
for measurements. MLRsearch fails if lower transmit rate needs for measurements. MLRsearch fails if lower transmit rate needs
to be used to meet search criteria. Default: 2 * 10 kpps (could to be used to meet search criteria. Default: 2 * 10 kpps (could
be higher). be higher).
3. *final_trial_duration* - required trial duration for final rate 3. *final_trial_duration* - required trial duration for final rate
measurements. Default: 30 sec. measurements. Default: 30 sec.
4. *initial_trial_duration* - trial duration for initial MLRsearch 4. *initial_trial_duration* - trial duration for initial MLRsearch
skipping to change at page 6, line 39 skipping to change at page 9, line 28
PDR measurements. Default: 0.5%. PDR measurements. Default: 0.5%.
7. *number_of_intermediate_phases* - number of phases between the 7. *number_of_intermediate_phases* - number of phases between the
initial phase and the final phase. Impacts the overall MLRsearch initial phase and the final phase. Impacts the overall MLRsearch
duration. Less phases are required for well behaving cases, more duration. Less phases are required for well behaving cases, more
phases may be needed to reduce the overall search duration for phases may be needed to reduce the overall search duration for
worse behaving cases. Default (2). (Value chosen based on worse behaving cases. Default (2). (Value chosen based on
limited experimentation to date. More experimentation needed to limited experimentation to date. More experimentation needed to
arrive to clearer guidelines.) arrive to clearer guidelines.)
4.2. Initial phase 4.2. Initial Phase
1. First trial measures at maximum rate and discovers MRR. 1. First trial measures at configured maximum transmit rate (MTR)
and discovers maximum receive rate (MRR).
* _in_: trial_duration = initial_trial_duration. * IN: trial_duration = initial_trial_duration.
* _in_: offered_transmit_rate = maximum_transmit_rate. * IN: offered_transmit_rate = maximum_transmit_rate.
* _do_: single trial. * DO: single trial.
* _out_: measured loss ratio. * OUT: measured loss ratio.
* _out_: mrr = measured receive rate. * OUT: MRR = measured receive rate.
2. Second trial measures at MRR and discovers MRR2. 2. Second trial measures at MRR and discovers MRR2.
* _in_: trial_duration = initial_trial_duration. * IN: trial_duration = initial_trial_duration.
* _in_: offered_transmit_rate = MRR. * IN: offered_transmit_rate = MRR.
* _do_: single trial. * DO: single trial.
* _out_: measured loss ratio. * OUT: measured loss ratio.
* _out_: mrr2 = measured receive rate. * OUT: MRR2 = measured receive rate.
3. Third trial measures at MRR2. 3. Third trial measures at MRR2.
* _in_: trial_duration = initial_trial_duration. * IN: trial_duration = initial_trial_duration.
* _in_: offered_transmit_rate = MRR2. * IN: offered_transmit_rate = MRR2.
* _do_: single trial. * DO: single trial.
* _out_: measured loss ratio. * OUT: measured loss ratio.
4.3. Non-initial phases 4.3. Non-Initial Phases
1. Main loop: 1. Main loop:
* _in_: trial_duration for the current phase. Set to 1. IN: trial_duration for the current phase. Set to
initial_trial_duration for the first intermediate phase; to initial_trial_duration for the first intermediate phase; to
final_trial_duration for the final phase; or to the element of final_trial_duration for the final phase; or to the element
interpolating geometric sequence for other intermediate of interpolating geometric sequence for other intermediate
phases. For example with two intermediate phases, phases. For example with two intermediate phases,
trial_duration of the second intermediate phase is the trial_duration of the second intermediate phase is the
geometric average of initial_strial_duration and geometric average of initial_trial_duration and
final_trial_duration. final_trial_duration.
* _in_: relative_width_goal for the current phase. Set to 2. IN: relative_width_goal for the current phase. Set to
final_relative_width for the final phase; doubled for each final_relative_width for the final phase; doubled for each
preceding phase. For example with two intermediate phases, preceding phase. For example with two intermediate phases,
the first intermediate phase uses quadruple of the first intermediate phase uses quadruple of
final_relative_width and the second intermediate phase uses final_relative_width and the second intermediate phase uses
double of final_relative_width. double of final_relative_width.
* _in_: ndr_interval, pdr_interval from the previous main loop 3. IN: ndr_interval, pdr_interval from the previous main loop
iteration or the previous phase. If the previous phase is the iteration or the previous phase. If the previous phase is
initial phase, both intervals have lower_bound = MRR2, the initial phase, both intervals have lower_bound = MRR2,
uper_bound = MRR. Note that the initial phase is likely to upper_bound = MRR. Note that the initial phase is likely to
create intervals with invalid bounds. create intervals with invalid bounds.
* _do_: According to the procedure described in point 2, either 4. DO: According to the procedure described in point 2., either
exit the phase (by jumping to 1.g.), or prepare new transmit exit the phase (by jumping to 1.7.), or calculate new
rate to measure with. transmit rate to measure with.
* _do_: Perform the trial measurement at the new transmit rate 5. DO: Perform the trial measurement at the new transmit rate
and trial_duration, compute its loss ratio. and trial_duration, compute its loss ratio.
* _do_: Update the bounds of both intervals, based on the new 6. DO: Update the bounds of both intervals, based on the new
measurement. The actual update rules are numerous, as NDR measurement. The actual update rules are numerous, as NDR
external search can affect PDR interval and vice versa, but external search can affect PDR interval and vice versa, but
the result agrees with rules of both internal and external the result agrees with rules of both internal and external
search. For example, any new measurement below an invalid search. For example, any new measurement below an invalid
lower_bound becomes the new lower_bound, while the old lower_bound becomes the new lower_bound, while the old
measurement (previously acting as the invalid lower_bound) measurement (previously acting as the invalid lower_bound)
becomes a new and valid upper_bound. Go to next iteration becomes a new and valid upper_bound. Go to next iteration
(1.c.), taking the updated intervals as new input. (1.3.), taking the updated intervals as new input.
* _out_: current ndr_interval and pdr_interval. In the final 7. OUT: current ndr_interval and pdr_interval. In the final
phase this is also considered to be the result of the whole phase this is also considered to be the result of the whole
search. For other phases, the next phase loop is started with search. For other phases, the next phase loop is started
the current results as an input. with the current results as an input.
2. New transmit rate (or exit) calculation (for 1.d.): 2. New transmit rate (or exit) calculation (for point 1.4.):
* If there is an invalid bound then prepare for external search: 1. If there is an invalid bound then prepare for external
search:
+ _If_ the most recent measurement at NDR lower_bound + IF the most recent measurement at NDR lower_bound transmit
transmit rate had the loss higher than zero, then the new rate had the loss higher than zero, then the new transmit
transmit rate is NDR lower_bound decreased by two NDR rate is NDR lower_bound decreased by two NDR interval
interval widths. widths or the amount needed to hit the current width goal,
whichever is larger.
+ Else, _if_ the most recent measurement at PDR lower_bound + Else, IF the most recent measurement at PDR lower_bound
transmit rate had the loss higher than PLR, then the new transmit rate had the loss higher than PLR, then the new
transmit rate is PDR lower_bound decreased by two PDR transmit rate is PDR lower_bound decreased by two PDR
interval widths. interval widths.
+ Else, _if_ the most recent measurement at NDR upper_bound + Else, IF the most recent measurement at NDR upper_bound
transmit rate had no loss, then the new transmit rate is transmit rate had no loss, then the new transmit rate is
NDR upper_bound increased by two NDR interval widths. NDR upper_bound increased by two NDR interval widths.
+ Else, _if_ the most recent measurement at PDR upper_bound + Else, IF the most recent measurement at PDR upper_bound
transmit rate had the loss lower or equal to PLR, then the transmit rate had the loss lower or equal to PLR, then the
new transmit rate is PDR upper_bound increased by two PDR new transmit rate is PDR upper_bound increased by two PDR
interval widths. interval widths.
* If interval width is higher than the current phase goal: 2. If interval width is higher than the current phase goal:
+ Else, _if_ NDR interval does not meet the current phase + Else, IF NDR interval does not meet the current phase
width goal, prepare for internal search. The new transmit width goal, prepare for internal search. The new transmit
rate is (NDR lower bound + NDR upper bound) / 2. rate is a geometric average of NDR lower_bound and NDR
upper_bound.
+ Else, _if_ PDR interval does not meet the current phase + Else, IF PDR interval does not meet the current phase
width goal, prepare for internal search. The new transmit width goal, prepare for internal search. The new transmit
rate is (PDR lower bound + PDR upper bound) / 2. rate is a geometric average of PDR lower_bound and PDR
upper_bound.
* Else, _if_ some bound has still only been measured at a lower 3. Else, IF some bound has still only been measured at a lower
duration, prepare to re-measure at the current duration (and duration, prepare to re-measure at the current duration (and
the same transmit rate). The order of priorities is: the same transmit rate). The order of priorities is:
+ NDR lower_bound, + NDR lower_bound,
+ PDR lower_bound, + PDR lower_bound,
+ NDR upper_bound, + NDR upper_bound,
+ PDR upper_bound. + PDR upper_bound.
* _Else_, do not prepare any new rate, to exit the phase. This 4. Else, do not prepare any new rate, to exit the phase. This
ensures that at the end of each non-initial phase all ensures that at the end of each non-initial phase all
intervals are valid, narrow enough, and measured at current intervals are valid, narrow enough, and measured at current
phase trial duration. phase trial duration.
4.4. Sample MLRsearch Run
TODO add a sample MLRsearch run with values.
5. Known Implementations 5. Known Implementations
The only known working implementation of MLRsearch is in Linux The only known working implementation of MLRsearch is in Linux
Foundation FD.io CSIT project. https://wiki.fd.io/view/CSIT. Foundation FD.io CSIT project [FDio-CSIT-MLRsearch]. MLRsearch is
https://git.fd.io/csit/. also available as a Python package in [PyPI-MLRsearch].
5.1. FD.io CSIT Implementation Deviations 5.1. FD.io CSIT Implementation Deviations
This document so far has been describing a simplified version of This document so far has been describing a simplified version of
MLRsearch algorithm. The full algorithm as implemented contains MLRsearch algorithm. The full algorithm as implemented contains
additional logic, which makes some of the details (but not general additional logic, which makes some of the details (but not general
ideas) above incorrect. Here is a short description of the ideas) above incorrect. Here is a short description of the
additional logic as a list of principles, explaining their main additional logic as a list of principles, explaining their main
differences from (or additions to) the simplified description, but differences from (or additions to) the simplified description, but
without detailing their mutual interaction. without detailing their mutual interaction.
1. Logarithmic transmit rate. In order to better fit the relative 1. Logarithmic transmit rate.
width goal, the interval doubling and halving is done
differently. For example, the middle of 2 and 8 is 4, not 5.
2. Optimistic maximum rate. The increased rate is never higher than * In order to better fit the relative width goal, the interval
the maximum rate. Upper bound at that rate is always considered doubling and halving is done differently.
valid.
3. Pessimistic minimum rate. The decreased rate is never lower than * For example, the middle of 2 and 8 is 4, not 5.
the minimum rate. If a lower bound at that rate is invalid, a
phase stops refining the interval further (until it gets re-
measured).
4. Conservative interval updates. Measurements above current upper 2. Optimistic maximum rate.
bound never update a valid upper bound, even if drop ratio is
low. Measurements below current lower bound always update any
lower bound if drop ratio is high.
5. Ensure sufficient interval width. Narrow intervals make external * The increased rate is never higher than the maximum rate.
search take more time to find a valid bound. If the new transmit
increased or decreased rate would result in width less than the
current goal, increase/decrease more. This can happen if the
measurement for the other interval makes the current interval too
narrow. Similarly, take care the measurements in the initial
phase create wide enough interval.
6. Timeout for bad cases. The worst case for MLRsearch is when each * Upper bound at that rate is always considered valid.
phase converges to intervals way different than the results of
the previous phase. Rather than suffer total search time several 3. Pessimistic minimum rate.
times larger than pure binary search, the implemented tests fail
themselves when the search takes too long (given by argument * The decreased rate is never lower than the minimum rate.
_timeout_).
* If a lower bound at that rate is invalid, a phase stops
refining the interval further (until it gets re-measured).
4. Conservative interval updates.
* Measurements above current upper bound never update a valid
upper bound, even if drop ratio is low.
* Measurements below current lower bound always update any lower
bound if drop ratio is high.
5. Ensure sufficient interval width.
* Narrow intervals make external search take more time to find a
valid bound.
* If the new transmit increased or decreased rate would result
in width less than the current goal, increase/decrease more.
* This can happen if the measurement for the other interval
makes the current interval too narrow.
* Similarly, take care the measurements in the initial phase
create wide enough interval.
6. Timeout for bad cases.
* The worst case for MLRsearch is when each phase converges to
intervals way different than the results of the previous
phase.
* Rather than suffer total search time several times larger than
pure binary search, the implemented tests fail themselves when
the search takes too long (given by argument _timeout_).
6. IANA Considerations 6. IANA Considerations
.. No requests of IANA.
7. Security Considerations 7. 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.
8. Acknowledgements 8. Acknowledgements
.. Many thanks to Alec Hothan of OPNFV NFVbench project for thorough
review and numerous useful comments and suggestions.
9. Normative References 9. References
9.1. Normative References
[RFC2544] Bradner, S. and J. McQuaid, "Benchmarking Methodology for [RFC2544] Bradner, S. and J. McQuaid, "Benchmarking Methodology for
Network Interconnect Devices", RFC 2544, Network Interconnect Devices", RFC 2544,
DOI 10.17487/RFC2544, March 1999, DOI 10.17487/RFC2544, March 1999,
<https://www.rfc-editor.org/info/rfc2544>. <https://www.rfc-editor.org/info/rfc2544>.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://www.rfc-editor.org/info/rfc8174>. May 2017, <https://www.rfc-editor.org/info/rfc8174>.
9.2. Informative References
[FDio-CSIT-MLRsearch]
"FD.io CSIT Test Methodology - MLRsearch", June 2019,
<https://docs.fd.io/csit/rls1904/report/introduction/
methodology_data_plane_throughput/
methodology_mlrsearch_tests.html>.
[PyPI-MLRsearch]
"MLRsearch 0.2.0, Python Package Index", August 2018,
<https://pypi.org/project/MLRsearch/>.
Authors' Addresses Authors' Addresses
Maciek Konstantynowicz (editor) Maciek Konstantynowicz (editor)
Cisco Systems Cisco Systems
Email: mkonstan@cisco.com Email: mkonstan@cisco.com
Vratko Polak (editor) Vratko Polak (editor)
Cisco Systems Cisco Systems
 End of changes. 91 change blocks. 
225 lines changed or deleted 417 lines changed or added

This html diff was produced by rfcdiff 1.47. The latest version is available from http://tools.ietf.org/tools/rfcdiff/