docs/report/introduction/methodology_data_plane_throughput/methodology_mlrsearch_tests.rst

   1 .. _mlrsearch_algorithm:
   2
   3 MLRsearch Tests
   4 ^^^^^^^^^^^^^^^
   5
   6 Overview
   7 ~~~~~~~~
   8
   9 Multiple Loss Ratio search (MLRsearch) tests use an optimized search algorithm
  10 implemented in FD.io CSIT project. MLRsearch discovers any number of
  11 loss ratio loads in a single search.
  12
  13 Two loss ratio goals are of interest in FD.io CSIT, leading to Non-Drop Rate
  14 (NDR, loss ratio goal is exact zero) and Partial Drop Rate
  15 (PDR, non-zero loss ratio goal, currently 0.5%).
  16
  17 MLRsearch discovers all the loads in a single pass, reducing required time
  18 duration compared to separate `binary search`_es for each rate. Overall
  19 search time is reduced even further by relying on shorter trial
  20 durations of intermediate steps, with only the final measurements
  21 conducted at the specified final trial duration. This results in the
  22 shorter overall execution time when compared to standard NDR/PDR binary
  23 search, while guaranteeing similar results.
  24
  25 .. Note:: All throughput rates are *always* bi-directional
  26    aggregates of two equal (symmetric) uni-directional packet rates
  27    received and reported by an external traffic generator,
  28    unless the test specifically requires unidirectional traffic.
  29
  30 Search Implementation
  31 ~~~~~~~~~~~~~~~~~~~~~
  32
  33 Detailed description of the MLRsearch algorithm is included in the IETF
  34 draft `draft-ietf-bmwg-mlrsearch-02
  35 <https://datatracker.ietf.org/doc/html/draft-ietf-bmwg-mlrsearch-02>`_
  36 that is in the process of being standardized in the IETF Benchmarking
  37 Methodology Working Group (BMWG).
  38 (Newer version is published in IETF, describing improvements not yet used
  39 in CSIT production.)
  40
  41 MLRsearch is also available as a `PyPI (Python Package Index) library
  42 <https://pypi.org/project/MLRsearch/>`_.
  43
  44 Algorithm highlights
  45 ~~~~~~~~~~~~~~~~~~~~
  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 `exponential search`_.
  66
  67 Shorter trial durations use double width goal,
  68 because one bisection is always safe before risking external search.
  69
  70 Within an iteration for a specific trial duration, smaller loss ratios (NDR)
  71 are narrowed down first before search continues with higher loss ratios (PDR).
  72
  73 Other heuristics are there, aimed to prevent unneccessarily narrow intervals,
  74 and to handle corner cases around min and max load.
  75
  76 Deviations from RFC 2544
  77 ~~~~~~~~~~~~~~~~~~~~~~~~
  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 stretching).
  84
  85 The final trial duration is only 30s (10s for reconf tests).
  86
  87 .. _binary search: https://en.wikipedia.org/wiki/Binary_search
  88 .. _exponential search: https://en.wikipedia.org/wiki/Exponential_search