aboutsummaryrefslogtreecommitdiffstats
path: root/docs/ietf/draft-vpolak-bmwg-plrsearch-02.md
blob: dc0313575363425bf31de25e8ab69e7423d833a1 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
---
title: Probabilistic Loss Ratio Search for Packet Throughput (PLRsearch)
# abbrev: PLRsearch
docname: draft-vpolak-bmwg-plrsearch-01
date: 2019-xx-xx

ipr: trust200902
area: ops
wg: Benchmarking Working Group
kw: Internet-Draft
cat: info

coding: us-ascii
pi:    # can use array (if all yes) or hash here
#  - toc
#  - sortrefs
#  - symrefs
  toc: yes
  sortrefs:   # defaults to yes
  symrefs: yes

author:
      -
        ins: M. Konstantynowicz
        name: Maciek Konstantynowicz
        org: Cisco Systems
        role: editor
        email: mkonstan@cisco.com
      -
        ins: V. Polak
        name: Vratko Polak
        org: Cisco Systems
        role: editor
        email: vrpolak@cisco.com

normative:
  RFC2544:
  RFC8174:

informative:
  draft-vpolak-mkonstan-bmwg-mlrsearch:
    target: https://tools.ietf.org/html/draft-vpolak-mkonstan-bmwg-mlrsearch-00
    title: "Multiple Loss Ratio Search for Packet Throughput (MLRsearch)"
    date: 2018-11

--- abstract

This document addresses challenges while applying methodologies
described in [RFC2544] to benchmarking software based NFV (Network
Function Virtualization) data planes over an extended period of time,
sometimes referred to as "soak testing". Packet throughput search
approach proposed by this document assumes that system under test is
probabilistic in nature, and not deterministic.

--- middle

# Motivation

Network providers are interested in throughput a system can sustain.

[RFC2544] assumes loss ratio is given by a deterministic function of
offered load. But NFV software systems are not deterministic enough.
This makes deterministic algorithms (such as Binary Search per [RFC2544]
and [draft-vpolak-mkonstan-bmwg-mlrsearch] with single trial) to return
results, which when repeated show relatively high standard deviation,
thus making it harder to tell what "the throughput" actually is.

We need another algorithm, which takes this indeterminism into account.

# Relation To RFC2544

The aim of this document is to become an extension of [RFC2544] suitable
for benchmarking networking setups such as software based NFV systems.

# Terms And Assumptions

## Device Under Test

In software networking, "device" denotes a specific piece of software
tasked with packet processing. Such device is surrounded with other
software components (such as operating system kernel). It is not
possible to run devices without also running the other components, and
hardware resources are shared between both.

For purposes of testing, the whole set of hardware and software
components is called "system under test" (SUT). As SUT is the part of
the whole test setup performance of which can be measured by [RFC2544]
methods, this document uses SUT instead of [RFC2544] DUT.

Device under test (DUT) can be re-introduced when analysing test results
using whitebox techniques, but this document sticks to blackbox testing.

## System Under Test

System under test (SUT) is a part of the whole test setup whose
performance is to be benchmarked. The complete methodology contains
other parts, whose performance is either already established, or not
affecting the benchmarking result.

## SUT Configuration

Usually, system under test allows different configurations, affecting
its performance. The rest of this document assumes a single
configuration has been chosen.

## SUT Setup

Similarly to [RFC2544], it is assumed that the system under test has
been updated with all the packet forwarding information it needs, before
the trial measurements (see below) start.

## Network Traffic

Network traffic is a type of interaction between system under test and
the rest of the system (traffic generator), used to gather information
about the system under test performance. PLRsearch is applicable only to
areas where network traffic consists of packets.

## Packet

Unit of interaction between traffic generator and the system under test.
Term "packet" is used also as an abstractions of Ethernet frames.

### Packet Offered

Packet can be offered, which means it is sent from traffic generator
to the system under test.

Each offered packet is assumed to become received or lost in a short
time.

### Packet Received

