Internet-Draft | Multiple Loss Ratio Search | March 2022 |
Konstantynowicz & Polak | Expires 8 September 2022 | [Page] |
TODO: Update after all sections are ready.¶
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 MLRsearch 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 challenge in a simple way of getting the same result sooner, so more repetitions can be done to describe the replicability.¶
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."¶
This Internet-Draft will expire on 8 September 2022.¶
Copyright (c) 2022 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 Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License.¶
TODO: Update after most other sections are updated.¶
TODO: Mention NIC/PCI bandwidth/pps limits can be lower than bandwidth of medium.¶
The intention of this document is to provide recommendations for: * optimizing search for multiple target loss ratios at once, * speeding up the overall search time, * improve search results repeatability and comparability.¶
No part of RFC2544 is intended to be obsoleted by this document.¶
It is useful to restate the key requirements of RFC2544 using the new terminology (see section Terminology).¶
The following sections of RFC2544 are of interest for this document.¶
No additional constraints are placed on the load selection, and there is no mention of an exit condition, e.g. when there is enough trial measurements to proclaim the largest load with zero trial loss (and final trial duration) to be the Throughput found.¶
RFC2544 does not suggest to repeat Throughput search, and from just one Throughput value, it cannot be determined how repeatable that value is (how likely it is for a repeated Throughput search to end up with a value less then the precision goal away from the first value).¶
Depending on SUT behavior, different benchmark groups can report significantly different Througput values, even when using identical SUT and test equipment, just because of minor differences in their search algorithm (e.g. different max load value).¶
While repeatability can be addressed by repeating the search several times, the differences in the comparability scenario may be systematic, e.g. seeming like a bias in one or both benchmark groups.¶
MLRsearch algorithm does not really help with the repeatability problem. This document RECOMMENDS to repeat a selection of "important" tests ten times, so users can ascertain the repeatability of the results.¶
TODO: How to report? Average and standard deviation?¶
Following MLRsearch algorithm leaves less freedom for the benchmark groups to encounter the comparability problem, alghough more research is needed to determine the effect of MLRsearch's tweakable parameters.¶
https://datatracker.ietf.org/doc/html/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.¶
New "software DUTs" (traffic forwarding programs running on commercial-off-the-shelf compute server hardware) frequently exhibit quite low repeatability of Throughput results per above definition.¶
This is due to, in general, throughput rates of software DUTs (programs) being sensitive to server resource allocation by OS during runtime, as well as any interrupts or blocking of software threads involved in packet processing.¶
To deal with this, this document recommends discovery of multiple throughput rates of interest for software DUTs that run on general purpose COTS servers (with x86, AArch64 Instruction Set Architectures): * throughput rate with target of zero packet loss ratio. * at least one throughput rate with target of non-zero packet loss ratio.¶
In our experience, the higher the target loss ratio is, the better is the repeatability of the corresponding load found.¶
TODO: Define a good name for a load corresponding to a specific non-zero target loss ration, while keeping Throughput for the load corresponding to zero target loss ratio.¶
This document RECOMMENDS the benchmark groups to search for corresponding loads to at least one non-zero target loss ratio. This document does not suggest any particular non-zero target loss ratio value to search the corresponding load for.¶
This document gives several independent ideas on how to lower the (average) overall search time, while remaining unconditionally compliant with RFC2544 (and adding some of extensions).¶
This document also specifies one particular way to combine all the ideas into a single search algorithm class (single logic with few tweakable parameters).¶
Little to no research has been done into the question of which combination of ideas achieves the best compromise with respect to overal search time, high repeatability and high comparability.¶
TODO: How important it is to discuss particular implementation choices, especially when motivated by non-deterministic SUT behavior?¶
https://datatracker.ietf.org/doc/html/rfc2544#section-24 already mentions the possibity of using shorter duration for trials that are not part of "final determination".¶
Obviously, the upper and lower bound from a smaller duration trial can be used as the initial upper and lower bound for the final determination.¶
MLRsearch makes it clear a re-measurement is always needed (new trial measurement with the same load but longer duration). It also specifes what to do if the longer trial is no longer a valid bound (TODO define?), e.g. start an external search. Additionaly one halving can be saved during the shorter duration search.¶
TODO expand: Overal search ends with "final determination" search, preceded by "shorter duration search" preceded by "bound initialization", where the bounds can be considerably different from min and max load.¶
For SUTs with high repeatability, the FRMOL is usually a good approximation of Throughput. But for less repeatable SUTs, forwarding rate (TODO define) is frequently a bad approximation to Throughput, therefore halving and other robust-to-worst-case approaches have to be used. Still, forwarding rate at FRMOL load can be a good initial bound.¶
See the "Popularity of non-zero target loss ratios" section above.¶
TODO: Define "trial measurement result classification criteria", or keep reusing long phrases without definitions?¶
A search for a load corresponding to a non-zero target loss rate is very similar to a search for Throughput, just the criterion when to increase or decrease the intended load for the next trial measurement uses the comparison of trial loss ratio to the target loss ratio (instead of comparing loss count to zero) Any search algorithm that works for Throughput can be easily used also for non-zero target loss rates, perhaps with small modifications in places where the measured forwarding rate is used.¶
Note that it is possible to search for multiple loss ratio goals if needed.¶
A single trial measurement result can act as an upper bound for a lower target loss ratio, and as a lower bound for a higher target loss ratio at the same time. This is an example of how it can be advantageous to search for all loss ratio goals "at once", or at least "reuse" trial measurement result done so far.¶
Even when a search algorithm is fully deterministic in load selection while focusing on a single loss ratio and trial duration, the choice of iteration order between target loss ratios and trial durations can affect the obtained results in subtle ways. MLRsearch offers one particular ordering.¶
Aside of the two heuristics already mentioned (FRMOL based initial bounds and saving one halving when increasing trial duration), there are other tricks that can save some overall search time at the cost of keeping the difference between final lower and upper bound intentionally large (but still within the precision goal).¶
TODO: Refer implementation subsections on: * Uneven splits. * Rounding the interval width up. * Using old invalid bounds for interval width guessing.¶
The impact on overall duration is probably small, and the effect on result distribution maybe even smaller. TODO: Is the two-liner above useful at all?¶
It is possible to achieve even faster search times by abandoning some requirements and suggestions of RFC2544, mainly by reducing the wait times at start and end of trial.¶
Such results are therefore no longer compliant with RFC2544 (or at least not unconditionally), but they may still be useful for internal usage, or for comparing results of different DUTs achieved with an identical non-compliant algorithm.¶
TODO: Refer to the subsection with CSIT customizations.¶
RFC2544 can be understood as having a number of implicit requirements. They are made explicit in this section (as requirements for this document, not for RFC2544).¶
Recommendations on how to properly address the implicit requirements are out of scope of this document.¶
TODO: Mention the timeout parameter?¶
Both TG and TA MUST be able to handle correctly every intended load used during the search.¶
On TG side, the difference between Intended Load and Offered Load MUST be small.¶
TODO: How small? Difference of one packet may not be measurable due to time uncertainties.¶
TODO expand: time uncertainty.¶
To ensure that, max load (see Terminology) has to be set to low enough value. Benchmark groups MAY list the max load value used, especially if the Throughput value is equal (or close) to the max load.¶
Solutions (even problem formulations) for the following open problems are outside of the scope of this document: * Detecting when the test equipment operates above its safe load. * Finding a large but safe load value. * Correcting any result affected by max load value not being a safe load.¶
RFC2544 requires quite conservative time delays see https://datatracker.ietf.org/doc/html/rfc2544#section-23 to prevent frames buffered in one trial measurement to be counted as received in a subsequent trial measurement.¶
However, for some SUTs it may still be possible to buffer enough frames, so they are still sending them (perhaps in bursts) when the next trial measurement starts. Sometimes, this can be detected as a negative trial loss count, e.g. TA receiving more frames than TG has sent during this trial measurement. Frame duplication is another way of causing the negative trial loss count.¶
https://datatracker.ietf.org/doc/html/rfc2544#section-10 recommends to use sequence numbers in frame payloads, but generating and verifying them requires test equipment resources, which may be not plenty enough to suport at high loads. (Using low enough max load would work, but frequently that would be smaller than SUT's sctual Throughput.)¶
RFC2544 does not offer any solution to the negative loss problem, except implicitly treating negative trial loss counts the same way as positive trial loss counts.¶
This document also does not offer any practical solution.¶
Instead, this document SUGGESTS the search algorithm to take any precaution necessary to avoid very late frames.¶
This document also REQUIRES any detected duplicate frames to be counted as additional lost frames. This document also REQUIRES, any negative trial loss ratio to be treated as positive trial loss ratio of the same absolute value.¶
!!! Nothing below is up-to-date with draft v02. !!!¶
TODO: Old section, probably obsoleted by preceding section(s).¶
Multiple Loss Ratio search (MLRsearch) is a packet throughput search algorithm suitable for deterministic systems (as opposed to probabilistic systems). MLRsearch discovers multiple packet throughput rates in a single search, each rate is associated with a distinct Packet Loss Ratio (PLR) criterion.¶
For cases when multiple rates need to be found, this property makes MLRsearch more efficient in terms of time execution, compared to traditional throughput search algorithms that discover a single packet rate per defined search criteria (e.g. a binary search specified by [RFC2544]). 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 traditional binary search, while guaranteeing the same results for deterministic systems.¶
In practice, two rates with distinct PLRs are commonly used for packet 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 with NDR and PDR pair as an example.¶
Similarly to other throughput search approaches like binary search, MLRsearch is effective for SUTs/DUTs with PLR curve that is non-decreasing with growing offered load. It may not be as effective for SUTs/DUTs with abnormal PLR curves, although it will always converge to some value.¶
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:¶
MLRsearch can be applied even without those assumptions, but in that case the aggregate loss ratio is less useful as a metric.¶
MLRsearch can be used for network transactions consisting of more than just one packet, or anything else that has intended load as input and loss ratio as output (duration as input is optional). This text uses mostly packet-centric language.¶
The main properties of MLRsearch:¶
MLRsearch is a duration aware multi-phase multi-rate search algorithm:¶
Initial Phase:¶
Multiple Intermediate Phases:¶
Trial duration:¶
Track all previous trial measurement results:¶
Effective loss ratios are tracked.¶
The algorithm queries the results to find best lower and upper bounds.¶
Search:¶
Use of internal and external searches:¶
External search:¶
Internal search:¶
The interval does not need to be split into exact halves, if other split can get to the target width goal faster.¶
Final Phase:¶
The returned bounds stay within prescribed min_rate and max_rate.¶
The main benefits of MLRsearch vs. binary search include:¶
Caveats:¶
Following is a brief description of a sample MLRsearch implementation, which is a simplified version of the existing implementation.¶
First trial measures at configured maximum transmit rate (MTR) and discovers maximum receive rate (MRR).¶
If MRR is too close to MTR, MRR is set below MTR so that interval width is equal to the width goal of the first intermediate phase. If MRR is less than min_rate, min_rate is used.¶
Second trial measures at MRR and discovers MRR2.¶
Third trial measures at MRR2.¶
Main phase loop:¶
Internal target ratio loop:¶
DO: According to the procedure described in point 2:¶
OUT: In the final phase, bounds for each target loss ratio are extracted and returned.¶
New transmit rate (or exit) calculation (for point 1.4.3):¶
If the previous duration has the best upper and lower bound, select the middle point as the new transmit rate.¶
Discussion, assuming the middle point is selected and measured:¶
This also explains why previous phase has double width goal:¶
If only upper bound exists in current duration results:¶
Select new transmit rate using external search:¶
If only lower bound exists in current duration results:¶
The only remaining option is both bounds in current duration results.¶
This can happen in two ways, depending on how the lower bound was chosen.¶
Compute "bisecting" candidate transmit rate:¶
The only known working implementation of MLRsearch is in the open-source code running in Linux Foundation FD.io CSIT project [FDio-CSIT-MLRsearch] as part of a Continuous Integration / Continuous Development (CI/CD) framework.¶
MLRsearch is also available as a Python package in [PyPI-MLRsearch].¶
This document so far has been describing a simplified version of MLRsearch algorithm. The full algorithm as implemented in CSIT 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.¶
Logarithmic transmit rate.¶
Timeout for bad cases.¶
Intended count.¶
Duration stretching.¶
The implementation uses an explicit stop,¶
The implementation tolerates some small difference between attempted count and intended count.¶
If the difference is higher, the unsent packets are counted as lost.¶
Excess packets.¶
The following list describes a search from a real test run in CSIT (using the default input values as above).¶
Measurement 1, intended load 18750000.0 pps (MTR), measured loss ratio 0.7089514628479618 (valid upper bound for both NDR and PDR).¶
Measurement 2, intended load 5457160.071600716 pps (MRR), measured loss ratio 0.018650817320118702 (new tightest upper bounds).¶
Measurement 3, intended load 5348832.933500009 pps (slightly less than MRR2 in preparation for first intermediate phase target interval width), measured loss ratio 0.00964383362905351 (new tightest upper bounds).¶
Measurement 4, intended load 4936605.579021453 pps (no lower bound, performing external search downwards, for NDR), measured loss ratio 0.0 (valid lower bound for both NDR and PDR).¶
Measurement 5, intended load 5138587.208637197 pps (bisecting for NDR), measured loss ratio 0.0 (new tightest lower bounds).¶
Measurement 6, intended load 5242656.244044665 pps (bisecting), measured loss ratio 0.013523745379347257 (new tightest upper bounds).¶
Measurement 7, intended load 5190360.904111567 pps (initial bisect for NDR), measured loss ratio 0.0023533920869969953 (NDR upper bound, PDR lower bound).¶
Measurement 8, intended load 5138587.208637197 pps (re-measuring NDR lower bound), measured loss ratio 1.2080222912800403e-06 (new tightest NDR upper bound).¶
Measurement 9, intended load 4936605.381062318 pps (external NDR search down), measured loss ratio 0.0 (new valid NDR lower bound).¶
Measurement 10, intended load 5036583.888432355 pps (NDR bisect), measured loss ratio 0.0 (new tightest NDR lower bound).¶
Measurement 11, intended load 5087329.903232804 pps (NDR bisect), measured loss ratio 0.0 (new tightest NDR lower bound).¶
Measurement 12, intended load 5242656.244044665 pps (re-measuring PDR upper bound), measured loss ratio 0.0101174866190136 (still valid PDR upper bound).¶
Measurement 13, intended load 5112894.3238511775 pps (initial bisect for NDR), measured loss ratio 0.0 (new tightest NDR lower bound).¶
Measurement 14, intended load 5138587.208637197 (re-measuring NDR upper bound), measured loss ratio 2.030389804256833e-06 (still valid PDR upper bound).¶
Measurement 15, intended load 5216443.04126728 pps (initial bisect for PDR), measured loss ratio 0.005620871287975237 (new tightest PDR upper bound).¶
Measurement 16, intended load 5190360.904111567 (re-measuring PDR lower bound), measured loss ratio 0.0027629971184465604 (still valid PDR lower bound).¶
No requests of IANA.¶
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.¶
Many thanks to Alec Hothan of OPNFV NFVbench project for thorough review and numerous useful comments and suggestions.¶