docs/content/methodology/data_plane_throughput/mlrsearch.md

   1 ---
   2 bookToc: false
   3 title: "MLRsearch"
   4 weight: 2
   5 ---
   6
   7 # MLRsearch
   8
   9 ## Overview
  10
  11 Multiple Loss Ratio search (MLRsearch) tests use an optimized search algorithm
  12 implemented in FD.io CSIT project. MLRsearch discovers any number of
  13 loss ratio loads in a single search.
  14
  15 Two loss ratio goals are of interest in FD.io CSIT, leading to Non-Drop Rate
  16 (NDR, loss ratio goal is exact zero) and Partial Drop Rate
  17 (PDR, non-zero loss ratio goal, currently 0.5%).
  18
  19 MLRsearch discovers all the loads in a single pass, reducing required time
  20 duration compared to separate `binary search`es[^1] for each rate. Overall
  21 search time is reduced even further by relying on shorter trial
  22 durations of intermediate steps, with only the final measurements
  23 conducted at the specified final trial duration. This results in the
  24 shorter overall execution time when compared to standard NDR/PDR binary
  25 search, while guaranteeing similar results.
  26
  27 .. Note:: All throughput rates are *always* bi-directional
  28    aggregates of two equal (symmetric) uni-directional packet rates
  29    received and reported by an external traffic generator,
  30    unless the test specifically requires unidirectional traffic.
  31
  32 ## Search Implementation
  33
  34 Detailed description of the MLRsearch algorithm is included in the IETF
  35 draft
  36 [draft-ietf-bmwg-mlrsearch-02](https://datatracker.ietf.org/doc/html/draft-ietf-bmwg-mlrsearch-02)
  37 that is in the process of being standardized in the IETF Benchmarking
  38 Methodology Working Group (BMWG).
  39 (Newer version is published in IETF, describing improvements not yet used
  40 in CSIT production.)
  41
  42 MLRsearch is also available as a
  43 [PyPI (Python Package Index) library](https://pypi.org/project/MLRsearch/).
  44
  45 ## Algorithm highlights
  46
  47 MRR and receive rate at MRR load are used as initial guesses for the search.
  48
  49 All previously measured trials (except the very first one which can act
  50 as a warm-up) are taken into consideration, unless superseded
  51 by a trial at the same load but higher duration.
  52
  53 For every loss ratio goal, tightest upper and lower bound
  54 (from results of large enough trial duration) form an interval.
  55 Exit condition is given by that interval reaching low enough relative width.
  56 Small enough width is achieved by bisecting the current interval.
  57 The bisection can be uneven, to save measurements based on information theory.
  58
  59 Switching to higher trial duration generally requires a re-measure
  60 at a load from previous trial duration.
  61 When the re-measurement does not confirm previous bound classification
  62 (e.g. tightest lower bound at shorter trial duration becomes
  63 a newest tightest upper bound upon re-measurement),
  64 external search is used to find close enough bound of the lost type.
  65 External search is a generalization of the first stage of
  66 `exponential search`[^2].
  67
  68 Shorter trial durations use double width goal,
  69 because one bisection is always safe before risking external search.
  70
  71 Within an iteration for a specific trial duration, smaller loss ratios (NDR)
  72 are narrowed down first before search continues with higher loss ratios (PDR).
  73
  74 Other heuristics are there, aimed to prevent unneccessarily narrow intervals,
  75 and to handle corner cases around min and max load.
  76
  77 ## Deviations from RFC 2544
  78
  79 CSIT does not have any explicit wait times before and after trial traffic.
  80
  81 Small differences between intended and offered load are tolerated,
  82 mainly due to various time overheads preventing precise measurement
  83 of the traffic duration (and TRex can sometimes suffer from duration
  84 stretching).
  85
  86 The final trial duration is only 30s (10s for reconf tests).
  87
  88 [^1]: [binary search](https://en.wikipedia.org/wiki/Binary_search)
  89 [^2]: [exponential search](https://en.wikipedia.org/wiki/Exponential_search)