From 374954b9d648f503f6783325a1266457953a998d Mon Sep 17 00:00:00 2001 From: Tibor Frank Date: Wed, 3 May 2023 13:53:27 +0000 Subject: C-Docs: New structure Change-Id: I73d107f94b28b138f3350a9e1eedb0555583a9ca Signed-off-by: Tibor Frank --- .../data_plane_throughput/mlr_search.md | 88 ++++++++++++++++++++++ 1 file changed, 88 insertions(+) create mode 100644 docs/content/methodology/measurements/data_plane_throughput/mlr_search.md (limited to 'docs/content/methodology/measurements/data_plane_throughput/mlr_search.md') diff --git a/docs/content/methodology/measurements/data_plane_throughput/mlr_search.md b/docs/content/methodology/measurements/data_plane_throughput/mlr_search.md new file mode 100644 index 0000000000..93bdb51efe --- /dev/null +++ b/docs/content/methodology/measurements/data_plane_throughput/mlr_search.md @@ -0,0 +1,88 @@ +--- +title: "MLR Search" +weight: 2 +--- + +# MLR Search + +## 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. + +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 +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 +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. + +## 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) +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/). + +## Algorithm highlights + +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. + +For every loss ratio goal, tightest upper and lower bound +(from results of large enough trial duration) 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), +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, +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). + +Other heuristics are there, aimed to prevent unneccessarily narrow intervals, +and to handle corner cases around min and max load. + +## Deviations from RFC 2544 + +CSIT does not have any explicit wait times before and after trial traffic. + +Small differences between intended and offered load are 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). + +[^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