Packet can be received, which means the traffic generator verifies it
has been processed. Typically, when it is succesfully sent from the
system under test to traffic generator.

It is assumed that each received packet has been caused by an offered
packet, so the number of packets received cannot be larger than the
number of packets offered.

### Packet Lost

Packet can be lost, which means sent but not received in a timely
manner.

It is assumed that each lost packet has been caused by an offered
packet, so the number of packets lost cannot be larger than the number
of packets offered.

Usually, the number of packets lost is computed as the number of packets
offered, minus the number of packets received.

###  Other Packets

PLRsearch is not considering other packet behaviors known from
networking (duplicated, reordered, greatly delayed), assuming the test
specification reclassifies those behaviors to fit into the first three
categories.

### Tasks As Packets

Ethernet frames are the prime example of packets, but other units are
possible.

For example, a task processing system can fit the description. Packet
offered can stand for task submitted, packet received for task processed
successfully, and packet lost for task aborted (or not processed
successfully for some other reason).

In networking context, such a task can be a route update.

## Traffic Profile

Usually, the performance of the system under test depends on a "type" of
a particular packet (for example size), and "composition" if the network
traffic consists of a mixture of different packet types.

Also, some systems under test contain multiple "ports" packets can be
offered to and received from.

All such qualities together (but not including properties of trial
measurements) are called traffic profile.

Similarly to system under test configuration, this document assumes only
one traffic profile has been chosen for a particular test.

##  Traffic Generator

Traffic generator is the part of the whole test setup, distinct from the
system under test, responsible both for offering packets in a highly
predictable manner (so the number of packets offered is known), and for
counting received packets in a precise enough way (to distinguish lost
packets from tolerably delayed packets).

Traffic generator must offer only packets compatible with the traffic
profile, and only count similarly compatible packets as received.

## Offered Load

Offered load is an aggregate rate (measured in packets per second) of
network traffic offered to the system under test, the rate is kept
constant for the duration of trial measurement.

## Trial Measurement

Trial measurement is a process of stressing (previously setup) system
under test by offering traffic of a particular offered load, for a
particular duration.

After that, the system has a short time to become idle, while the
traffic generator decides how many packets were lost.

After that, another trial measurement (possibly with different offered
load and duration) can be immediately performed. Traffic generator
should ignore received packets caused by packets offered in previous
trial measurements.

## Trial Duration

Duration for which the traffic generator was offering packets at
constant offered load.

In theory, care has to be taken to ensure the offered load and trial
duration predict integer number of packets to offer, and that the
traffic generator really sends appropriate number of packets within
precisely enough timed duration. In practice, such consideration do not
change PLRsearch result in any significant way.

## Packet Loss

Packet loss is any quantity describing a result of trial measurement.

It can be loss count, loss rate or loss ratio. Packet loss is zero (or
non-zero) if either of the three quantities are zero (or non-zero,
respecively).

### Loss Count

Number of packets lost (or delayed too much) at a trial measurement by
the system under test as determined by packet generator. Measured in
packets.

### Loss Rate

Loss rate is computed as loss count divided by trial duration. Measured
in packets per second.

### Loss Ratio

Loss ratio is computed as loss count divided by number of packets
offered. Measured as a real (in practice rational) number between zero
or one (including).

## Trial Order Independent System

Trial order independent system is a system under test, proven (or just
assumed) to produce trial measurement results that display trial order
independence.

That means when a pair of consequent trial measurements are performed,
the probability to observe a pair of specific results is the same, as
the probability to observe the reversed pair of results whe performing
the reversed pair of consequent measurements.

PLRsearch assumes the system under test is trial order independent.

In practice, most system under test are not entirely trial order
independent, but it is not easy to devise an algorithm taking that into
account.

## Trial Measurement Result Distribution

When a trial order independent system is subjected to repeated trial
measurements of constant offered load and duration, Law of Large Numbers
implies the observed loss count frequencies will converge to a specific
probability distribution over possible loss counts.

