vpp - Vector Packet Processing

Age	Commit message (Expand)	Author	Files	Lines
2019-01-22	VOM: GBP bridge domain flags	Neale Ranns	8	-23/+69
2019-01-17	VOM: ip-mroute inspect register handler fix	Neale Ranns	1	-1/+2
2019-01-17	DOC ONLY: wireshark dissector upstreamed	Dave Barach	1	-84/+0
2019-01-16	DOC ONLY: update readme.md	Dave Barach	3	-469/+28
2019-01-10	vpp_config: Rework for Python2/3 compatibility.	Paul Vinciguerra	12	-406/+554
2019-01-10	VOM: IP route ECMP support	Neale Ranns	3	-24/+56
2019-01-09	Use the official libpcap file type	Dave Barach	1	-1/+1
2019-01-07	VOM: mroutes	Neale Ranns	12	-117/+1306
2019-01-04	libmemif: fix incorrect write leading to memory corruption	Koichiro Den	1	-3/+3
2019-01-04	VPP-1525: additional fixes for strings in Japi	Michal Cmarada	5	-21/+104
2018-12-24	GBP: fix dump and VOM populate	Neale Ranns	12	-205/+96
2018-12-23	VOM: stats	Neale Ranns	7	-47/+87
2018-12-21	GBP: add allowed ethertypes to contracts	Neale Ranns	6	-93/+138
2018-12-19	VOM: stats fixes	Neale Ranns	6	-83/+88
2018-12-19	VOM: VXLAN-GBP command fixes	Neale Ranns	3	-6/+9
2018-12-19	VOM: GBP-bridge-domain fix	Neale Ranns	2	-14/+8
2018-12-19	Allow the user to select master or release during the install	jdenisco	3	-51/+38
2018-12-18	VAPI/VOM: Removing legacy stats tests, add string type.	Ole Troan	2	-9/+10
2018-12-18	Build changes required for Fedora and CentOS	Thomas F Herbert	1	-7/+8
2018-12-18	PAPI: Add MACAddress object wrapper for vl_api_mac_address_t	Ole Troan	5	-13/+9
2018-12-18	Remove autotools files from extras/libmemif	Mauro Sardara	3	-117/+0
2018-12-17	VOM: IGMP only supports IPv4	Neale Ranns	7	-19/+73
2018-12-17	libmemif: fix possible segfault on memif_get_details	Koichiro Den	1	-31/+28
2018-12-17	Added CMake building system for libmemif	msardara	12	-69/+367
2018-12-16	VOM: fixes for stats	Neale Ranns	4	-10/+9
2018-12-13	API: Use string type instead of u8.	Ole Troan	15	-40/+122
2018-12-13	vom: Add support for new stats	Mohsin Kazmi	13	-266/+990
2018-12-12	VOM: vxlan-tunnel takes egress interface for multicast	Neale Ranns	6	-17/+49
2018-12-10	VOM: vxlan-gbp	Neale Ranns	11	-100/+522
2018-12-07	vpp_if_stats: Fixing a bug in getting vpp interfaces indexes	Koren Lev	2	-10/+10
2018-12-07	vom: Fix the api type definition	Mohsin Kazmi	1	-2/+4
2018-12-06	API: Change ip4_address and ip6_address to use type alias.	Ole Troan	6	-54/+19
2018-12-06	Update japi to support type aliases	Michal Cmarada	5	-32/+126
2018-12-05	VOM: interface event struct	Neale Ranns	7	-5/+72
2018-11-30	Metadata / opaque formatting belongs in vpp	Dave Barach	1	-781/+178
2018-11-29	VOM: missing GBP symbol	Neale Ranns	1	-1/+2
2018-11-29	VOM: deprecate TAP add ip-punt redirect dump	Neale Ranns	13	-297/+174
2018-11-29	GBP: l3-out subnets	Neale Ranns	7	-1/+685
2018-11-29	VPP-1507: Added binary api to dump configured ip_punt_redirect	Pavel Kotucek	1	-8/+7
2018-11-29	API: Add support for type aliases	Ole Troan	1	-0/+7
2018-11-26	Minor tweaks	Dave Barach	1	-10/+38
2018-11-25	Use a dissector table instead of strcmp	Dave Barach	1	-30/+51
2018-11-23	Fix permission for vpp_papi	Onong Tayeng	1	-1/+1
2018-11-22	stats: golang vpp_if_stats_client	Koren Lev	8	-0/+1180
2018-11-20	Add wireshark dissector to extras	Dave Barach	3	-0/+1079
2018-11-20	Fix inspection for 18.10, requirements	jdenisco	5	-42/+68
2018-11-20	vom: Add support for redirect contracts in gbp	Mohsin Kazmi	7	-13/+613
2018-11-15	GBP: redirect contracts	Neale Ranns	1	-2/+2
2018-11-14	VPP-1477: Replace DatatypeConverter.printHexBinary with bytesToHex	Michal Cmarada	1	-3/+14
2018-11-13	docs and Config utility, package cloud support	jdenisco	1	-53/+80

--- 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