Trending: Partially remove 3n-hsw
[csit.git] / docs / ietf / draft-vpolak-bmwg-plrsearch-03.md
1 ---
2 title: Probabilistic Loss Ratio Search for Packet Throughput (PLRsearch)
3 # abbrev: PLRsearch
4 docname: draft-vpolak-bmwg-plrsearch-03
5 date: 2020-03-06
6
7 ipr: trust200902
8 area: ops
9 wg: Benchmarking Working Group
10 kw: Internet-Draft
11 cat: info
12
13 coding: us-ascii
14 pi:    # can use array (if all yes) or hash here
15 #  - toc
16 #  - sortrefs
17 #  - symrefs
18   toc: yes
19   sortrefs:   # defaults to yes
20   symrefs: yes
21
22 author:
23       -
24         ins: M. Konstantynowicz
25         name: Maciek Konstantynowicz
26         org: Cisco Systems
27         role: editor
28         email: mkonstan@cisco.com
29       -
30         ins: V. Polak
31         name: Vratko Polak
32         org: Cisco Systems
33         role: editor
34         email: vrpolak@cisco.com
35
36 normative:
37   RFC2544:
38   RFC8174:
39
40 informative:
41
42   FDio-CSIT-PLRsearch:
43     target: https://docs.fd.io/csit/rls2001/report/introduction/methodology_data_plane_throughput/methodology_plrsearch.html
44     title: "FD.io CSIT Test Methodology - PLRsearch"
45     date: 2020-02
46
47   draft-vpolak-mkonstan-bmwg-mlrsearch:
48     target: https://tools.ietf.org/html/draft-vpolak-mkonstan-bmwg-mlrsearch
49     title: "Multiple Loss Ratio Search for Packet Throughput (MLRsearch)"
50     date: 2020-02
51
52 --- abstract
53
54 This document addresses challenges while applying methodologies
55 described in [RFC2544] to benchmarking software based NFV (Network
56 Function Virtualization) data planes over an extended period of time,
57 sometimes referred to as "soak testing". Packet throughput search
58 approach proposed by this document assumes that system under test is
59 probabilistic in nature, and not deterministic.
60
61 --- middle
62
63 # Motivation
64
65 Network providers are interested in throughput a networking system can
66 sustain.
67
68 [RFC2544] assumes loss ratio is given by a deterministic function of
69 offered load. But NFV software systems are not deterministic enough.
70 This makes deterministic algorithms (such as Binary Search per [RFC2544]
71 and [draft-vpolak-mkonstan-bmwg-mlrsearch] with single trial) to return
72 results, which when repeated show relatively high standard deviation,
73 thus making it harder to tell what "the throughput" actually is.
74
75 We need another algorithm, which takes this indeterminism into account.
76
77 # Relation To RFC2544
78
79 The aim of this document is to become an extension of [RFC2544] suitable
80 for benchmarking networking setups such as software based NFV systems.
81
82 # Terms And Assumptions
83
84 Due to the indeterministic nature of certain NFV systems that are the
85 targetted by PLRsearch algorithm, existing network benchmarking terms
86 are explicated and a number of new terms and assumptions are introduced.
87
88 ## Device Under Test
89
90 In software networking, "device" denotes a specific piece of software
91 tasked with packet processing. Such device is surrounded with other
92 software components (such as operating system kernel). It is not
93 possible to run devices without also running the other components, and
94 hardware resources are shared between both.
95
96 For purposes of testing, the whole set of hardware and software
97 components is called "system under test" (SUT). As SUT is the part of
98 the whole test setup performance of which can be measured by [RFC2544]
99 methods, this document uses SUT instead of [RFC2544] DUT.
100
101 Device under test (DUT) can be re-introduced when analysing test results
102 using whitebox techniques, but that is outside the scope of this document.
103
104 ## System Under Test
105
106 System under test (SUT) is a part of the whole test setup whose
107 performance is to be benchmarked. The complete methodology contains
108 other parts, whose performance is either already established, or not
109 affecting the benchmarking result.
110
111 ## SUT Configuration
112
113 Usually, system under test allows different configurations, affecting
114 its performance. The rest of this document assumes a single
115 configuration has been chosen.
116
117 ## SUT Setup
118
119 Similarly to [RFC2544], it is assumed that the system under test has
120 been updated with all the packet forwarding information it needs, before
121 the trial measurements (see below) start.
122
123 ## Network Traffic
124
125 Network traffic is a type of interaction between system under test and
126 the rest of the system (traffic generator), used to gather information
127 about the system under test performance. PLRsearch is applicable only to
128 areas where network traffic consists of packets.
129
130 ## Packet
131
132 Unit of interaction between traffic generator and the system under test.
133 Term "packet" is used also as an abstraction of Ethernet frames.
134
135 ### Packet Offered
136
137 Packet can be offered, which means it is sent from traffic generator
138 to the system under test.
139
140 Each offered packet is assumed to become received or lost in a short
141 time.
142
143 ### Packet Received
144
145 Packet can be received, which means the traffic generator verifies it
146 has been processed. Typically, when it is succesfully sent from the
147 system under test to traffic generator.
148
149 It is assumed that each received packet has been caused by an offered
150 packet, so the number of packets received cannot be larger than the
151 number of packets offered.
152
153 ### Packet Lost
154
155 Packet can be lost, which means sent but not received in a timely
156 manner.
157
158 It is assumed that each lost packet has been caused by an offered
159 packet, so the number of packets lost cannot be larger than the number
160 of packets offered.
161
162 Usually, the number of packets lost is computed as the number of packets
163 offered, minus the number of packets received.
164
165 ###  Other Packets
166
167 PLRsearch is not considering other packet behaviors known from
168 networking (duplicated, reordered, greatly delayed), assuming the test
169 specification reclassifies those behaviors to fit into the first three
170 categories.
171
172 ## Traffic Profile
173
174 Usually, the performance of the system under test depends on a "type" of
175 a particular packet (for example size), and "composition" if the network
176 traffic consists of a mixture of different packet types.
177
178 Also, some systems under test contain multiple "ports" packets can be
179 offered to and received from.
180
181 All such qualities together (but not including properties of trial
182 measurements) are called traffic profile.
183
184 Similarly to system under test configuration, this document assumes only
185 one traffic profile has been chosen for a particular test.
186
187 ##  Traffic Generator
188
189 Traffic generator is the part of the whole test setup, distinct from the
190 system under test, responsible both for offering packets in a highly
191 predictable manner (so the number of packets offered is known), and for
192 counting received packets in a precise enough way (to distinguish lost
193 packets from tolerably delayed packets).
194
195 Traffic generator must offer only packets compatible with the traffic
196 profile, and only count similarly compatible packets as received.
197
198 Criteria defining which received packets are compatible are left
199 for test specification to decide.
200
201 ## Offered Load
202
203 Offered load is an aggregate rate (measured in packets per second) of
204 network traffic offered to the system under test, the rate is kept
205 constant for the duration of trial measurement.
206
207 ## Trial Measurement
208
209 Trial measurement is a process of stressing (previously setup) system
210 under test by offering traffic of a particular offered load, for a
211 particular duration.
212
213 After that, the system has a short time to become idle, while the
214 traffic generator decides how many packets were lost.
215
216 After that, another trial measurement (possibly with different offered
217 load and duration) can be immediately performed. Traffic generator
218 should ignore received packets caused by packets offered in previous
219 trial measurements.
220
221 ## Trial Duration
222
223 Duration for which the traffic generator was offering packets at
224 constant offered load.
225
226 In theory, care has to be taken to ensure the offered load and trial
227 duration predict integer number of packets to offer, and that the
228 traffic generator really sends appropriate number of packets within
229 precisely enough timed duration. In practice, such consideration do not
230 change PLRsearch result in any significant way.
231
232 ## Packet Loss
233
234 Packet loss is any quantity describing a result of trial measurement.
235
236 It can be loss count, loss rate or loss ratio. Packet loss is zero (or
237 non-zero) if either of the three quantities are zero (or non-zero,
238 respecively).
239
240 ### Loss Count
241
242 Number of packets lost (or delayed too much) at a trial measurement by
243 the system under test as determined by packet generator. Measured in
244 packets.
245
246 ### Loss Rate
247
248 Loss rate is computed as loss count divided by trial duration. Measured
249 in packets per second.
250
251 ### Loss Ratio
252
253 Loss ratio is computed as loss count divided by number of packets
254 offered. Measured as a real (in practice rational) number between zero
255 or one (including).
256
257 ## Trial Order Independent System
258
259 Trial order independent system is a system under test, proven (or just
260 assumed) to produce trial measurement results that display trial order
261 independence.
262
263 That means when a pair of consequent trial measurements are performed,
264 the probability to observe a pair of specific results is the same, as
265 the probability to observe the reversed pair of results whe performing
266 the reversed pair of consequent measurements.
267
268 PLRsearch assumes the system under test is trial order independent.
269
270 In practice, most system under test are not entirely trial order
271 independent, but it is not easy to devise an algorithm taking that into
272 account.
273
274 ## Trial Measurement Result Distribution
275
276 When a trial order independent system is subjected to repeated trial
277 measurements of constant duration and offered load, Law of Large Numbers
278 implies the observed loss count frequencies will converge to a specific
279 probability distribution over possible loss counts.
280
281 This probability distribution is called trial measurement result
282 distribution, and it depends on all properties fixed when defining it.
283 That includes the system under test, its chosen configuration, the
284 chosen traffic profile, the offered load and the trial duration.
285
286 As the system is trial order independent, trial measurement result
287 distribution does not depend on results of few initial trial
288 measurements, of any offered load or (finite) duration.
289
290 ## Average Loss Ratio
291
292 Probability distribution over some (finite) set of states enables
293 computation of probability-weighted average of any quantity evaluated on
294 the states (called the expected value of the quantity).
295
296 Average loss ratio is simply the expected value of loss ratio for a
297 given trial measurement result distribution.
298
299 ## Duration Independent System
300
301 Duration independent system is a trial order independent system, whose
302 trial measurement result distribution is proven (or just assumed) to
303 display practical independence from trial duration. See definition of
304 trial duration for discussion on practical versus theoretical.
305
306 The only requirement is for average loss ratio to be independent of
307 trial duration.
308
309 In theory, that would necessitate each trial measurement result
310 distribution to be a binomial distribution. In practice, more
311 distributions are allowed.
312
313 PLRsearch assumes the system under test is duration independent, at
314 least for trial durations typically chosen for trial measurements
315 initiated by PLRsearch.
316
317 ## Load Regions
318
319 For a duration independent system, trial measurement result distribution
320 depends only on offered load.
321
322 It is convenient to name some areas of offered load space by possible
323 trial results.
324
325 ### Zero Loss Region
326
327 A particular offered load value is said to belong to zero loss region,
328 if the probability of seeing non-zero loss trial measurement result is
329 exactly zero, or at least practically indistinguishable from zero.
330
331 ### Guaranteed Loss Region
332
333 A particular offered load value is said to belong to guaranteed loss
334 region, if the probability of seeing zero loss trial measurement result
335 (for non-negligible count of packets offered) is exactly zero, or at
336 least practically indistinguishable from zero.
337
338 ### Non-Deterministic Region
339
340 A particular offered load value is said to belong to non-deterministic
341 region, if the probability of seeing zero loss trial measurement result
342 (for non-negligible count of packets offered) is practically
343 distinguishable from both zero and one.
344
345 ### Normal Region Ordering
346
347 Although theoretically the three regions can be arbitrary sets, this
348 document assumes they are intervals, where zero loss region contains
349 values smaller than non-deterministic region, which in turn contains
350 values smaller than guaranteed loss region.
351
352 ## Deterministic System
353
354 A hypothetical duration independent system with normal region ordering,
355 whose non-deterministic region is extremely narrow (only present due to
356 "practical distinguishibility" and cases when the expected number of
357 packets offered is not and integer).
358
359 A duration independent system which is not deterministic is called non-
360 deterministic system.
361
362 ## Througphput
363
364 Throughput is the highest offered load provably causing zero packet loss
365 for trial measurements of duration at least 60 seconds.
366
367 For duration independent systems with normal region ordering, the
368 throughput is the highest value within the zero loss region.
369
370 ## Deterministic Search
371
372 Any algorithm that assumes each measurement is a proof of the offered
373 load belonging to zero loss region (or not) is called deterministic
374 search.
375
376 This definition includes algorithms based on "composite measurements"
377 which perform multiple trial measurements, somehow re-classifying
378 results pointing at non-deterministic region.
379
380 Binary Search is an example of deterministic search.
381
382 Single run of a deterministic search launched against a deterministic
383 system is guaranteed to find the throughput with any prescribed
384 precision (not better than non-deterministic region width).
385
386 Multiple runs of a deterministic search launched against a non-
387 deterministic system can return varied results within non-deterministic
388 region. The exact distribution of deterministic search results depends
389 on the algorithm used.
390
391 ## Probabilistic Search
392
393 Any algorithm which performs probabilistic computations based on
394 observed results of trial measurements, and which does not assume that
395 non-deterministic region is practically absent, is called probabilistic
396 search.
397
398 A probabilistic search algorithm, which would assume that non-
399 deterministic region is practically absent, does not really need to
400 perform probabilistic computations, so it would become a deterministic
401 search.
402
403 While probabilistic search for estimating throughput is possible, it
404 would need a careful model for boundary between zero loss region and
405 non-deterministic region, and it would need a lot of measurements of
406 almost surely zero loss to reach good precision.
407
408 ## Loss Ratio Function
409
410 For any duration independent system, the average loss ratio depends only
411 on offered load (for a particular test setup).
412
413 Loss ratio function is the name used for the function mapping offered
414 load to average loss ratio.
415
416 This function is initially unknown.
417
418 ## Target Loss Ratio
419
420 Input parameter of PLRsearch. The average loss ratio the output of
421 PLRsearch aims to achieve.
422
423 ## Critical Load
424
425 Aggregate rate of network traffic, which would lead to average loss
426 ratio exactly matching target loss ratio, if used as the offered load
427 for infinite many trial measurement.
428
429 ## Critical Load Estimate
430
431 Any quantitative description of the possible critical load PLRsearch is
432 able to give after observing finite amount of trial measurements.
433
434 ## Fitting Function
435
436 Any function PLRsearch uses internally instead of the unknown loss ratio
437 function. Typically chosen from small set of formulas (shapes) with few
438 parameters to tweak.
439
440 ## Shape of Fitting Function
441
442 Any formula with few undetermined parameters.
443
444 ## Parameter Space
445
446 A subset of Real Coordinate Space. A point of parameter space is a
447 vector of real numbers. Fitting function is defined by shape (a formula
448 with parameters) and point of parameter space (specifying values for the
449 parameters).
450
451 # Abstract Algorithm
452
453 ## High level description
454
455 PLRsearch accepts some input arguments, then iteratively performs trial
456 measurements at varying offered loads (and durations), and returns some
457 estimates of critical load.
458
459 PLRsearch input arguments form three groups.
460
461 First group has a single argument: measurer. This is a callback
462 (function) accepting offered load and duration, and returning the
463 measured loss count.
464
465 Second group consists of load related arguments required for measurer to
466 work correctly, typically minimal and maximal load to offer. Also,
467 target loss ratio (if not hardcoded) is a required argument.
468
469 Third group consists of time related arguments. Typically the duration
470 for the first trial measurement, duration increment per subsequent trial
471 measurement, and total time for search. Some PLRsearch implementation may
472 use estimation accuracy parameters as an exit condition instead of total
473 search time.
474
475 The returned quantities should describe the final (or best) estimate of
476 critical load. Implementers can chose any description that suits their
477 users, typically it is average and standard deviation, or lower and
478 upper boundary.
479
480 ## Main Ideas
481
482 The search tries to perform measurements at offered load close to the
483 critical load, because measurement results at offered loads far from the
484 critical load give less information on precise location of the critical
485 load. As virtually every trial measurement result alters the estimate of
486 the critical load, offered loads vary as they approach the critical
487 load.
488
489 The only quantity of trial measurement result affecting the computation
490 is loss count. No latency (or other information) is taken into account.
491
492 PLRsearch uses Bayesian Inference, computed using numerical integration,
493 which takes long time to get reliable enough results. Therefore it takes
494 some time before the most recent measurement result starts affecting
495 subsequent offered loads and critical rate estimates.
496
497 During the search, PLRsearch spawns few processes that perform numerical
498 computations, the main process is calling the measurer to perform trial
499 measurements, without any significant delays between them. The durations
500 of the trial measurements are increasing linearly, as higher number of
501 trial measurement results take longer to process.
502
503 ### Trial Durations
504
505 [RFC2544] motivates the usage of at least 60 second duration by the idea
506 of the system under test slowly running out of resources (such as memory
507 buffers).
508
509 Practical results when measuring NFV software systems show that relative
510 change of trial duration has negligible effects on average loss ratio,
511 compared to relative change in offered load.
512
513 While the standard deviation of loss ratio usually shows some effects of
514 trial duration, they are hard to model. So PLRsearch assumes SUT
515 is duration independent, and chooses trial durations only based on
516 numeric integration requirements.
517
518 ### Target Loss Ratio
519
520 (TODO: Link to why we think 1e-7 is acceptable loss ratio.)
521
522 ## PLRsearch Building Blocks
523
524 Here we define notions used by PLRsearch which are not applicable to
525 other search methods, nor probabilistic systems under test in general.
526
527 ### Bayesian Inference
528
529 PLRsearch uses a fixed set of fitting function shapes,
530 and uses Bayesian inference to track posterior distribution
531 on each fitting function parameter space.
532
533 Specifically, the few parameters describing a fitting function
534 become the model space. Given a prior over the model space, and trial
535 duration results, a posterior distribution is computed, together
536 with quantities describing the critical load estimate.
537
538 Likelihood of a particular loss count is computed using Poisson distribution
539 of average loss rate given by the fitting function (at specific point of
540 parameter space).
541
542 Side note: Binomial Distribution is a better fit compared to Poisson
543 distribution (acknowledging that the number of packets lost cannot be
544 higher than the number of packets offered), but the difference tends to
545 be relevant only in high loss region. Using Poisson distribution lowers
546 the impact of measurements in high loss region, thus helping the
547 algorithm to converge towards critical load faster.
548
549 ### Iterative Search
550
551 The idea PLRsearch is to iterate trial measurements, using Bayesian
552 inference to compute both the current estimate of the critical load and
553 the next offered load to measure at.
554
555 The required numerical computations are done in parallel with the trial
556 measurements.
557
558 This means the result of measurement "n" comes as an (additional) input
559 to the computation running in parallel with measurement "n+1", and the
560 outputs of the computation are used for determining the offered load for
561 measurement "n+2".
562
563 Other schemes are possible, aimed to increase the number of measurements
564 (by decreasing their duration), which would have even higher number of
565 measurements run before a result of a measurement affects offered load.
566
567 ### Fitting Functions
568
569 To make the space of possible loss ratio functions more tractable
570 the algorithm uses only few fitting function shapes for its predicitons.
571 As the search algorithm needs to evaluate the function also far away
572 from the critical load, the fitting function have to be reasonably behaved
573 for every positive offered load, specifically cannot cannot predict
574 non-positive packet loss ratio.
575
576 ### Measurement Impact
577
578 Results from trials far from the critical load are likely to affect
579 the critical load estimate negatively, as the fitting functions do not
580 need to be good approximations there. This is true mainly for guaranteed loss
581 region, as in zero loss region even badly behaved fitting function
582 predicts loss count to be "almost zero", so seeing a measurement
583 confirming the loss has been zero indeed has small impact.
584
585 Discarding some results, or "suppressing" their impact with ad-hoc
586 methods (other than using Poisson distribution instead of binomial) is
587 not used, as such methods tend to make the overall search unstable. We
588 rely on most of measurements being done (eventually) near the critical load,
589 and overweighting far-off measurements (eventually) for well-behaved
590 fitting functions.
591
592 ### Fitting Function Coefficients Distribution
593
594 To accomodate systems with different behaviours, a fitting function is
595 expected to have few numeric parameters affecting its shape (mainly
596 affecting the linear approximation in the critical region).
597
598 The general search algorithm can use whatever increasing fitting
599 function, some specific functions are described later.
600
601 It is up to implementer to chose a fitting function and prior
602 distribution of its parameters. The rest of this document assumes each
603 parameter is independently and uniformly distributed over a common
604 interval. Implementers are to add non-linear transformations into their
605 fitting functions if their prior is different.
606
607 ### Exit Condition
608
609 Exit condition for the search is either the standard deviation of the
610 critical load estimate becoming small enough (or similar), or overal
611 search time becoming long enough.
612
613 The algorithm should report both average and standard deviation for its
614 critical load posterior.
615
616 ### Integration
617
618 The posterior distributions for fitting function parameters are not be
619 integrable in general.
620
621 The search algorithm utilises the fact that trial measurement takes some
622 time, so this time can be used for numeric integration (using suitable
623 method, such as Monte Carlo) to achieve sufficient precision.
624
625 ### Optimizations
626
627 After enough trials, the posterior distribution will be concentrated in
628 a narrow area of the parameter space. The integration method should take
629 advantage of that.
630
631 Even in the concentrated area, the likelihood can be quite small, so the
632 integration algorithm should avoid underflow errors by some means,
633 for example by tracking the logarithm of the likelihood.
634
635 ### Offered Load Selection
636
637 The simplest rule is to set offered load for next trial measurememnt
638 equal to the current average (both over posterio and over
639 fitting function shapes) of the critical load estimate.
640
641 Contrary to critical load estimate computation, heuristic algorithms
642 affecting offered load selection do not introduce instability,
643 and can help with convergence speed.
644
645 ### Trend Analysis
646
647 If the reported averages follow a trend (maybe without reaching equilibrium),
648 average and standard deviation COULD refer to the equilibrium estimates
649 based on the trend, not to immediate posterior values.
650
651 But such post-processing is discouraged, unless a clear reason
652 for the trend is known. Frequently, presence of such a trend is a sign
653 of some of PLRsearch assumption being violated (usually trial order
654 independence or duration independence).
655
656 It is RECOMMENDED to report any trend quantification together with
657 direct critical load estimate, so users can draw their own conclusion.
658 Alternatively, trend analysis may be a part of exit conditions,
659 requiring longer searches for systems displaying trends.
660
661 # Known Implementations
662
663 The only known working implementation of PLRsearch is in Linux
664 Foundation FD.io CSIT open-source project [FDio-CSIT-PLRsearch].
665
666 ## FD.io CSIT Implementation Specifics
667
668 The search receives min_rate and max_rate values, to avoid measurements
669 at offered loads not supporeted by the traffic generator.
670
671 The implemented tests cases use bidirectional traffic. The algorithm
672 stores each rate as bidirectional rate (internally, the algorithm is
673 agnostic to flows and directions, it only cares about overall counts of
674 packets sent and packets lost), but debug output from traffic generator
675 lists unidirectional values.
676
677 ### Measurement Delay
678
679 In a sample implemenation in FD.io CSIT project, there is roughly 0.5
680 second delay between trials due to restrictons imposed by packet traffic
681 generator in use (T-Rex).
682
683 As measurements results come in, posterior distribution computation
684 takes more time (per sample), although there is a considerable constant
685 part (mostly for inverting the fitting functions).
686
687 Also, the integrator needs a fair amount of samples to reach the region
688 the posterior distribution is concentrated at.
689
690 And of course, speed of the integrator depends on computing power of the
691 CPUs the algorithm is able to use.
692
693 All those timing related effects are addressed by arithmetically
694 increasing trial durations with configurable coefficients (currently 5.1
695 seconds for the first trial, each subsequent trial being 0.1 second
696 longer).
697
698 ### Rounding Errors and Underflows
699
700 In order to avoid them, the current implementation tracks natural
701 logarithm (instead of the original quantity) for any quantity which is
702 never negative. Logarithm of zero is minus infinity (not supported by
703 Python), so special value "None" is used instead. Specific functions for
704 frequent operations (such as "logarithm of sum of exponentials") are
705 defined to handle None correctly.
706
707 ### Fitting Functions
708
709 Current implementation uses two fitting functions. In general, their
710 estimates for critical rate differ, which adds a simple source of
711 systematic error, on top of posterior dispersion reported by integrator.
712 Otherwise the reported stdev of critical rate estimate is
713 unrealistically low.
714
715 Both functions are not only increasing, but also convex (meaning the
716 rate of increase is also increasing).
717
718 As Primitive Function to any positive function is an increasing
719 function, and Primitive Function to any increasing function is convex
720 function; both fitting functions were constructed as double Primitive
721 Function to a positive function (even though the intermediate increasing
722 function is easier to describe).
723
724 As not any function is integrable, some more realistic functions
725 (especially with respect to behavior at very small offered loads) are
726 not easily available.
727
728 Both fitting functions have a "central point" and a "spread", varied by
729 simply shifting and scaling (in x-axis, the offered load direction) the
730 function to be doubly integrated. Scaling in y-axis (the loss rate
731 direction) is fixed by the requirement of transfer rate staying nearly
732 constant in very high offered loads.
733
734 In both fitting functions (as they are a double Primitive Function to a
735 symmetric function), the "central point" turns out to be equal to the
736 aforementioned limiting transfer rate, so the fitting function parameter
737 is named "mrr", the same quantity CSIT Maximum Receive Rate tests are
738 designed to measure.
739
740 Both fitting functions return logarithm of loss rate, to avoid rounding
741 errors and underflows. Parameters and offered load are not given as
742 logarithms, as they are not expected to be extreme, and the formulas are
743 simpler that way.
744
745 Both fitting functions have several mathematically equivalent formulas,
746 each can lead to an overflow or underflow in different places. Overflows
747 can be eliminated by using different exact formulas for different
748 argument ranges. Underflows can be avoided by using approximate formulas
749 in affected argument ranges, such ranges have their own formulas to
750 compute. At the end, both fitting function implementations contain
751 multiple "if" branches, discontinuities are a possibility at range
752 boundaries.
753
754 #### Stretch Function
755
756 The original function (before applying logarithm) is Primitive Function
757 to Logistic Function. The name "stretch" is used for related a function
758 in context of neural networks with sigmoid activation function.
759
760 Formula for stretch fitting function: average loss rate (r) computed from
761 offered load (b), mrr parameter (m) and spread parameter (a),
762 given as InputForm of Wolfram language:
763
764     r = (a*(1 + E^(m/a))*Log[(E^(b/a) + E^(m/a))/(1 + E^(m/a))])/E^(m/a)
765
766 #### Erf Function
767
768 The original function is double Primitive Function to Gaussian Function.
769 The name "erf" comes from error function, the first primitive to
770 Gaussian.
771
772 Formula for erf fitting function: average loss rate (r) computed from
773 offered load (b), mrr parameter (m) and spread parameter (a),
774 given as InputForm of Wolfram language:
775
776     r = ((a*(E^(-((b - m)^2/a^2)) - E^(-(m^2/a^2))))/Sqrt[Pi] + m*Erfc[m/a]
777         + (b - m)*Erfc[(-b + m)/a])/(1 + Erf[m/a])
778
779 ### Prior Distributions
780
781 The numeric integrator expects all the parameters to be distributed
782 (independently and) uniformly on an interval (-1, 1).
783
784 As both "mrr" and "spread" parameters are positive and not
785 dimensionless, a transformation is needed. Dimentionality is inherited
786 from max_rate value.
787
788 The "mrr" parameter follows a Lomax Distribution with alpha equal to
789 one, but shifted so that mrr is always greater than 1 packet per second.
790
791 The "stretch" parameter is generated simply as the "mrr" value raised to
792 a random power between zero and one; thus it follows a Reciprocal
793 Distribution.
794
795 ### Integrator
796
797 After few measurements, the posterior distribution of fitting function
798 arguments gets quite concentrated into a small area. The integrator is
799 using Monte Carlo with Importance Sampling where the biased distribution
800 is Bivariate Gaussian distribution, with deliberately larger variance.
801 If the generated sample falls outside (-1, 1) interval, another sample
802 is generated.
803
804 The the center and the covariance matrix for the biased distribution is
805 based on the first and second moments of samples seen so far (within the
806 computation), with the following additional features designed to avoid
807 hyper-focused distributions.
808
809 Each computation starts with the biased distribution inherited from the
810 previous computation (zero point and unit covariance matrix is used in
811 the first computation), but the overal weight of the data is set to the
812 weight of the first sample of the computation. Also, the center is set
813 to the first sample point. When additional samples come, their weight
814 (including the importance correction) is compared to the weight of data
815 seen so far (within the computation). If the new sample is more than one
816 e-fold more impactful, both weight values (for data so far and for the
817 new sample) are set to (geometric) average if the two weights. Finally,
818 the actual sample generator uses covariance matrix scaled up by a
819 configurable factor (8.0 by default).
820
821 This combination showed the best behavior, as the integrator usually
822 follows two phases. First phase (where inherited biased distribution or
823 single big sasmples are dominating) is mainly important for locating the
824 new area the posterior distribution is concentrated at. The second phase
825 (dominated by whole sample population) is actually relevant for the
826 critical rate estimation.
827
828 ### Offered Load Selection
829
830 First two measurements are hardcoded to happen at the middle of rate interval
831 and at max_rate. Next two measurements follow MRR-like logic,
832 offered load is decreased so that it would reach target loss ratio
833 if offered load decrease lead to equal decrease of loss rate.
834
835 Basis for offered load for next trial measurements is the integrated average
836 of current critical rate estimate, averaged over fitting function.
837
838 There is one workaround implemented, aimed at reducing the number of consequent
839 zero loss measurements. The workaround first stores every measurement
840 result which loss ratio was the targed loss ratio or higher.
841 Sorted list (called lossy loads) of such results is maintained.
842
843 When a sequence of one or more zero loss measurement results is encountered,
844 a smallest of lossy loads is drained from the list.
845 If the estimate average is smaller than the drained value,
846 a weighted average of this estimate and the drained value is used
847 as the next offered load. The weight of the drained value doubles
848 with each additional consecutive zero loss results.
849
850 This behavior helps the algorithm with convergence speed,
851 as it does not need so many zero loss result to get near critical load.
852 Using the smallest (not drained yet) of lossy loads makes it sure
853 the new offered load is unlikely to result in big loss region.
854 Draining even if the estimate is large enough helps to discard
855 early measurements when loss hapened at too low offered load.
856 Current implementation adds 4 copies of lossy loads and drains 3 of them,
857 which leads to fairly stable behavior even for somewhat inconsistent SUTs.
858
859 # IANA Considerations
860
861 No requests of IANA.
862
863 # Security Considerations
864
865 Benchmarking activities as described in this memo are limited to
866 technology characterization of a DUT/SUT using controlled stimuli in a
867 laboratory environment, with dedicated address space and the constraints
868 specified in the sections above.
869
870 The benchmarking network topology will be an independent test setup and
871 MUST NOT be connected to devices that may forward the test traffic into
872 a production network or misroute traffic to the test management network.
873
874 Further, benchmarking is performed on a "black-box" basis, relying
875 solely on measurements observable external to the DUT/SUT.
876
877 Special capabilities SHOULD NOT exist in the DUT/SUT specifically for
878 benchmarking purposes.  Any implications for network security arising
879 from the DUT/SUT SHOULD be identical in the lab and in production
880 networks.
881
882 # Acknowledgements
883
884 To be added.
885
886 --- back