docs/content/methodology/measurements/data_plane_throughput/mlr_search.md

   1 ---
   2 title: "MLR Search"
   3 weight: 2
   4 ---
   5
   6 # MLR Search
   7
   8 ## Overview
   9
  10 Multiple Loss Ratio search (MLRsearch) tests use an optimized search algorithm
  11 implemented in FD.io CSIT project. MLRsearch discovers conditional throughput
  12 corresponding to any number of loss ratio goals, within a single search.
  13
  14 Two loss ratio goals are of interest in FD.io CSIT, leading to Non-Drop Rate
  15 (NDR, loss ratio goal is exact zero) and Partial Drop Rate
  16 (PDR, 0.5% loss ratio goal).
  17 Instead of a single long trial, a sequence of short (1s) trials is done.
  18 Thus, instead of final trial duration, a duration sum (20s) is prescribed.
  19 This allows the algorithm to make a decision sooner,
  20 when the results are quite one-sided.
  21 Also, only one half of the trial results is required to meet
  22 the loss ratio requirement, making the conditional throughput more stable.
  23 The conditional throughput in this case is the median forwarding rate
  24 among all full-length trials (including imaginary missing ones with high loss)
  25 at the relevant lower bound intended load.
  26
  27 MLRsearch discovers all the loads in single search, reducing required time
  28 duration compared to separate `binary search`es[^1] for each rate. Overall
  29 search time is reduced even further by relying on shorter trial
  30 duration sums for intermediate targets, with only measurements for
  31 final targets require the full duration sum. This results in the
  32 shorter overall execution time when compared to standard NDR/PDR binary
  33 search, while guaranteeing similar results.
  34
  35     Note: The conditional throughput is *always* reported by Robot code
  36     as a bi-directional aggregate of two (usually symmetric)
  37     uni-directional packet rates received and reported by an
  38     external traffic generator (TRex), unless the test specifically requires
  39     unidirectional traffic. The underlying Python library uses
  40     unidirectional values instead, as min and max load are given for those.
  41
  42 ## Search Implementation
  43
  44 Detailed description of the MLRsearch algorithm is included in the IETF
  45 draft
  46 [draft-ietf-bmwg-mlrsearch](https://datatracker.ietf.org/doc/html/draft-ietf-bmwg-mlrsearch)
  47 that is in the process of being standardized in the IETF Benchmarking
  48 Methodology Working Group (BMWG).
  49
  50 MLRsearch is also available as a
  51 [PyPI (Python Package Index) library](https://pypi.org/project/MLRsearch/).
  52
  53 ## Algorithm highlights
  54
  55 MRR and receive rate at MRR load are used as initial guesses for the search.
  56
  57 All previously measured trials (except the very first one which acts
  58 as a warm-up) are taken into consideration.
  59
  60 For every loss ratio goal, the relevant upper and lower bound
  61 (intended loads, among loads of large enough duration sum) form an interval.
  62 Exit condition is given by that interval reaching low enough relative width.
  63 Small enough width is achieved by bisecting the current interval.
  64 The bisection can be uneven, to save measurements based on information theory.
  65
  66 Switching to higher trial duration sum generally requires additional trials
  67 at a load from previous duration sum target.
  68 When this refinement does not confirm previous bound classification
  69 (e.g. a lower bound for preceding target
  70 becomes an upper bound of the new target due to new trail results),
  71 external search is used to find close enough bound of the lost type.
  72 External search is a generalization of the first stage of
  73 `exponential search`[^2].
  74
  75 A preceding target uses double of the next width goal,
  76 because one bisection is always safe before risking external search.
  77
  78 As different search targets are interested at different loads,
  79 lower intended load are measured first,
  80 as that approach saves more time when trial results are not very consistent.
  81 Other heuristics are there, aimed to prevent unneccessarily narrow intervals,
  82 and to handle corner cases around min and max load.
  83
  84 ## Deviations from RFC 2544
  85
  86 RFC 2544 implies long final trial duration (just one long trial is needed
  87 for classification to lower or uper bound, so exceed ratio does not matter).
  88 With 1s trials and 0.5 exceed ratio, NDR values reported by CSIT
  89 are likely higher than RFC 2544 throughput (especially for less stable tests).
  90
  91 CSIT does not have any explicit wait times before and after trial traffic.
  92 (But the TRex-based measurer takes almost half a second between targets.)
  93
  94 Small difference between intended load and offered load is tolerated,
  95 mainly due to various time overheads preventing precise measurement
  96 of the traffic duration (and TRex can sometimes suffer from duration
  97 stretching). Large difference is reported as unsent packets
  98 (measurement is forcibly stopped after given time), counted as
  99 a packet loss, so search focuses on loads actually achievable by TRex.
 100
 101 In some tests, negative loss count is observed (TRex sees more packets
 102 coming back to it than TRex sent this trial). CSIT code treats that
 103 as a packet loss (as if VPP duplicated the packets),
 104 but TRex does not check other packets for duplication
 105 (as many traffic profiles generate non-unique packets).
 106
 107 [^1]: [binary search](https://en.wikipedia.org/wiki/Binary_search)
 108 [^2]: [exponential search](https://en.wikipedia.org/wiki/Exponential_search)