idnits 2.16.02
/tmp/draft-vpolak-mkonstan-bmwg-mlrsearch-01.txt:
Checking boilerplate required by RFC 5378 and the IETF Trust (see
https://trustee.ietf.org/license-info):
----------------------------------------------------------------------------
No issues found here.
Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt:
----------------------------------------------------------------------------
No issues found here.
Checking nits according to https://www.ietf.org/id-info/checklist :
----------------------------------------------------------------------------
** The document seems to lack an Introduction section.
** The abstract seems to contain references ([RFC2544]), which it
shouldn't. Please replace those with straight textual mentions of the
documents in question.
Miscellaneous warnings:
----------------------------------------------------------------------------
-- The document date (March 27, 2019) is 85 days in the past. Is this
intentional?
Checking references for intended status: Informational
----------------------------------------------------------------------------
== Unused Reference: 'RFC8174' is defined on line 474, but no explicit
reference was found in the text
Summary: 2 errors (**), 0 flaws (~~), 1 warning (==), 1 comment (--).
Run idnits with the --verbose option for more detailed information about
the items above.
--------------------------------------------------------------------------------
2 Benchmarking Working Group M. Konstantynowicz, Ed.
3 Internet-Draft V. Polak, Ed.
4 Intended status: Informational Cisco Systems
5 Expires: September 28, 2019 March 27, 2019
7 Multiple Loss Ratio Search for Packet Throughput (MLRsearch)
8 draft-vpolak-mkonstan-bmwg-mlrsearch-01
10 Abstract
12 This document proposes changes to [RFC2544], specifically to packet
13 throughput search methodology, by defining a new search algorithm
14 referred to as Multiple Loss Ratio search (MLRsearch for short).
15 Instead of relying on binary search with pre-set starting offered
16 load, it proposes a novel approach discovering the starting point in
17 the initial phase, and then searching for packet throughput based on
18 defined packet loss ratio (PLR) input criteria and defined final
19 trial duration time. One of the key design principles behind
20 MLRsearch is minimizing the total test duration and searching for
21 multiple packet throughput rates (each with a corresponding PLR)
22 concurrently, instead of doing it sequentially.
24 The main motivation behind MLRsearch is the new set of challenges and
25 requirements posed by NFV (Network Function Virtualization),
26 specifically software based implementations of NFV data planes.
27 Using [RFC2544] in the experience of the authors yields often not
28 repetitive and not replicable end results due to a large number of
29 factors that are out of scope for this draft. MLRsearch aims to
30 address this challenge and define a common (standard?) way to
31 evaluate NFV packet throughput performance that takes into account
32 varying characteristics of NFV systems under test.
34 Status of This Memo
36 This Internet-Draft is submitted in full conformance with the
37 provisions of BCP 78 and BCP 79.
39 Internet-Drafts are working documents of the Internet Engineering
40 Task Force (IETF). Note that other groups may also distribute
41 working documents as Internet-Drafts. The list of current Internet-
42 Drafts is at https://datatracker.ietf.org/drafts/current/.
44 Internet-Drafts are draft documents valid for a maximum of six months
45 and may be updated, replaced, or obsoleted by other documents at any
46 time. It is inappropriate to use Internet-Drafts as reference
47 material or to cite them other than as "work in progress."
48 This Internet-Draft will expire on September 28, 2019.
50 Copyright Notice
52 Copyright (c) 2019 IETF Trust and the persons identified as the
53 document authors. All rights reserved.
55 This document is subject to BCP 78 and the IETF Trust's Legal
56 Provisions Relating to IETF Documents
57 (https://trustee.ietf.org/license-info) in effect on the date of
58 publication of this document. Please review these documents
59 carefully, as they describe your rights and restrictions with respect
60 to this document. Code Components extracted from this document must
61 include Simplified BSD License text as described in Section 4.e of
62 the Trust Legal Provisions and are provided without warranty as
63 described in the Simplified BSD License.
65 Table of Contents
67 1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 2
68 2. MLRsearch Background . . . . . . . . . . . . . . . . . . . . 3
69 3. MLRsearch Overview . . . . . . . . . . . . . . . . . . . . . 3
70 4. Sample Implementation . . . . . . . . . . . . . . . . . . . . 5
71 4.1. Input Parameters . . . . . . . . . . . . . . . . . . . . 6
72 4.2. Initial phase . . . . . . . . . . . . . . . . . . . . . . 6
73 4.3. Non-initial phases . . . . . . . . . . . . . . . . . . . 7
74 5. Known Implementations . . . . . . . . . . . . . . . . . . . . 9
75 5.1. FD.io CSIT Implementation Deviations . . . . . . . . . . 9
76 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10
77 7. Security Considerations . . . . . . . . . . . . . . . . . . . 10
78 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 10
79 9. Normative References . . . . . . . . . . . . . . . . . . . . 10
80 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 11
82 1. Terminology
84 o NDR - Non-Drop Rate, a packet throughput metric with Packet Loss
85 Ratio equal zero (a zero packet loss), expressed in packets-per-
86 second (pps). NDR packet throughput has an associated metric
87 oftentimes referred to as NDR bandwidth expressed in bits-per-
88 second (bps), and calculated as a product of:
90 * NDR packet rate for specific packet (frame) size, and
92 * Packet (L2 frame size) size in bits plus any associated L1
93 overhead.
95 o PLR - Packet Loss Ratio, a packet loss metric calculated as a
96 ratio of (packets_transmitted - packets_received) to
97 packets_transmitted, over the test trial duration.
99 o PDR - Partial-Drop Rate, a packet throughput metric with Packet
100 Loss Ratio greater than zero (a non-zero packet loss), expressed
101 in packets-per-second (pps). PDR packet throughput has an
102 associated metric oftentimes referred to as PDR bandwidth
103 expressed in bits-per- second (bps), and calculated as a product
104 of:
106 * PDR packet rate for specific packet (frame) size, and
108 * Packet (L2 frame size) size in bits plus any associated L1
109 overhead.
111 2. MLRsearch Background
113 Multiple Loss Rate search (MLRsearch) is a packet throughput search
114 algorithm suitable for deterministic (as opposed to probabilistic)
115 systems. MLRsearch discovers multiple packet throughput rates in a
116 single search, each rate associated with a distinct Packet Loss Ratio
117 (PLR) criteria.
119 Two popular names for particular PLR criteria are Non-Drop Rate (NDR,
120 with PLR=0, zero packet loss) and Partial Drop Rate (PDR, with PLR>0,
121 non-zero packet loss). MLRsearch discovers NDR and PDR in a single
122 search reducing required execution time compared to separate binary
123 searches for NDR and PDR. MLRsearch reduces execution time even
124 further by relying on shorter trial durations of intermediate steps,
125 with only the final measurements conducted at the specified final
126 trial duration. This results in the shorter overall search execution
127 time when compared to a standard NDR/PDR binary search, while
128 guaranteeing the same or similar results. (TODO: Specify "standard"
129 in the previous sentence.)
131 If needed, MLRsearch can be easily adopted to discover more
132 throughput rates with different pre-defined PLRs.
134 Unless otherwise noted, all throughput rates are _always_ bi-
135 directional aggregates of two equal (symmetric) uni-directional
136 packet rates received and reported by an external traffic generator.
138 3. MLRsearch Overview
140 The main properties of MLRsearch:
142 o MLRsearch is a duration aware multi-phase multi-rate search
143 algorithm.
145 * Initial phase determines promising starting interval for the
146 search.
148 * Intermediate phases progress towards defined final search
149 criteria.
151 * Final phase executes measurements according to the final search
152 criteria.
154 o Initial phase:
156 * Uses link rate as a starting transmit rate and discovers the
157 Maximum Receive Rate (MRR) used as an input to the first
158 intermediate phase.
160 o Intermediate phases:
162 * Start with initial trial duration (in the first phase) and
163 converge geometrically towards the final trial duration (in the
164 final phase).
166 * Track two values for NDR and two for PDR.
168 + The values are called (NDR or PDR) lower_bound and
169 upper_bound.
171 + Each value comes from a specific trial measurement (most
172 recent for that transmit rate), and as such the value is
173 associated with that measurement's duration and loss.
175 + A bound can be invalid, for example if NDR lower_bound has
176 been measured with nonzero loss.
178 + Invalid bounds are not real boundaries for the searched
179 value, but are needed to track interval widths.
181 + Valid bounds are real boundaries for the searched value.
183 + Each non-initial phase ends with all bounds valid.
185 * Start with a large (lower_bound, upper_bound) interval width
186 and geometrically converge towards the width goal (measurement
187 resolution) of the phase. Each phase halves the previous width
188 goal.
190 * Use internal and external searches:
192 + External search - measures at transmit rates outside the
193 (lower_bound, upper_bound) interval. Activated when a bound
194 is invalid, to search for a new valid bound by doubling the
195 interval width. It is a variant of "exponential search".
197 + Internal search - "binary search", measures at transmit
198 rates within the (lower_bound, upper_bound) valid interval,
199 halving the interval width.
201 o Final phase
203 * Executed with the final test trial duration, and the final
204 width goal that determines resolution of the overall search.
206 o Intermediate phases together with the final phase are called non-
207 initial phases.
209 The main benefits of MLRsearch vs. binary search include:
211 o In general MLRsearch is likely to execute more search trials
212 overall, but less trials at a set final duration.
214 o In well behaving cases it greatly reduces (>50%) the overall
215 duration compared to a single PDR (or NDR) binary search duration,
216 while finding multiple drop rates.
218 o In all cases MLRsearch yields the same or similar results to
219 binary search.
221 o Note: both binary search and MLRsearch are susceptible to
222 reporting non-repeatable results across multiple runs for very bad
223 behaving cases.
225 Caveats:
227 o Worst case MLRsearch can take longer than a binary search e.g. in
228 case of drastic changes in behaviour for trials at varying
229 durations.
231 4. Sample Implementation
233 Following is a brief description of a sample MLRsearch implementation
234 based on the open-source code running in FD.io CSIT project as part
235 of a Continuous Integration / Continuous Development (CI/CD)
236 framework.
238 4.1. Input Parameters
240 1. *maximum_transmit_rate* - maximum packet transmit rate to be used
241 by external traffic generator, limited by either the actual
242 Ethernet link rate or traffic generator NIC model capabilities.
243 Sample defaults: 2 * 14.88 Mpps for 64B 10GE link rate, 2 * 18.75
244 Mpps for 64B 40GE NIC maximum rate.
246 2. *minimum_transmit_rate* - minimum packet transmit rate to be used
247 for measurements. MLRsearch fails if lower transmit rate needs
248 to be used to meet search criteria. Default: 2 * 10 kpps (could
249 be higher).
251 3. *final_trial_duration* - required trial duration for final rate
252 measurements. Default: 30 sec.
254 4. *initial_trial_duration* - trial duration for initial MLRsearch
255 phase. Default: 1 sec.
257 5. *final_relative_width* - required measurement resolution
258 expressed as (lower_bound, upper_bound) interval width relative
259 to upper_bound. Default: 0.5%.
261 6. *packet_loss_ratio* - maximum acceptable PLR search criteria for
262 PDR measurements. Default: 0.5%.
264 7. *number_of_intermediate_phases* - number of phases between the
265 initial phase and the final phase. Impacts the overall MLRsearch
266 duration. Less phases are required for well behaving cases, more
267 phases may be needed to reduce the overall search duration for
268 worse behaving cases. Default (2). (Value chosen based on
269 limited experimentation to date. More experimentation needed to
270 arrive to clearer guidelines.)
272 4.2. Initial phase
274 1. First trial measures at maximum rate and discovers MRR.
276 * _in_: trial_duration = initial_trial_duration.
278 * _in_: offered_transmit_rate = maximum_transmit_rate.
280 * _do_: single trial.
282 * _out_: measured loss ratio.
284 * _out_: mrr = measured receive rate.
286 2. Second trial measures at MRR and discovers MRR2.
288 * _in_: trial_duration = initial_trial_duration.
290 * _in_: offered_transmit_rate = MRR.
292 * _do_: single trial.
294 * _out_: measured loss ratio.
296 * _out_: mrr2 = measured receive rate.
298 3. Third trial measures at MRR2.
300 * _in_: trial_duration = initial_trial_duration.
302 * _in_: offered_transmit_rate = MRR2.
304 * _do_: single trial.
306 * _out_: measured loss ratio.
308 4.3. Non-initial phases
310 1. Main loop:
312 * _in_: trial_duration for the current phase. Set to
313 initial_trial_duration for the first intermediate phase; to
314 final_trial_duration for the final phase; or to the element of
315 interpolating geometric sequence for other intermediate
316 phases. For example with two intermediate phases,
317 trial_duration of the second intermediate phase is the
318 geometric average of initial_strial_duration and
319 final_trial_duration.
321 * _in_: relative_width_goal for the current phase. Set to
322 final_relative_width for the final phase; doubled for each
323 preceding phase. For example with two intermediate phases,
324 the first intermediate phase uses quadruple of
325 final_relative_width and the second intermediate phase uses
326 double of final_relative_width.
328 * _in_: ndr_interval, pdr_interval from the previous main loop
329 iteration or the previous phase. If the previous phase is the
330 initial phase, both intervals have lower_bound = MRR2,
331 uper_bound = MRR. Note that the initial phase is likely to
332 create intervals with invalid bounds.
334 * _do_: According to the procedure described in point 2, either
335 exit the phase (by jumping to 1.g.), or prepare new transmit
336 rate to measure with.
338 * _do_: Perform the trial measurement at the new transmit rate
339 and trial_duration, compute its loss ratio.
341 * _do_: Update the bounds of both intervals, based on the new
342 measurement. The actual update rules are numerous, as NDR
343 external search can affect PDR interval and vice versa, but
344 the result agrees with rules of both internal and external
345 search. For example, any new measurement below an invalid
346 lower_bound becomes the new lower_bound, while the old
347 measurement (previously acting as the invalid lower_bound)
348 becomes a new and valid upper_bound. Go to next iteration
349 (1.c.), taking the updated intervals as new input.
351 * _out_: current ndr_interval and pdr_interval. In the final
352 phase this is also considered to be the result of the whole
353 search. For other phases, the next phase loop is started with
354 the current results as an input.
356 2. New transmit rate (or exit) calculation (for 1.d.):
358 * If there is an invalid bound then prepare for external search:
360 + _If_ the most recent measurement at NDR lower_bound
361 transmit rate had the loss higher than zero, then the new
362 transmit rate is NDR lower_bound decreased by two NDR
363 interval widths.
365 + Else, _if_ the most recent measurement at PDR lower_bound
366 transmit rate had the loss higher than PLR, then the new
367 transmit rate is PDR lower_bound decreased by two PDR
368 interval widths.
370 + Else, _if_ the most recent measurement at NDR upper_bound
371 transmit rate had no loss, then the new transmit rate is
372 NDR upper_bound increased by two NDR interval widths.
374 + Else, _if_ the most recent measurement at PDR upper_bound
375 transmit rate had the loss lower or equal to PLR, then the
376 new transmit rate is PDR upper_bound increased by two PDR
377 interval widths.
379 * If interval width is higher than the current phase goal:
381 + Else, _if_ NDR interval does not meet the current phase
382 width goal, prepare for internal search. The new transmit
383 rate is (NDR lower bound + NDR upper bound) / 2.
385 + Else, _if_ PDR interval does not meet the current phase
386 width goal, prepare for internal search. The new transmit
387 rate is (PDR lower bound + PDR upper bound) / 2.
389 * Else, _if_ some bound has still only been measured at a lower
390 duration, prepare to re-measure at the current duration (and
391 the same transmit rate). The order of priorities is:
393 + NDR lower_bound,
395 + PDR lower_bound,
397 + NDR upper_bound,
399 + PDR upper_bound.
401 * _Else_, do not prepare any new rate, to exit the phase. This
402 ensures that at the end of each non-initial phase all
403 intervals are valid, narrow enough, and measured at current
404 phase trial duration.
406 5. Known Implementations
408 The only known working implementation of MLRsearch is in Linux
409 Foundation FD.io CSIT project. https://wiki.fd.io/view/CSIT.
410 https://git.fd.io/csit/.
412 5.1. FD.io CSIT Implementation Deviations
414 This document so far has been describing a simplified version of
415 MLRsearch algorithm. The full algorithm as implemented contains
416 additional logic, which makes some of the details (but not general
417 ideas) above incorrect. Here is a short description of the
418 additional logic as a list of principles, explaining their main
419 differences from (or additions to) the simplified description, but
420 without detailing their mutual interaction.
422 1. Logarithmic transmit rate. In order to better fit the relative
423 width goal, the interval doubling and halving is done
424 differently. For example, the middle of 2 and 8 is 4, not 5.
426 2. Optimistic maximum rate. The increased rate is never higher than
427 the maximum rate. Upper bound at that rate is always considered
428 valid.
430 3. Pessimistic minimum rate. The decreased rate is never lower than
431 the minimum rate. If a lower bound at that rate is invalid, a
432 phase stops refining the interval further (until it gets re-
433 measured).
435 4. Conservative interval updates. Measurements above current upper
436 bound never update a valid upper bound, even if drop ratio is
437 low. Measurements below current lower bound always update any
438 lower bound if drop ratio is high.
440 5. Ensure sufficient interval width. Narrow intervals make external
441 search take more time to find a valid bound. If the new transmit
442 increased or decreased rate would result in width less than the
443 current goal, increase/decrease more. This can happen if the
444 measurement for the other interval makes the current interval too
445 narrow. Similarly, take care the measurements in the initial
446 phase create wide enough interval.
448 6. Timeout for bad cases. The worst case for MLRsearch is when each
449 phase converges to intervals way different than the results of
450 the previous phase. Rather than suffer total search time several
451 times larger than pure binary search, the implemented tests fail
452 themselves when the search takes too long (given by argument
453 _timeout_).
455 6. IANA Considerations
457 ..
459 7. Security Considerations
461 ..
463 8. Acknowledgements
465 ..
467 9. Normative References
469 [RFC2544] Bradner, S. and J. McQuaid, "Benchmarking Methodology for
470 Network Interconnect Devices", RFC 2544,
471 DOI 10.17487/RFC2544, March 1999,
472 .
474 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
475 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
476 May 2017, .
478 Authors' Addresses
480 Maciek Konstantynowicz (editor)
481 Cisco Systems
483 Email: mkonstan@cisco.com
485 Vratko Polak (editor)
486 Cisco Systems
488 Email: vrpolak@cisco.com