This probability distribution is called trial measurement result
distribution, and it depends on all properties fixed when defining it.
That includes the system under test, its chosen configuration, the
chosen traffic profile, the offered load and the trial duration.

As the system is trial order independent, trial measurement result
distribution does not depend on results of few initial trial
measurements, of any offered load or (finite) duration.

## Average Loss Ratio

Probability distribution over some (finite) set of states enables
computation of probability-weighted average of any quantity evaluated on
the states (called the expected value of the quantity).

Average loss ratio is simply the expected value of loss ratio for a
given trial measurement result distribution.

## Duration Independent System

Duration independent system is a trial order independent system, whose
trial measurement result distribution is proven (or just assumed) to
display practical independence from trial duration. See definition of
trial duration for discussion on practical versus theoretical.

The only requirement is for average loss ratio to be independent of
trial duration.

In theory, that would necessitate each trial measurement result
distribution to be a binomial distribution. In practice, more
distributions are allowed.

PLRsearch assumes the system under test is duration independent, at
least for trial durations typically chosen for trial measurements
initiated by PLRsearch.

## Load Regions

For a duration independent system, trial measurement result distribution
depends only on offered load.

It is convenient to name some areas of offered load space by possible
trial results.

### Zero Loss Region

A particular offered load value is said to belong to zero loss region,
if the probability of seeing non-zero loss trial measurement result is
exactly zero, or at least practically indistinguishable from zero.

### Guaranteed Loss Region

A particular offered load value is said to belong to guaranteed loss
region, if the probability of seeing zero loss trial measurement result
(for non-negligible count of packets offered) is exactly zero, or at
least practically indistinguishable from zero.

### Non-Deterministic Region

A particular offered load value is said to belong to non-deterministic
region, if the probability of seeing zero loss trial measurement result
(for non-negligible count of packets offered) practically
distinguishable from both zero and one.

### Normal Region Ordering

Although theoretically the three regions can be arbitrary sets, this
document assumes they are intervals, where zero loss region contains
values smaller than non-deterministic region, which in turn contains
values smaller than guaranteed loss region.

## Deterministic System

A hypothetical duration independent system with normal region ordering,
whose non-deterministic region is extremely narrow; only present due to
"practical distinguishibility" and cases when the expected number of
packets offered is not and integer.

A duration independent system which is not deterministic is called non-
deterministic system.

## Througphput

Throughput is the highest offered load provably causing zero packet loss
for trial measurements of duration at least 60 seconds.

For duration independent systems with normal region ordering, the
throughput is the highest value within the zero loss region.

## Deterministic Search

Any algorithm that assumes each measurement is a proof of the offered
load belonging to zero loss region (or not) is called deterministic
search.

This definition includes algorithms based on "composite measurements"
which perform multiple trial measurements, somehow re-classifying
results pointing at non-deterministic region.

Binary Search is an example of deterministic search.

Single run of a deterministic search launched against a deterministic
system is guaranteed to find the throughput with any prescribed
precision (not better than non-deterministic region width).

Multiple runs of a deterministic search launched against a non-
deterministic system can return varied results within non-deterministic
region. The exact distribution of deterministic search results depends
on the algorithm used.

## Probabilistic Search

Any algorithm which performs probabilistic computations based on
observed results of trial measurements, and which does not assume that
non-deterministic region is practically absent is called probabilistic
search.

A probabilistic search algorithm, which would assume that non-
deterministic region is practically absent, does not really need to
perform probabilistic computations, so it would become a deterministic
search.

While probabilistic search for estimating throughput is possible, it
would need a careful model for boundary between zero loss region and
non-deterministic region, and it would need a lot of measurements of
almost surely zero loss to reach good precision.

## Loss Ratio Function

For any duration independent system, the average loss ratio depends only
on offered load (for a particular test setup).

Loss ratio function is the name used for the function mapping offered
load to average loss ratio.

This function is initially unknown.

## Target Loss Ratio

Input parameter of PLRsearch. The average loss ratio the output of
PLRsearch aims to achieve.

## Critical Load

