--- /dev/null
+---
+title: Probabilistic Loss Ratio Search for Packet Throughput (PLRsearch)
+# abbrev: PLRsearch
+docname: draft-vpolak-bmwg-plrsearch-01
+date: 2019-03-11
+
+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
\ No newline at end of file
Code Review / csit.git / commitdiff