idnits 2.17.1 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 copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (March 27, 2019) is 1855 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 (~~), 2 warnings (==), 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