+---
+title: Probabilistic Loss Ratio Search for Packet Throughput (PLRsearch)
+# abbrev: PLRsearch
+docname: draft-vpolak-plrsearch-00
+date: 2018-10-22
+
+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:
+
+--- abstract
+
+This document addresses challenges while applying methodologies
+described in [RFC2544] to benchmarking NFV (Network Function
+Virtualization) over an extended period of time, sometimes referred to
+as "soak testing". More specifically to benchmarking software based
+implementations of NFV data planes. 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 device can sustain.
+
+RFC 2544 assumes loss ratio is given by a deterministic function of
+offered load. But NFV software devices are not deterministic (enough).
+This leads for deterministic algorithms (such as 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.
+
+# Model
+
+Each algorithm searches for an answer to a precisely formulated
+question. When the question involves indeterministic systems, it has to
+specify probabilities (or prior distributions) which are tied to a
+specific probabilistic model. Different models will have different
+number (and meaning) of parameters. Complicated (but more realistic)
+models have many parameters, and the math involved can be very
+complicated. It is better to start with simpler probabilistic model, and
+only change it when the output of the simpler algorithm is not stable or
+useful enough.
+
+TODO: Refer to packet forwarding terminology, such as "offered load" and
+"loss ratio".
+
+TODO: Mention that no packet duplication is expected (or is filtered
+out).
+
+TODO: Define critical load and critical region earlier.
+
+This document is focused on algorithms related to packet loss count
+only. No latency (or other information) is taken into account. For
+simplicity, only one type of measurement is considered: dynamically
+computed offered load, constant within trial measurement of
+predetermined trial duration.
+
+Also, running longer trials (in some situations) could be more efficient,
+but in order to perform trial at multiple offered loads withing critical region,
+trial durations should be kept as short as possible.
+
+# Poisson Distribution
+
+TODO: Give link to more officially published literature about Poisson
+distribution.
+
+Note-1: that the algorithm makes an assumption that packet traffic
+generator detects duplicate packets on receive detection, and reports
+this as an error.
+
+Note-2: 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 in loads far above the critical region, so using Poisson
+distribution helps the algorithm focus on critical region better.
+
+When comparing different offered loads, the average loss per second is
+assumed to increase, but the (deterministic) function from offered load
+into average loss rate is otherwise unknown.
+
+Given a loss target (configurable, by default one packet lost per
+second), there is an unknown offered load when the average is exactly
+that. We call that the "critical load". If critical load seems higher
+than maximum offerable load, we should use the maximum offerable load to
+make search output more stable.
+
+Of course, there are great many increasing functions. The offered load
+has to be chosen for each trial, and the computed posterior distribution
+of critical load can change with each trial result.
+
+To make the space of possible functions more tractable, some other
+simplifying assumption is needed. As the algorithm will be examining
+(also) loads close to the critical load, linear approximation to the
+function (TODO: name the function) in the critical region 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 well-
+behaved for every positive offered load, specifically it cannot predict
+non-positive packet loss rate.
+
+Within this document, "fitting function" is the name for such well-behaved
+function which approximates the unknown function in the critical region.
+
+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. Instead of 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.
+
+# 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 be described later.
+
+TODO: Describe sigmoid-based and erf-based functions.
+
+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 common
+interval. Implementers are to add non-linear transformations into their
+fitting functions if their prior is different.
+
+TODO: Move the following sentence into more appropriate place.
+
+Speaking about new trials, each next trial will be done at offered load
+equal to the current average of the critical load.
+
+Exit condition is either critical load stdev becoming small enough, or
+overal search time becoming long enough.
+
+The algorithm should report both avg and stdev for critical load. If the
+reported averages follow a trend (without reaching equilibrium), avg and
+stdev should refer to the equilibrium estibated based on the trend, not
+to immediate posterior values.
+
+TODO: Explicitly mention the iterative character of the search.
+
+# Algorithm Formulas
+
+## 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 parameter space. The integration method could take
+advantage of that.
+
+Even in the concentrated area, the likelihood can be quite small, so the
+integration algorithm should track the logarithm of the likelihood, and
+also avoid underflow errors bu ther means.
+
+# Known Implementations
+
+The only known working implementatin of Probabilistic Loss Ratio Search
+for Packet Throughput is in Linux Foundation FD.io CSIT project. https://wiki.fd.io/view/CSIT. https://git.fd.io/csit/.
+
+## FD.io CSIT Implementation Specifics
+
+In a sample implemenation in FD.io CSIT project, there is around 0.5
+second delay between trials due to restrictons imposed by packet traffic
+generator in use (T-Rex), avoiding that delay is out of scope of this
+document.
+
+TODO: Describe how the current integration algorithm finds the
+concentrated area.
+
+# IANA Considerations
+
+..
+
+# Security Considerations
+
+..
+
+# Acknowledgements
+
+..
+
+--- back
\ No newline at end of file
Code Review / csit.git / commitdiff