2 title: Multiple Loss Ratio Search for Packet Throughput (MLRsearch)
4 docname: draft-vpolak-mkonstan-bmwg-mlrsearch-02
9 wg: Benchmarking Working Group
14 pi: # can use array (if all yes) or hash here
19 sortrefs: # defaults to yes
24 ins: M. Konstantynowicz
25 name: Maciek Konstantynowicz
28 email: mkonstan@cisco.com
34 email: vrpolak@cisco.com
42 target: https://docs.fd.io/csit/rls1904/report/introduction/methodology_data_plane_throughput/methodology_mlrsearch_tests.html
43 title: "FD.io CSIT Test Methodology - MLRsearch"
46 target: https://pypi.org/project/MLRsearch/
47 title: MLRsearch 0.2.0, Python Package Index
52 This document proposes changes to [RFC2544], specifically to packet
53 throughput search methodology, by defining a new search algorithm
54 referred to as Multiple Loss Ratio search (MLRsearch for short). Instead
55 of relying on binary search with pre-set starting offered load, it
56 proposes a novel approach discovering the starting point in the initial
57 phase, and then searching for packet throughput based on defined packet
58 loss ratio (PLR) input criteria and defined final trial duration time.
59 One of the key design principles behind MLRsearch is minimizing the
60 total test duration and searching for multiple packet throughput rates
61 (each with a corresponding PLR) concurrently, instead of doing it
64 The main motivation behind MLRsearch is the new set of challenges and
65 requirements posed by NFV (Network Function Virtualization),
66 specifically software based implementations of NFV data planes. Using
67 [RFC2544] in the experience of the authors yields often not repetitive
68 and not replicable end results due to a large number of factors that are
69 out of scope for this draft. MLRsearch aims to address this challenge and
70 define a common (standard?) way to evaluate NFV packet throughput
71 performance that takes into account varying characteristics of NFV
78 * Frame size: size of an Ethernet Layer-2 frame on the wire, including
79 any VLAN tags (dot1q, dot1ad) and Ethernet FCS, but excluding Ethernet
80 preamble and inter-frame gap. Measured in bytes.
81 * Packet size: same as frame size, both terms used interchangeably.
82 * Inner L2 size: for tunneled L2 frames only, size of an encapsulated
83 Ethernet Layer-2 frame, preceded with tunnel header, and followed by
84 tunnel trailer. Measured in Bytes.
85 * Inner IP size: for tunneled IP packets only, size of an encapsulated
86 IPv4 or IPv6 packet, preceded with tunnel header, and followed by
87 tunnel trailer. Measured in Bytes.
88 * Device Under Test (DUT): In software networking, "device" denotes a
89 specific piece of software tasked with packet processing. Such device
90 is surrounded with other software components (such as operating system
91 kernel). It is not possible to run devices without also running the
92 other components, and hardware resources are shared between both. For
93 purposes of testing, the whole set of hardware and software components
94 is called "system under test" (SUT). As SUT is the part of the whole
95 test setup performance of which can be measured by [RFC2544] methods,
96 this document uses SUT instead of [RFC2544] DUT. Device under test
97 (DUT) can be re-introduced when analysing test results using whitebox
98 techniques, but this document sticks to blackbox testing.
99 * System Under Test (SUT): System under test (SUT) is a part of the
100 whole test setup whose performance is to be benchmarked. The complete
101 methodology contains other parts, whose performance is either already
102 established, or not affecting the benchmarking result.
103 * Bi-directional throughput tests: involve packets/frames flowing in
104 both transmit and receive directions over every tested interface of
105 SUT/DUT. Packet flow metrics are measured per direction, and can be
106 reported as aggregate for both directions (i.e. throughput) and/or
107 separately for each measured direction (i.e. latency). In most cases
108 bi-directional tests use the same (symmetric) load in both directions.
109 * Uni-directional throughput tests: involve packets/frames flowing in
110 only one direction, i.e. either transmit or receive direction, over
111 every tested interface of SUT/DUT. Packet flow metrics are measured
112 and are reported for measured direction.
113 * Packet Loss Ratio (PLR): ratio of packets received relative to packets
114 transmitted over the test trial duration, calculated using formula:
115 PLR = ( pkts_transmitted - pkts_received ) / pkts_transmitted.
116 For bi-directional throughput tests aggregate PLR is calculated based
117 on the aggregate number of packets transmitted and received.
118 * Packet Throughput Rate: maximum packet offered load DUT/SUT forwards
119 within the specified Packet Loss Ratio (PLR). In many cases the rate
120 depends on the frame size processed by DUT/SUT. Hence packet
121 throughput rate MUST be quoted with specific frame size as received by
122 DUT/SUT during the measurement. For bi-directional tests, packet
123 throughput rate should be reported as aggregate for both directions.
124 Measured in packets-per-second (pps) or frames-per-second (fps),
126 * Bandwidth Throughput Rate: a secondary metric calculated from packet
127 throughput rate using formula: bw_rate = pkt_rate * (frame_size +
128 L1_overhead) * 8, where L1_overhead for Ethernet includes preamble (8
129 Bytes) and inter-frame gap (12 Bytes). For bi-directional tests,
130 bandwidth throughput rate should be reported as aggregate for both
131 directions. Expressed in bits-per-second (bps).
132 * Non Drop Rate (NDR): maximum packet/bandwith throughput rate sustained
133 by DUT/SUT at PLR equal zero (zero packet loss) specific to tested
134 frame size(s). MUST be quoted with specific packet size as received by
135 DUT/SUT during the measurement. Packet NDR measured in
136 packets-per-second (or fps), bandwidth NDR expressed in
137 bits-per-second (bps).
138 * Partial Drop Rate (PDR): maximum packet/bandwith throughput rate
139 sustained by DUT/SUT at PLR greater than zero (non-zero packet loss)
140 specific to tested frame size(s). MUST be quoted with specific packet
141 size as received by DUT/SUT during the measurement. Packet PDR
142 measured in packets-per-second (or fps), bandwidth PDR expressed in
143 bits-per-second (bps).
144 * Maximum Receive Rate (MRR): packet/bandwidth rate regardless of PLR
145 sustained by DUT/SUT under specified Maximum Transmit Rate (MTR)
146 packet load offered by traffic generator. MUST be quoted with both
147 specific packet size and MTR as received by DUT/SUT during the
148 measurement. Packet MRR measured in packets-per-second (or fps),
149 bandwidth MRR expressed in bits-per-second (bps).
150 * Trial: a single measurement step.
151 * Trial duration: amount of time over which packets are transmitted and
152 received in a single throughput measurement step.
154 # MLRsearch Background
156 Multiple Loss Ratio search (MLRsearch) is a packet throughput search
157 algorithm suitable for deterministic systems (as opposed to
158 probabilistic systems). MLRsearch discovers multiple packet throughput
159 rates in a single search, with each rate associated with a distinct
160 Packet Loss Ratio (PLR) criteria.
162 For cases when multiple rates need to be found, this property makes
163 MLRsearch more efficient in terms of time execution, compared to
164 traditional throughput search algorithms that discover a single packet
165 rate per defined search criteria (e.g. a binary search specified by
166 [RFC2544]). MLRsearch reduces execution time even further by relying on
167 shorter trial durations of intermediate steps, with only the final
168 measurements conducted at the specified final trial duration. This
169 results in the shorter overall search execution time when compared to a
170 traditional binary search, while guaranteeing the same results for
171 deterministic systems.
173 In practice two rates with distinct PLRs are commonly used for packet
174 throughput measurements of NFV systems: Non Drop Rate (NDR) with PLR=0
175 and Partial Drop Rate (PDR) with PLR>0. The rest of this document
176 describes MLRsearch for NDR and PDR. If needed, MLRsearch can be easily
177 adapted to discover more throughput rates with different pre-defined
180 Similarly to other throughput search approaches like binary search,
181 MLRsearch is effective for SUTs/DUTs with PLR curve that is continuously
182 flat or increasing with growing offered load. It may not be as
183 effective for SUTs/DUTs with abnormal PLR curves.
185 MLRsearch relies on traffic generator to qualify the received packet
186 stream as error-free, and invalidate the results if any disqualifying
187 errors are present e.g. out-of-sequence frames.
189 MLRsearch can be applied to both uni-directional and bi-directional
192 For bi-directional tests, MLRsearch rates and ratios are aggregates of
193 both directions, based on the following assumptions:
195 * Packet rates transmitted by traffic generator and received by SUT/DUT
196 are the same in each direction, in other words the load is symmetric.
197 * SUT/DUT packet processing capacity is the same in both directions,
198 resulting in the same packet loss under load.
202 The main properties of MLRsearch:
204 * MLRsearch is a duration aware multi-phase multi-rate search algorithm:
205 * Initial Phase determines promising starting interval for the search.
206 * Intermediate Phases progress towards defined final search criteria.
207 * Final Phase executes measurements according to the final search
209 * Final search criteria is defined by following inputs:
210 * PLRs associated with NDR and PDR.
211 * Final trial duration.
212 * Measurement resolution.
214 * Measure MRR over initial trial duration.
215 * Measured MRR is used as an input to the first intermediate phase.
216 * Multiple Intermediate Phases:
218 * Start with initial trial duration in the first intermediate phase.
219 * Converge geometrically towards the final trial duration.
220 * Track two values for NDR and two for PDR:
221 * The values are called lower_bound and upper_bound.
222 * Each value comes from a specific trial measurement:
223 * Most recent for that transmit rate.
224 * As such the value is associated with that measurement's duration
226 * A bound can be valid or invalid:
227 * Valid lower_bound must conform with PLR search criteria.
228 * Valid upper_bound must not conform with PLR search criteria.
229 * Example of invalid NDR lower_bound is if it has been measured
231 * Invalid bounds are not real boundaries for the searched value:
232 * They are needed to track interval widths.
233 * Valid bounds are real boundaries for the searched value.
234 * Each non-initial phase ends with all bounds valid.
235 * Bound can become invalid if it re-measured at longer trial
236 duration in sub-sequent phase.
238 * Start with a large (lower_bound, upper_bound) interval width, that
239 determines measurement resolution.
240 * Geometrically converge towards the width goal of the phase.
241 * Each phase halves the previous width goal.
242 * Use of internal and external searches:
244 * Measures at transmit rates outside the (lower_bound,
245 upper_bound) interval.
246 * Activated when a bound is invalid, to search for a new valid
247 bound by doubling the interval width.
248 * It is a variant of "exponential search".
250 * A "binary search" that measures at transmit rates within the
251 (lower_bound, upper_bound) valid interval, halving the interval
254 * Executed with the final test trial duration, and the final width
255 goal that determines resolution of the overall search.
256 * Intermediate Phases together with the Final Phase are called
259 The main benefits of MLRsearch vs. binary search include:
261 * In general MLRsearch is likely to execute more trials overall, but
262 likely less trials at a set final trial duration.
263 * In well behaving cases, e.g. when results do not depend on trial
264 duration, it greatly reduces (>50%) the overall duration compared to a
265 single PDR (or NDR) binary search over duration, while finding
267 * In all cases MLRsearch yields the same or similar results to binary
269 * Note: both binary search and MLRsearch are susceptible to reporting
270 non-repeatable results across multiple runs for very bad behaving
275 * Worst case MLRsearch can take longer than a binary search e.g. in case of
276 drastic changes in behaviour for trials at varying durations.
278 # Sample Implementation
280 Following is a brief description of a sample MLRsearch implementation
281 based on the open-source code running in FD.io CSIT project as part of a
282 Continuous Integration / Continuous Development (CI/CD) framework.
286 1. **maximum_transmit_rate** - Maximum Transmit Rate (MTR) of packets to
287 be used by external traffic generator implementing MLRsearch,
288 limited by the actual Ethernet link(s) rate, NIC model or traffic
289 generator capabilities. Sample defaults: 2 * 14.88 Mpps for 64B
290 10GE link rate, 2 * 18.75 Mpps for 64B 40GE NIC (specific model)
291 maximum rate (lower than 2 * 59.52 Mpps 40GE link rate).
292 2. **minimum_transmit_rate** - minimum packet transmit rate to be used for
293 measurements. MLRsearch fails if lower transmit rate needs to be
294 used to meet search criteria. Default: 2 * 10 kpps (could be higher).
295 3. **final_trial_duration** - required trial duration for final rate
296 measurements. Default: 30 sec.
297 4. **initial_trial_duration** - trial duration for initial MLRsearch phase.
299 5. **final_relative_width** - required measurement resolution expressed as
300 (lower_bound, upper_bound) interval width relative to upper_bound.
302 6. **packet_loss_ratio** - maximum acceptable PLR search criteria for
303 PDR measurements. Default: 0.5%.
304 7. **number_of_intermediate_phases** - number of phases between the initial
305 phase and the final phase. Impacts the overall MLRsearch duration.
306 Less phases are required for well behaving cases, more phases
307 may be needed to reduce the overall search duration for worse behaving cases.
308 Default (2). (Value chosen based on limited experimentation to date.
309 More experimentation needed to arrive to clearer guidelines.)
313 1. First trial measures at configured maximum transmit rate (MTR) and
314 discovers maximum receive rate (MRR).
315 * IN: trial_duration = initial_trial_duration.
316 * IN: offered_transmit_rate = maximum_transmit_rate.
318 * OUT: measured loss ratio.
319 * OUT: MRR = measured receive rate.
320 2. Second trial measures at MRR and discovers MRR2.
321 * IN: trial_duration = initial_trial_duration.
322 * IN: offered_transmit_rate = MRR.
324 * OUT: measured loss ratio.
325 * OUT: MRR2 = measured receive rate.
326 3. Third trial measures at MRR2.
327 * IN: trial_duration = initial_trial_duration.
328 * IN: offered_transmit_rate = MRR2.
330 * OUT: measured loss ratio.
332 ## Non-Initial Phases
335 1. IN: trial_duration for the current phase. Set to
336 initial_trial_duration for the first intermediate phase; to
337 final_trial_duration for the final phase; or to the element of
338 interpolating geometric sequence for other intermediate phases.
339 For example with two intermediate phases, trial_duration of the
340 second intermediate phase is the geometric average of
341 initial_trial_duration and final_trial_duration.
342 2. IN: relative_width_goal for the current phase. Set to
343 final_relative_width for the final phase; doubled for each
344 preceding phase. For example with two intermediate phases, the
345 first intermediate phase uses quadruple of final_relative_width
346 and the second intermediate phase uses double of
347 final_relative_width.
348 3. IN: ndr_interval, pdr_interval from the previous main loop
349 iteration or the previous phase. If the previous phase is the
350 initial phase, both intervals have lower_bound = MRR2, upper_bound
351 = MRR. Note that the initial phase is likely to create intervals
353 4. DO: According to the procedure described in point 2., either exit
354 the phase (by jumping to 1.7.), or calculate new transmit rate to
356 5. DO: Perform the trial measurement at the new transmit rate and
357 trial_duration, compute its loss ratio.
358 6. DO: Update the bounds of both intervals, based on the new
359 measurement. The actual update rules are numerous, as NDR external
360 search can affect PDR interval and vice versa, but the result
361 agrees with rules of both internal and external search. For
362 example, any new measurement below an invalid lower_bound becomes
363 the new lower_bound, while the old measurement (previously acting
364 as the invalid lower_bound) becomes a new and valid upper_bound.
365 Go to next iteration (1.3.), taking the updated intervals as new
367 7. OUT: current ndr_interval and pdr_interval. In the final phase
368 this is also considered to be the result of the whole search. For
369 other phases, the next phase loop is started with the current
371 2. New transmit rate (or exit) calculation (for point 1.4.):
372 1. If there is an invalid bound then prepare for external search:
373 * IF the most recent measurement at NDR lower_bound transmit
374 rate had the loss higher than zero, then the new transmit rate
375 is NDR lower_bound decreased by two NDR interval widths or the
376 amount needed to hit the current width goal, whichever is
378 * Else, IF the most recent measurement at PDR lower_bound
379 transmit rate had the loss higher than PLR, then the new
380 transmit rate is PDR lower_bound decreased by two PDR interval
382 * Else, IF the most recent measurement at NDR upper_bound
383 transmit rate had no loss, then the new transmit rate is NDR
384 upper_bound increased by two NDR interval widths.
385 * Else, IF the most recent measurement at PDR upper_bound
386 transmit rate had the loss lower or equal to PLR, then the new
387 transmit rate is PDR upper_bound increased by two PDR interval
389 2. If interval width is higher than the current phase goal:
390 * Else, IF NDR interval does not meet the current phase width
391 goal, prepare for internal search. The new transmit rate is a
392 geometric average of NDR lower_bound and NDR upper_bound.
393 * Else, IF PDR interval does not meet the current phase width
394 goal, prepare for internal search. The new transmit rate is a
395 geometric average of PDR lower_bound and PDR upper_bound.
396 3. Else, IF some bound has still only been measured at a lower
397 duration, prepare to re-measure at the current duration (and the
398 same transmit rate). The order of priorities is:
403 4. Else, do not prepare any new rate, to exit the phase.
404 This ensures that at the end of each non-initial phase
405 all intervals are valid, narrow enough, and measured
406 at current phase trial duration.
408 ## Sample MLRsearch Run
410 TODO add a sample MLRsearch run with values.
412 # Known Implementations
414 The only known working implementation of MLRsearch is in Linux
415 Foundation FD.io CSIT project [FDio-CSIT-MLRsearch]. MLRsearch is also
416 available as a Python package in [PyPI-MLRsearch].
418 ## FD.io CSIT Implementation Deviations
420 This document so far has been describing a simplified version of
421 MLRsearch algorithm. The full algorithm as implemented contains
422 additional logic, which makes some of the details (but not general
423 ideas) above incorrect. Here is a short description of the additional
424 logic as a list of principles, explaining their main differences from
425 (or additions to) the simplified description, but without detailing
426 their mutual interaction.
428 1. Logarithmic transmit rate.
429 * In order to better fit the relative width goal, the interval
430 doubling and halving is done differently.
431 * For example, the middle of 2 and 8 is 4, not 5.
432 2. Optimistic maximum rate.
433 * The increased rate is never higher than the maximum rate.
434 * Upper bound at that rate is always considered valid.
435 3. Pessimistic minimum rate.
436 * The decreased rate is never lower than the minimum rate.
437 * If a lower bound at that rate is invalid, a phase stops refining
438 the interval further (until it gets re-measured).
439 4. Conservative interval updates.
440 * Measurements above current upper bound never update a valid upper
441 bound, even if drop ratio is low.
442 * Measurements below current lower bound always update any lower
443 bound if drop ratio is high.
444 5. Ensure sufficient interval width.
445 * Narrow intervals make external search take more time to find a
447 * If the new transmit increased or decreased rate would result in
448 width less than the current goal, increase/decrease more.
449 * This can happen if the measurement for the other interval
450 makes the current interval too narrow.
451 * Similarly, take care the measurements in the initial phase create
452 wide enough interval.
453 6. Timeout for bad cases.
454 * The worst case for MLRsearch is when each phase converges to
455 intervals way different than the results of the previous phase.
456 * Rather than suffer total search time several times larger than pure
457 binary search, the implemented tests fail themselves when the
458 search takes too long (given by argument *timeout*).
460 # IANA Considerations
464 # Security Considerations
466 Benchmarking activities as described in this memo are limited to
467 technology characterization of a DUT/SUT using controlled stimuli in a
468 laboratory environment, with dedicated address space and the constraints
469 specified in the sections above.
471 The benchmarking network topology will be an independent test setup and
472 MUST NOT be connected to devices that may forward the test traffic into
473 a production network or misroute traffic to the test management network.
475 Further, benchmarking is performed on a "black-box" basis, relying
476 solely on measurements observable external to the DUT/SUT.
478 Special capabilities SHOULD NOT exist in the DUT/SUT specifically for
479 benchmarking purposes. Any implications for network security arising
480 from the DUT/SUT SHOULD be identical in the lab and in production
485 Many thanks to Alec Hothan of OPNFV NFVbench project for thorough
486 review and numerous useful comments and suggestions.