Aggregate rate of network traffic, which would lead to average loss
ratio exactly matching target loss ratio (when used as the offered load
for infinite many trial measurement).

## Critical Load Estimate

Any quantitative description of the possible critical load PLRsearch is
able to give after observing finite amount of trial measurements.

## Fitting Function

Any function PLRsearch uses internally instead of the unknown loss ratio
function. Typically chosen from small set of formulas (shapes) with few
parameters to tweak.

## Shape of Fitting Function

Any formula with few undetermined parameters.

## Parameter Space

A subset of Real Coordinate Space. A point of parameter space is a
vector of real numbers. Fitting function is defined by shape (a formula
with parameters) and point of parameter space (specifying values for the
parameters).

# Abstract Algorithm

## High level description

PLRsearch accepts some input arguments, then iteratively performs trial
measurements at varying offered loads (and durations), and returns some
estimates of critical load.

PLRsearch input arguments form three groups.

First group has a single argument: measurer. This is a callback
(function) accepting offered load and duration, and returning the
measured loss count.

Second group consists of load related arguments required for measurer to
work correctly, typically minimal and maximal load to offer. Also,
target loss ratio (if not hardcoded) is a required argument.

Third group consists of time related arguments. Typically the duration
for the first trial measurement, duration increment per subsequent trial
measurement and total time for search. Some PLRsearch implementation may
use estimation accuracy parameters as an exit condition instead of total
search time.

The returned quantities should describe the final (or best) estimate of
critical load. Implementers can chose any description that suits their
users, typically it is average and standard deviation, or lower and
upper boundary.

## Main Ideas

The search tries to perform measurements at offered load close to the
critical load, because measurement results at offered loads far from the
critical load give less information on precise location of the critical
load. As virtually every trial measurement result alters the estimate of
the critical load, offered loads vary as they approach the critical
load.

PLRsearch uses Bayesian Inference, computed using numerical integration,
which takes long time to get reliable enough results. Therefore it takes
some time before the most recent measurement result starts affecting
subsequent offered loads and critical rate estimates.

During the search, PLRsearch spawns few processes that perform numerical
computations, the main process is calling the measurer to perform trial
measurements, without any significant delays between them. The durations
of the trial measurements are increasing linearly, as higher number of
trial measurement results take longer to process.

## Probabilistic Notions

Before internals of PLRsearch are described, we need to define notions
valid for situations when loss ratio is not entirely determined by
offered load.

Some of the notions already incorporate assumptions the PLRsearch
algorithm applies.

### Loss Count Only

It is assumed that the traffic generator detects duplicate packets on
receive, and reports this as an error.

No latency (or other information) is taken into account.

### Independent Trials

PLRsearch still assumes the system under test can be subjected to trial
measurements. The loss count is no longer determined precisely, but it
is assumed that for every system under test, its configuration, traffic
type and trial duration, there is a probability distribution over
possible loss counts.

This implies trial measurements are probabilistic, but the distribution
is independent of possible previous trial measurements.

Independence from previous measurements is not guaranteed in the real
world. The previous measurements may improve performance (via long-term
warmup effects), or decrease performance (due to long-term resource
leaks).

### Trial Durations

[RFC2544] motivates the usage of at least 60 second duration by the idea
of the system under test slowly running out of resources (such as memory
buffers).

Practical results when measuring NFV software systems show that relative
change of trial duration has negligible effects on average loss ratio,
compared to relative change in offered load.

While the standard deviation of loss ratio usually shows some effects of
trial duration, they are hard to model; so further assumtions in
PLRsearch will make it insensitive to trial duration.

### Target Loss Ratio

Loss ratio function could be used to generalize throughput as the
biggest offered load which still leads to zero average loss ratio.
Unfortunately, most realistic loss ratio functions always predict non-
zero (even if negligible) average loss ratio.

On the other hand, users do not really require the average loss ratio to
be an exact zero. Most users are satisfied when the average loss ratio
is small enough.

One of PLRsearch inputs is called target loss ratio. It is the loss
ratio users would accept as negligible.

