rls1807 report: moved and renamed s/mdr_search/mlr_search/.
[csit.git] / docs / report / vpp_performance_tests / documentation / mlr_search.rst
1 MLRsearch Algorithm
2 ===================
3
4 Multiple Loss Rate search (MLRsearch) is a new search algorithm
5 implemented in FD.io CSIT project. MLRsearch discovers multiple packet
6 throughput rates in a single search, with each rate associated with a
7 distinct Packet Loss Ratio (PLR) criteria.
8
9 Two throughput measurements used in FD.io CSIT are Non-Drop Rate (NDR,
10 with zero packet loss, PLR=0) and Partial Drop Rate (PDR, with packet
11 loss rate not greater than the configured non-zero PLR). MLRsearch
12 discovers NDR and PDR in a single pass reducing required execution time
13 compared to separate binary searches for NDR and PDR. MLRsearch reduces
14 execution time even further by relying on shorter trial durations
15 of intermediate steps, with only the final measurements
16 conducted at the specified final trial duration.
17 This results in the shorter overall search
18 execution time when compared to a standard NDR/PDR binary search,
19 while guaranteeing the same or similar results.
20
21 If needed, MLRsearch can be easily adopted to discover more throughput rates
22 with different pre-defined PLRs.
23
24 .. Note:: All throughput rates are *always* bi-directional
25    aggregates of two equal (symmetric) uni-directional packet rates
26    received and reported by an external traffic generator.
27
28 Overview
29 ---------
30
31 The main properties of MLRsearch:
32
33 - MLRsearch is a duration aware multi-phase multi-rate search algorithm.
34
35   - Initial phase determines promising starting interval for the search.
36   - Intermediate phases progress towards defined final search criteria.
37   - Final phase executes measurements according to the final search
38     criteria.
39
40 - *Initial phase*:
41
42   - Uses link rate as a starting transmit rate and discovers the Maximum
43     Receive Rate (MRR) used as an input to the first intermediate phase.
44
45 - *Intermediate phases*:
46
47   - Start with initial trial duration (in the first phase) and converge
48     geometrically towards the final trial duration (in the final phase).
49   - Track two values for NDR and two for PDR.
50
51     - The values are called (NDR or PDR) lower_bound and upper_bound.
52     - Each value comes from a specific trial measurement
53       (most recent for that transmit rate),
54       and as such the value is associated with that measurement's duration and loss.
55     - A bound can be invalid, for example if NDR lower_bound
56       has been measured with nonzero loss.
57     - Invalid bounds are not real boundaries for the searched value,
58       but are needed to track interval widths.
59     - Valid bounds are real boundaries for the searched value.
60     - Each non-initial phase ends with all bounds valid.
61
62   - Start with a large (lower_bound, upper_bound) interval width and
63     geometrically converge towards the width goal (measurement resolution)
64     of the phase. Each phase halves the previous width goal.
65   - Use internal and external searches:
66
67     - External search - measures at transmit rates outside the (lower_bound,
68       upper_bound) interval. Activated when a bound is invalid,
69       to search for a new valid bound by doubling the interval width.
70       It is a variant of `exponential search`_.
71     - Internal search - `binary search`_, measures at transmit rates within the
72       (lower_bound, upper_bound) valid interval, halving the interval width.
73
74 - *Final phase* is executed with the final test trial duration, and the final
75   width goal that determines resolution of the overall search.
76   Intermediate phases together with the final phase are called non-initial phases.
77
78 The main benefits of MLRsearch vs. binary search include:
79
80 - In general MLRsearch is likely to execute more search trials overall, but
81   less trials at a set final duration.
82 - In well behaving cases it greatly reduces (>50%) the overall duration
83   compared to a single PDR (or NDR) binary search duration,
84   while finding multiple drop rates.
85 - In all cases MLRsearch yields the same or similar results to binary search.
86 - Note: both binary search and MLRsearch are susceptible to reporting
87   non-repeatable results across multiple runs for very bad behaving
88   cases.
89
90 Caveats:
91
92 - Worst case MLRsearch can take longer than a binary search e.g. in case of
93   drastic changes in behaviour for trials at varying durations.
94
95 Search Implementation
96 ---------------------
97
98 Following is a brief description of the current MLRsearch
99 implementation in FD.io CSIT.
100
101 Input Parameters
102 ````````````````
103
104 #. *maximum_transmit_rate* - maximum packet transmit rate to be used by
105    external traffic generator, limited by either the actual Ethernet
106    link rate or traffic generator NIC model capabilities. Sample
107    defaults: 2 * 14.88 Mpps for 64B 10GE link rate,
108    2 * 18.75 Mpps for 64B 40GE NIC maximum rate.
109 #. *minimum_transmit_rate* - minimum packet transmit rate to be used for
110    measurements. MLRsearch fails if lower transmit rate needs to be
111    used to meet search criteria. Default: 2 * 10 kpps (could be higher).
112 #. *final_trial_duration* - required trial duration for final rate
113    measurements. Default: 30 sec.
114 #. *initial_trial_duration* - trial duration for initial MLRsearch phase.
115    Default: 1 sec.
116 #. *final_relative_width* - required measurement resolution expressed as
117    (lower_bound, upper_bound) interval width relative to upper_bound.
118    Default: 0.5%.
119 #. *packet_loss_ratio* - maximum acceptable PLR search criteria for
120    PDR measurements. Default: 0.5%.
121 #. *number_of_intermediate_phases* - number of phases between the initial
122    phase and the final phase. Impacts the overall MLRsearch duration.
123    Less phases are required for well behaving cases, more phases
124    may be needed to reduce the overall search duration for worse behaving cases.
125    Default (2). (Value chosen based on limited experimentation to date.
126    More experimentation needed to arrive to clearer guidelines.)
127
128 Initial phase
129 `````````````
130
131 1. First trial measures at maximum rate and discovers MRR.
132
133    a. *in*: trial_duration = initial_trial_duration.
134    b. *in*: offered_transmit_rate = maximum_transmit_rate.
135    c. *do*: single trial.
136    d. *out*: measured loss ratio.
137    e. *out*: mrr = measured receive rate.
138
139 2. Second trial measures at MRR and discovers MRR2.
140
141    a. *in*: trial_duration = initial_trial_duration.
142    b. *in*: offered_transmit_rate = MRR.
143    c. *do*: single trial.
144    d. *out*: measured loss ratio.
145    e. *out*: mrr2 = measured receive rate.
146
147 3. Third trial measures at MRR2.
148
149    a. *in*: trial_duration = initial_trial_duration.
150    b. *in*: offered_transmit_rate = MRR2.
151    c. *do*: single trial.
152    d. *out*: measured loss ratio.
153
154 Non-initial phases
155 ``````````````````
156
157 1. Main loop:
158
159    a. *in*: trial_duration for the current phase.
160       Set to initial_trial_duration for the first intermediate phase;
161       to final_trial_duration for the final phase;
162       or to the element of interpolating geometric sequence
163       for other intermediate phases.
164       For example with two intermediate phases, trial_duration
165       of the second intermediate phase is the geometric average
166       of initial_strial_duration and final_trial_duration.
167    b. *in*: relative_width_goal for the current phase.
168       Set to final_relative_width for the final phase;
169       doubled for each preceding phase.
170       For example with two intermediate phases,
171       the first intermediate phase uses quadruple of final_relative_width
172       and the second intermediate phase uses double of final_relative_width.
173    c. *in*: ndr_interval, pdr_interval from the previous main loop iteration
174       or the previous phase.
175       If the previous phase is the initial phase, both intervals have
176       lower_bound = MRR2, uper_bound = MRR.
177       Note that the initial phase is likely to create intervals with invalid bounds.
178    d. *do*: According to the procedure described in point 2,
179       either exit the phase (by jumping to 1.g.),
180       or prepare new transmit rate to measure with.
181    e. *do*: Perform the trial measurement at the new transmit rate
182       and trial_duration, compute its loss ratio.
183    f. *do*: Update the bounds of both intervals, based on the new measurement.
184       The actual update rules are numerous, as NDR external search
185       can affect PDR interval and vice versa, but the result
186       agrees with rules of both internal and external search.
187       For example, any new measurement below an invalid lower_bound
188       becomes the new lower_bound, while the old measurement
189       (previously acting as the invalid lower_bound)
190       becomes a new and valid upper_bound.
191       Go to next iteration (1.c.), taking the updated intervals as new input.
192    g. *out*: current ndr_interval and pdr_interval.
193       In the final phase this is also considered
194       to be the result of the whole search.
195       For other phases, the next phase loop is started
196       with the current results as an input.
197
198 2. New transmit rate (or exit) calculation (for 1.d.):
199
200    - If there is an invalid bound then prepare for external search:
201
202      - *If* the most recent measurement at NDR lower_bound transmit rate
203        had the loss higher than zero, then
204        the new transmit rate is NDR lower_bound
205        decreased by two NDR interval widths.
206      - Else, *if* the most recent measurement at PDR lower_bound
207        transmit rate had the loss higher than PLR, then
208        the new transmit rate is PDR lower_bound
209        decreased by two PDR interval widths.
210      - Else, *if* the most recent measurement at NDR upper_bound
211        transmit rate had no loss, then
212        the new transmit rate is NDR upper_bound
213        increased by two NDR interval widths.
214      - Else, *if* the most recent measurement at PDR upper_bound
215        transmit rate had the loss lower or equal to PLR, then
216        the new transmit rate is PDR upper_bound
217        increased by two PDR interval widths.
218    - If interval width is higher than the current phase goal:
219
220      - Else, *if* NDR interval does not meet the current phase width goal,
221        prepare for internal search. The new transmit rate is
222        (NDR lower bound + NDR upper bound) / 2.
223      - Else, *if* PDR interval does not meet the current phase width goal,
224        prepare for internal search. The new transmit rate is
225        (PDR lower bound + PDR upper bound) / 2.
226    - Else, *if* some bound has still only been measured at a lower duration,
227      prepare to re-measure at the current duration (and the same transmit rate).
228      The order of priorities is:
229
230      - NDR lower_bound,
231      - PDR lower_bound,
232      - NDR upper_bound,
233      - PDR upper_bound.
234    - *Else*, do not prepare any new rate, to exit the phase.
235      This ensures that at the end of each non-initial phase
236      all intervals are valid, narrow enough, and measured
237      at current phase trial duration.
238
239 Implementation Deviations
240 -------------------------
241
242 This document so far has been describing a simplified version of MLRsearch algorithm.
243 The full algorithm as implemented contains additional logic,
244 which makes some of the details (but not general ideas) above incorrect.
245 Here is a short description of the additional logic as a list of principles,
246 explaining their main differences from (or additions to) the simplified description,
247 but without detailing their mutual interaction.
248
249 1. *Logarithmic transmit rate.*
250    In order to better fit the relative width goal,
251    the interval doubling and halving is done differently.
252    For example, the middle of 2 and 8 is 4, not 5.
253 2. *Optimistic maximum rate.*
254    The increased rate is never higher than the maximum rate.
255    Upper bound at that rate is always considered valid.
256 3. *Pessimistic minimum rate.*
257    The decreased rate is never lower than the minimum rate.
258    If a lower bound at that rate is invalid,
259    a phase stops refining the interval further (until it gets re-measured).
260 4. *Conservative interval updates.*
261    Measurements above current upper bound never update a valid upper bound,
262    even if drop ratio is low.
263    Measurements below current lower bound always update any lower bound
264    if drop ratio is high.
265 5. *Ensure sufficient interval width.*
266    Narrow intervals make external search take more time to find a valid bound.
267    If the new transmit increased or decreased rate would result in width
268    less than the current goal, increase/decrease more.
269    This can happen if the measurement for the other interval
270    makes the current interval too narrow.
271    Similarly, take care the measurements in the initial phase
272    create wide enough interval.
273 6. *Timeout for bad cases.*
274    The worst case for MLRsearch is when each phase converges to intervals
275    way different than the results of the previous phase.
276    Rather than suffer total search time several times larger
277    than pure binary search, the implemented tests fail themselves
278    when the search takes too long (given by argument *timeout*).
279
280 .. _binary search: https://en.wikipedia.org/wiki/Binary_search
281 .. _exponential search: https://en.wikipedia.org/wiki/Exponential_search
282 .. _estimation of standard deviation: https://en.wikipedia.org/wiki/Unbiased_estimation_of_standard_deviation
283 .. _simplified error propagation formula: https://en.wikipedia.org/wiki/Propagation_of_uncertainty#Simplification

©2016 FD.io a Linux Foundation Collaborative Project. All Rights Reserved.
Linux Foundation is a registered trademark of The Linux Foundation. Linux is a registered trademark of Linus Torvalds.
Please see our privacy policy and terms of use.