idnits 2.17.1 draft-vpolak-bmwg-plrsearch-03.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 seems to lack the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. (The document does seem to have the reference to RFC 2119 which the ID-Checklist requires). -- The document date (March 06, 2020) is 1505 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: 'Pi' is mentioned on line 858, but not defined == Unused Reference: 'RFC8174' is defined on line 982, but no explicit reference was found in the text Summary: 2 errors (**), 0 flaws (~~), 4 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 7, 2020 March 06, 2020 7 Probabilistic Loss Ratio Search for Packet Throughput (PLRsearch) 8 draft-vpolak-bmwg-plrsearch-03 10 Abstract 12 This document addresses challenges while applying methodologies 13 described in [RFC2544] to benchmarking software based NFV (Network 14 Function Virtualization) data planes over an extended period of time, 15 sometimes referred to as "soak testing". Packet throughput search 16 approach proposed by this document assumes that system under test is 17 probabilistic in nature, and not deterministic. 19 Status of This Memo 21 This Internet-Draft is submitted in full conformance with the 22 provisions of BCP 78 and BCP 79. 24 Internet-Drafts are working documents of the Internet Engineering 25 Task Force (IETF). Note that other groups may also distribute 26 working documents as Internet-Drafts. The list of current Internet- 27 Drafts is at https://datatracker.ietf.org/drafts/current/. 29 Internet-Drafts are draft documents valid for a maximum of six months 30 and may be updated, replaced, or obsoleted by other documents at any 31 time. It is inappropriate to use Internet-Drafts as reference 32 material or to cite them other than as "work in progress." 34 This Internet-Draft will expire on September 7, 2020. 36 Copyright Notice 38 Copyright (c) 2020 IETF Trust and the persons identified as the 39 document authors. All rights reserved. 41 This document is subject to BCP 78 and the IETF Trust's Legal 42 Provisions Relating to IETF Documents 43 (https://trustee.ietf.org/license-info) in effect on the date of 44 publication of this document. Please review these documents 45 carefully, as they describe your rights and restrictions with respect 46 to this document. Code Components extracted from this document must 47 include Simplified BSD License text as described in Section 4.e of 48 the Trust Legal Provisions and are provided without warranty as 49 described in the Simplified BSD License. 51 Table of Contents 53 1. Motivation . . . . . . . . . . . . . . . . . . . . . . . . . 3 54 2. Relation To RFC2544 . . . . . . . . . . . . . . . . . . . . . 4 55 3. Terms And Assumptions . . . . . . . . . . . . . . . . . . . . 4 56 3.1. Device Under Test . . . . . . . . . . . . . . . . . . . . 4 57 3.2. System Under Test . . . . . . . . . . . . . . . . . . . . 4 58 3.3. SUT Configuration . . . . . . . . . . . . . . . . . . . . 4 59 3.4. SUT Setup . . . . . . . . . . . . . . . . . . . . . . . . 4 60 3.5. Network Traffic . . . . . . . . . . . . . . . . . . . . . 5 61 3.6. Packet . . . . . . . . . . . . . . . . . . . . . . . . . 5 62 3.6.1. Packet Offered . . . . . . . . . . . . . . . . . . . 5 63 3.6.2. Packet Received . . . . . . . . . . . . . . . . . . . 5 64 3.6.3. Packet Lost . . . . . . . . . . . . . . . . . . . . . 5 65 3.6.4. Other Packets . . . . . . . . . . . . . . . . . . . . 5 66 3.7. Traffic Profile . . . . . . . . . . . . . . . . . . . . . 6 67 3.8. Traffic Generator . . . . . . . . . . . . . . . . . . . . 6 68 3.9. Offered Load . . . . . . . . . . . . . . . . . . . . . . 6 69 3.10. Trial Measurement . . . . . . . . . . . . . . . . . . . . 6 70 3.11. Trial Duration . . . . . . . . . . . . . . . . . . . . . 7 71 3.12. Packet Loss . . . . . . . . . . . . . . . . . . . . . . . 7 72 3.12.1. Loss Count . . . . . . . . . . . . . . . . . . . . . 7 73 3.12.2. Loss Rate . . . . . . . . . . . . . . . . . . . . . 7 74 3.12.3. Loss Ratio . . . . . . . . . . . . . . . . . . . . . 7 75 3.13. Trial Order Independent System . . . . . . . . . . . . . 7 76 3.14. Trial Measurement Result Distribution . . . . . . . . . . 8 77 3.15. Average Loss Ratio . . . . . . . . . . . . . . . . . . . 8 78 3.16. Duration Independent System . . . . . . . . . . . . . . . 8 79 3.17. Load Regions . . . . . . . . . . . . . . . . . . . . . . 9 80 3.17.1. Zero Loss Region . . . . . . . . . . . . . . . . . . 9 81 3.17.2. Guaranteed Loss Region . . . . . . . . . . . . . . . 9 82 3.17.3. Non-Deterministic Region . . . . . . . . . . . . . . 9 83 3.17.4. Normal Region Ordering . . . . . . . . . . . . . . . 9 84 3.18. Deterministic System . . . . . . . . . . . . . . . . . . 10 85 3.19. Througphput . . . . . . . . . . . . . . . . . . . . . . . 10 86 3.20. Deterministic Search . . . . . . . . . . . . . . . . . . 10 87 3.21. Probabilistic Search . . . . . . . . . . . . . . . . . . 10 88 3.22. Loss Ratio Function . . . . . . . . . . . . . . . . . . . 11 89 3.23. Target Loss Ratio . . . . . . . . . . . . . . . . . . . . 11 90 3.24. Critical Load . . . . . . . . . . . . . . . . . . . . . . 11 91 3.25. Critical Load Estimate . . . . . . . . . . . . . . . . . 11 92 3.26. Fitting Function . . . . . . . . . . . . . . . . . . . . 11 93 3.27. Shape of Fitting Function . . . . . . . . . . . . . . . . 11 94 3.28. Parameter Space . . . . . . . . . . . . . . . . . . . . . 12 95 4. Abstract Algorithm . . . . . . . . . . . . . . . . . . . . . 12 96 4.1. High level description . . . . . . . . . . . . . . . . . 12 97 4.2. Main Ideas . . . . . . . . . . . . . . . . . . . . . . . 12 98 4.2.1. Trial Durations . . . . . . . . . . . . . . . . . . . 13 99 4.2.2. Target Loss Ratio . . . . . . . . . . . . . . . . . . 13 100 4.3. PLRsearch Building Blocks . . . . . . . . . . . . . . . . 13 101 4.3.1. Bayesian Inference . . . . . . . . . . . . . . . . . 13 102 4.3.2. Iterative Search . . . . . . . . . . . . . . . . . . 14 103 4.3.3. Fitting Functions . . . . . . . . . . . . . . . . . . 14 104 4.3.4. Measurement Impact . . . . . . . . . . . . . . . . . 14 105 4.3.5. Fitting Function Coefficients Distribution . . . . . 15 106 4.3.6. Exit Condition . . . . . . . . . . . . . . . . . . . 15 107 4.3.7. Integration . . . . . . . . . . . . . . . . . . . . . 15 108 4.3.8. Optimizations . . . . . . . . . . . . . . . . . . . . 15 109 4.3.9. Offered Load Selection . . . . . . . . . . . . . . . 16 110 4.3.10. Trend Analysis . . . . . . . . . . . . . . . . . . . 16 111 5. Known Implementations . . . . . . . . . . . . . . . . . . . . 16 112 5.1. FD.io CSIT Implementation Specifics . . . . . . . . . . . 16 113 5.1.1. Measurement Delay . . . . . . . . . . . . . . . . . . 17 114 5.1.2. Rounding Errors and Underflows . . . . . . . . . . . 17 115 5.1.3. Fitting Functions . . . . . . . . . . . . . . . . . . 17 116 5.1.4. Prior Distributions . . . . . . . . . . . . . . . . . 19 117 5.1.5. Integrator . . . . . . . . . . . . . . . . . . . . . 19 118 5.1.6. Offered Load Selection . . . . . . . . . . . . . . . 20 119 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 120 7. Security Considerations . . . . . . . . . . . . . . . . . . . 21 121 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 21 122 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 21 123 9.1. Normative References . . . . . . . . . . . . . . . . . . 21 124 9.2. Informative References . . . . . . . . . . . . . . . . . 21 125 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 22 127 1. Motivation 129 Network providers are interested in throughput a networking system 130 can sustain. 132 [RFC2544] assumes loss ratio is given by a deterministic function of 133 offered load. But NFV software systems are not deterministic enough. 134 This makes deterministic algorithms (such as Binary Search per 135 [RFC2544] and [draft-vpolak-mkonstan-bmwg-mlrsearch] with single 136 trial) to return results, which when repeated show relatively high 137 standard deviation, thus making it harder to tell what "the 138 throughput" actually is. 140 We need another algorithm, which takes this indeterminism into 141 account. 143 2. Relation To RFC2544 145 The aim of this document is to become an extension of [RFC2544] 146 suitable for benchmarking networking setups such as software based 147 NFV systems. 149 3. Terms And Assumptions 151 Due to the indeterministic nature of certain NFV systems that are the 152 targetted by PLRsearch algorithm, existing network benchmarking terms 153 are explicated and a number of new terms and assumptions are 154 introduced. 156 3.1. Device Under Test 158 In software networking, "device" denotes a specific piece of software 159 tasked with packet processing. Such device is surrounded with other 160 software components (such as operating system kernel). It is not 161 possible to run devices without also running the other components, 162 and hardware resources are shared between both. 164 For purposes of testing, the whole set of hardware and software 165 components is called "system under test" (SUT). As SUT is the part 166 of the whole test setup performance of which can be measured by 167 [RFC2544] methods, this document uses SUT instead of [RFC2544] DUT. 169 Device under test (DUT) can be re-introduced when analysing test 170 results using whitebox techniques, but that is outside the scope of 171 this document. 173 3.2. System Under Test 175 System under test (SUT) is a part of the whole test setup whose 176 performance is to be benchmarked. The complete methodology contains 177 other parts, whose performance is either already established, or not 178 affecting the benchmarking result. 180 3.3. SUT Configuration 182 Usually, system under test allows different configurations, affecting 183 its performance. The rest of this document assumes a single 184 configuration has been chosen. 186 3.4. SUT Setup 188 Similarly to [RFC2544], it is assumed that the system under test has 189 been updated with all the packet forwarding information it needs, 190 before the trial measurements (see below) start. 192 3.5. Network Traffic 194 Network traffic is a type of interaction between system under test 195 and the rest of the system (traffic generator), used to gather 196 information about the system under test performance. PLRsearch is 197 applicable only to areas where network traffic consists of packets. 199 3.6. Packet 201 Unit of interaction between traffic generator and the system under 202 test. Term "packet" is used also as an abstraction of Ethernet 203 frames. 205 3.6.1. Packet Offered 207 Packet can be offered, which means it is sent from traffic generator 208 to the system under test. 210 Each offered packet is assumed to become received or lost in a short 211 time. 213 3.6.2. Packet Received 215 Packet can be received, which means the traffic generator verifies it 216 has been processed. Typically, when it is succesfully sent from the 217 system under test to traffic generator. 219 It is assumed that each received packet has been caused by an offered 220 packet, so the number of packets received cannot be larger than the 221 number of packets offered. 223 3.6.3. Packet Lost 225 Packet can be lost, which means sent but not received in a timely 226 manner. 228 It is assumed that each lost packet has been caused by an offered 229 packet, so the number of packets lost cannot be larger than the 230 number of packets offered. 232 Usually, the number of packets lost is computed as the number of 233 packets offered, minus the number of packets received. 235 3.6.4. Other Packets 237 PLRsearch is not considering other packet behaviors known from 238 networking (duplicated, reordered, greatly delayed), assuming the 239 test specification reclassifies those behaviors to fit into the first 240 three categories. 242 3.7. Traffic Profile 244 Usually, the performance of the system under test depends on a "type" 245 of a particular packet (for example size), and "composition" if the 246 network traffic consists of a mixture of different packet types. 248 Also, some systems under test contain multiple "ports" packets can be 249 offered to and received from. 251 All such qualities together (but not including properties of trial 252 measurements) are called traffic profile. 254 Similarly to system under test configuration, this document assumes 255 only one traffic profile has been chosen for a particular test. 257 3.8. Traffic Generator 259 Traffic generator is the part of the whole test setup, distinct from 260 the system under test, responsible both for offering packets in a 261 highly predictable manner (so the number of packets offered is 262 known), and for counting received packets in a precise enough way (to 263 distinguish lost packets from tolerably delayed packets). 265 Traffic generator must offer only packets compatible with the traffic 266 profile, and only count similarly compatible packets as received. 268 Criteria defining which received packets are compatible are left for 269 test specification to decide. 271 3.9. Offered Load 273 Offered load is an aggregate rate (measured in packets per second) of 274 network traffic offered to the system under test, the rate is kept 275 constant for the duration of trial measurement. 277 3.10. Trial Measurement 279 Trial measurement is a process of stressing (previously setup) system 280 under test by offering traffic of a particular offered load, for a 281 particular duration. 283 After that, the system has a short time to become idle, while the 284 traffic generator decides how many packets were lost. 286 After that, another trial measurement (possibly with different 287 offered load and duration) can be immediately performed. Traffic 288 generator should ignore received packets caused by packets offered in 289 previous trial measurements. 291 3.11. Trial Duration 293 Duration for which the traffic generator was offering packets at 294 constant offered load. 296 In theory, care has to be taken to ensure the offered load and trial 297 duration predict integer number of packets to offer, and that the 298 traffic generator really sends appropriate number of packets within 299 precisely enough timed duration. In practice, such consideration do 300 not change PLRsearch result in any significant way. 302 3.12. Packet Loss 304 Packet loss is any quantity describing a result of trial measurement. 306 It can be loss count, loss rate or loss ratio. Packet loss is zero 307 (or non-zero) if either of the three quantities are zero (or non- 308 zero, respecively). 310 3.12.1. Loss Count 312 Number of packets lost (or delayed too much) at a trial measurement 313 by the system under test as determined by packet generator. Measured 314 in packets. 316 3.12.2. Loss Rate 318 Loss rate is computed as loss count divided by trial duration. 319 Measured in packets per second. 321 3.12.3. Loss Ratio 323 Loss ratio is computed as loss count divided by number of packets 324 offered. Measured as a real (in practice rational) number between 325 zero or one (including). 327 3.13. Trial Order Independent System 329 Trial order independent system is a system under test, proven (or 330 just assumed) to produce trial measurement results that display trial 331 order independence. 333 That means when a pair of consequent trial measurements are 334 performed, the probability to observe a pair of specific results is 335 the same, as the probability to observe the reversed pair of results 336 whe performing the reversed pair of consequent measurements. 338 PLRsearch assumes the system under test is trial order independent. 340 In practice, most system under test are not entirely trial order 341 independent, but it is not easy to devise an algorithm taking that 342 into account. 344 3.14. Trial Measurement Result Distribution 346 When a trial order independent system is subjected to repeated trial 347 measurements of constant duration and offered load, Law of Large 348 Numbers implies the observed loss count frequencies will converge to 349 a specific probability distribution over possible loss counts. 351 This probability distribution is called trial measurement result 352 distribution, and it depends on all properties fixed when defining 353 it. That includes the system under test, its chosen configuration, 354 the chosen traffic profile, the offered load and the trial duration. 356 As the system is trial order independent, trial measurement result 357 distribution does not depend on results of few initial trial 358 measurements, of any offered load or (finite) duration. 360 3.15. Average Loss Ratio 362 Probability distribution over some (finite) set of states enables 363 computation of probability-weighted average of any quantity evaluated 364 on the states (called the expected value of the quantity). 366 Average loss ratio is simply the expected value of loss ratio for a 367 given trial measurement result distribution. 369 3.16. Duration Independent System 371 Duration independent system is a trial order independent system, 372 whose trial measurement result distribution is proven (or just 373 assumed) to display practical independence from trial duration. See 374 definition of trial duration for discussion on practical versus 375 theoretical. 377 The only requirement is for average loss ratio to be independent of 378 trial duration. 380 In theory, that would necessitate each trial measurement result 381 distribution to be a binomial distribution. In practice, more 382 distributions are allowed. 384 PLRsearch assumes the system under test is duration independent, at 385 least for trial durations typically chosen for trial measurements 386 initiated by PLRsearch. 388 3.17. Load Regions 390 For a duration independent system, trial measurement result 391 distribution depends only on offered load. 393 It is convenient to name some areas of offered load space by possible 394 trial results. 396 3.17.1. Zero Loss Region 398 A particular offered load value is said to belong to zero loss 399 region, if the probability of seeing non-zero loss trial measurement 400 result is exactly zero, or at least practically indistinguishable 401 from zero. 403 3.17.2. Guaranteed Loss Region 405 A particular offered load value is said to belong to guaranteed loss 406 region, if the probability of seeing zero loss trial measurement 407 result (for non-negligible count of packets offered) is exactly zero, 408 or at least practically indistinguishable from zero. 410 3.17.3. Non-Deterministic Region 412 A particular offered load value is said to belong to non- 413 deterministic region, if the probability of seeing zero loss trial 414 measurement result (for non-negligible count of packets offered) is 415 practically distinguishable from both zero and one. 417 3.17.4. Normal Region Ordering 419 Although theoretically the three regions can be arbitrary sets, this 420 document assumes they are intervals, where zero loss region contains 421 values smaller than non-deterministic region, which in turn contains 422 values smaller than guaranteed loss region. 424 3.18. Deterministic System 426 A hypothetical duration independent system with normal region 427 ordering, whose non-deterministic region is extremely narrow (only 428 present due to "practical distinguishibility" and cases when the 429 expected number of packets offered is not and integer). 431 A duration independent system which is not deterministic is called 432 non- deterministic system. 434 3.19. Througphput 436 Throughput is the highest offered load provably causing zero packet 437 loss for trial measurements of duration at least 60 seconds. 439 For duration independent systems with normal region ordering, the 440 throughput is the highest value within the zero loss region. 442 3.20. Deterministic Search 444 Any algorithm that assumes each measurement is a proof of the offered 445 load belonging to zero loss region (or not) is called deterministic 446 search. 448 This definition includes algorithms based on "composite measurements" 449 which perform multiple trial measurements, somehow re-classifying 450 results pointing at non-deterministic region. 452 Binary Search is an example of deterministic search. 454 Single run of a deterministic search launched against a deterministic 455 system is guaranteed to find the throughput with any prescribed 456 precision (not better than non-deterministic region width). 458 Multiple runs of a deterministic search launched against a non- 459 deterministic system can return varied results within non- 460 deterministic region. The exact distribution of deterministic search 461 results depends on the algorithm used. 463 3.21. Probabilistic Search 465 Any algorithm which performs probabilistic computations based on 466 observed results of trial measurements, and which does not assume 467 that non-deterministic region is practically absent, is called 468 probabilistic search. 470 A probabilistic search algorithm, which would assume that non- 471 deterministic region is practically absent, does not really need to 472 perform probabilistic computations, so it would become a 473 deterministic search. 475 While probabilistic search for estimating throughput is possible, it 476 would need a careful model for boundary between zero loss region and 477 non-deterministic region, and it would need a lot of measurements of 478 almost surely zero loss to reach good precision. 480 3.22. Loss Ratio Function 482 For any duration independent system, the average loss ratio depends 483 only on offered load (for a particular test setup). 485 Loss ratio function is the name used for the function mapping offered 486 load to average loss ratio. 488 This function is initially unknown. 490 3.23. Target Loss Ratio 492 Input parameter of PLRsearch. The average loss ratio the output of 493 PLRsearch aims to achieve. 495 3.24. Critical Load 497 Aggregate rate of network traffic, which would lead to average loss 498 ratio exactly matching target loss ratio, if used as the offered load 499 for infinite many trial measurement. 501 3.25. Critical Load Estimate 503 Any quantitative description of the possible critical load PLRsearch 504 is able to give after observing finite amount of trial measurements. 506 3.26. Fitting Function 508 Any function PLRsearch uses internally instead of the unknown loss 509 ratio function. Typically chosen from small set of formulas (shapes) 510 with few parameters to tweak. 512 3.27. Shape of Fitting Function 514 Any formula with few undetermined parameters. 516 3.28. Parameter Space 518 A subset of Real Coordinate Space. A point of parameter space is a 519 vector of real numbers. Fitting function is defined by shape (a 520 formula with parameters) and point of parameter space (specifying 521 values for the parameters). 523 4. Abstract Algorithm 525 4.1. High level description 527 PLRsearch accepts some input arguments, then iteratively performs 528 trial measurements at varying offered loads (and durations), and 529 returns some estimates of critical load. 531 PLRsearch input arguments form three groups. 533 First group has a single argument: measurer. This is a callback 534 (function) accepting offered load and duration, and returning the 535 measured loss count. 537 Second group consists of load related arguments required for measurer 538 to work correctly, typically minimal and maximal load to offer. 539 Also, target loss ratio (if not hardcoded) is a required argument. 541 Third group consists of time related arguments. Typically the 542 duration for the first trial measurement, duration increment per 543 subsequent trial measurement, and total time for search. Some 544 PLRsearch implementation may use estimation accuracy parameters as an 545 exit condition instead of total search time. 547 The returned quantities should describe the final (or best) estimate 548 of critical load. Implementers can chose any description that suits 549 their users, typically it is average and standard deviation, or lower 550 and upper boundary. 552 4.2. Main Ideas 554 The search tries to perform measurements at offered load close to the 555 critical load, because measurement results at offered loads far from 556 the critical load give less information on precise location of the 557 critical load. As virtually every trial measurement result alters 558 the estimate of the critical load, offered loads vary as they 559 approach the critical load. 561 The only quantity of trial measurement result affecting the 562 computation is loss count. No latency (or other information) is 563 taken into account. 565 PLRsearch uses Bayesian Inference, computed using numerical 566 integration, which takes long time to get reliable enough results. 567 Therefore it takes some time before the most recent measurement 568 result starts affecting subsequent offered loads and critical rate 569 estimates. 571 During the search, PLRsearch spawns few processes that perform 572 numerical computations, the main process is calling the measurer to 573 perform trial measurements, without any significant delays between 574 them. The durations of the trial measurements are increasing 575 linearly, as higher number of trial measurement results take longer 576 to process. 578 4.2.1. Trial Durations 580 [RFC2544] motivates the usage of at least 60 second duration by the 581 idea of the system under test slowly running out of resources (such 582 as memory buffers). 584 Practical results when measuring NFV software systems show that 585 relative change of trial duration has negligible effects on average 586 loss ratio, compared to relative change in offered load. 588 While the standard deviation of loss ratio usually shows some effects 589 of trial duration, they are hard to model. So PLRsearch assumes SUT 590 is duration independent, and chooses trial durations only based on 591 numeric integration requirements. 593 4.2.2. Target Loss Ratio 595 (TODO: Link to why we think 1e-7 is acceptable loss ratio.) 597 4.3. PLRsearch Building Blocks 599 Here we define notions used by PLRsearch which are not applicable to 600 other search methods, nor probabilistic systems under test in 601 general. 603 4.3.1. Bayesian Inference 605 PLRsearch uses a fixed set of fitting function shapes, and uses 606 Bayesian inference to track posterior distribution on each fitting 607 function parameter space. 609 Specifically, the few parameters describing a fitting function become 610 the model space. Given a prior over the model space, and trial 611 duration results, a posterior distribution is computed, together with 612 quantities describing the critical load estimate. 614 Likelihood of a particular loss count is computed using Poisson 615 distribution of average loss rate given by the fitting function (at 616 specific point of parameter space). 618 Side note: Binomial Distribution is a better fit compared to Poisson 619 distribution (acknowledging that the number of packets lost cannot be 620 higher than the number of packets offered), but the difference tends 621 to be relevant only in high loss region. Using Poisson distribution 622 lowers the impact of measurements in high loss region, thus helping 623 the algorithm to converge towards critical load faster. 625 4.3.2. Iterative Search 627 The idea PLRsearch is to iterate trial measurements, using Bayesian 628 inference to compute both the current estimate of the critical load 629 and the next offered load to measure at. 631 The required numerical computations are done in parallel with the 632 trial measurements. 634 This means the result of measurement "n" comes as an (additional) 635 input to the computation running in parallel with measurement "n+1", 636 and the outputs of the computation are used for determining the 637 offered load for measurement "n+2". 639 Other schemes are possible, aimed to increase the number of 640 measurements (by decreasing their duration), which would have even 641 higher number of measurements run before a result of a measurement 642 affects offered load. 644 4.3.3. Fitting Functions 646 To make the space of possible loss ratio functions more tractable the 647 algorithm uses only few fitting function shapes for its predicitons. 648 As the search algorithm needs to evaluate the function also far away 649 from the critical load, the fitting function have to be reasonably 650 behaved for every positive offered load, specifically cannot cannot 651 predict non-positive packet loss ratio. 653 4.3.4. Measurement Impact 655 Results from trials far from the critical load are likely to affect 656 the critical load estimate negatively, as the fitting functions do 657 not need to be good approximations there. This is true mainly for 658 guaranteed loss region, as in zero loss region even badly behaved 659 fitting function predicts loss count to be "almost zero", so seeing a 660 measurement confirming the loss has been zero indeed has small 661 impact. 663 Discarding some results, or "suppressing" their impact with ad-hoc 664 methods (other than using Poisson distribution instead of binomial) 665 is not used, as such methods tend to make the overall search 666 unstable. We rely on most of measurements being done (eventually) 667 near the critical load, and overweighting far-off measurements 668 (eventually) for well-behaved fitting functions. 670 4.3.5. Fitting Function Coefficients Distribution 672 To accomodate systems with different behaviours, a fitting function 673 is expected to have few numeric parameters affecting its shape 674 (mainly affecting the linear approximation in the critical region). 676 The general search algorithm can use whatever increasing fitting 677 function, some specific functions are described later. 679 It is up to implementer to chose a fitting function and prior 680 distribution of its parameters. The rest of this document assumes 681 each parameter is independently and uniformly distributed over a 682 common interval. Implementers are to add non-linear transformations 683 into their fitting functions if their prior is different. 685 4.3.6. Exit Condition 687 Exit condition for the search is either the standard deviation of the 688 critical load estimate becoming small enough (or similar), or overal 689 search time becoming long enough. 691 The algorithm should report both average and standard deviation for 692 its critical load posterior. 694 4.3.7. Integration 696 The posterior distributions for fitting function parameters are not 697 be integrable in general. 699 The search algorithm utilises the fact that trial measurement takes 700 some time, so this time can be used for numeric integration (using 701 suitable method, such as Monte Carlo) to achieve sufficient 702 precision. 704 4.3.8. Optimizations 706 After enough trials, the posterior distribution will be concentrated 707 in a narrow area of the parameter space. The integration method 708 should take advantage of that. 710 Even in the concentrated area, the likelihood can be quite small, so 711 the integration algorithm should avoid underflow errors by some 712 means, for example by tracking the logarithm of the likelihood. 714 4.3.9. Offered Load Selection 716 The simplest rule is to set offered load for next trial measurememnt 717 equal to the current average (both over posterio and over fitting 718 function shapes) of the critical load estimate. 720 Contrary to critical load estimate computation, heuristic algorithms 721 affecting offered load selection do not introduce instability, and 722 can help with convergence speed. 724 4.3.10. Trend Analysis 726 If the reported averages follow a trend (maybe without reaching 727 equilibrium), average and standard deviation COULD refer to the 728 equilibrium estimates based on the trend, not to immediate posterior 729 values. 731 But such post-processing is discouraged, unless a clear reason for 732 the trend is known. Frequently, presence of such a trend is a sign 733 of some of PLRsearch assumption being violated (usually trial order 734 independence or duration independence). 736 It is RECOMMENDED to report any trend quantification together with 737 direct critical load estimate, so users can draw their own 738 conclusion. Alternatively, trend analysis may be a part of exit 739 conditions, requiring longer searches for systems displaying trends. 741 5. Known Implementations 743 The only known working implementation of PLRsearch is in Linux 744 Foundation FD.io CSIT open-source project [FDio-CSIT-PLRsearch]. 746 5.1. FD.io CSIT Implementation Specifics 748 The search receives min_rate and max_rate values, to avoid 749 measurements at offered loads not supporeted by the traffic 750 generator. 752 The implemented tests cases use bidirectional traffic. The algorithm 753 stores each rate as bidirectional rate (internally, the algorithm is 754 agnostic to flows and directions, it only cares about overall counts 755 of packets sent and packets lost), but debug output from traffic 756 generator lists unidirectional values. 758 5.1.1. Measurement Delay 760 In a sample implemenation in FD.io CSIT project, there is roughly 0.5 761 second delay between trials due to restrictons imposed by packet 762 traffic generator in use (T-Rex). 764 As measurements results come in, posterior distribution computation 765 takes more time (per sample), although there is a considerable 766 constant part (mostly for inverting the fitting functions). 768 Also, the integrator needs a fair amount of samples to reach the 769 region the posterior distribution is concentrated at. 771 And of course, speed of the integrator depends on computing power of 772 the CPUs the algorithm is able to use. 774 All those timing related effects are addressed by arithmetically 775 increasing trial durations with configurable coefficients (currently 776 5.1 seconds for the first trial, each subsequent trial being 0.1 777 second longer). 779 5.1.2. Rounding Errors and Underflows 781 In order to avoid them, the current implementation tracks natural 782 logarithm (instead of the original quantity) for any quantity which 783 is never negative. Logarithm of zero is minus infinity (not 784 supported by Python), so special value "None" is used instead. 785 Specific functions for frequent operations (such as "logarithm of sum 786 of exponentials") are defined to handle None correctly. 788 5.1.3. Fitting Functions 790 Current implementation uses two fitting functions. In general, their 791 estimates for critical rate differ, which adds a simple source of 792 systematic error, on top of posterior dispersion reported by 793 integrator. Otherwise the reported stdev of critical rate estimate 794 is unrealistically low. 796 Both functions are not only increasing, but also convex (meaning the 797 rate of increase is also increasing). 799 As Primitive Function to any positive function is an increasing 800 function, and Primitive Function to any increasing function is convex 801 function; both fitting functions were constructed as double Primitive 802 Function to a positive function (even though the intermediate 803 increasing function is easier to describe). 805 As not any function is integrable, some more realistic functions 806 (especially with respect to behavior at very small offered loads) are 807 not easily available. 809 Both fitting functions have a "central point" and a "spread", varied 810 by simply shifting and scaling (in x-axis, the offered load 811 direction) the function to be doubly integrated. Scaling in y-axis 812 (the loss rate direction) is fixed by the requirement of transfer 813 rate staying nearly constant in very high offered loads. 815 In both fitting functions (as they are a double Primitive Function to 816 a symmetric function), the "central point" turns out to be equal to 817 the aforementioned limiting transfer rate, so the fitting function 818 parameter is named "mrr", the same quantity CSIT Maximum Receive Rate 819 tests are designed to measure. 821 Both fitting functions return logarithm of loss rate, to avoid 822 rounding errors and underflows. Parameters and offered load are not 823 given as logarithms, as they are not expected to be extreme, and the 824 formulas are simpler that way. 826 Both fitting functions have several mathematically equivalent 827 formulas, each can lead to an overflow or underflow in different 828 places. Overflows can be eliminated by using different exact 829 formulas for different argument ranges. Underflows can be avoided by 830 using approximate formulas in affected argument ranges, such ranges 831 have their own formulas to compute. At the end, both fitting 832 function implementations contain multiple "if" branches, 833 discontinuities are a possibility at range boundaries. 835 5.1.3.1. Stretch Function 837 The original function (before applying logarithm) is Primitive 838 Function to Logistic Function. The name "stretch" is used for 839 related a function in context of neural networks with sigmoid 840 activation function. 842 Formula for stretch fitting function: average loss rate (r) computed 843 from offered load (b), mrr parameter (m) and spread parameter (a), 844 given as InputForm of Wolfram language: 846 r = (a*(1 + E^(m/a))*Log[(E^(b/a) + E^(m/a))/(1 + E^(m/a))])/E^(m/a) 848 5.1.3.2. Erf Function 850 The original function is double Primitive Function to Gaussian 851 Function. The name "erf" comes from error function, the first 852 primitive to Gaussian. 854 Formula for erf fitting function: average loss rate (r) computed from 855 offered load (b), mrr parameter (m) and spread parameter (a), given 856 as InputForm of Wolfram language: 858 r = ((a*(E^(-((b - m)^2/a^2)) - E^(-(m^2/a^2))))/Sqrt[Pi] + m*Erfc[m/a] 859 + (b - m)*Erfc[(-b + m)/a])/(1 + Erf[m/a]) 861 5.1.4. Prior Distributions 863 The numeric integrator expects all the parameters to be distributed 864 (independently and) uniformly on an interval (-1, 1). 866 As both "mrr" and "spread" parameters are positive and not 867 dimensionless, a transformation is needed. Dimentionality is 868 inherited from max_rate value. 870 The "mrr" parameter follows a Lomax Distribution with alpha equal to 871 one, but shifted so that mrr is always greater than 1 packet per 872 second. 874 The "stretch" parameter is generated simply as the "mrr" value raised 875 to a random power between zero and one; thus it follows a Reciprocal 876 Distribution. 878 5.1.5. Integrator 880 After few measurements, the posterior distribution of fitting 881 function arguments gets quite concentrated into a small area. The 882 integrator is using Monte Carlo with Importance Sampling where the 883 biased distribution is Bivariate Gaussian distribution, with 884 deliberately larger variance. If the generated sample falls outside 885 (-1, 1) interval, another sample is generated. 887 The the center and the covariance matrix for the biased distribution 888 is based on the first and second moments of samples seen so far 889 (within the computation), with the following additional features 890 designed to avoid hyper-focused distributions. 892 Each computation starts with the biased distribution inherited from 893 the previous computation (zero point and unit covariance matrix is 894 used in the first computation), but the overal weight of the data is 895 set to the weight of the first sample of the computation. Also, the 896 center is set to the first sample point. When additional samples 897 come, their weight (including the importance correction) is compared 898 to the weight of data seen so far (within the computation). If the 899 new sample is more than one e-fold more impactful, both weight values 900 (for data so far and for the new sample) are set to (geometric) 901 average if the two weights. Finally, the actual sample generator 902 uses covariance matrix scaled up by a configurable factor (8.0 by 903 default). 905 This combination showed the best behavior, as the integrator usually 906 follows two phases. First phase (where inherited biased distribution 907 or single big sasmples are dominating) is mainly important for 908 locating the new area the posterior distribution is concentrated at. 909 The second phase (dominated by whole sample population) is actually 910 relevant for the critical rate estimation. 912 5.1.6. Offered Load Selection 914 First two measurements are hardcoded to happen at the middle of rate 915 interval and at max_rate. Next two measurements follow MRR-like 916 logic, offered load is decreased so that it would reach target loss 917 ratio if offered load decrease lead to equal decrease of loss rate. 919 Basis for offered load for next trial measurements is the integrated 920 average of current critical rate estimate, averaged over fitting 921 function. 923 There is one workaround implemented, aimed at reducing the number of 924 consequent zero loss measurements. The workaround first stores every 925 measurement result which loss ratio was the targed loss ratio or 926 higher. Sorted list (called lossy loads) of such results is 927 maintained. 929 When a sequence of one or more zero loss measurement results is 930 encountered, a smallest of lossy loads is drained from the list. If 931 the estimate average is smaller than the drained value, a weighted 932 average of this estimate and the drained value is used as the next 933 offered load. The weight of the drained value doubles with each 934 additional consecutive zero loss results. 936 This behavior helps the algorithm with convergence speed, as it does 937 not need so many zero loss result to get near critical load. Using 938 the smallest (not drained yet) of lossy loads makes it sure the new 939 offered load is unlikely to result in big loss region. Draining even 940 if the estimate is large enough helps to discard early measurements 941 when loss hapened at too low offered load. Current implementation 942 adds 4 copies of lossy loads and drains 3 of them, which leads to 943 fairly stable behavior even for somewhat inconsistent SUTs. 945 6. IANA Considerations 947 No requests of IANA. 949 7. Security Considerations 951 Benchmarking activities as described in this memo are limited to 952 technology characterization of a DUT/SUT using controlled stimuli in 953 a laboratory environment, with dedicated address space and the 954 constraints specified in the sections above. 956 The benchmarking network topology will be an independent test setup 957 and MUST NOT be connected to devices that may forward the test 958 traffic into a production network or misroute traffic to the test 959 management network. 961 Further, benchmarking is performed on a "black-box" basis, relying 962 solely on measurements observable external to the DUT/SUT. 964 Special capabilities SHOULD NOT exist in the DUT/SUT specifically for 965 benchmarking purposes. Any implications for network security arising 966 from the DUT/SUT SHOULD be identical in the lab and in production 967 networks. 969 8. Acknowledgements 971 To be added. 973 9. References 975 9.1. Normative References 977 [RFC2544] Bradner, S. and J. McQuaid, "Benchmarking Methodology for 978 Network Interconnect Devices", RFC 2544, 979 DOI 10.17487/RFC2544, March 1999, 980 . 982 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 983 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 984 May 2017, . 986 9.2. Informative References 988 [draft-vpolak-mkonstan-bmwg-mlrsearch] 989 "Multiple Loss Ratio Search for Packet Throughput 990 (MLRsearch)", February 2020, . 993 [FDio-CSIT-PLRsearch] 994 "FD.io CSIT Test Methodology - PLRsearch", February 2020, 995 . 999 Authors' Addresses 1001 Maciek Konstantynowicz (editor) 1002 Cisco Systems 1004 Email: mkonstan@cisco.com 1006 Vratko Polak (editor) 1007 Cisco Systems 1009 Email: vrpolak@cisco.com