From b2b84bde7a75101ce32c3dd514b519324a0f6c81 Mon Sep 17 00:00:00 2001 From: Vratko Polak Date: Thu, 19 Oct 2023 12:00:37 +0200 Subject: fix(methodology): update MLRsearch page for v8 Change-Id: I1c369ab8e52a6f6fabede0617f526eab39e4469f Signed-off-by: Vratko Polak (cherry picked from commit fcf4250fa06e9615953de0f3d18a509b8288200e) --- .../data_plane_throughput/mlr_search.md | 84 +++++++++++++--------- 1 file changed, 52 insertions(+), 32 deletions(-) diff --git a/docs/content/methodology/measurements/data_plane_throughput/mlr_search.md b/docs/content/methodology/measurements/data_plane_throughput/mlr_search.md index 93bdb51efe..72e68a5fc7 100644 --- a/docs/content/methodology/measurements/data_plane_throughput/mlr_search.md +++ b/docs/content/methodology/measurements/data_plane_throughput/mlr_search.md @@ -8,35 +8,44 @@ weight: 2 ## Overview Multiple Loss Ratio search (MLRsearch) tests use an optimized search algorithm -implemented in FD.io CSIT project. MLRsearch discovers any number of -loss ratio loads in a single search. +implemented in FD.io CSIT project. MLRsearch discovers conditional throughput +corresponding to any number of loss ratio goals, within a single search. Two loss ratio goals are of interest in FD.io CSIT, leading to Non-Drop Rate (NDR, loss ratio goal is exact zero) and Partial Drop Rate -(PDR, non-zero loss ratio goal, currently 0.5%). - -MLRsearch discovers all the loads in a single pass, reducing required time +(PDR, 0.5% loss ratio goal). +Instead of a single long trial, a sequence of short (1s) trials is done. +Thus, instead of final trial duration, a duration sum (20s) is prescribed. +This allows the algorithm to make a decision sooner, +when the results are quite one-sided. +Also, only one half of the trial results is required to meet +the loss ratio requirement, making the conditional throughput more stable. +The conditional throughput in this case is the median forwarding rate +among all full-length trials (including imaginary missing ones with high loss) +at the relevant lower bound intended load. + +MLRsearch discovers all the loads in single search, reducing required time duration compared to separate `binary search`es[^1] for each rate. Overall search time is reduced 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 +duration sums for intermediate targets, with only measurements for +final targets require the full duration sum. This results in the shorter overall execution time when compared to standard NDR/PDR binary search, while guaranteeing similar results. - Note: All throughput rates are *always* bi-directional aggregates of two - equal (symmetric) uni-directional packet rates received and reported by an - external traffic generator, unless the test specifically requires - unidirectional traffic. + Note: The conditional throughput is *always* reported by Robot code + as a bi-directional aggregate of two (usually symmetric) + uni-directional packet rates received and reported by an + external traffic generator (TRex), unless the test specifically requires + unidirectional traffic. The underlying Python library uses + unidirectional values instead, as min and max load are given for those. ## Search Implementation Detailed description of the MLRsearch algorithm is included in the IETF draft -[draft-ietf-bmwg-mlrsearch-02](https://datatracker.ietf.org/doc/html/draft-ietf-bmwg-mlrsearch-02) +[draft-ietf-bmwg-mlrsearch](https://datatracker.ietf.org/doc/html/draft-ietf-bmwg-mlrsearch) that is in the process of being standardized in the IETF Benchmarking Methodology Working Group (BMWG). -(Newer version is published in IETF, describing improvements not yet used -in CSIT production.) MLRsearch is also available as a [PyPI (Python Package Index) library](https://pypi.org/project/MLRsearch/). @@ -45,44 +54,55 @@ MLRsearch is also available as a MRR and receive rate at MRR load are used as initial guesses for the search. -All previously measured trials (except the very first one which can act -as a warm-up) are taken into consideration, unless superseded -by a trial at the same load but higher duration. +All previously measured trials (except the very first one which acts +as a warm-up) are taken into consideration. -For every loss ratio goal, tightest upper and lower bound -(from results of large enough trial duration) form an interval. +For every loss ratio goal, the relevant upper and lower bound +(intended loads, among loads of large enough duration sum) form an interval. Exit condition is given by that interval reaching low enough relative width. Small enough width is achieved by bisecting the current interval. The bisection can be uneven, to save measurements based on information theory. -Switching to higher trial duration generally requires a re-measure -at a load from previous trial duration. -When the re-measurement does not confirm previous bound classification -(e.g. tightest lower bound at shorter trial duration becomes -a newest tightest upper bound upon re-measurement), +Switching to higher trial duration sum generally requires additional trials +at a load from previous duration sum target. +When this refinement does not confirm previous bound classification +(e.g. a lower bound for preceding target +becomes an upper bound of the new target due to new trail results), external search is used to find close enough bound of the lost type. External search is a generalization of the first stage of `exponential search`[^2]. -Shorter trial durations use double width goal, +A preceding target uses double of the next width goal, because one bisection is always safe before risking external search. -Within an iteration for a specific trial duration, smaller loss ratios (NDR) -are narrowed down first before search continues with higher loss ratios (PDR). - +As different search targets are interested at different loads, +lower intended load are measured first, +as that approach saves more time when trial results are not very consistent. Other heuristics are there, aimed to prevent unneccessarily narrow intervals, and to handle corner cases around min and max load. ## Deviations from RFC 2544 +RFC 2544 implies long final trial duration (just one long trial is needed +for classification to lower or uper bound, so exceed ratio does not matter). +With 1s trials and 0.5 exceed ratio, NDR values reported by CSIT +are likely higher than RFC 2544 throughput (especially for less stable tests). + CSIT does not have any explicit wait times before and after trial traffic. +(But the TRex-based measurer takes almost half a second between targets.) -Small differences between intended and offered load are tolerated, +Small difference between intended load and offered load is tolerated, mainly due to various time overheads preventing precise measurement of the traffic duration (and TRex can sometimes suffer from duration -stretching). - -The final trial duration is only 30s (10s for reconf tests). +stretching). Large difference is reported as unsent packets +(measurement is forcibly stopped after given time), counted as +a packet loss, so search focuses on loads actually achievable by TRex. + +In some tests, negative loss count is observed (TRex sees more packets +coming back to it than TRex sent this trial). CSIT code treats that +as a packet loss (as if VPP duplicated the packets), +but TRex does not check other packets for duplication +(as many traffic profiles generate non-unique packets). [^1]: [binary search](https://en.wikipedia.org/wiki/Binary_search) [^2]: [exponential search](https://en.wikipedia.org/wiki/Exponential_search) -- cgit 1.2.3-korg