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