(TODO: Link to why we think 1e-7 is acceptable loss ratio.)

### Critical Load

Critical load (sometimes called critical rate) is the offered load which
leads to average loss ratio to become exactly equal to the target loss
ratio.

In principle, there could be such loss ratio functions which allow more
than one offered load to achieve target loss ratio. To avoid that,
PLRsearch assumes only increasing loss ratio functions are possible.

Similarly, some loss ratio functions may never return the target loss
ratio. PLRsearch assumes loss ratio function is continuous, that the
average loss ratio approaches zero as offered load approaches zero, and
that the average loss ratio approaches one as offered load approaches
infinity.

Under these assumptions, each loss ratio function has unique critical
load. PLRsearch attempts to locate the critical load.

### Load Regions

Critical region is the interval of offered load close to critical load,
where single measurement is not likely to distinguish whether the
critical load is higher or lower than the current offered load.

In typical case of small target loss ratio, rates below critical region
form "zero loss region", and rates above form "high loss region".

### Finite Models

Of course, finite amount of trial measurements, each of finite duration
does not give enough information to pinpoint the critical load exactly.
Therefore the output of PLRsearch is just an estimate with some
precision.

Aside of the usual substitution of infinitely precise real numbers by
finitely precise floating point numbers, there are two other instances
within PLRsearch where an objects of high information are replaced by
objects of low information.

One is the probability distribution of loss count, which is replaced by
average loss ratio. The other is the loss ratio function, which is
replaced by a few parameters, to be described later.

## PLRsearch Building Blocks

Here we define notions used by PLRsearch which are not applicable to
other search methods, nor probabilistic systems under test, in general.

### Bayesian Inference

Having reduced the model space significantly, the task of estimating the
critical load becomes simple enough so that Bayesian inference can be
used (instead of neural networks, or other Artifical Intelligence
methods).

In this case, the few parameters describing the loss ration function
become the model space. Given a prior over the model space, and trial
duration results, a posterior distribution can be computed, together
with quantities describing the critical load estimate.

### Iterative Search

The idea PLRsearch is to iterate trial measurements, using Bayesian
inference to compute both the current estimate of the critical load and
the next offered load to measure at.

The required numerical computations are done in parallel with the trial
measurements.

This means the result of measurement "n" comes as an (additional) input
to the computation running in parallel with measurement "n+1", and the
outputs of the computation are used for determining the offered load for
measurement "n+2".

Other schemes are possible, aimed to increase the number of measurements
(by decreasing their duration), which would have even higher number of
measurements run before a result of a measurement affects offered load.

### Poisson Distribution

For given offered load, number of packets lost during trial measurement
is assumed to come from Poisson distribution, and the (unknown) Poisson
parameter is expressed as average loss ratio.

Side note: Binomial Distribution is a better fit compared to Poisson
distribution (acknowledging that the number of packets lost cannot be
higher than the number of packets offered), but the difference tends to
be relevant only in high loss region. Using Poisson distribution lowers
the impact of measurements in high loss region, thus helping the
algorithm to focus on critical region better.

### Fitting Functions

There are great many increasing functions (as candidates for the loss
ratio function).

To make the space of possible functions more tractable, some other
simplifying assumptions are needed. As the algorithm will be examining
(also) loads very close to the critical load, linear approximation to
the loss rate function around the critical load is important. But as the
search algorithm needs to evaluate the function also far away from the
critical region, the approximate function has to be reasonably behaved
for every positive offered load, specifically it cannot predict non-
positive packet loss ratio.

Within this document, "fitting function" is the name for such a
reasonably behaved function, which approximates the loss ratio function
well in the critical region.

### Measurement Impact

Results from trials far from the critical region are likely to affect
the critical rate estimate negatively, as the fitting function does not
need to be a good approximation there. This is true mainly for high loss
region, as in zero loss region even badly behaved fitting function
predicts loss count to be "almost zero", so seeing a measurement
confirming the loss has been zero indeed has small impact.

