Benchmarking Working Group M. Konstantynowicz, Ed.
Internet-Draft V. Polak, Ed.
Intended status: Informational Cisco Systems
Expires: April 25, 2019 October 22, 2018
Multiple Loss Ratio Search for Packet Throughput (MLRsearch)
draft-vpolak-mkonstan-mlrsearch-00
Abstract
This document proposes changes to [RFC2544], specifically to packet
throughput search methodology, by defining a new search algorithm
referred to as Multiple Loss Ratio search (MLRsearch for short).
Instead of relying on binary search with pre-set starting offered
load, it proposes a novel approach discovering the starting point in
the initial phase, and then searching for packet throughput based on
defined packet loss ratio (PLR) input criteria and defined final
trial duration time. One of the key design principles behind
MLSsearch is minimizing the total test duration and searching for
multiple packet throughput rates (each with a corresponding PLR)
concurrently, instead of doing it sequentially.
The main motivation behind MLRsearch is the new set of challenges and
requirements posed by NFV (Network Function Virtualization),
specifically software based implementations of NFV data planes.
Using [RFC2544] in the experience of the authors yields often not
repetitive and not replicable end results due to a large number of
factors that are out of scope for this draft. MLRsearch aims to
address this chalenge and define a common (standard?) way to evaluate
NFV packet throughput performance that takes into account varying
characteristics of NFV systems under test.
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
Konstantynowicz & Polak Expires April 25, 2019 [Page 1]
Internet-DrafMultiple Loss Ratio Search for Packet Throughp October 2018
This Internet-Draft will expire on April 25, 2019.
Copyright Notice
Copyright (c) 2018 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 2
2. MLRsearch Background . . . . . . . . . . . . . . . . . . . . 3
3. MLRsearch Overview . . . . . . . . . . . . . . . . . . . . . 3
4. Sample Implementation . . . . . . . . . . . . . . . . . . . . 5
4.1. Input Parameters . . . . . . . . . . . . . . . . . . . . 6
4.2. Initial phase . . . . . . . . . . . . . . . . . . . . . . 6
4.3. Non-initial phases . . . . . . . . . . . . . . . . . . . 7
5. Known Implementations . . . . . . . . . . . . . . . . . . . . 8
5.1. FD.io CSIT Implementation Deviations . . . . . . . . . . 9
6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9
7. Security Considerations . . . . . . . . . . . . . . . . . . . 10
8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 10
9. Normative References . . . . . . . . . . . . . . . . . . . . 10
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 10
1. Terminology
o NDR - Non-Drop Rate, a packet throughput metric with Packet Loss
Ratio equal zero (a zero packet loss), expressed in packets-per-
second (pps). NDR packet throughput has an associated metric
oftentimes referred to as NDR bandwidth expressed in bits-per-
second (bps), and calculated as a product of:
* NDR packet rate for specific packet (frame) size, and
* Packet (L2 frame size) size in bits plus any associated L1
overhead.
Konstantynowicz & Polak Expires April 25, 2019 [Page 2]
Internet-DrafMultiple Loss Ratio Search for Packet Throughp October 2018
o PLR - Packet Loss Ratio, a packet loss metric calculated as a
ratio of (packets_transmitted - packets_received) to
packets_transmitted, over the test trial duration.
o PDR - Partial-Drop Rate, a packet throughput metric with Packet
Loss Ratio greater than zero (a non-zero packet loss), expressed
in packets-per-second (pps). PDR packet throughput has an
associated metric oftentimes referred to as PDR bandwidth
expressed in bits-per- second (bps), and calculated as a product
of:
* PDR packet rate for specific packet (frame) size, and
* Packet (L2 frame size) size in bits plus any associated L1
overhead.
2. MLRsearch Background
Multiple Loss Rate search (MLRsearch) is a packet throughput search
algorithm suitable for deterministic (as opposed to probabilistic)
systems. MLRsearch discovers multiple packet throughput rates in a
single search, each rate associated with a distinct Packet Loss Ratio
(PLR) criteria.
Two popular names for particular PLR criteria are Non-Drop Rate (NDR,
with PLR=0, zero packet loss) and Partial Drop Rate (PDR, with PLR>0,
non-zero packet loss). MLRsearch discovers NDR and PDR in a single
search reducing required execution time compared to separate binary
searches for NDR and PDR. MLRsearch reduces execution time even
further by relying on shorter trial durations of intermediate steps,
with only the final measurements conducted at the specified final
trial duration. This results in the shorter overall search execution
time when compared to a standard NDR/PDR binary search, while
guaranteeing the same or similar results. (TODO: Specify "standard"
in the previous sentence.)
If needed, MLRsearch can be easily adopted to discover more
throughput rates with different pre-defined PLRs.
Unless otherwise noted, all throughput rates are _always_ bi-
directional aggregates of two equal (symmetric) uni-directional
packet rates received and reported by an external traffic generator.
3. MLRsearch Overview
The main properties of MLRsearch:
Konstantynowicz & Polak Expires April 25, 2019 [Page 3]
Internet-DrafMultiple Loss Ratio Search for Packet Throughp October 2018
o MLRsearch is a duration aware multi-phase multi-rate search
algorithm.
* Initial phase determines promising starting interval for the
search.
* Intermediate phases progress towards defined final search
criteria.
* Final phase executes measurements according to the final search
criteria.
o *Initial phase*:
* Uses link rate as a starting transmit rate and discovers the
Maximum Receive Rate (MRR) used as an input to the first
intermediate phase.
o *Intermediate phases*:
* Start with initial trial duration (in the first phase) and
converge geometrically towards the final trial duration (in the
final phase).
* Track two values for NDR and two for PDR.
+ The values are called (NDR or PDR) lower_bound and
upper_bound.
+ Each value comes from a specific trial measurement (most
recent for that transmit rate), and as such the value is
associated with that measurement's duration and loss.
+ A bound can be invalid, for example if NDR lower_bound has
been measured with nonzero loss.
+ Invalid bounds are not real boundaries for the searched
value, but are needed to track interval widths.
+ Valid bounds are real boundaries for the searched value.
+ Each non-initial phase ends with all bounds valid.
* Start with a large (lower_bound, upper_bound) interval width
and geometrically converge towards the width goal (measurement
resolution) of the phase. Each phase halves the previous width
goal.
Konstantynowicz & Polak Expires April 25, 2019 [Page 4]
Internet-DrafMultiple Loss Ratio Search for Packet Throughp October 2018
* Use 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 - "binary search"_, measures at transmit
rates within the (lower_bound, upper_bound) valid interval,
halving the interval width.
o *Final phase* is executed with the final test trial duration, and
the final width goal that determines resolution of the overall
search. Intermediate phases together with the final phase are
called non-initial phases.
The main benefits of MLRsearch vs. binary search include:
o In general MLRsearch is likely to execute more search trials
overall, but less trials at a set final duration.
o In well behaving cases it greatly reduces (>50%) the overall
duration compared to a single PDR (or NDR) binary search duration,
while finding multiple drop rates.
o In all cases MLRsearch yields the same or similar results to
binary search.
o Note: both binary search and MLRsearch are susceptible to
reporting non-repeatable results across multiple runs for very bad
behaving cases.
Caveats:
o Worst case MLRsearch can take longer than a binary search e.g. in
case of drastic changes in behaviour for trials at varying
durations.
4. Sample 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
of a Continuous Integration / Continuous Development (CI/CD)
framework.
Konstantynowicz & Polak Expires April 25, 2019 [Page 5]
Internet-DrafMultiple Loss Ratio Search for Packet Throughp October 2018
4.1. Input Parameters
1. *maximum_transmit_rate* - maximum packet transmit rate to be used
by external traffic generator, limited by either the actual
Ethernet link rate or traffic generator NIC model capabilities.
Sample defaults: 2 * 14.88 Mpps for 64B 10GE link rate, 2 * 18.75
Mpps for 64B 40GE NIC maximum rate.
2. *minimum_transmit_rate* - minimum packet transmit rate to be used
for measurements. MLRsearch fails if lower transmit rate needs
to be used to meet search criteria. Default: 2 * 10 kpps (could
be higher).
3. *final_trial_duration* - required trial duration for final rate
measurements. Default: 30 sec.
4. *initial_trial_duration* - trial duration for initial MLRsearch
phase. Default: 1 sec.
5. *final_relative_width* - required measurement resolution
expressed as (lower_bound, upper_bound) interval width relative
to upper_bound. Default: 0.5%.
6. *packet_loss_ratio* - maximum acceptable PLR search criteria for
PDR measurements. Default: 0.5%.
7. *number_of_intermediate_phases* - number of phases between the
initial phase and the final phase. Impacts the overall MLRsearch
duration. Less phases are required for well behaving cases, more
phases may be needed to reduce the overall search duration for
worse behaving cases. Default (2). (Value chosen based on
limited experimentation to date. More experimentation needed to
arrive to clearer guidelines.)
4.2. Initial phase
1. First trial measures at maximum rate and discovers MRR. a. _in_:
trial_duration = initial_trial_duration. b. _in_:
offered_transmit_rate = maximum_transmit_rate. c. _do_: single
trial. d. _out_: measured loss ratio. e. _out_: mrr = measured
receive rate.
2. Second trial measures at MRR and discovers MRR2. a. _in_:
trial_duration = initial_trial_duration. b. _in_:
offered_transmit_rate = MRR. c. _do_: single trial. d. _out_:
measured loss ratio. e. _out_: mrr2 = measured receive rate.
Konstantynowicz & Polak Expires April 25, 2019 [Page 6]
Internet-DrafMultiple Loss Ratio Search for Packet Throughp October 2018
3. Third trial measures at MRR2. a. _in_: trial_duration =
initial_trial_duration. b. _in_: offered_transmit_rate = MRR2.
c. _do_: single trial. d. _out_: measured loss ratio.
4.3. Non-initial phases
1. Main loop: a. _in_: trial_duration for the current phase. Set to
initial_trial_duration for the first intermediate phase; to
final_trial_duration for the final phase; or to the element of
interpolating geometric sequence for other intermediate phases.
For example with two intermediate phases, trial_duration of the
second intermediate phase is the geometric average of
initial_strial_duration and final_trial_duration. b. _in_:
relative_width_goal for the current phase. Set to
final_relative_width for the final phase; doubled for each
preceding phase. For example with two intermediate phases, the
first intermediate phase uses quadruple of final_relative_width
and the second intermediate phase uses double of
final_relative_width. c. _in_: ndr_interval, pdr_interval from
the previous main loop iteration or the previous phase. If the
previous phase is the initial phase, both intervals have
lower_bound = MRR2, uper_bound = MRR. Note that the initial
phase is likely to create intervals with invalid bounds. d.
_do_: According to the procedure described in point 2, either
exit the phase (by jumping to 1.g.), or prepare new transmit rate
to measure with. e. _do_: Perform the trial measurement at the
new transmit rate and trial_duration, compute its loss ratio. f.
_do_: Update the bounds of both intervals, based on the new
measurement. The actual update rules are numerous, as NDR
external search can affect PDR interval and vice versa, but the
result agrees with rules of both internal and external search.
For example, any new measurement below an invalid lower_bound
becomes the new lower_bound, while the old measurement
(previously acting as the invalid lower_bound) becomes a new and
valid upper_bound. Go to next iteration (1.c.), taking the
updated intervals as new input. g. _out_: current ndr_interval
and pdr_interval. In the final phase this is also considered to
be the result of the whole search. For other phases, the next
phase loop is started with the current results as an input.
2. New transmit rate (or exit) calculation (for 1.d.):
* If there is an invalid bound then prepare for external search:
+ _If_ the most recent measurement at NDR lower_bound
transmit rate had the loss higher than zero, then the new
transmit rate is NDR lower_bound decreased by two NDR
interval widths.
Konstantynowicz & Polak Expires April 25, 2019 [Page 7]
Internet-DrafMultiple Loss Ratio Search for Packet Throughp October 2018
+ Else, _if_ the most recent measurement at PDR lower_bound
transmit rate had the loss higher than PLR, then the new
transmit rate is PDR lower_bound decreased by two PDR
interval widths.
+ Else, _if_ the most recent measurement at NDR upper_bound
transmit rate had no loss, then the new transmit rate is
NDR upper_bound increased by two NDR interval widths.
+ Else, _if_ the most recent measurement at PDR upper_bound
transmit rate had the loss lower or equal to PLR, then the
new transmit rate is PDR upper_bound increased by two PDR
interval widths.
* If interval width is higher than the current phase goal:
+ Else, _if_ NDR interval does not meet the current phase
width goal, prepare for internal search. The new transmit
rate is (NDR lower bound + NDR upper bound) / 2.
+ Else, _if_ PDR interval does not meet the current phase
width goal, prepare for internal search. The new transmit
rate is (PDR lower bound + PDR upper bound) / 2.
* Else, _if_ some bound has still only been measured at a lower
duration, prepare to re-measure at the current duration (and
the same transmit rate). The order of priorities is:
+ NDR lower_bound,
+ PDR lower_bound,
+ NDR upper_bound,
+ PDR upper_bound.
* _Else_, do not prepare any new rate, to exit the phase. This
ensures that at the end of each non-initial phase all
intervals are valid, narrow enough, and measured at current
phase trial duration.
5. Known Implementations
The only known working implementatin of MLRsearch is in Linux
Foundation FD.io CSIT project. https://wiki.fd.io/view/CSIT.
https://git.fd.io/csit/.
Konstantynowicz & Polak Expires April 25, 2019 [Page 8]
Internet-DrafMultiple Loss Ratio Search for Packet Throughp October 2018
5.1. FD.io CSIT Implementation Deviations
This document so far has been describing a simplified version of
MLRsearch algorithm. The full algorithm as implemented contains
additional logic, which makes some of the details (but not general
ideas) above incorrect. Here is a short description of the
additional logic as a list of principles, explaining their main
differences from (or additions to) the simplified description, but
without detailing their mutual interaction.
1. _Logarithmic transmit rate._ In order to better fit the relative
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 the maximum rate. Upper bound at that rate is always
considered valid.
3. _Pessimistic minimum rate._ The decreased rate is never lower
than 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
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
..
Konstantynowicz & Polak Expires April 25, 2019 [Page 9]
Internet-DrafMultiple Loss Ratio Search for Packet Throughp October 2018
7. Security Considerations
..
8. Acknowledgements
..
9. Normative References
[RFC2544] Bradner, S. and J. McQuaid, "Benchmarking Methodology for
Network Interconnect Devices", RFC 2544,
DOI 10.17487/RFC2544, March 1999,
<https://www.rfc-editor.org/info/rfc2544>.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://www.rfc-editor.org/info/rfc8174>.
Authors' Addresses
Maciek Konstantynowicz (editor)
Cisco Systems
Email: mkonstan@cisco.com
Vratko Polak (editor)
Cisco Systems
Email: vrpolak@cisco.com
Konstantynowicz & Polak Expires April 25, 2019 [Page 10]