idnits 2.17.1 draft-vpolak-bmwg-plrsearch-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Introduction section. ** The abstract seems to contain references ([RFC2544]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (March 11, 2019) is 1872 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Unused Reference: 'RFC8174' is defined on line 1018, but no explicit reference was found in the text Summary: 2 errors (**), 0 flaws (~~), 2 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Benchmarking Working Group M. Konstantynowicz, Ed. 3 Internet-Draft V. Polak, Ed. 4 Intended status: Informational Cisco Systems 5 Expires: September 12, 2019 March 11, 2019 7 Probabilistic Loss Ratio Search for Packet Throughput (PLRsearch) 8 draft-vpolak-bmwg-plrsearch-01 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 12, 2019. 36 Copyright Notice 38 Copyright (c) 2019 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.6.5. Tasks As Packets . . . . . . . . . . . . . . . . . . 6 67 3.7. Traffic Profile . . . . . . . . . . . . . . . . . . . . . 6 68 3.8. Traffic Generator . . . . . . . . . . . . . . . . . . . . 6 69 3.9. Offered Load . . . . . . . . . . . . . . . . . . . . . . 6 70 3.10. Trial Measurement . . . . . . . . . . . . . . . . . . . . 7 71 3.11. Trial Duration . . . . . . . . . . . . . . . . . . . . . 7 72 3.12. Packet Loss . . . . . . . . . . . . . . . . . . . . . . . 7 73 3.12.1. Loss Count . . . . . . . . . . . . . . . . . . . . . 7 74 3.12.2. Loss Rate . . . . . . . . . . . . . . . . . . . . . 7 75 3.12.3. Loss Ratio . . . . . . . . . . . . . . . . . . . . . 8 76 3.13. Trial Order Independent System . . . . . . . . . . . . . 8 77 3.14. Trial Measurement Result Distribution . . . . . . . . . . 8 78 3.15. Average Loss Ratio . . . . . . . . . . . . . . . . . . . 8 79 3.16. Duration Independent System . . . . . . . . . . . . . . . 9 80 3.17. Load Regions . . . . . . . . . . . . . . . . . . . . . . 9 81 3.17.1. Zero Loss Region . . . . . . . . . . . . . . . . . . 9 82 3.17.2. Guaranteed Loss Region . . . . . . . . . . . . . . . 9 83 3.17.3. Non-Deterministic Region . . . . . . . . . . . . . . 9 84 3.17.4. Normal Region Ordering . . . . . . . . . . . . . . . 10 85 3.18. Deterministic System . . . . . . . . . . . . . . . . . . 10 86 3.19. Througphput . . . . . . . . . . . . . . . . . . . . . . . 10 87 3.20. Deterministic Search . . . . . . . . . . . . . . . . . . 10 88 3.21. Probabilistic Search . . . . . . . . . . . . . . . . . . 11 89 3.22. Loss Ratio Function . . . . . . . . . . . . . . . . . . . 11 90 3.23. Target Loss Ratio . . . . . . . . . . . . . . . . . . . . 11 91 3.24. Critical Load . . . . . . . . . . . . . . . . . . . . . . 11 92 3.25. Critical Load Estimate . . . . . . . . . . . . . . . . . 11 93 3.26. Fitting Function . . . . . . . . . . . . . . . . . . . . 11 94 3.27. Shape of Fitting Function . . . . . . . . . . . . . . . . 12 95 3.28. Parameter Space . . . . . . . . . . . . . . . . . . . . . 12 97 4. Abstract Algorithm . . . . . . . . . . . . . . . . . . . . . 12 98 4.1. High level description . . . . . . . . . . . . . . . . . 12 99 4.2. Main Ideas . . . . . . . . . . . . . . . . . . . . . . . 12 100 4.3. Probabilistic Notions . . . . . . . . . . . . . . . . . . 13 101 4.3.1. Loss Count Only . . . . . . . . . . . . . . . . . . . 13 102 4.3.2. Independent Trials . . . . . . . . . . . . . . . . . 13 103 4.3.3. Trial Durations . . . . . . . . . . . . . . . . . . . 14 104 4.3.4. Target Loss Ratio . . . . . . . . . . . . . . . . . . 14 105 4.3.5. Critical Load . . . . . . . . . . . . . . . . . . . . 14 106 4.3.6. Load Regions . . . . . . . . . . . . . . . . . . . . 15 107 4.3.7. Finite Models . . . . . . . . . . . . . . . . . . . . 15 108 4.4. PLRsearch Building Blocks . . . . . . . . . . . . . . . . 15 109 4.4.1. Bayesian Inference . . . . . . . . . . . . . . . . . 15 110 4.4.2. Iterative Search . . . . . . . . . . . . . . . . . . 16 111 4.4.3. Poisson Distribution . . . . . . . . . . . . . . . . 16 112 4.4.4. Fitting Functions . . . . . . . . . . . . . . . . . . 16 113 4.4.5. Measurement Impact . . . . . . . . . . . . . . . . . 17 114 4.4.6. Fitting Function Coefficients Distribution . . . . . 17 115 4.4.7. Integration . . . . . . . . . . . . . . . . . . . . . 18 116 4.4.8. Optimizations . . . . . . . . . . . . . . . . . . . . 18 117 5. Sample Implementation Specifics: FD.io CSIT . . . . . . . . . 18 118 5.1. Measurement Delay . . . . . . . . . . . . . . . . . . . . 18 119 5.2. Rounding Errors and Underflows . . . . . . . . . . . . . 19 120 5.3. Fitting Functions . . . . . . . . . . . . . . . . . . . . 19 121 5.3.1. Stretch Function . . . . . . . . . . . . . . . . . . 20 122 5.3.2. Erf Function . . . . . . . . . . . . . . . . . . . . 20 123 5.4. Prior Distributions . . . . . . . . . . . . . . . . . . . 21 124 5.5. Integrator . . . . . . . . . . . . . . . . . . . . . . . 21 125 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 22 126 7. Security Considerations . . . . . . . . . . . . . . . . . . . 22 127 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 22 128 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 22 129 9.1. Normative References . . . . . . . . . . . . . . . . . . 22 130 9.2. Informative References . . . . . . . . . . . . . . . . . 22 131 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 22 133 1. Motivation 135 Network providers are interested in throughput a system can sustain. 137 [RFC2544] assumes loss ratio is given by a deterministic function of 138 offered load. But NFV software systems are not deterministic enough. 139 This makes deterministic algorithms (such as Binary Search per 140 [RFC2544] and [draft-vpolak-mkonstan-bmwg-mlrsearch] with single 141 trial) to return results, which when repeated show relatively high 142 standard deviation, thus making it harder to tell what "the 143 throughput" actually is. 145 We need another algorithm, which takes this indeterminism into 146 account. 148 2. Relation To RFC2544 150 The aim of this document is to become an extension of [RFC2544] 151 suitable for benchmarking networking setups such as software based 152 NFV systems. 154 3. Terms And Assumptions 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 this document sticks to 171 blackbox testing. 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 abstractions 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.6.5. Tasks As Packets 244 Ethernet frames are the prime example of packets, but other units are 245 possible. 247 For example, a task processing system can fit the description. 248 Packet offered can stand for task submitted, packet received for task 249 processed successfully, and packet lost for task aborted (or not 250 processed successfully for some other reason). 252 In networking context, such a task can be a route update. 254 3.7. Traffic Profile 256 Usually, the performance of the system under test depends on a "type" 257 of a particular packet (for example size), and "composition" if the 258 network traffic consists of a mixture of different packet types. 260 Also, some systems under test contain multiple "ports" packets can be 261 offered to and received from. 263 All such qualities together (but not including properties of trial 264 measurements) are called traffic profile. 266 Similarly to system under test configuration, this document assumes 267 only one traffic profile has been chosen for a particular test. 269 3.8. Traffic Generator 271 Traffic generator is the part of the whole test setup, distinct from 272 the system under test, responsible both for offering packets in a 273 highly predictable manner (so the number of packets offered is 274 known), and for counting received packets in a precise enough way (to 275 distinguish lost packets from tolerably delayed packets). 277 Traffic generator must offer only packets compatible with the traffic 278 profile, and only count similarly compatible packets as received. 280 3.9. Offered Load 282 Offered load is an aggregate rate (measured in packets per second) of 283 network traffic offered to the system under test, the rate is kept 284 constant for the duration of trial measurement. 286 3.10. Trial Measurement 288 Trial measurement is a process of stressing (previously setup) system 289 under test by offering traffic of a particular offered load, for a 290 particular duration. 292 After that, the system has a short time to become idle, while the 293 traffic generator decides how many packets were lost. 295 After that, another trial measurement (possibly with different 296 offered load and duration) can be immediately performed. Traffic 297 generator should ignore received packets caused by packets offered in 298 previous trial measurements. 300 3.11. Trial Duration 302 Duration for which the traffic generator was offering packets at 303 constant offered load. 305 In theory, care has to be taken to ensure the offered load and trial 306 duration predict integer number of packets to offer, and that the 307 traffic generator really sends appropriate number of packets within 308 precisely enough timed duration. In practice, such consideration do 309 not change PLRsearch result in any significant way. 311 3.12. Packet Loss 313 Packet loss is any quantity describing a result of trial measurement. 315 It can be loss count, loss rate or loss ratio. Packet loss is zero 316 (or non-zero) if either of the three quantities are zero (or non- 317 zero, respecively). 319 3.12.1. Loss Count 321 Number of packets lost (or delayed too much) at a trial measurement 322 by the system under test as determined by packet generator. Measured 323 in packets. 325 3.12.2. Loss Rate 327 Loss rate is computed as loss count divided by trial duration. 328 Measured in packets per second. 330 3.12.3. Loss Ratio 332 Loss ratio is computed as loss count divided by number of packets 333 offered. Measured as a real (in practice rational) number between 334 zero or one (including). 336 3.13. Trial Order Independent System 338 Trial order independent system is a system under test, proven (or 339 just assumed) to produce trial measurement results that display trial 340 order independence. 342 That means when a pair of consequent trial measurements are 343 performed, the probability to observe a pair of specific results is 344 the same, as the probability to observe the reversed pair of results 345 whe performing the reversed pair of consequent measurements. 347 PLRsearch assumes the system under test is trial order independent. 349 In practice, most system under test are not entirely trial order 350 independent, but it is not easy to devise an algorithm taking that 351 into account. 353 3.14. Trial Measurement Result Distribution 355 When a trial order independent system is subjected to repeated trial 356 measurements of constant offered load and duration, Law of Large 357 Numbers implies the observed loss count frequencies will converge to 358 a specific probability distribution over possible loss counts. 360 This probability distribution is called trial measurement result 361 distribution, and it depends on all properties fixed when defining 362 it. That includes the system under test, its chosen configuration, 363 the chosen traffic profile, the offered load and the trial duration. 365 As the system is trial order independent, trial measurement result 366 distribution does not depend on results of few initial trial 367 measurements, of any offered load or (finite) duration. 369 3.15. Average Loss Ratio 371 Probability distribution over some (finite) set of states enables 372 computation of probability-weighted average of any quantity evaluated 373 on the states (called the expected value of the quantity). 375 Average loss ratio is simply the expected value of loss ratio for a 376 given trial measurement result distribution. 378 3.16. Duration Independent System 380 Duration independent system is a trial order independent system, 381 whose trial measurement result distribution is proven (or just 382 assumed) to display practical independence from trial duration. See 383 definition of trial duration for discussion on practical versus 384 theoretical. 386 The only requirement is for average loss ratio to be independent of 387 trial duration. 389 In theory, that would necessitate each trial measurement result 390 distribution to be a binomial distribution. In practice, more 391 distributions are allowed. 393 PLRsearch assumes the system under test is duration independent, at 394 least for trial durations typically chosen for trial measurements 395 initiated by PLRsearch. 397 3.17. Load Regions 399 For a duration independent system, trial measurement result 400 distribution depends only on offered load. 402 It is convenient to name some areas of offered load space by possible 403 trial results. 405 3.17.1. Zero Loss Region 407 A particular offered load value is said to belong to zero loss 408 region, if the probability of seeing non-zero loss trial measurement 409 result is exactly zero, or at least practically indistinguishable 410 from zero. 412 3.17.2. Guaranteed Loss Region 414 A particular offered load value is said to belong to guaranteed loss 415 region, if the probability of seeing zero loss trial measurement 416 result (for non-negligible count of packets offered) is exactly zero, 417 or at least practically indistinguishable from zero. 419 3.17.3. Non-Deterministic Region 421 A particular offered load value is said to belong to non- 422 deterministic region, if the probability of seeing zero loss trial 423 measurement result (for non-negligible count of packets offered) 424 practically distinguishable from both zero and one. 426 3.17.4. Normal Region Ordering 428 Although theoretically the three regions can be arbitrary sets, this 429 document assumes they are intervals, where zero loss region contains 430 values smaller than non-deterministic region, which in turn contains 431 values smaller than guaranteed loss region. 433 3.18. Deterministic System 435 A hypothetical duration independent system with normal region 436 ordering, whose non-deterministic region is extremely narrow; only 437 present due to "practical distinguishibility" and cases when the 438 expected number of packets offered is not and integer. 440 A duration independent system which is not deterministic is called 441 non- deterministic system. 443 3.19. Througphput 445 Throughput is the highest offered load provably causing zero packet 446 loss for trial measurements of duration at least 60 seconds. 448 For duration independent systems with normal region ordering, the 449 throughput is the highest value within the zero loss region. 451 3.20. Deterministic Search 453 Any algorithm that assumes each measurement is a proof of the offered 454 load belonging to zero loss region (or not) is called deterministic 455 search. 457 This definition includes algorithms based on "composite measurements" 458 which perform multiple trial measurements, somehow re-classifying 459 results pointing at non-deterministic region. 461 Binary Search is an example of deterministic search. 463 Single run of a deterministic search launched against a deterministic 464 system is guaranteed to find the throughput with any prescribed 465 precision (not better than non-deterministic region width). 467 Multiple runs of a deterministic search launched against a non- 468 deterministic system can return varied results within non- 469 deterministic region. The exact distribution of deterministic search 470 results depends on the algorithm used. 472 3.21. Probabilistic Search 474 Any algorithm which performs probabilistic computations based on 475 observed results of trial measurements, and which does not assume 476 that non-deterministic region is practically absent is called 477 probabilistic search. 479 A probabilistic search algorithm, which would assume that non- 480 deterministic region is practically absent, does not really need to 481 perform probabilistic computations, so it would become a 482 deterministic search. 484 While probabilistic search for estimating throughput is possible, it 485 would need a careful model for boundary between zero loss region and 486 non-deterministic region, and it would need a lot of measurements of 487 almost surely zero loss to reach good precision. 489 3.22. Loss Ratio Function 491 For any duration independent system, the average loss ratio depends 492 only on offered load (for a particular test setup). 494 Loss ratio function is the name used for the function mapping offered 495 load to average loss ratio. 497 This function is initially unknown. 499 3.23. Target Loss Ratio 501 Input parameter of PLRsearch. The average loss ratio the output of 502 PLRsearch aims to achieve. 504 3.24. Critical Load 506 Aggregate rate of network traffic, which would lead to average loss 507 ratio exactly matching target loss ratio (when used as the offered 508 load for infinite many trial measurement). 510 3.25. Critical Load Estimate 512 Any quantitative description of the possible critical load PLRsearch 513 is able to give after observing finite amount of trial measurements. 515 3.26. Fitting Function 517 Any function PLRsearch uses internally instead of the unknown loss 518 ratio function. Typically chosen from small set of formulas (shapes) 519 with few parameters to tweak. 521 3.27. Shape of Fitting Function 523 Any formula with few undetermined parameters. 525 3.28. Parameter Space 527 A subset of Real Coordinate Space. A point of parameter space is a 528 vector of real numbers. Fitting function is defined by shape (a 529 formula with parameters) and point of parameter space (specifying 530 values for the parameters). 532 4. Abstract Algorithm 534 4.1. High level description 536 PLRsearch accepts some input arguments, then iteratively performs 537 trial measurements at varying offered loads (and durations), and 538 returns some estimates of critical load. 540 PLRsearch input arguments form three groups. 542 First group has a single argument: measurer. This is a callback 543 (function) accepting offered load and duration, and returning the 544 measured loss count. 546 Second group consists of load related arguments required for measurer 547 to work correctly, typically minimal and maximal load to offer. 548 Also, target loss ratio (if not hardcoded) is a required argument. 550 Third group consists of time related arguments. Typically the 551 duration for the first trial measurement, duration increment per 552 subsequent trial measurement and total time for search. Some 553 PLRsearch implementation may use estimation accuracy parameters as an 554 exit condition instead of total search time. 556 The returned quantities should describe the final (or best) estimate 557 of critical load. Implementers can chose any description that suits 558 their users, typically it is average and standard deviation, or lower 559 and upper boundary. 561 4.2. Main Ideas 563 The search tries to perform measurements at offered load close to the 564 critical load, because measurement results at offered loads far from 565 the critical load give less information on precise location of the 566 critical load. As virtually every trial measurement result alters 567 the estimate of the critical load, offered loads vary as they 568 approach the critical load. 570 PLRsearch uses Bayesian Inference, computed using numerical 571 integration, which takes long time to get reliable enough results. 572 Therefore it takes some time before the most recent measurement 573 result starts affecting subsequent offered loads and critical rate 574 estimates. 576 During the search, PLRsearch spawns few processes that perform 577 numerical computations, the main process is calling the measurer to 578 perform trial measurements, without any significant delays between 579 them. The durations of the trial measurements are increasing 580 linearly, as higher number of trial measurement results take longer 581 to process. 583 4.3. Probabilistic Notions 585 Before internals of PLRsearch are described, we need to define 586 notions valid for situations when loss ratio is not entirely 587 determined by offered load. 589 Some of the notions already incorporate assumptions the PLRsearch 590 algorithm applies. 592 4.3.1. Loss Count Only 594 It is assumed that the traffic generator detects duplicate packets on 595 receive, and reports this as an error. 597 No latency (or other information) is taken into account. 599 4.3.2. Independent Trials 601 PLRsearch still assumes the system under test can be subjected to 602 trial measurements. The loss count is no longer determined 603 precisely, but it is assumed that for every system under test, its 604 configuration, traffic type and trial duration, there is a 605 probability distribution over possible loss counts. 607 This implies trial measurements are probabilistic, but the 608 distribution is independent of possible previous trial measurements. 610 Independence from previous measurements is not guaranteed in the real 611 world. The previous measurements may improve performance (via long- 612 term warmup effects), or decrease performance (due to long-term 613 resource leaks). 615 4.3.3. Trial Durations 617 [RFC2544] motivates the usage of at least 60 second duration by the 618 idea of the system under test slowly running out of resources (such 619 as memory buffers). 621 Practical results when measuring NFV software systems show that 622 relative change of trial duration has negligible effects on average 623 loss ratio, compared to relative change in offered load. 625 While the standard deviation of loss ratio usually shows some effects 626 of trial duration, they are hard to model; so further assumtions in 627 PLRsearch will make it insensitive to trial duration. 629 4.3.4. Target Loss Ratio 631 Loss ratio function could be used to generalize throughput as the 632 biggest offered load which still leads to zero average loss ratio. 633 Unfortunately, most realistic loss ratio functions always predict 634 non- zero (even if negligible) average loss ratio. 636 On the other hand, users do not really require the average loss ratio 637 to be an exact zero. Most users are satisfied when the average loss 638 ratio is small enough. 640 One of PLRsearch inputs is called target loss ratio. It is the loss 641 ratio users would accept as negligible. 643 (TODO: Link to why we think 1e-7 is acceptable loss ratio.) 645 4.3.5. Critical Load 647 Critical load (sometimes called critical rate) is the offered load 648 which leads to average loss ratio to become exactly equal to the 649 target loss ratio. 651 In principle, there could be such loss ratio functions which allow 652 more than one offered load to achieve target loss ratio. To avoid 653 that, PLRsearch assumes only increasing loss ratio functions are 654 possible. 656 Similarly, some loss ratio functions may never return the target loss 657 ratio. PLRsearch assumes loss ratio function is continuous, that the 658 average loss ratio approaches zero as offered load approaches zero, 659 and that the average loss ratio approaches one as offered load 660 approaches infinity. 662 Under these assumptions, each loss ratio function has unique critical 663 load. PLRsearch attempts to locate the critical load. 665 4.3.6. Load Regions 667 Critical region is the interval of offered load close to critical 668 load, where single measurement is not likely to distinguish whether 669 the critical load is higher or lower than the current offered load. 671 In typical case of small target loss ratio, rates below critical 672 region form "zero loss region", and rates above form "high loss 673 region". 675 4.3.7. Finite Models 677 Of course, finite amount of trial measurements, each of finite 678 duration does not give enough information to pinpoint the critical 679 load exactly. Therefore the output of PLRsearch is just an estimate 680 with some precision. 682 Aside of the usual substitution of infinitely precise real numbers by 683 finitely precise floating point numbers, there are two other 684 instances within PLRsearch where an objects of high information are 685 replaced by objects of low information. 687 One is the probability distribution of loss count, which is replaced 688 by average loss ratio. The other is the loss ratio function, which 689 is replaced by a few parameters, to be described later. 691 4.4. PLRsearch Building Blocks 693 Here we define notions used by PLRsearch which are not applicable to 694 other search methods, nor probabilistic systems under test, in 695 general. 697 4.4.1. Bayesian Inference 699 Having reduced the model space significantly, the task of estimating 700 the critical load becomes simple enough so that Bayesian inference 701 can be used (instead of neural networks, or other Artifical 702 Intelligence methods). 704 In this case, the few parameters describing the loss ration function 705 become the model space. Given a prior over the model space, and 706 trial duration results, a posterior distribution can be computed, 707 together with quantities describing the critical load estimate. 709 4.4.2. Iterative Search 711 The idea PLRsearch is to iterate trial measurements, using Bayesian 712 inference to compute both the current estimate of the critical load 713 and the next offered load to measure at. 715 The required numerical computations are done in parallel with the 716 trial measurements. 718 This means the result of measurement "n" comes as an (additional) 719 input to the computation running in parallel with measurement "n+1", 720 and the outputs of the computation are used for determining the 721 offered load for measurement "n+2". 723 Other schemes are possible, aimed to increase the number of 724 measurements (by decreasing their duration), which would have even 725 higher number of measurements run before a result of a measurement 726 affects offered load. 728 4.4.3. Poisson Distribution 730 For given offered load, number of packets lost during trial 731 measurement is assumed to come from Poisson distribution, and the 732 (unknown) Poisson parameter is expressed as average loss ratio. 734 Side note: Binomial Distribution is a better fit compared to Poisson 735 distribution (acknowledging that the number of packets lost cannot be 736 higher than the number of packets offered), but the difference tends 737 to be relevant only in high loss region. Using Poisson distribution 738 lowers the impact of measurements in high loss region, thus helping 739 the algorithm to focus on critical region better. 741 4.4.4. Fitting Functions 743 There are great many increasing functions (as candidates for the loss 744 ratio function). 746 To make the space of possible functions more tractable, some other 747 simplifying assumptions are needed. As the algorithm will be 748 examining (also) loads very close to the critical load, linear 749 approximation to the loss rate function around the critical load is 750 important. But as the search algorithm needs to evaluate the 751 function also far away from the critical region, the approximate 752 function has to be reasonably behaved for every positive offered 753 load, specifically it cannot predict non- positive packet loss ratio. 755 Within this document, "fitting function" is the name for such a 756 reasonably behaved function, which approximates the loss ratio 757 function well in the critical region. 759 4.4.5. Measurement Impact 761 Results from trials far from the critical region are likely to affect 762 the critical rate estimate negatively, as the fitting function does 763 not need to be a good approximation there. This is true mainly for 764 high loss region, as in zero loss region even badly behaved fitting 765 function predicts loss count to be "almost zero", so seeing a 766 measurement confirming the loss has been zero indeed has small 767 impact. 769 Discarding some results, or "suppressing" their impact with ad-hoc 770 methods (other than using Poisson distribution instead of binomial) 771 is not used, as such methods tend to make the overall search 772 unstable. We rely on most of measurements being done (eventually) 773 within the critical region, and overweighting far-off measurements 774 (eventually) for well- behaved fitting functions. 776 Speaking about new trials, each next trial will be done at offered 777 load equal to the current average of the critical load. Alternative 778 methods for selecting offered load might be used, in an attempt to 779 speed up convergence. For example by employing the aforementioned 780 unstable ad-hoc methods. 782 4.4.6. Fitting Function Coefficients Distribution 784 To accomodate systems with different behaviours, the fitting function 785 is expected to have few numeric parameters affecting its shape 786 (mainly affecting the linear approximation in the critical region). 788 The general search algorithm can use whatever increasing fitting 789 function, some specific functions can described later. 791 It is up to implementer to chose a fitting function and prior 792 distribution of its parameters. The rest of this document assumes 793 each parameter is independently and uniformly distributed over a 794 common interval. Implementers are to add non-linear transformations 795 into their fitting functions if their prior is different. 797 Exit condition for the search is either the standard deviation of the 798 critical load estimate becoming small enough (or similar), or overal 799 search time becoming long enough. 801 The algorithm should report both average and standard deviation for 802 its critical load posterior. If the reported averages follow a trend 803 (without reaching equilibrium), average and standard deviation should 804 refer to the equilibrium estimates based on the trend, not to 805 immediate posterior values. 807 4.4.7. Integration 809 The posterior distributions for fitting function parameters will not 810 be integrable in general. 812 The search algorithm utilises the fact that trial measurement takes 813 some time, so this time can be used for numeric integration (using 814 suitable method, such as Monte Carlo) to achieve sufficient 815 precision. 817 4.4.8. Optimizations 819 After enough trials, the posterior distribution will be concentrated 820 in a narrow area of the parameter space. The integration method 821 should take advantage of that. 823 Even in the concentrated area, the likelihood can be quite small, so 824 the integration algorithm should avoid underflow errors by some 825 means, for example by tracking the logarithm of the likelihood. 827 5. Sample Implementation Specifics: FD.io CSIT 829 The search receives min_rate and max_rate values, to avoid 830 measurements at offered loads not supporeted by the traffic 831 generator. 833 The implemented tests cases use bidirectional traffic. The algorithm 834 stores each rate as bidirectional rate (internally, the algorithm is 835 agnostic to flows and directions, it only cares about overall counts 836 of packets sent and packets lost), but debug output from traffic 837 generator lists unidirectional values. 839 5.1. Measurement Delay 841 In a sample implemenation in FD.io CSIT project, there is roughly 0.5 842 second delay between trials due to restrictons imposed by packet 843 traffic generator in use (T-Rex). 845 As measurements results come in, posterior distribution computation 846 takes more time (per sample), although there is a considerable 847 constant part (mostly for inverting the fitting functions). 849 Also, the integrator needs a fair amount of samples to reach the 850 region the posterior distribution is concentrated at. 852 And of course, speed of the integrator depends on computing power of 853 the CPU the algorithm is able to use. 855 All those timing related effects are addressed by arithmetically 856 increasing trial durations with configurable coefficients (currently 857 5.1 seconds for the first trial, each subsequent trial being 0.1 858 second longer). 860 5.2. Rounding Errors and Underflows 862 In order to avoid them, the current implementation tracks natural 863 logarithm (instead of the original quantity) for any quantity which 864 is never negative. Logarithm of zero is minus infinity (not 865 supported by Python), so special value "None" is used instead. 866 Specific functions for frequent operations (such as "logarithm of sum 867 of exponentials") are defined to handle None correctly. 869 5.3. Fitting Functions 871 Current implementation uses two fitting functions. In general, their 872 estimates for critical rate differ, which adds a simple source of 873 systematic error, on top of randomness error reported by integrator. 874 Otherwise the reported stdev of critical rate estimate is 875 unrealistically low. 877 Both functions are not only increasing, but also convex (meaning the 878 rate of increase is also increasing). 880 As Primitive Function to any positive function is an increasing 881 function, and Primitive Function to any increasing function is convex 882 function; both fitting functions were constructed as double Primitive 883 Function to a positive function (even though the intermediate 884 increasing function is easier to describe). 886 As not any function is integrable, some more realistic functions 887 (especially with respect to behavior at very small offered loads) are 888 not easily available. 890 Both fitting functions have a "central point" and a "spread", varied 891 by simply shifting and scaling (in x-axis, the offered load 892 direction) the function to be doubly integrated. Scaling in y-axis 893 (the loss rate direction) is fixed by the requirement of transfer 894 rate staying nearly constant in very high offered loads. 896 In both fitting functions (as they are a double Primitive Function to 897 a symmetric function), the "central point" turns out to be equal to 898 the aforementioned limiting transfer rate, so the fitting function 899 parameter is named "mrr", the same quantity our Maximum Receive Rate 900 tests are designed to measure. 902 Both fitting functions return logarithm of loss rate, to avoid 903 rounding errors and underflows. Parameters and offered load are not 904 given as logarithms, as they are not expected to be extreme, and the 905 formulas are simpler that way. 907 Both fitting functions have several mathematically equivalent 908 formulas, each can lead to an overflow or underflow in different 909 places. Overflows can be eliminated by using different exact 910 formulas for different argument ranges. Underflows can be avoided by 911 using approximate formulas in affected argument ranges, such ranges 912 have their own formulas to compute. At the end, both fitting 913 function implementations contain multiple "if" branches, 914 discontinuities are a possibility at range boundaries. 916 Offered load for next trial measurement is the average of critical 917 rate estimate. During each measurement, two estimates are computed, 918 even though only one (in alternating order) is used for next offered 919 load. 921 5.3.1. Stretch Function 923 The original function (before applying logarithm) is Primitive 924 Function to Logistic Function. The name "stretch" is used for 925 related a function in context of neural networks with sigmoid 926 activation function. 928 Formula for stretch function: loss rate (r) computed from offered 929 load (b), mrr parameter (m) and spread parameter (a): 931 r = a (Log(E^(b/a) + E^(m/a)) - Log(1 + E^(m/a))) 933 5.3.2. Erf Function 935 The original function is double Primitive Function to Gaussian 936 Function. The name "erf" comes from error function, the first 937 primitive to Gaussian. 939 Formula for erf function: loss rate (r) computed from offered load 940 (b), mrr parameter (m) and spread parameter (a): 942 r = (b + (a (E^(-((b - m)^2/a^2)) - E^(-(m^2/a^2))))/Sqrt(Pi) + (b - 943 m) Erf((b - m)/a) - m Erf(m/a))/2 945 5.4. Prior Distributions 947 The numeric integrator expects all the parameters to be distributed 948 (independently and) uniformly on an interval (-1, 1). 950 As both "mrr" and "spread" parameters are positive and not not 951 dimensionless, a transformation is needed. Dimentionality is 952 inherited from max_rate value. 954 The "mrr" parameter follows a Lomax Distribution with alpha equal to 955 one, but shifted so that mrr is always greater than 1 packet per 956 second. 958 The "stretch" parameter is generated simply as the "mrr" value raised 959 to a random power between zero and one; thus it follows a Reciprocal 960 Distribution. 962 5.5. Integrator 964 After few measurements, the posterior distribution of fitting 965 function arguments gets quite concentrated into a small area. The 966 integrator is using Monte Carlo with Importance Sampling where the 967 biased distribution is Bivariate Gaussian distribution, with 968 deliberately larger variance. If the generated sample falls outside 969 (-1, 1) interval, another sample is generated. 971 The the center and the covariance matrix for the biased distribution 972 is based on the first and second moments of samples seen so far 973 (within the computation), with the following additional features 974 designed to avoid hyper-focused distributions. 976 Each computation starts with the biased distribution inherited from 977 the previous computation (zero point and unit covariance matrix is 978 used in the first computation), but the overal weight of the data is 979 set to the weight of the first sample of the computation. Also, the 980 center is set to the first sample point. When additional samples 981 come, their weight (including the importance correction) is compared 982 to the weight of data seen so far (within the computation). If the 983 new sample is more than one e-fold more impactful, both weight values 984 (for data so far and for the new sample) are set to (geometric) 985 average if the two weights. Finally, the actual sample generator 986 uses covariance matrix scaled up by a configurable factor (8.0 by 987 default). 989 This combination showed the best behavior, as the integrator usually 990 follows two phases. First phase (where inherited biased distribution 991 or single big sasmples are dominating) is mainly important for 992 locating the new area the posterior distribution is concentrated at. 994 The second phase (dominated by whole sample population) is actually 995 relevant for the critical rate estimation. 997 6. IANA Considerations 999 .. 1001 7. Security Considerations 1003 .. 1005 8. Acknowledgements 1007 .. 1009 9. References 1011 9.1. Normative References 1013 [RFC2544] Bradner, S. and J. McQuaid, "Benchmarking Methodology for 1014 Network Interconnect Devices", RFC 2544, 1015 DOI 10.17487/RFC2544, March 1999, 1016 . 1018 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 1019 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 1020 May 2017, . 1022 9.2. Informative References 1024 [draft-vpolak-mkonstan-bmwg-mlrsearch] 1025 "Multiple Loss Ratio Search for Packet Throughput 1026 (MLRsearch)", November 2018, . 1029 Authors' Addresses 1031 Maciek Konstantynowicz (editor) 1032 Cisco Systems 1034 Email: mkonstan@cisco.com 1036 Vratko Polak (editor) 1037 Cisco Systems 1039 Email: vrpolak@cisco.com