idnits 2.17.1 draft-ietf-bmwg-mlrsearch-02.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. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 145: '...ts absolute value MUST be used to keep...' RFC 2119 keyword, line 158: '...low. This value MUST NOT be higher th...' RFC 2119 keyword, line 219: '... the max load SHOULD not be larget ...' RFC 2119 keyword, line 440: '... Both TG and TA MUST be able to handl...' RFC 2119 keyword, line 444: '... MUST be small....' (4 more instances...) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'SHOULD not' in this paragraph: * https://datatracker.ietf.org/doc/html/rfc2544#section-20 Mentions the max load SHOULD not be larget than the theoretical maximum rate for the frame size on the media. -- The document date (7 March 2022) is 774 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- No issues found here. Summary: 3 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 4 Intended status: Informational Cisco Systems 5 Expires: 8 September 2022 7 March 2022 7 Multiple Loss Ratio Search for Packet Throughput (MLRsearch) 8 draft-ietf-bmwg-mlrsearch-02 10 Abstract 12 TODO: Update after all sections are ready. 14 This document proposes changes to [RFC2544], specifically to packet 15 throughput search methodology, by defining a new search algorithm 16 referred to as Multiple Loss Ratio search (MLRsearch for short). 17 Instead of relying on binary search with pre-set starting offered 18 load, it proposes a novel approach discovering the starting point in 19 the initial phase, and then searching for packet throughput based on 20 defined packet loss ratio (PLR) input criteria and defined final 21 trial duration time. One of the key design principles behind 22 MLRsearch is minimizing the total test duration and searching for 23 multiple packet throughput rates (each with a corresponding PLR) 24 concurrently, instead of doing it sequentially. 26 The main motivation behind MLRsearch is the new set of challenges and 27 requirements posed by NFV (Network Function Virtualization), 28 specifically software based implementations of NFV data planes. 29 Using [RFC2544] in the experience of the authors yields often not 30 repetitive and not replicable end results due to a large number of 31 factors that are out of scope for this draft. MLRsearch aims to 32 address this challenge in a simple way of getting the same result 33 sooner, so more repetitions can be done to describe the 34 replicability. 36 Status of This Memo 38 This Internet-Draft is submitted in full conformance with the 39 provisions of BCP 78 and BCP 79. 41 Internet-Drafts are working documents of the Internet Engineering 42 Task Force (IETF). Note that other groups may also distribute 43 working documents as Internet-Drafts. The list of current Internet- 44 Drafts is at https://datatracker.ietf.org/drafts/current/. 46 Internet-Drafts are draft documents valid for a maximum of six months 47 and may be updated, replaced, or obsoleted by other documents at any 48 time. It is inappropriate to use Internet-Drafts as reference 49 material or to cite them other than as "work in progress." 51 This Internet-Draft will expire on 8 September 2022. 53 Copyright Notice 55 Copyright (c) 2022 IETF Trust and the persons identified as the 56 document authors. All rights reserved. 58 This document is subject to BCP 78 and the IETF Trust's Legal 59 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 60 license-info) in effect on the date of publication of this document. 61 Please review these documents carefully, as they describe your rights 62 and restrictions with respect to this document. Code Components 63 extracted from this document must include Revised BSD License text as 64 described in Section 4.e of the Trust Legal Provisions and are 65 provided without warranty as described in the Revised BSD License. 67 Table of Contents 69 1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 70 2. Intentions of this document . . . . . . . . . . . . . . . . . 5 71 3. RFC2544 . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 72 3.1. Throughput search . . . . . . . . . . . . . . . . . . . . 5 73 4. Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 6 74 4.1. Repeatability and Comparability . . . . . . . . . . . . . 6 75 4.2. Non-Zero Target Loss Ratios . . . . . . . . . . . . . . . 6 76 5. Solution ideas . . . . . . . . . . . . . . . . . . . . . . . 7 77 5.1. Short duration trials . . . . . . . . . . . . . . . . . . 8 78 5.2. FRMOL as reasonable start . . . . . . . . . . . . . . . . 8 79 5.3. Non-zero loss ratios . . . . . . . . . . . . . . . . . . 8 80 5.4. Concurrent ratio search . . . . . . . . . . . . . . . . . 9 81 5.5. Load selection heuristics and shortcuts . . . . . . . . . 9 82 6. Non-compliance with RFC2544 . . . . . . . . . . . . . . . . . 9 83 7. Additional Requirements . . . . . . . . . . . . . . . . . . . 10 84 7.1. TODO: Search Stop Criteria . . . . . . . . . . . . . . . 10 85 7.2. Reliability of Test Equipment . . . . . . . . . . . . . . 10 86 7.2.1. Very late frames . . . . . . . . . . . . . . . . . . 10 87 8. MLRsearch Background . . . . . . . . . . . . . . . . . . . . 11 88 9. MLRsearch Overview . . . . . . . . . . . . . . . . . . . . . 13 89 10. Sample Implementation . . . . . . . . . . . . . . . . . . . . 16 90 10.1. Input Parameters . . . . . . . . . . . . . . . . . . . . 16 91 10.2. Initial Phase . . . . . . . . . . . . . . . . . . . . . 17 92 10.3. Non-Initial Phases . . . . . . . . . . . . . . . . . . . 18 93 11. FD.io CSIT Implementation . . . . . . . . . . . . . . . . . . 22 94 11.1. Additional details . . . . . . . . . . . . . . . . . . . 22 95 11.1.1. FD.io CSIT Input Parameters . . . . . . . . . . . . 24 96 11.2. Example MLRsearch Run . . . . . . . . . . . . . . . . . 25 97 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 27 98 13. Security Considerations . . . . . . . . . . . . . . . . . . . 27 99 14. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 27 100 15. References . . . . . . . . . . . . . . . . . . . . . . . . . 27 101 15.1. Normative References . . . . . . . . . . . . . . . . . . 27 102 15.2. Informative References . . . . . . . . . . . . . . . . . 28 103 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 28 105 1. Terminology 107 TODO: Update after most other sections are updated. 109 * TODO: The current text uses Throughput for the zero loss ratio 110 load. Is the capital T needed/useful? 112 * DUT and SUT: see the definitions in https://gerrit.fd.io/r/c/ 113 csit/+/35545 115 * Traffic Generator (TG) and Traffic Analyzer (TA): see 116 https://datatracker.ietf.org/doc/html/rfc6894#section-4 TODO: 117 Maybe there is an earlier RFC? 119 * Overall search time: the time it takes to find all required loads 120 within their precision goals, starting from zero trials measured 121 at given DUT configuration and traffic profile. 123 * TODO: traffic profile? 125 * Intended load: https://datatracker.ietf.org/doc/html/ 126 rfc2285#section-3.5.1 128 * Offered load: https://datatracker.ietf.org/doc/html/ 129 rfc2285#section-3.5.2 131 * Maximum offered load (MOL): see 132 https://datatracker.ietf.org/doc/html/rfc2285#section-3.5.3 134 * Forwarding rate at maximum offered load (FRMOL) 135 https://datatracker.ietf.org/doc/html/rfc2285#section-3.6.2 137 * Trial Loss Count: the number of frames transmitted minus the 138 number of frames received. Negative count is possible, e.g. when 139 SUT duplicates some frames. 141 * Trial Loss Ratio: ratio of frames received relative to frames 142 transmitted over the trial duration. For bi-directional 143 throughput tests, the aggregate ratio is calculated, based on the 144 aggregate number of frames transmitted and received. If the trial 145 loss count is negative, its absolute value MUST be used to keep 146 compliance with RFC2544. 148 * Safe load: any value, such that trial measurement at this (or 149 lower) intended load is correcrly handled by both TG and TA, 150 regardless of SUT behavior. Frequently, it is not known what the 151 safe load is. 153 * Max load (TODO rename?): Maximal intended load to be used during 154 search. Benchmarking team decides which value is low enough to 155 guarantee values reported by TG and TA are reliable. It has to be 156 a safe load, but it can be lower than a safe load estimate for 157 added safety. See the subsection on unreliable test equipment 158 below. This value MUST NOT be higher than MOL, which itself MUST 159 NOT be higher than Maximum Frame Rate 160 https://datatracker.ietf.org/doc/html/rfc2544#section-20 162 * Min load: Minimal intended load to be used during search. 163 Benchmarking team decides which value is high enough to guarantee 164 the trial measurement results are valid. E.g. considerable 165 overall search time can be saved by declaring SUT faulty if min 166 load trial shows too high loss rate. Zero frames per second is a 167 valid min load value 169 * Effective loss ratio: a corrected value of trial loss ratio chosen 170 to avoid difficulties if SUT exhibits decreasing loss ratio with 171 increasing load. It is the maximum of trial loss ratios measured 172 at the same duration on all loads smaller than (and including) the 173 current one. 175 * Target loss ratio: a loss ratio value acting as an input for the 176 search. The search is finding tight enough lower and upper bounds 177 in intended load, so that the measurement at the lower bound has 178 smaller or equal trial loss ratio, and upper bound has strictly 179 larger trial loss ratio. For the tightest upper bound, the 180 effective loss ratio is the same as trial loss ratio at that upper 181 bound load. For the tightest lower bound, the effective loss 182 ratio can be higher than the trial loss ratio at that lower bound, 183 but still not larger than the target loss ratio. 185 * TODO: Search algorithm. 187 * TODO: Precision goal. 189 * TODO: Define a "benchmarking group". 191 * TODO: Upper and lower bound. 193 * TODO: Valid and invalid bound? 195 * TODO: Interval and interval width? 197 TODO: Mention NIC/PCI bandwidth/pps limits can be lower than 198 bandwidth of medium. 200 2. Intentions of this document 202 The intention of this document is to provide recommendations for: * 203 optimizing search for multiple target loss ratios at once, * speeding 204 up the overall search time, * improve search results repeatability 205 and comparability. 207 No part of RFC2544 is intended to be obsoleted by this document. 209 3. RFC2544 211 3.1. Throughput search 213 It is useful to restate the key requirements of RFC2544 using the new 214 terminology (see section Terminology). 216 The following sections of RFC2544 are of interest for this document. 218 * https://datatracker.ietf.org/doc/html/rfc2544#section-20 Mentions 219 the max load SHOULD not be larget than the theoretical maximum 220 rate for the frame size on the media. 222 * https://datatracker.ietf.org/doc/html/rfc2544#section-23 Lists the 223 actions to be done for each trial measurement, it also mentions 224 loss rate as an example of trial measurement results. This 225 document uses loss count instead, as that is the quantity that is 226 easier for the current test equipment to measure, e.g. it is not 227 affected by the real traffic duration. TODO: Time uncertainty 228 again. 230 * https://datatracker.ietf.org/doc/html/rfc2544#section-24 Mentions 231 "full length trials" leading to the Throughput found, as opposed 232 to shorter trial durations, allowed in an attempt to "minimize the 233 length of search procedure". This document talks about "final 234 trial duration" and aims to "optimize overal search time". 236 * https://datatracker.ietf.org/doc/html/rfc2544#section-26.1 with 237 https://www.rfc-editor.org/errata/eid422 finaly states 238 requirements for the search procedure. It boils down to "increase 239 intended load upon zero trial loss and decrease intended load upon 240 non-zero trial loss". 242 No additional constraints are placed on the load selection, and there 243 is no mention of an exit condition, e.g. when there is enough trial 244 measurements to proclaim the largest load with zero trial loss (and 245 final trial duration) to be the Throughput found. 247 4. Problems 249 4.1. Repeatability and Comparability 251 RFC2544 does not suggest to repeat Throughput search, and from just 252 one Throughput value, it cannot be determined how repeatable that 253 value is (how likely it is for a repeated Throughput search to end up 254 with a value less then the precision goal away from the first value). 256 Depending on SUT behavior, different benchmark groups can report 257 significantly different Througput values, even when using identical 258 SUT and test equipment, just because of minor differences in their 259 search algorithm (e.g. different max load value). 261 While repeatability can be addressed by repeating the search several 262 times, the differences in the comparability scenario may be 263 systematic, e.g. seeming like a bias in one or both benchmark groups. 265 MLRsearch algorithm does not really help with the repeatability 266 problem. This document RECOMMENDS to repeat a selection of 267 "important" tests ten times, so users can ascertain the repeatability 268 of the results. 270 TODO: How to report? Average and standard deviation? 272 Following MLRsearch algorithm leaves less freedom for the benchmark 273 groups to encounter the comparability problem, alghough more research 274 is needed to determine the effect of MLRsearch's tweakable 275 parameters. 277 4.2. Non-Zero Target Loss Ratios 279 https://datatracker.ietf.org/doc/html/rfc1242#section-3.17 defines 280 Throughput as: The maximum rate at which none of the offered frames 281 are dropped by the device. 283 and then it says: Since even the loss of one frame in a data stream 284 can cause significant delays while waiting for the higher level 285 protocols to time out, it is useful to know the actual maximum data 286 rate that the device can support. 288 New "software DUTs" (traffic forwarding programs running on 289 commercial-off-the-shelf compute server hardware) frequently exhibit 290 quite low repeatability of Throughput results per above definition. 292 This is due to, in general, throughput rates of software DUTs 293 (programs) being sensitive to server resource allocation by OS during 294 runtime, as well as any interrupts or blocking of software threads 295 involved in packet processing. 297 To deal with this, this document recommends discovery of multiple 298 throughput rates of interest for software DUTs that run on general 299 purpose COTS servers (with x86, AArch64 Instruction Set 300 Architectures): * throughput rate with target of zero packet loss 301 ratio. * at least one throughput rate with target of non-zero packet 302 loss ratio. 304 In our experience, the higher the target loss ratio is, the better is 305 the repeatability of the corresponding load found. 307 TODO: Define a good name for a load corresponding to a specific non- 308 zero target loss ration, while keeping Throughput for the load 309 corresponding to zero target loss ratio. 311 This document RECOMMENDS the benchmark groups to search for 312 corresponding loads to at least one non-zero target loss ratio. This 313 document does not suggest any particular non-zero target loss ratio 314 value to search the corresponding load for. 316 5. Solution ideas 318 This document gives several independent ideas on how to lower the 319 (average) overall search time, while remaining unconditionally 320 compliant with RFC2544 (and adding some of extensions). 322 This document also specifies one particular way to combine all the 323 ideas into a single search algorithm class (single logic with few 324 tweakable parameters). 326 Little to no research has been done into the question of which 327 combination of ideas achieves the best compromise with respect to 328 overal search time, high repeatability and high comparability. 330 TODO: How important it is to discuss particular implementation 331 choices, especially when motivated by non-deterministic SUT behavior? 333 5.1. Short duration trials 335 https://datatracker.ietf.org/doc/html/rfc2544#section-24 already 336 mentions the possibity of using shorter duration for trials that are 337 not part of "final determination". 339 Obviously, the upper and lower bound from a smaller duration trial 340 can be used as the initial upper and lower bound for the final 341 determination. 343 MLRsearch makes it clear a re-measurement is always needed (new trial 344 measurement with the same load but longer duration). It also 345 specifes what to do if the longer trial is no longer a valid bound 346 (TODO define?), e.g. start an external search. Additionaly one 347 halving can be saved during the shorter duration search. 349 5.2. FRMOL as reasonable start 351 TODO expand: Overal search ends with "final determination" search, 352 preceded by "shorter duration search" preceded by "bound 353 initialization", where the bounds can be considerably different from 354 min and max load. 356 For SUTs with high repeatability, the FRMOL is usually a good 357 approximation of Throughput. But for less repeatable SUTs, 358 forwarding rate (TODO define) is frequently a bad approximation to 359 Throughput, therefore halving and other robust-to-worst-case 360 approaches have to be used. Still, forwarding rate at FRMOL load can 361 be a good initial bound. 363 5.3. Non-zero loss ratios 365 See the "Popularity of non-zero target loss ratios" section above. 367 TODO: Define "trial measurement result classification criteria", or 368 keep reusing long phrases without definitions? 370 A search for a load corresponding to a non-zero target loss rate is 371 very similar to a search for Throughput, just the criterion when to 372 increase or decrease the intended load for the next trial measurement 373 uses the comparison of trial loss ratio to the target loss ratio 374 (instead of comparing loss count to zero) Any search algorithm that 375 works for Throughput can be easily used also for non-zero target loss 376 rates, perhaps with small modifications in places where the measured 377 forwarding rate is used. 379 Note that it is possible to search for multiple loss ratio goals if 380 needed. 382 5.4. Concurrent ratio search 384 A single trial measurement result can act as an upper bound for a 385 lower target loss ratio, and as a lower bound for a higher target 386 loss ratio at the same time. This is an example of how it can be 387 advantageous to search for all loss ratio goals "at once", or at 388 least "reuse" trial measurement result done so far. 390 Even when a search algorithm is fully deterministic in load selection 391 while focusing on a single loss ratio and trial duration, the choice 392 of iteration order between target loss ratios and trial durations can 393 affect the obtained results in subtle ways. MLRsearch offers one 394 particular ordering. 396 5.5. Load selection heuristics and shortcuts 398 Aside of the two heuristics already mentioned (FRMOL based initial 399 bounds and saving one halving when increasing trial duration), there 400 are other tricks that can save some overall search time at the cost 401 of keeping the difference between final lower and upper bound 402 intentionally large (but still within the precision goal). 404 TODO: Refer implementation subsections on: * Uneven splits. * 405 Rounding the interval width up. * Using old invalid bounds for 406 interval width guessing. 408 The impact on overall duration is probably small, and the effect on 409 result distribution maybe even smaller. TODO: Is the two-liner above 410 useful at all? 412 6. Non-compliance with RFC2544 414 It is possible to achieve even faster search times by abandoning some 415 requirements and suggestions of RFC2544, mainly by reducing the wait 416 times at start and end of trial. 418 Such results are therefore no longer compliant with RFC2544 (or at 419 least not unconditionally), but they may still be useful for internal 420 usage, or for comparing results of different DUTs achieved with an 421 identical non-compliant algorithm. 423 TODO: Refer to the subsection with CSIT customizations. 425 7. Additional Requirements 427 RFC2544 can be understood as having a number of implicit 428 requirements. They are made explicit in this section (as 429 requirements for this document, not for RFC2544). 431 Recommendations on how to properly address the implicit requirements 432 are out of scope of this document. 434 7.1. TODO: Search Stop Criteria 436 TODO: Mention the timeout parameter? 438 7.2. Reliability of Test Equipment 440 Both TG and TA MUST be able to handle correctly every intended load 441 used during the search. 443 On TG side, the difference between Intended Load and Offered Load 444 MUST be small. 446 TODO: How small? Difference of one packet may not be measurable due 447 to time uncertainties. 449 TODO expand: time uncertainty. 451 To ensure that, max load (see Terminology) has to be set to low 452 enough value. Benchmark groups MAY list the max load value used, 453 especially if the Throughput value is equal (or close) to the max 454 load. 456 Solutions (even problem formulations) for the following open problems 457 are outside of the scope of this document: * Detecting when the test 458 equipment operates above its safe load. * Finding a large but safe 459 load value. * Correcting any result affected by max load value not 460 being a safe load. 462 7.2.1. Very late frames 464 RFC2544 requires quite conservative time delays see 465 https://datatracker.ietf.org/doc/html/rfc2544#section-23 to prevent 466 frames buffered in one trial measurement to be counted as received in 467 a subsequent trial measurement. 469 However, for some SUTs it may still be possible to buffer enough 470 frames, so they are still sending them (perhaps in bursts) when the 471 next trial measurement starts. Sometimes, this can be detected as a 472 negative trial loss count, e.g. TA receiving more frames than TG has 473 sent during this trial measurement. Frame duplication is another way 474 of causing the negative trial loss count. 476 https://datatracker.ietf.org/doc/html/rfc2544#section-10 recommends 477 to use sequence numbers in frame payloads, but generating and 478 verifying them requires test equipment resources, which may be not 479 plenty enough to suport at high loads. (Using low enough max load 480 would work, but frequently that would be smaller than SUT's sctual 481 Throughput.) 483 RFC2544 does not offer any solution to the negative loss problem, 484 except implicitly treating negative trial loss counts the same way as 485 positive trial loss counts. 487 This document also does not offer any practical solution. 489 Instead, this document SUGGESTS the search algorithm to take any 490 precaution necessary to avoid very late frames. 492 This document also REQUIRES any detected duplicate frames to be 493 counted as additional lost frames. This document also REQUIRES, any 494 negative trial loss ratio to be treated as positive trial loss ratio 495 of the same absolute value. 497 !!! Nothing below is up-to-date with draft v02. !!! 499 8. MLRsearch Background 501 TODO: Old section, probably obsoleted by preceding section(s). 503 Multiple Loss Ratio search (MLRsearch) is a packet throughput search 504 algorithm suitable for deterministic systems (as opposed to 505 probabilistic systems). MLRsearch discovers multiple packet 506 throughput rates in a single search, each rate is associated with a 507 distinct Packet Loss Ratio (PLR) criterion. 509 For cases when multiple rates need to be found, this property makes 510 MLRsearch more efficient in terms of time execution, compared to 511 traditional throughput search algorithms that discover a single 512 packet rate per defined search criteria (e.g. a binary search 513 specified by [RFC2544]). MLRsearch reduces execution time even 514 further by relying on shorter trial durations of intermediate steps, 515 with only the final measurements conducted at the specified final 516 trial duration. This results in the shorter overall search execution 517 time when compared to a traditional binary search, while guaranteeing 518 the same results for deterministic systems. 520 In practice, two rates with distinct PLRs are commonly used for 521 packet throughput measurements of NFV systems: Non Drop Rate (NDR) 522 with PLR=0 and Partial Drop Rate (PDR) with PLR>0. The rest of this 523 document describes MLRsearch with NDR and PDR pair as an example. 525 Similarly to other throughput search approaches like binary search, 526 MLRsearch is effective for SUTs/DUTs with PLR curve that is non- 527 decreasing with growing offered load. It may not be as effective for 528 SUTs/DUTs with abnormal PLR curves, although it will always converge 529 to some value. 531 MLRsearch relies on traffic generator to qualify the received packet 532 stream as error-free, and invalidate the results if any disqualifying 533 errors are present e.g. out-of-sequence frames. 535 MLRsearch can be applied to both uni-directional and bi-directional 536 throughput tests. 538 For bi-directional tests, MLRsearch rates and ratios are aggregates 539 of both directions, based on the following assumptions: 541 * Traffic transmitted by traffic generator and received by SUT/DUT 542 has the same packet rate in each direction, in other words the 543 offered load is symmetric. 545 * SUT/DUT packet processing capacity is the same in both directions, 546 resulting in the same packet loss under load. 548 MLRsearch can be applied even without those assumptions, but in that 549 case the aggregate loss ratio is less useful as a metric. 551 MLRsearch can be used for network transactions consisting of more 552 than just one packet, or anything else that has intended load as 553 input and loss ratio as output (duration as input is optional). This 554 text uses mostly packet-centric language. 556 9. MLRsearch Overview 558 The main properties of MLRsearch: 560 * MLRsearch is a duration aware multi-phase multi-rate search 561 algorithm: 563 - Initial Phase determines promising starting interval for the 564 search. 566 - Intermediate Phases progress towards defined final search 567 criteria. 569 - Final Phase executes measurements according to the final search 570 criteria. 572 - Final search criteria are defined by following inputs: 574 o Target PLRs (e.g. 0.0 and 0.005 when searching for NDR and 575 PDR). 577 o Final trial duration. 579 o Measurement resolution. 581 * Initial Phase: 583 - Measure MRR over initial trial duration. 585 - Measured MRR is used as an input to the first intermediate 586 phase. 588 * Multiple Intermediate Phases: 590 - Trial duration: 592 o Start with initial trial duration in the first intermediate 593 phase. 595 o Converge geometrically towards the final trial duration. 597 - Track all previous trial measurement results: 599 o Duration, offered load and loss ratio are tracked. 601 o Effective loss ratios are tracked. 603 + While in practice, real loss ratios can decrease with 604 increasing load, effective loss ratios never decrease. 605 This is achieved by sorting results by load, and using 606 the effective loss ratio of the previous load if the 607 current loss ratio is smaller than that. 609 o The algorithm queries the results to find best lower and 610 upper bounds. 612 + Effective loss ratios are always used. 614 o The phase ends if all target loss ratios have tight enough 615 bounds. 617 - Search: 619 o Iterate over target loss ratios in increasing order. 621 o If both upper and lower bound are in measurement results for 622 this duration, apply bisect until the bounds are tight 623 enough, and continue with next loss ratio. 625 o If a bound is missing for this duration, but there exists a 626 bound from the previous duration (compatible with the other 627 bound at this duration), re-measure at the current duration. 629 o If a bound in one direction (upper or lower) is missing for 630 this duration, and the previous duration does not have a 631 compatible bound, compute the current "interval size" from 632 the second tightest bound in the other direction (lower or 633 upper respectively) for the current duration, and choose 634 next offered load for external search. 636 o The logic guarantees that a measurement is never repeated 637 with both duration and offered load being the same. 639 o The logic guarantees that measurements for higher target 640 loss ratio iterations (still within the same phase duration) 641 do not affect validity and tightness of bounds for previous 642 target loss ratio iterations (at the same duration). 644 - Use of internal and external searches: 646 o External search: 648 + It is a variant of "exponential search". 650 + The "interval size" is multiplied by a configurable 651 constant (powers of two work well with the subsequent 652 internal search). 654 o Internal search: 656 + A variant of binary search that measures at offered load 657 between the previously found bounds. 659 + The interval does not need to be split into exact halves, 660 if other split can get to the target width goal faster. 662 * The idea is to avoid returning interval narrower than 663 the current width goal. See sample implementation 664 details, below. 666 * Final Phase: 668 - Executed with the final test trial duration, and the final 669 width goal that determines resolution of the overall search. 671 * Intermediate Phases together with the Final Phase are called Non- 672 Initial Phases. 674 * The returned bounds stay within prescribed min_rate and max_rate. 676 - When returning min_rate or max_rate, the returned bounds may be 677 invalid. 679 o E.g. upper bound at max_rate may come from a measurement 680 with loss ratio still not higher than the target loss ratio. 682 The main benefits of MLRsearch vs. binary search include: 684 * In general, MLRsearch is likely to execute more trials overall, 685 but likely less trials at a set final trial duration. 687 * In well behaving cases, e.g. when results do not depend on trial 688 duration, it greatly reduces (>50%) the overall duration compared 689 to a single PDR (or NDR) binary search over duration, while 690 finding multiple drop rates. 692 * In all cases MLRsearch yields the same or similar results to 693 binary search. 695 * Note: both binary search and MLRsearch are susceptible to 696 reporting non-repeatable results across multiple runs for very bad 697 behaving cases. 699 Caveats: 701 * Worst case MLRsearch can take longer than a binary search, e.g. in 702 case of drastic changes in behaviour for trials at varying 703 durations. 705 - Re-measurement at higher duration can trigger a long external 706 search. That never happens in binary search, which uses the 707 final duration from the start. 709 10. Sample Implementation 711 Following is a brief description of a sample MLRsearch 712 implementation, which is a simplified version of the existing 713 implementation. 715 10.1. Input Parameters 717 1. *max_rate* - Maximum Transmit Rate (MTR) of packets to be used by 718 external traffic generator implementing MLRsearch, limited by the 719 actual Ethernet link(s) rate, NIC model or traffic generator 720 capabilities. 722 2. *min_rate* - minimum packet transmit rate to be used for 723 measurements. MLRsearch fails if lower transmit rate needs to be 724 used to meet search criteria. 726 3. *final_trial_duration* - required trial duration for final rate 727 measurements. 729 4. *initial_trial_duration* - trial duration for initial MLRsearch 730 phase. 732 5. *final_relative_width* - required measurement resolution 733 expressed as (lower_bound, upper_bound) interval width relative 734 to upper_bound. 736 6. *packet_loss_ratios* - list of maximum acceptable PLR search 737 criteria. 739 7. *number_of_intermediate_phases* - number of phases between the 740 initial phase and the final phase. Impacts the overall MLRsearch 741 duration. Less phases are required for well behaving cases, more 742 phases may be needed to reduce the overall search duration for 743 worse behaving cases. 745 10.2. Initial Phase 747 1. First trial measures at configured maximum transmit rate (MTR) 748 and discovers maximum receive rate (MRR). 750 * IN: trial_duration = initial_trial_duration. 752 * IN: offered_transmit_rate = maximum_transmit_rate. 754 * DO: single trial. 756 * OUT: measured loss ratio. 758 * OUT: MRR = measured receive rate. Received rate is computed 759 as intended load multiplied by pass ratio (which is one minus 760 loss ratio). This is useful when loss ratio is computed from 761 a different metric than intended load. For example, intended 762 load can be in transactions (multiple packets each), but loss 763 ratio is computed on level of packets, not transactions. 765 * Example: If MTR is 10 transactions per second, and each 766 transaction has 10 packets, and receive rate is 90 packets per 767 second, then loss rate is 10%, and MRR is computed to be 9 768 transactions per second. 770 If MRR is too close to MTR, MRR is set below MTR so that interval 771 width is equal to the width goal of the first intermediate phase. 772 If MRR is less than min_rate, min_rate is used. 774 2. Second trial measures at MRR and discovers MRR2. 776 * IN: trial_duration = initial_trial_duration. 778 * IN: offered_transmit_rate = MRR. 780 * DO: single trial. 782 * OUT: measured loss ratio. 784 * OUT: MRR2 = measured receive rate. If MRR2 is less than 785 min_rate, min_rate is used. If loss ratio is less or equal to 786 the smallest target loss ratio, MRR2 is set to a value above 787 MRR, so that interval width is equal to the width goal of the 788 first intermediate phase. MRR2 could end up being equal to 789 MTR (for example if both measurements so far had zero loss), 790 which was already measured, step 3 is skipped in that case. 792 3. Third trial measures at MRR2. 794 * IN: trial_duration = initial_trial_duration. 796 * IN: offered_transmit_rate = MRR2. 798 * DO: single trial. 800 * OUT: measured loss ratio. 802 * OUT: MRR3 = measured receive rate. If MRR3 is less than 803 min_rate, min_rate is used. If step 3 is not skipped, the 804 first trial measurement is forgotten. This is done because in 805 practice (if MRR2 is above MRR), external search from MRR and 806 MRR2 is likely to lead to a faster intermediate phase than a 807 bisect between MRR2 and MTR. 809 10.3. Non-Initial Phases 811 1. Main phase loop: 813 1. IN: trial_duration for the current phase. Set to 814 initial_trial_duration for the first intermediate phase; to 815 final_trial_duration for the final phase; or to the element 816 of interpolating geometric sequence for other intermediate 817 phases. For example with two intermediate phases, 818 trial_duration of the second intermediate phase is the 819 geometric average of initial_trial_duration and 820 final_trial_duration. 822 2. IN: relative_width_goal for the current phase. Set to 823 final_relative_width for the final phase; doubled for each 824 preceding phase. For example with two intermediate phases, 825 the first intermediate phase uses quadruple of 826 final_relative_width and the second intermediate phase uses 827 double of final_relative_width. 829 3. IN: Measurement results from the previous phase (previous 830 duration). 832 4. Internal target ratio loop: 834 1. IN: Target loss ratio for this iteration of ratio loop. 836 2. IN: Measurement results from all previous ratio loop 837 iterations of current phase (current duration). 839 3. DO: According to the procedure described in point 2: 841 1. either exit the phase (by jumping to 1.5), 842 2. or exit loop iteration (by continuing with next 843 target loss ratio, jumping to 1.4.1), 845 3. or calculate new transmit rate to measure with. 847 4. DO: Perform the trial measurement at the new transmit 848 rate and current trial duration, compute its loss ratio. 850 5. DO: Add the result and go to next iteration (1.4.1), 851 including the added trial result in 1.4.2. 853 5. OUT: Measurement results from this phase. 855 6. OUT: In the final phase, bounds for each target loss ratio 856 are extracted and returned. 858 1. If a valid bound does not exist, use min_rate or 859 max_rate. 861 2. New transmit rate (or exit) calculation (for point 1.4.3): 863 1. If the previous duration has the best upper and lower bound, 864 select the middle point as the new transmit rate. 866 1. See 2.5.3. below for the exact splitting logic. 868 2. This can be a no-op if interval is narrow enough already, 869 in that case continue with 2.2. 871 3. Discussion, assuming the middle point is selected and 872 measured: 874 1. Regardless of loss rate measured, the result becomes 875 either best upper or best lower bound at current 876 duration. 878 2. So this condition is satisfied at most once per 879 iteration. 881 3. This also explains why previous phase has double 882 width goal: 884 1. We avoid one more bisection at previous phase. 886 2. At most one bound (per iteration) is re-measured 887 with current duration. 889 3. Each re-measurement can trigger an external 890 search. 892 4. Such surprising external searches are the main 893 hurdle in achieving low overall search durations. 895 5. Even without 1.1, there is at most one external 896 search per phase and target loss ratio. 898 6. But without 1.1 there can be two re-measurements, 899 each coming with a risk of triggering external 900 search. 902 2. If the previous duration has one bound best, select its 903 transmit rate. In deterministic case this is the last 904 measurement needed this iteration. 906 3. If only upper bound exists in current duration results: 908 1. This can only happen for the smallest target loss ratio. 910 2. If the upper bound was measured at min_rate, exit the 911 whole phase early (not investigating other target loss 912 ratios). 914 3. Select new transmit rate using external search: 916 1. For computing previous interval size, use: 918 1. second tightest bound at current duration, 920 2. or tightest bound of previous duration, if 921 compatible and giving a more narrow interval, 923 3. or target interval width if none of the above is 924 available. 926 4. In any case increase to target interval width if 927 smaller. 929 2. Quadruple the interval width. 931 3. Use min_rate if the new transmit rate is lower. 933 4. If only lower bound exists in current duration results: 935 1. If the lower bound was measured at max_rate, exit this 936 iteration (continue with next lowest target loss ratio). 938 2. Select new transmit rate using external search: 940 1. For computing previous interval size, use: 942 1. second tightest bound at current duration, 944 2. or tightest bound of previous duration, if 945 compatible and giving a more narrow interval, 947 3. or target interval width if none of the above is 948 available. 950 4. In any case increase to target interval width if 951 smaller. 953 2. Quadruple the interval width. 955 3. Use max_rate if the new transmit rate is higher. 957 5. The only remaining option is both bounds in current duration 958 results. 960 1. This can happen in two ways, depending on how the lower 961 bound was chosen. 963 1. It could have been selected for the current loss 964 ratio, e.g. in re-measurement (2.2) or in initial 965 bisect (2.1). 967 2. It could have been found as an upper bound for the 968 previous smaller target loss ratio, in which case it 969 might be too low. 971 3. The algorithm does not track which one is the case, 972 as the decision logic works well regardless. 974 2. Compute "extending down" candidate transmit rate exactly 975 as in 2.3. 977 3. Compute "bisecting" candidate transmit rate: 979 1. Compute the current interval width from the two 980 bounds. 982 2. Express the width as a (float) multiple of the target 983 width goal for this phase. 985 3. If the multiple is not higher than one, it means the 986 width goal is met. Exit this iteration and continue 987 with next higher target loss ratio. 989 4. If the multiple is two or less, use half of that for 990 new width if the lower subinterval. 992 5. Round the multiple up to nearest even integer. 994 6. Use half of that for new width if the lower 995 subinterval. 997 7. Example: If lower bound is 2.0 and upper bound is 998 5.0, and width goal is 1.0, the new candidate 999 transmit rate will be 4.0. This can save a 1000 measurement when 4.0 has small loss. Selecting the 1001 average (3.5) would never save a measurement, giving 1002 more narrow bounds instead. 1004 4. If either candidate computation want to exit the 1005 iteration, do as bisecting candidate computation says. 1007 5. The remaining case is both candidates wanting to measure 1008 at some rate. Use the higher rate. This prefers 1009 external search down narrow enough interval, competing 1010 with perfectly sized lower bisect subinterval. 1012 11. FD.io CSIT Implementation 1014 The only known working implementation of MLRsearch is in the open- 1015 source code running in Linux Foundation FD.io CSIT project 1016 [FDio-CSIT-MLRsearch] as part of a Continuous Integration / 1017 Continuous Development (CI/CD) framework. 1019 MLRsearch is also available as a Python package in [PyPI-MLRsearch]. 1021 11.1. Additional details 1023 This document so far has been describing a simplified version of 1024 MLRsearch algorithm. The full algorithm as implemented in CSIT 1025 contains additional logic, which makes some of the details (but not 1026 general ideas) above incorrect. Here is a short description of the 1027 additional logic as a list of principles, explaining their main 1028 differences from (or additions to) the simplified description, but 1029 without detailing their mutual interaction. 1031 1. Logarithmic transmit rate. 1033 * In order to better fit the relative width goal, the interval 1034 doubling and halving is done differently. 1036 * For example, the middle of 2 and 8 is 4, not 5. 1038 2. Timeout for bad cases. 1040 * The worst case for MLRsearch is when each phase converges to 1041 intervals way different than the results of the previous 1042 phase. 1044 * Rather than suffer total search time several times larger than 1045 pure binary search, the implemented tests fail themselves when 1046 the search takes too long (given by argument _timeout_). 1048 3. Intended count. 1050 * The number of packets to send during the trial should be equal 1051 to the intended load multiplied by the duration. 1053 - Also multiplied by a coefficient, if loss ratio is 1054 calculated from a different metric. 1056 o Example: If a successful transaction uses 10 packets, 1057 load is given in transactions per second, but loss ratio 1058 is calculated from packets, so the coefficient to get 1059 intended count of packets is 10. 1061 * But in practice that does not work. 1063 - It could result in a fractional number of packets, 1065 - so it has to be rounded in a way traffic generator chooses, 1067 - which may depend on the number of traffic flows and traffic 1068 generator worker threads. 1070 4. Attempted count. As the real number of intended packets is not 1071 known exactly, the computation uses the number of packets traffic 1072 generator reports as sent. Unless overridden by the next point. 1074 5. Duration stretching. 1076 * In some cases, traffic generator may get overloaded, causing 1077 it to take significantly longer (than duration) to send all 1078 packets. 1080 * The implementation uses an explicit stop, 1081 - causing lower attempted count in those cases. 1083 * The implementation tolerates some small difference between 1084 attempted count and intended count. 1086 - 10 microseconds worth of traffic is sufficient for our 1087 tests. 1089 * If the difference is higher, the unsent packets are counted as 1090 lost. 1092 - This forces the search to avoid the regions of high 1093 duration stretching. 1095 - The final bounds describe the performance of not just SUT, 1096 but of the whole system, including the traffic generator. 1098 6. Excess packets. 1100 * In some test (e.g. using TCP flows) Traffic generator reacts 1101 to packet loss by retransmission. Usually, such packet loss 1102 is already affecting loss ratio. If a test also wants to 1103 treat retransmissions due to heavily delayed packets also as a 1104 failure, this is once again visible as a mismatch between the 1105 intended count and the attempted count. 1107 * The CSIT implementation simply looks at absolute value of the 1108 difference, so it offers the same small tolerance before it 1109 starts marking a "loss". 1111 7. For result processing, we use lower bounds and ignore upper 1112 bounds. 1114 11.1.1. FD.io CSIT Input Parameters 1116 1. *max_rate* - Typical values: 2 * 14.88 Mpps for 64B 10GE link 1117 rate, 2 * 18.75 Mpps for 64B 40GE NIC (specific model). 1119 2. *min_rate* - Value: 2 * 9001 pps (we reserve 9000 pps for latency 1120 measurements). 1122 3. *final_trial_duration* - Value: 30.0 seconds. 1124 4. *initial_trial_duration* - Value: 1.0 second. 1126 5. *final_relative_width* - Value: 0.005 (0.5%). 1128 6. *packet_loss_ratios* - Value: 0.0, 0.005 (0.0% for NDR, 0.5% for 1129 PDR). 1131 7. *number_of_intermediate_phases* - Value: 2. The value has been 1132 chosen based on limited experimentation to date. More 1133 experimentation needed to arrive to clearer guidelines. 1135 8. *timeout* - Limit for the overall search duration (for one 1136 search). If MLRsearch oversteps this limit, it immediately 1137 declares the test failed, to avoid wasting even more time on a 1138 misbehaving SUT. Value: 600.0 (seconds). 1140 9. *expansion_coefficient* - Width multiplier for external search. 1141 Value: 4.0 (interval width is quadroupled). Value of 2.0 is best 1142 for well-behaved SUTs, but value of 4.0 has been found to 1143 decrease overall search time for worse-behaved SUT 1144 configurations, contributing more to the overall set of different 1145 SUT configurations tested. 1147 11.2. Example MLRsearch Run 1149 The following list describes a search from a real test run in CSIT 1150 (using the default input values as above). 1152 * Initial phase, trial duration 1.0 second. 1154 Measurement 1, intended load 18750000.0 pps (MTR), measured loss 1155 ratio 0.7089514628479618 (valid upper bound for both NDR and PDR). 1157 Measurement 2, intended load 5457160.071600716 pps (MRR), measured 1158 loss ratio 0.018650817320118702 (new tightest upper bounds). 1160 Measurement 3, intended load 5348832.933500009 pps (slightly less 1161 than MRR2 in preparation for first intermediate phase target interval 1162 width), measured loss ratio 0.00964383362905351 (new tightest upper 1163 bounds). 1165 * First intermediate phase starts, trial duration still 1.0 seconds. 1167 Measurement 4, intended load 4936605.579021453 pps (no lower bound, 1168 performing external search downwards, for NDR), measured loss ratio 1169 0.0 (valid lower bound for both NDR and PDR). 1171 Measurement 5, intended load 5138587.208637197 pps (bisecting for 1172 NDR), measured loss ratio 0.0 (new tightest lower bounds). 1174 Measurement 6, intended load 5242656.244044665 pps (bisecting), 1175 measured loss ratio 0.013523745379347257 (new tightest upper bounds). 1177 * Both intervals are narrow enough. 1179 * Second intermediate phase starts, trial duration 5.477225575051661 1180 seconds. 1182 Measurement 7, intended load 5190360.904111567 pps (initial bisect 1183 for NDR), measured loss ratio 0.0023533920869969953 (NDR upper bound, 1184 PDR lower bound). 1186 Measurement 8, intended load 5138587.208637197 pps (re-measuring NDR 1187 lower bound), measured loss ratio 1.2080222912800403e-06 (new 1188 tightest NDR upper bound). 1190 * The two intervals have separate bounds from now on. 1192 Measurement 9, intended load 4936605.381062318 pps (external NDR 1193 search down), measured loss ratio 0.0 (new valid NDR lower bound). 1195 Measurement 10, intended load 5036583.888432355 pps (NDR bisect), 1196 measured loss ratio 0.0 (new tightest NDR lower bound). 1198 Measurement 11, intended load 5087329.903232804 pps (NDR bisect), 1199 measured loss ratio 0.0 (new tightest NDR lower bound). 1201 * NDR interval is narrow enough, PDR interval not ready yet. 1203 Measurement 12, intended load 5242656.244044665 pps (re-measuring PDR 1204 upper bound), measured loss ratio 0.0101174866190136 (still valid PDR 1205 upper bound). 1207 * Also PDR interval is narrow enough, with valid bounds for this 1208 duration. 1210 * Final phase starts, trial duration 30.0 seconds. 1212 Measurement 13, intended load 5112894.3238511775 pps (initial bisect 1213 for NDR), measured loss ratio 0.0 (new tightest NDR lower bound). 1215 Measurement 14, intended load 5138587.208637197 (re-measuring NDR 1216 upper bound), measured loss ratio 2.030389804256833e-06 (still valid 1217 PDR upper bound). 1219 * NDR interval is narrow enough, PDR interval not yet. 1221 Measurement 15, intended load 5216443.04126728 pps (initial bisect 1222 for PDR), measured loss ratio 0.005620871287975237 (new tightest PDR 1223 upper bound). 1225 Measurement 16, intended load 5190360.904111567 (re-measuring PDR 1226 lower bound), measured loss ratio 0.0027629971184465604 (still valid 1227 PDR lower bound). 1229 * PDR interval is also narrow enough. 1231 * Returning bounds: 1233 * NDR_LOWER = 5112894.3238511775 pps; NDR_UPPER = 5138587.208637197 1234 pps; 1236 * PDR_LOWER = 5190360.904111567 pps; PDR_UPPER = 5216443.04126728 1237 pps. 1239 12. IANA Considerations 1241 No requests of IANA. 1243 13. Security Considerations 1245 Benchmarking activities as described in this memo are limited to 1246 technology characterization of a DUT/SUT using controlled stimuli in 1247 a laboratory environment, with dedicated address space and the 1248 constraints specified in the sections above. 1250 The benchmarking network topology will be an independent test setup 1251 and MUST NOT be connected to devices that may forward the test 1252 traffic into a production network or misroute traffic to the test 1253 management network. 1255 Further, benchmarking is performed on a "black-box" basis, relying 1256 solely on measurements observable external to the DUT/SUT. 1258 Special capabilities SHOULD NOT exist in the DUT/SUT specifically for 1259 benchmarking purposes. Any implications for network security arising 1260 from the DUT/SUT SHOULD be identical in the lab and in production 1261 networks. 1263 14. Acknowledgements 1265 Many thanks to Alec Hothan of OPNFV NFVbench project for thorough 1266 review and numerous useful comments and suggestions. 1268 15. References 1270 15.1. Normative References 1272 [RFC2544] Bradner, S. and J. McQuaid, "Benchmarking Methodology for 1273 Network Interconnect Devices", RFC 2544, 1274 DOI 10.17487/RFC2544, March 1999, 1275 . 1277 15.2. Informative References 1279 [FDio-CSIT-MLRsearch] 1280 "FD.io CSIT Test Methodology - MLRsearch", November 2021, 1281 . 1285 [PyPI-MLRsearch] 1286 "MLRsearch 0.4.0, Python Package Index", April 2021, 1287 . 1289 Authors' Addresses 1291 Maciek Konstantynowicz (editor) 1292 Cisco Systems 1293 Email: mkonstan@cisco.com 1295 Vratko Polak 1296 Cisco Systems 1297 Email: vrpolak@cisco.com