Discarding some results, or "suppressing" their impact with ad-hoc
methods (other than using Poisson distribution instead of binomial) is
not used, as such methods tend to make the overall search unstable. We
rely on most of measurements being done (eventually) within the critical
region, and overweighting far-off measurements (eventually) for well-
behaved fitting functions.

Speaking about new trials, each next trial will be done at offered load
equal to the current average of the critical load. Alternative methods
for selecting offered load might be used, in an attempt to speed up
convergence. For example by employing the aforementioned unstable ad-hoc
methods.

### Fitting Function Coefficients Distribution

To accomodate systems with different behaviours, the fitting function is
expected to have few numeric parameters affecting its shape (mainly
affecting the linear approximation in the critical region).

The general search algorithm can use whatever increasing fitting
function, some specific functions can described later.

It is up to implementer to chose a fitting function and prior
distribution of its parameters. The rest of this document assumes each
parameter is independently and uniformly distributed over a common
interval. Implementers are to add non-linear transformations into their
fitting functions if their prior is different.

Exit condition for the search is either the standard deviation of the
critical load estimate becoming small enough (or similar), or overal
search time becoming long enough.

The algorithm should report both average and standard deviation for its
critical load posterior. If the reported averages follow a trend
(without reaching equilibrium), average and standard deviation should
refer to the equilibrium estimates based on the trend, not to immediate
posterior values.

### Integration

The posterior distributions for fitting function parameters will not be
integrable in general.

The search algorithm utilises the fact that trial measurement takes some
time, so this time can be used for numeric integration (using suitable
method, such as Monte Carlo) to achieve sufficient precision.

### Optimizations

After enough trials, the posterior distribution will be concentrated in
a narrow area of the parameter space. The integration method should take
advantage of that.

Even in the concentrated area, the likelihood can be quite small, so the
integration algorithm should avoid underflow errors by some means,
for example by tracking the logarithm of the likelihood.

# Sample Implementation Specifics: FD.io CSIT

The search receives min_rate and max_rate values, to avoid measurements
at offered loads not supporeted by the traffic generator.

The implemented tests cases use bidirectional traffic. The algorithm
stores each rate as bidirectional rate (internally, the algorithm is
agnostic to flows and directions, it only cares about overall counts of
packets sent and packets lost), but debug output from traffic generator
lists unidirectional values.

## Measurement Delay

In a sample implemenation in FD.io CSIT project, there is roughly 0.5
second delay between trials due to restrictons imposed by packet traffic
generator in use (T-Rex).

As measurements results come in, posterior distribution computation
takes more time (per sample), although there is a considerable constant
part (mostly for inverting the fitting functions).

Also, the integrator needs a fair amount of samples to reach the region
the posterior distribution is concentrated at.

And of course, speed of the integrator depends on computing power of the
CPU the algorithm is able to use.

All those timing related effects are addressed by arithmetically
increasing trial durations with configurable coefficients (currently 5.1
seconds for the first trial, each subsequent trial being 0.1 second
longer).

## Rounding Errors and Underflows

In order to avoid them, the current implementation tracks natural
logarithm (instead of the original quantity) for any quantity which is
never negative. Logarithm of zero is minus infinity (not supported by
Python), so special value "None" is used instead. Specific functions for
frequent operations (such as "logarithm of sum of exponentials") are
defined to handle None correctly.

## Fitting Functions

Current implementation uses two fitting functions. In general, their
estimates for critical rate differ, which adds a simple source of
systematic error, on top of randomness error reported by integrator.
Otherwise the reported stdev of critical rate estimate is
unrealistically low.

Both functions are not only increasing, but also convex (meaning the
rate of increase is also increasing).

As Primitive Function to any positive function is an increasing
function, and Primitive Function to any increasing function is convex
function; both fitting functions were constructed as double Primitive
Function to a positive function (even though the intermediate increasing
function is easier to describe).

As not any function is integrable, some more realistic functions
(especially with respect to behavior at very small offered loads) are
not easily available.

