Overview
--------
+// Below paragraph needs to be updated.
This document describes a high-level design of a system for continuous
performance measuring, trending and change detection for FD.io VPP SW
data plane. It builds upon the existing FD.io CSIT framework with
engine (PAL – Presentation-and-Analytics-Layer) and associated Jenkins
jobs definitions.
+// Below paragraph needs to be updated.
Proposed design replaces existing CSIT performance trending jobs and
tests with new Performance Trending (PT) CSIT module and separate
Performance Analysis (PA) module ingesting results from PT and
Performance Tests
-----------------
-Performance trending is currently relying on the Maximum Receive Rate
+Performance trending is relies on Maximum Receive Rate
(MRR) tests. MRR tests measure the packet forwarding rate under the
maximum load offered by traffic generator over a set trial duration,
regardless of packet loss. Maximum load for specified Ethernet frame
- For 10GE NICs the maximum packet rate load is 2* 14.88 Mpps for 64B,
a 10GE bi-directional link rate.
- For 40GE NICs the maximum packet rate load is 2* 18.75 Mpps for 64B,
- a 40GE bi-directional link sub-rate limited by TG 40GE NIC used,
- XL710.
+ a 40GE bi-directional link sub-rate limited by the packet forwarding
+ capacity of 2-port 40GE NIC model (XL710) used on T-Rex Traffic
+ Generator.
-- **Trial duration**: 10sec.
-- **Execution frequency**: twice a day, every 12 hrs (02:00, 14:00 UTC).
+- **Trial duration**: 1 sec.
+- **Number of trials per test**: 10.
+- **Test execution frequency**: twice a day, every 12 hrs (02:00,
+ 14:00 UTC).
Note: MRR tests should be reporting bi-directional link rate (or NIC
rate, if lower) if tested VPP configuration can handle the packet rate
--------------
All measured performance trend data is treated as time-series data that
-can be modelled using normal distribution. After trimming the outliers,
-the median and deviations from median are used for detecting performance
-change anomalies following the three-sigma rule of thumb (a.k.a.
-68-95-99.7 rule).
-
-Metrics
-````````````````
-
-Following statistical metrics are used as performance trend indicators
-over the rolling window of last <N> sets of historical measurement data:
-
-- **Q1**, **Q2**, **Q3** : **Quartiles**, three points dividing a ranked
- data set of <N> values into four equal parts, Q2 is the median of the
- data.
-- **IQR** = Q3 - Q1 : **Inter Quartile Range**, measure of variability,
- used here to calculate and eliminate outliers.
-- **Outliers** : extreme values that are at least (1.5 * IQR) below Q1.
-
- - Note: extreme values that are at least (1.5 * IQR) above Q3 are not
- considered outliers, and are likely to be classified as
- progressions.
-
-- **TMA** : **Trimmed Moving Average**, average across the data set of
- <N> values without the outliers. Used here to calculate TMSD.
-- **TMSD** : **Trimmed Moving Standard Deviation**, standard deviation
- over the data set of <N> values without the outliers, requires
- calculating TMA. Used for anomaly detection.
-- **TMM** : **Trimmed Moving Median**, median across the data set of <N>
- values excluding the outliers. Used as a trending value and as a
- reference for anomaly detection.
-
-Outlier Detection
-`````````````````
-
-Outlier evaluation of test result of value :math:`X_n` follows the
-definition from previous section:
-
-+--------------------------------------------+----------------------+
-| Outlier Evaluation Formula | Evaluation Result |
-+============================================+======================+
-| :math:`X_n < \left( Q1 - 1.5 IQR \right)` | Outlier |
-+--------------------------------------------+----------------------+
-| :math:`X_n >= \left( Q1 - 1.5 IQR \right)` | Valid (For Trending) |
-+--------------------------------------------+----------------------+
+can be modelled as concatenation of groups, each group modelled
+using normal distribution. While sometimes the samples within a group
+are far from being distributed normally, currently we do not have a
+better tractable model.
+
+The group boundaries are selected based on `Minimum Description Length`_.
+
+Minimum Description Length
+--------------------------
+
+`Minimum Description Length`_ (MDL) is a particular formalization
+of `Occam's razor`_ principle.
+
+The general formulation mandates to evaluate a large set of models,
+but for anomaly detection purposes, it is useful to consider
+a smaller set of models, so that scoring and comparing them is easier.
+
+For each candidate model, the data should be compressed losslessly,
+which includes model definitions, encoded model parameters,
+and the raw data encoded based on probabilities computed by the model.
+The model resulting in shortest compressed message is the "the" correct model.
+
+For our model set (groups of normally distributed samples),
+we need to encode group length (which penalizes too many groups),
+group average (more on that later), group stdev and then all the samples.
+
+Luckily, the "all the samples" part turns out to be quite easy to compute.
+If sample values are considered as coordinates in (multi-dimensional)
+Euclidean space, fixing stdev means the point with allowed coordinates
+lays on a sphere. Fixing average intersects the sphere with a (hyper)-plane,
+and Gaussian probability density on the resulting sphere is constant.
+So the only contribution is the "area" of the sphere, which only depends
+on the number of samples and stdev.
+
+A somehow ambiguous part is in choosing which encoding
+is used for group size, average and stdev.
+Diferent encodings cause different biases to large or small values.
+In our implementation we have chosen probability density
+corresponding to uniform distribution (from zero to maximal sample value)
+for stdev and average of the first group,
+but for averages of subsequent groups we have chosen a distribution
+which disourages deliminating groups with averages close together.
+
+// Below paragraph needs to be updated.
+One part of our implementation which is not precise enough
+is handling of measurement precision.
+The minimal difference in MRR values is currently 0.1 pps
+(the difference of one packet over 10 second trial),
+but the code assumes the precision is 1.0.
+Also, all the calculations assume 1.0 is totally negligible,
+compared to stdev value.
+
+The group selection algorithm currently has no parameters,
+all the aforementioned encodings and handling of precision is hardcoded.
+In principle, every group selection is examined, and the one encodable
+with least amount of bits is selected.
+As the bit amount for a selection is just sum of bits for every group,
+finding the best selection takes number of comparisons
+quadratically increasing with the size of data,
+the overall time complexity being probably cubic.
+
+The resulting group distribution looks good
+if samples are distributed normally enough within a group.
+But for obviously different distributions (for example `bimodal distribution`_)
+the groups tend to focus on less relevant factors (such as "outlier" density).
Anomaly Detection
`````````````````
-To verify compliance of test result of valid value <X> against defined
-trend metrics and detect anomalies, three simple evaluation formulas are
-used:
-
-+---------------------------------------------------------------------------+-----------------------------+-------------------+
-| Anomaly Evaluation Formula | Compliance Confidence Level | Evaluation Result |
-+===========================================================================+=============================+===================+
-| :math:`\left( TMM - 3 TMSD \right) <= X_n <= \left( TMM + 3 TMSD \right)` | 99.73% | Normal |
-+---------------------------------------------------------------------------+-----------------------------+-------------------+
-| :math:`X_n < \left( TMM - 3 TMSD \right)` | Anomaly | Regression |
-+---------------------------------------------------------------------------+-----------------------------+-------------------+
-| :math:`X_n > \left( TMM + 3 TMSD \right)` | Anomaly | Progression |
-+---------------------------------------------------------------------------+-----------------------------+-------------------+
-
-TMM is used for the central trend reference point instead of TMA as it
-is more robust to anomalies.
+Once the trend data is divided into groups, each group has its population average.
+The start of the following group is marked as a regression (or progression)
+if the new group's average is lower (higher) then the previous group's.
Trend Compliance
````````````````
Trend compliance metrics are targeted to provide an indication of trend
changes over a short-term (i.e. weekly) and a long-term (i.e.
-quarterly), comparing the last trend value, TMM[last], to one from week
-ago, TMM[last - 1week] and to the maximum of trend values over last
-quarter except last week, max(TMM[(last - 3mths)..(last - 1week)]),
+quarterly), comparing the last group average AVG[last], to the one from week
+ago, AVG[last - 1week] and to the maximum of trend values over last
+quarter except last week, max(AVG[last - 3mths]..ANV[last - 1week]),
respectively. This results in following trend compliance calculations:
-+-------------------------+---------------------------------------------+--------------------------------+------------------------------------------------------------------------------------------------------------+
-| Trend Compliance Metric | Change Formula | Value | Reference |
-+=========================+=============================================+================================+============================================================================================================+
-| Short-Term Change | :math:`\frac{Value - Reference}{Reference}` | :math:`TMM \left[ last \right] | :math:`TMM \left[ last - 1 week \right]` |
-+-------------------------+---------------------------------------------+--------------------------------+------------------------------------------------------------------------------------------------------------+
-| Long-Term Change | :math:`\frac{Value - Reference}{Reference}` | :math:`TMM \left[ last \right] | :math:`max \left( TMM \left[ \left( last - 3 mths \right) .. \left( last - 1 week \right) \right] \right)` |
-+-------------------------+---------------------------------------------+--------------------------------+------------------------------------------------------------------------------------------------------------+
+// Below table needs to be updated.
++-------------------------+---------------------------------+-----------+-------------------------------------------+
+| Trend Compliance Metric | Trend Change Formula | Value | Reference |
++=========================+=================================+===========+===========================================+
+| Short-Term Change | (Value - Reference) / Reference | AVG[last] | AVG[last - 1week] |
++-------------------------+---------------------------------+-----------+-------------------------------------------+
+| Long-Term Change | (Value - Reference) / Reference | AVG[last] | max(AVG[last - 3mths]..AVG[last - 1week]) |
++-------------------------+---------------------------------+-----------+-------------------------------------------+
Trend Presentation
------------------
````````````````
Trendline graphs show per test case measured MRR throughput values with
-associated trendlines. The graphs are constructed as follows:
+associated gruop averages. The graphs are constructed as follows:
- X-axis represents performance trend job build Id (csit-vpp-perf-mrr-
daily-master-build).
- Y-axis represents MRR throughput in Mpps.
- Markers to indicate anomaly classification:
- - Outlier - gray circle around MRR value point.
- Regression - red circle.
- Progression - green circle.
+- The line shows average of each group.
+
In addition the graphs show dynamic labels while hovering over graph
data points, representing (trend job build Id, MRR value) and the actual
vpp build number (b<XXX>) tested.
archived data.
b) Parse out the data filtering test cases listed in PA specification
(part of CSIT PAL specification file).
- c) Evalute new data from latest PT job against the rolling window of
- <N> sets of historical data for trendline calculation, anomaly
- detection and short-term trend compliance. And against long-term
- trendline metrics for long-term trend compliance.
-
-3. Calculate trend metrics for the rolling window of <N> sets of
- historical data:
- a) Calculate quartiles Q1, Q2, Q3.
- b) Trim outliers using IQR.
- c) Calculate TMA and TMSD.
- d) Calculate normal trending range per test case based on TMM and
- TMSD.
+3. Re-calculate new groups and their averages.
-4. Evaluate new test data against trend metrics:
+4. Evaluate new test data:
- a) If within the range of (TMA +/- 3*TMSD) => Result = Pass,
+ a) If the existing group is prolonged => Result = Pass,
Reason = Normal. (to be updated base on the final Jenkins code).
- b) If below the range => Result = Fail, Reason = Regression.
- c) If above the range => Result = Pass, Reason = Progression.
+ b) If a new group is detected with lower average => Result = Fail, Reason = Regression.
+ c) If a new group is detected with higher average => Result = Pass, Reason = Progression.
5. Generate and publish results
b) Generate a new set of trend summary dashboard and graphs.
c) Publish trend dashboard and graphs in html format on
https://docs.fd.io/.
+
+Testbed HW configuration
+------------------------
+
+The testbed HW configuration is described on
+`this FD.IO wiki page <https://wiki.fd.io/view/CSIT/CSIT_LF_testbed#FD.IO_CSIT_testbed_-_Server_HW_Configuration>`_.
+
+.. _Minimum Description Length: https://en.wikipedia.org/wiki/Minimum_description_length
+.. _Occam's razor: https://en.wikipedia.org/wiki/Occam%27s_razor
+.. _bimodal distribution: https://en.wikipedia.org/wiki/Bimodal_distribution
Code Review / csit.git / blobdiff