6 Motivation for PLRsearch
7 ~~~~~~~~~~~~~~~~~~~~~~~~
9 Network providers are interested in throughput a system can sustain.
11 `RFC 2544`_ assumes loss ratio is given by a deterministic function of
12 offered load. But NFV software systems are not deterministic enough.
13 This makes deterministic algorithms (such as `binary search`_ per RFC 2544
14 and MLRsearch with single trial) to return results,
15 which when repeated show relatively high standard deviation,
16 thus making it harder to tell what "the throughput" actually is.
18 We need another algorithm, which takes this indeterminism into account.
23 Detailed description of the PLRsearch algorithm is included in the IETF
24 draft `draft-vpolak-bmwg-plrsearch-01`_ that is in the process
25 of being standardized in the IETF Benchmarking Methodology Working Group (BMWG).
30 The rest of this page assumes the reader is familiar with the following terms
31 defined in the IETF draft:
35 + Offered Load regions
38 + Non-Deterministic Region
39 + Guaranteed Loss Region
49 + Posterior Distribution
56 FD.io CSIT Implementation Specifics
57 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
59 The search receives min_rate and max_rate values, to avoid measurements
60 at offered loads not supporeted by the traffic generator.
62 The implemented tests cases use bidirectional traffic.
63 The algorithm stores each rate as bidirectional rate (internally,
64 the algorithm is agnostic to flows and directions,
65 it only cares about overall counts of packets sent and packets lost),
66 but debug output from traffic generator lists unidirectional values.
71 In a sample implemenation in FD.io CSIT project, there is roughly 0.5
72 second delay between trials due to restrictons imposed by packet traffic
73 generator in use (T-Rex).
75 As measurements results come in, posterior distribution computation takes
76 more time (per sample), although there is a considerable constant part
77 (mostly for inverting the fitting functions).
79 Also, the integrator needs a fair amount of samples to reach the region
80 the posterior distribution is concentrated at.
82 And of course, speed of the integrator depends on computing power
83 of the CPU the algorithm is able to use.
85 All those timing related effects are addressed by arithmetically increasing
86 trial durations with configurable coefficients
87 (currently 5.1 seconds for the first trial,
88 each subsequent trial being 0.1 second longer).
90 Rounding Errors and Underflows
91 ``````````````````````````````
93 In order to avoid them, the current implementation tracks natural logarithm
94 (instead of the original quantity) for any quantity which is never negative.
95 Logarithm of zero is minus infinity (not supported by Python),
96 so special value "None" is used instead.
97 Specific functions for frequent operations (such as "logarithm
98 of sum of exponentials") are defined to handle None correctly.
103 Current implementation uses two fitting functions.
104 In general, their estimates for critical rate differ,
105 which adds a simple source of systematic error,
106 on top of randomness error reported by integrator.
107 Otherwise the reported stdev of critical rate estimate
108 is unrealistically low.
110 Both functions are not only increasing, but also convex
111 (meaning the rate of increase is also increasing).
113 Both fitting functions have several mathematically equivalent formulas,
114 each can lead to an overflow or underflow in different places.
115 Overflows can be eliminated by using different exact formulas
116 for different argument ranges.
117 Underflows can be avoided by using approximate formulas
118 in affected argument ranges, such ranges have their own formulas to compute.
119 At the end, both fitting function implementations
120 contain multiple "if" branches, discontinuities are a possibility
126 The numeric integrator expects all the parameters to be distributed
127 (independently and) uniformly on an interval (-1, 1).
129 As both "mrr" and "spread" parameters are positive and not not dimensionless,
130 a transformation is needed. Dimentionality is inherited from max_rate value.
132 The "mrr" parameter follows a `Lomax distribution`_
133 with alpha equal to one, but shifted so that mrr is always greater than 1
136 The "stretch" parameter is generated simply as the "mrr" value
137 raised to a random power between zero and one;
138 thus it follows a `reciprocal distribution`_.
143 After few measurements, the posterior distribution of fitting function
144 arguments gets quite concentrated into a small area.
145 The integrator is using `Monte Carlo`_ with `importance sampling`_
146 where the biased distribution is `bivariate Gaussian`_ distribution,
147 with deliberately larger variance.
148 If the generated sample falls outside (-1, 1) interval,
149 another sample is generated.
151 The center and the covariance matrix for the biased distribution
152 is based on the first and second moments of samples seen so far
153 (within the computation), with the following additional features
154 designed to avoid hyper-focused distributions.
156 Each computation starts with the biased distribution inherited
157 from the previous computation (zero point and unit covariance matrix
158 is used in the first computation), but the overal weight of the data
159 is set to the weight of the first sample of the computation.
160 Also, the center is set to the first sample point.
161 When additional samples come, their weight (including the importance correction)
162 is compared to the weight of data seen so far (within the computation).
163 If the new sample is more than one e-fold more impactful, both weight values
164 (for data so far and for the new sample) are set to (geometric) average
165 of the two weights. Finally, the actual sample generator uses covariance matrix
166 scaled up by a configurable factor (8.0 by default).
168 This combination showed the best behavior, as the integrator usually follows
169 two phases. First phase (where inherited biased distribution
170 or single big samples are dominating) is mainly important
171 for locating the new area the posterior distribution is concentrated at.
172 The second phase (dominated by whole sample population)
173 is actually relevant for the critical rate estimation.
175 Offered Load Selection
176 ``````````````````````
178 First two measurements are hardcoded to happen at the middle of rate interval
179 and at max_rate. Next two measurements follow MRR-like logic,
180 offered load is decreased so that it would reach target loss ratio
181 if offered load decrease lead to equal decrease of loss rate.
183 The rest of measurements alternate between erf and stretch estimate average.
184 There is one workaround implemented, aimed at reducing the number of consequent
185 zero loss measurements (per fitting function). The workaround first stores
186 every measurement result which loss ratio was the targed loss ratio or higher.
187 Sorted list (called lossy loads) of such results is maintained.
189 When a sequence of one or more zero loss measurement results is encountered,
190 a smallest of lossy loads is drained from the list.
191 If the estimate average is smaller than the drained value,
192 a weighted average of this estimate and the drained value is used
193 as the next offered load. The weight of the estimate decreases exponentially
194 with the length of consecutive zero loss results.
196 This behavior helps the algorithm with convergence speed,
197 as it does not need so many zero loss result to get near critical region.
198 Using the smallest (not srained yet) of lossy loads makes it sure
199 the new offered load is unlikely to result in big loss region.
200 Draining even if the estimate is large enough helps to discard
201 early measurements when loss hapened at too low offered load.
202 Current implementation adds 4 copies of lossy loads and drains 3 of them,
203 which leads to fairly stable behavior even for somewhat inconsistent SUTs.
208 As high loss count measurements add many bits of information,
209 they need a large amount of small loss count measurements to balance them,
210 making the algorithm converge quite slowly. Typically, this happens
211 when few initial measurements suggest spread way bigger then later measurements.
212 The workaround in offered load selection helps,
213 but more intelligent workarounds could get faster convergence still.
215 Some systems evidently do not follow the assumption of repeated measurements
216 having the same average loss rate (when the offered load is the same).
217 The idea of estimating the trend is not implemented at all,
218 as the observed trends have varied characteristics.
220 Probably, using a more realistic fitting functions
221 will give better estimates than trend analysis.
226 The notion of Throughput is easy to grasp, but it is harder to measure
227 with any accuracy for non-deterministic systems.
229 Even though the notion of critical rate is harder to grasp than the notion
230 of throughput, it is easier to measure using probabilistic methods.
232 In testing, the difference between througput measurements and critical
233 rate measurements is usually small, see :ref:`soak vs ndr comparison`.
235 In pactice, rules of thumb such as "send at max 95% of purported throughput"
236 are common. The correct benchmarking analysis should ask "Which notion is
237 95% of throughput an approximation to?" before attempting to answer
238 "Is 95% of critical rate safe enough?".
246 While the estimation computation is based on hard probability science;
247 the offered load selection part of PLRsearch logic is pure heuristics,
248 motivated by what would a human do based on measurement and computation results.
250 The quality of any heuristic is not affected by soundness of its motivation,
251 just by its ability to achieve the intended goals.
252 In case of offered load selection, the goal is to help the search to converge
253 to the long duration estimates sooner.
255 But even those long duration estimates could still be of poor quality.
256 Even though the estimate computation is Bayesian (so it iss the best it could be
257 within the applied assumptions), it can still of poor quality when compared
258 to what a human would estimate.
260 One possible source of poor quality is the randomnes inherently present
261 in Monte Carlo numeric integration, but that can be supressed
262 by tweaking the time related input parameters.
264 The most likely source of poor quality then are the assumptions.
265 Most importantly, the number and the shape of fitting functions;
266 but also others, such as time the assumption of independence of loss ratio.
268 The result can have poor quality in basically two ways.
269 One way is related to location. Both upper and lower bounds
270 can be overestimates or underestimates, meaning the entire estimated interval
271 between lower bound and upper bound lays above or below (respectively)
272 of human-estimated interval.
273 The other way is related to the estimation interval width.
274 The interval can be too wide or too narrow, compared to human estimation.
276 An estimate from a particular fitting function can be classified
277 as an overestimate (or underestimate) just by looking at time evolution
278 (without human examining measurement results). Overestimates
279 decrease by time, underestimates increase by time (assuming
280 the sustem performance stays constant).
282 Quality of the width of the estimation interval needs human evaluation,
283 and is unrelated to both rate of narrowing (both good and bad estimate intervals
284 get narrower at approximately the same relative rate) and relatative width
285 (depends heavily on the system being tested).
290 The following pictures show the upper (red) and lower (blue) bound,
291 as well as average of Stretch (pink) and Erf (light green) estimate,
292 and offered load chosen (grey), as computed by PLRsearch,
293 after each trial measurement within the 2 hour duration of a test run.
295 Both graphs are focusing on later estimates. Estimates computed from
296 few initial measurements are wildly off the y-axis range shown.
298 The following analysis will rely on frequency of zero loss measurements
299 and magnitude of loss ratio if nonzero.
301 The offered load selection strategy used implies zero loss measurements
302 can me gleamed from the graph by looking at offered load points.
303 When the points leave their corresponding estimate, it means
304 the previous measurement had zero loss. After non-zero loss,
305 the offered load starts again at the estimate curve.
307 The very big loss ratio results are visible as noticeable jumps
308 of both estimates downwards. Medium and small loss ratios are much harder
309 to distinguish just by looking at the estimate curves,
310 the analysis is based on raw loss ratio measurement results.
312 The following descriptions should explain why the graphs seem to signal
313 low quality estimate at first sight, but a more detailed look
314 reveals the quality is good (considering the measurement results).
319 Both fitting functions give similar estimates, the graph shows
320 "stochasticity" of measurements (estimates increase and decrease
321 within small time regions), and an overall trend of decreasing estimates.
323 On the first look, the final interval looks fairly narrow,
324 especially compared to the region the estimates have travelled
325 during the search. But the look at the frequency of zero loss results shows
326 this is not a case of overestimation. Measurements at around the same
327 offered load have higher probability of zero loss earlier
328 (when performed at lower bound), but smaller probability later
329 (when performed neat upper bound). That means it is the performance
330 of the system under test that decreases (slightly) over time.
332 With that in mind, the apparent narrowness of the interval
333 is not a sign of low quality, just a consequence of PLRsearch assuming
334 the performance stays constant.
342 \graphicspath{{../_tmp/src/introduction/methodology_data_plane_throughput/}}
343 \includegraphics[width=0.90\textwidth]{PLR_patch}
344 \label{fig:PLR_patch}
349 .. figure:: PLR_patch.svg
356 This test case shows what looks like a quite broad estimation interval,
357 compared to other test cases with similarly looking zero loss frequencies.
359 Fitting functions give fairly differing estimates.
360 Erf function overestimates. Stretch function estimates look fairly precise.
362 Closer look at the loss distribution reveals a difference from other tests.
363 The distribution consists of mostly zero loss measurements,
364 partialy of medium loss measurements, and lacks small loss measurements
365 the loss ratio target would imply.
366 With this result composition, it is expected that the convergence
367 of the two bounds is slow.
369 In other words, human only seeing the graph would expect narrower interval,
370 but human seeing the measured loss ratios agrees that the interval should be
379 \graphicspath{{../_tmp/src/introduction/methodology_data_plane_throughput/}}
380 \includegraphics[width=0.90\textwidth]{PLR_vhost}
381 \label{fig:PLR_vhost}
386 .. figure:: PLR_vhost.svg
393 The two graphs show the behavior of PLRsearch algorithm applied to soaking test
394 when some of PLRsearch assumptions do not hold:
396 + L2 patch measurement results violate the assumption
397 of performance not changing over time.
398 + Vhost measurement results violate the assumption
399 of Poisson distribution matching the loss counts.
401 The reported upper and lower bounds can have distance larger or smaller
402 than a first look by a human would expect, but a more closer look reveals
403 the quality is good, considering the circumstances.
405 The usefullness of the critical load estimate is of questionable value
406 when the assumptions are violated.
408 Some improvements can be made via more specific workarounds,
409 for example long term limit of L2 patch performance could be estmated
412 Other improvements can be achieved only by asking users
413 whether loss patterns matter. Is it better to have single digit losses
414 distributed fairly evenly over time (as Poisson distribution would suggest),
415 or is it better to have short periods of medium losses
416 mixed with long periods of zero losses (as happens in Vhost test)
417 with the same overall loss ratio?
419 .. _draft-vpolak-bmwg-plrsearch-01: https://tools.ietf.org/html/draft-vpolak-bmwg-plrsearch-01
420 .. _plrsearch draft: https://tools.ietf.org/html/draft-vpolak-bmwg-plrsearch-00
421 .. _RFC 2544: https://tools.ietf.org/html/rfc2544
422 .. _Lomax distribution: https://en.wikipedia.org/wiki/Lomax_distribution
423 .. _reciprocal distribution: https://en.wikipedia.org/wiki/Reciprocal_distribution
424 .. _Monte Carlo: https://en.wikipedia.org/wiki/Monte_Carlo_integration
425 .. _importance sampling: https://en.wikipedia.org/wiki/Importance_sampling
426 .. _bivariate Gaussian: https://en.wikipedia.org/wiki/Multivariate_normal_distribution
427 .. _binary search: https://en.wikipedia.org/wiki/Binary_search_algorithm