Both fitting functions have a "central point" and a "spread", varied by
simply shifting and scaling (in x-axis, the offered load direction) the
function to be doubly integrated. Scaling in y-axis (the loss rate
direction) is fixed by the requirement of transfer rate staying nearly
constant in very high offered loads.

In both fitting functions (as they are a double Primitive Function to a
symmetric function), the "central point" turns out to be equal to the
aforementioned limiting transfer rate, so the fitting function parameter
is named "mrr", the same quantity our Maximum Receive Rate tests are
designed to measure.

Both fitting functions return logarithm of loss rate, to avoid rounding
errors and underflows. Parameters and offered load are not given as
logarithms, as they are not expected to be extreme, and the formulas are
simpler that way.

Both fitting functions have several mathematically equivalent formulas,
each can lead to an overflow or underflow in different places. Overflows
can be eliminated by using different exact formulas for different
argument ranges. Underflows can be avoided by using approximate formulas
in affected argument ranges, such ranges have their own formulas to
compute. At the end, both fitting function implementations contain
multiple "if" branches, discontinuities are a possibility at range
boundaries.

Offered load for next trial measurement is the average of critical rate
estimate. During each measurement, two estimates are computed, even
though only one (in alternating order) is used for next offered load.

### Stretch Function

The original function (before applying logarithm) is Primitive Function
to Logistic Function. The name "stretch" is used for related a function
in context of neural networks with sigmoid activation function.

Formula for stretch function: loss rate (r) computed from offered load
(b), mrr parameter (m) and spread parameter (a):

r = a (Log(E^(b/a) + E^(m/a)) - Log(1 + E^(m/a)))

### Erf Function

The original function is double Primitive Function to Gaussian Function.
The name "erf" comes from error function, the first primitive to
Gaussian.

Formula for erf function: loss rate (r) computed from offered load (b),
mrr parameter (m) and spread parameter (a):

r = (b + (a (E^(-((b - m)^2/a^2)) - E^(-(m^2/a^2))))/Sqrt(Pi) + (b - m) Erf((b - m)/a) - m Erf(m/a))/2

## Prior Distributions

The numeric integrator expects all the parameters to be distributed
(independently and) uniformly on an interval (-1, 1).

As both "mrr" and "spread" parameters are positive and not not
dimensionless, a transformation is needed. Dimentionality is inherited
from max_rate value.

The "mrr" parameter follows a Lomax Distribution with alpha equal to
one, but shifted so that mrr is always greater than 1 packet per second.

The "stretch" parameter is generated simply as the "mrr" value raised to
a random power between zero and one; thus it follows a Reciprocal
Distribution.

## Integrator

After few measurements, the posterior distribution of fitting function
arguments gets quite concentrated into a small area. The integrator is
using Monte Carlo with Importance Sampling where the biased distribution
is Bivariate Gaussian distribution, with deliberately larger variance.
If the generated sample falls outside (-1, 1) interval, another sample
is generated.

The the center and the covariance matrix for the biased distribution is
based on the first and second moments of samples seen so far (within the
computation), with the following additional features designed to avoid
hyper-focused distributions.

Each computation starts with the biased distribution inherited from the
previous computation (zero point and unit covariance matrix is used in
the first computation), but the overal weight of the data is set to the
weight of the first sample of the computation. Also, the center is set
to the first sample point. When additional samples come, their weight
(including the importance correction) is compared to the weight of data
seen so far (within the computation). If the new sample is more than one
e-fold more impactful, both weight values (for data so far and for the
new sample) are set to (geometric) average if the two weights. Finally,
the actual sample generator uses covariance matrix scaled up by a
configurable factor (8.0 by default).

This combination showed the best behavior, as the integrator usually
follows two phases. First phase (where inherited biased distribution or
single big sasmples are dominating) is mainly important for locating the
new area the posterior distribution is concentrated at. The second phase
(dominated by whole sample population) is actually relevant for the
critical rate estimation.

# IANA Considerations

..

# Security Considerations

..

# Acknowledgements

..

--- back