1 Experimental: MDR Search
2 ========================
4 Multiple Drop Rate (MDR) Search is a new search algorithm implemented in
5 FD.io CSIT project. MDR discovers multiple packet throughput rates in a
6 single search, with each rate associated with a distinct Packet Loss
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). MDR search
12 discovers NDR and PDR in a single pass reducing required execution time
13 compared to separate binary searches for NDR and PDR. MDR 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.
21 If needed, MDR can be easily adopted to discover more throughput rates
22 with different pre-defined PLRs.
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.
31 The main properties of MDR search:
33 - MDR is a duration aware multi-phase multi-rate search algorithm.
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
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.
45 - *Intermediate phases*:
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.
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.
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:
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.
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.
78 The main benefits of MDR search vs. binary search include:
80 - In general MDR 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 MDR yields the same or similar results to binary search.
86 - Note: both binary search and MDR are susceptible to reporting
87 non-repeatable results across multiple runs for very bad behaving
92 - Worst case MDR can take longer than a binary search e.g. in case of
93 drastic changes in behaviour for trials at varying durations.
98 Following is a brief description of the current MDR search
99 implementation in FD.io CSIT.
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. MDR search 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 MDR phase.
116 #. *final_relative_width* - required measurement resolution expressed as
117 (lower_bound, upper_bound) interval width relative to upper_bound.
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 MDR search 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.)
131 1. First trial measures at maximum rate and discovers MRR.
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.
139 2. Second trial measures at MRR and discovers MRR2.
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.
147 3. Third trial measures at MRR2.
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.
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.
198 2. New transmit rate (or exit) calculation (for 1.d.):
200 - If there is an invalid bound then prepare for external search:
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 - Else, *if* NDR (or PDR) interval does not meet the current phase width goal,
219 prepare for internal search. The new transmit rate is
220 (lower bound + upper bound) / 2.
221 It does not matter much which interval is investigated first.
222 The current implementation starts with NDR, unless PDR interval is wider
223 (but always preferring NDR is slightly better).
224 - Else, *if* some bound has still only been measured at a lower duration,
225 prepare to re-measure at the current duration (and the same transmit rate).
226 The order of priorities is:
232 - *Else*, do not prepare any new rate, to exit the phase.
233 This ensures that at the end of each non-initial phase
234 all intervals are valid, narrow enough, and measured
235 at current phase trial duration.
237 Implementation Deviations
238 -------------------------
240 This document so far has been describing a simplified version of MDR search algorithm.
241 The full algorithm as implemented contains additional logic,
242 which makes some of the details (but not general ideas) above incorrect.
243 Here is a short description of the additional logic as a list of principles,
244 explaining their main differences from (or additions to) the simplified description,
245 but without detailing their mutual interaction.
247 1. *Logarithmic transmit rate.*
248 In order to better fit the relative width goal,
249 the interval doubling and halving is done differently.
250 For example, the middle of 2 and 8 is 4, not 5.
251 2. *Optimistic maximum rate.*
252 The increased rate is never higher than the maximum rate.
253 Upper bound at that rate is always considered valid.
254 3. *Pessimistic minimum rate.*
255 The decreased rate is never lower than the minimum rate.
256 If a lower bound at that rate is invalid,
257 a phase stops refining the interval further (until it gets re-measured).
258 4. *Conservative interval updates.*
259 Measurements above current upper bound never update a valid upper bound,
260 even if drop ratio is low.
261 Measurements below current lower bound always update any lower bound
262 if drop ratio is high.
263 5. *Ensure sufficient interval width.*
264 Narrow intervals make external search take more time to find a valid bound.
265 If the new transmit increased or decreased rate would result in width
266 less than the current goal, increase/decrease more.
267 This can happen if measurement for the other interval
268 makes the current interval too narrow.
269 Similarly, take care the measurements in the initial phase
270 create wide enough interval.
271 6. *Timeout for bad cases.*
272 The worst case for MDR search is when each phase converges to intervals
273 way different than the results of the previous phase.
274 Rather than suffer total search time several times larger
275 than pure binary search, the implemented tests fail themselves
276 when the search takes too long (given by argument *timeout*).
278 Test Effectiveness Comparison
279 -----------------------------
284 CSIT release 1804 contains two test suites that use the new MDR search
285 to enable comparison against existing CSIT NDR and PDR binary searches.
286 The suites got chosen based on the level of consistency of their
287 historical NDR/PDR results:
289 #. *10Ge2P1X520-Ethip4-Ip4Base-Ndrpdr* - yielding very consistent binary
291 #. *10Ge2P1X520-Eth-L2Bdbasemaclrn-Eth-2Vhostvr1024-1Vm-Ndrpdr* - yielding
292 somewhat inconsistent results.
294 Here "inconsistent" means the values found differ between runs,
295 even though the setup and the test are exactly the same.
297 The search part of CSIT binary search tests requires a single 5-second warmup
298 and each trial measurement is set to 10 seconds.
300 New tests with MDR search do not have any warmup, as initial measurements
301 are not critical to the final result.
303 Fairness of the following comparison has been achieved
304 by setting MDR final relative width to values causing the width to match
305 the binary NDR/PDR result.
306 Each search algorithm has been run with three different
307 (final) trial durations: 10s, 30s and 60s.
309 Tables below compares overall test duration between the search tests.
310 For simplicity only data for single thread 64B packet tests is listed,
311 as it takes the longest in all cases.
313 Data in tables is based on result of 6 runs.
318 .. table:: Table 1. Search part of test duration.
320 ==================== ========== =========== =========== ========== =========== ===========
321 Duration+-avgdev [s] IP4 10s IP4 30s IP4 60s Vhost 10s Vhost 30s Vhost 60s
322 ==================== ========== =========== =========== ========== =========== ===========
323 MDR (both intervals) 50.8+-1.2 109.0+-10.0 202.8+-11.7 80.5+-9.0 201.9+-20.6 474.9+-58.2
324 NDR binary 98.9+-0.1 278.6+-0.1 548.8+-0.1 119.8+-0.1 339.3+-0.1 669.6+-0.2
325 PDR binary 98.9+-0.1 278.6+-0.1 548.8+-0.1 119.7+-0.1 339.3+-0.1 669.5+-0.1
326 NDR+PDR sum 197.8+-0.1 557.2+-0.2 1097.6+-0.1 239.5+-0.1 678.7+-0.1 1339.2+-0.1
327 ==================== ========== =========== =========== ========== =========== ===========
329 .. note:: Here "avgdev" is the estimated difference between
330 the average duration computed from the limited sample
331 and a true average duration as its hypothetical limit for infinite samples.
332 To get the usual "standard deviation" of duration, "avgdev" has to be multiplied
333 by the square root of the number of samples.
334 For the subtle details see `estimation of standard deviation`_,
335 we used zero ACF and c4==1.
337 .. table:: Table 2. MDR duration as percentage of NDR duration.
339 ==================================== ========= ========= ========= ========= ========= =========
340 Fraction+-stdev [%] IP4 10s IP4 30s IP4 60s Vhost 10s Vhost 30s Vhost 60s
341 ==================================== ========= ========= ========= ========= ========= =========
342 MDR duration divided by NDR duration 51.4+-1.2 39.1+-3.6 37.0+-2.1 67.2+-7.5 59.5+-6.1 70.9+-8.7
343 ==================================== ========= ========= ========= ========= ========= =========
345 .. note:: Here "stdev" is standard deviation as computed by the
346 `simplified error propagation formula`_.
351 In consistent tests, MDR is on average more than 50% faster
352 than a single NDR binary search (even though MDR also detects PDR).
354 One exception is 10 second final trial duration,
355 where MDR is (only) almost 50% faster than NDR binary search.
356 Most probably presence of 2 intermediate phases (instead of just 1) hurts there.
358 In inconsistent tests MDR is still somewhat faster than NDR binary search,
359 but it is not by 50%, and it is hard to quantify as MDR samples have wildly
365 The following graphs were created from the data gathered from comparison runs,
367 The vertical axis has always the same values,
368 zoomed into the interesting part of the search space.
369 The faint blue vertical lines separate the phases of MDR search.
370 The bound lines are sloped just to help locate the previous value,
371 in reality the bounds are updated instantly at the end of the measurement.
373 The graphs do not directly show when a particular bound is invalid.
374 However this can be gleaned indirectly by identifying
375 that the measurement does not satisfy that bound's validity conditions
377 Also, the external search follows, and the measurement previously acting
378 as and invalid upper or lower bound starts acting instead
379 as a valid lower or upper bound, respectively.
381 The following three graphs are for MDR with 10 second final trial duration,
382 showing different behavior in this inconsistent test,
383 and different amount of "work" done by each phase.
384 Also the horizontal axis has the same scaling here.
386 .. image:: MDR_10_1.svg
387 .. image:: MDR_10_2.svg
388 .. image:: MDR_10_3.svg
390 The next graph is for MDR with 60 second final trial duration,
391 to showcase the final phase takes the most of the overall search time.
392 The scaling of the horizontal axis is different.
394 .. image:: MDR_60.svg
396 Finally, here are two graphs showing NDR and PDR binary searches.
397 The trial duration is again 60 seconds,
398 but scaling of horizontal axis is once again different.
399 This shows the binary search spends most time measuring outside
400 the interesting rate region.
402 .. image:: NDR_60.svg
403 .. image:: PDR_60.svg
405 .. _binary search: https://en.wikipedia.org/wiki/Binary_search
406 .. _exponential search: https://en.wikipedia.org/wiki/Exponential_search
407 .. _estimation of standard deviation: https://en.wikipedia.org/wiki/Unbiased_estimation_of_standard_deviation
408 .. _simplified error propagation formula: https://en.wikipedia.org/wiki/Propagation_of_uncertainty#Simplification