docs/cpta/methodology/index.rst

   1 .. _trending_methodology:
   2
   3 Trending Methodology
   4 ====================
   5
   6 Overview
   7 --------
   8
   9 This document describes a high-level design of a system for continuous
  10 performance measuring, trending and change detection for FD.io VPP SW
  11 data plane. It builds upon the existing FD.io CSIT framework with
  12 extensions to its throughput testing methodology, CSIT data analytics
  13 engine (PAL – Presentation-and-Analytics-Layer) and associated Jenkins
  14 jobs definitions.
  15
  16 Proposed design replaces existing CSIT performance trending jobs and
  17 tests with new Performance Trending (PT) CSIT module and separate
  18 Performance Analysis (PA) module ingesting results from PT and
  19 analysing, detecting and reporting any performance anomalies using
  20 historical trending data and statistical metrics. PA does also produce
  21 trending dashboard and graphs with summary and drill-down views across
  22 all specified tests that can be reviewed and inspected regularly by
  23 FD.io developers and users community.
  24
  25 Performance Tests
  26 -----------------
  27
  28 Performance trending is currently relying on the Maximum Receive Rate
  29 (MRR) tests. MRR tests measure the packet forwarding rate under the
  30 maximum load offered by traffic generator over a set trial duration,
  31 regardless of packet loss. Maximum load for specified Ethernet frame
  32 size is set to the bi-directional link rate.
  33
  34 Current parameters for performance trending MRR tests:
  35
  36 - **Ethernet frame sizes**: 64B (78B for IPv6 tests) for all tests, IMIX for
  37   selected tests (vhost, memif); all quoted sizes include frame CRC, but
  38   exclude per frame transmission overhead of 20B (preamble, inter frame
  39   gap).
  40 - **Maximum load offered**: 10GE and 40GE link (sub-)rates depending on NIC
  41   tested, with the actual packet rate depending on frame size,
  42   transmission overhead and traffic generator NIC forwarding capacity.
  43
  44   - For 10GE NICs the maximum packet rate load is 2* 14.88 Mpps for 64B,
  45     a 10GE bi-directional link rate.
  46   - For 40GE NICs the maximum packet rate load is 2* 18.75 Mpps for 64B,
  47     a 40GE bi-directional link sub-rate limited by TG 40GE NIC used,
  48     XL710.
  49
  50 - **Trial duration**: 10sec.
  51 - **Execution frequency**: twice a day, every 12 hrs (02:00, 14:00 UTC).
  52
  53 Note: MRR tests should be reporting bi-directional link rate (or NIC
  54 rate, if lower) if tested VPP configuration can handle the packet rate
  55 higher than bi-directional link rate, e.g. large packet tests and/or
  56 multi-core tests. In other words MRR = min(VPP rate, bi-dir link rate,
  57 NIC rate).
  58
  59 Trend Analysis
  60 --------------
  61
  62 All measured performance trend data is treated as time-series data that
  63 can be modelled as concatenation of groups, each group modelled
  64 using normal distribution. While sometimes the samples within a group
  65 are far from being distributed normally, we do not have a better tractable model.
  66
  67 The group boundaries are selected based on `Minimum Description Length`_.
  68
  69 Minimum Description Length
  70 --------------------------
  71
  72 `Minimum Description Length`_ (MDL) is a particular formalization
  73 of `Occam's razor`_ principle.
  74
  75 The general formulation mandates to evaluate a large set of models,
  76 but for anomaly detection purposes, it is usefuls to consider
  77 a smaller set of models, so that scoring and comparing them is easier.
  78
  79 For each candidate model, the data should be compressed losslessly,
  80 which includes model definitions, encoded model parameters,
  81 and the raw data encoded based on probabilities computed by the model.
  82 The model resulting in shortest compressed message is the "the" correct model.
  83
  84 For our model set (groups of normally distributed samples),
  85 we need to encode group length (which penalizes too many groups),
  86 group average (more on that later), group stdev and then all the samples.
  87
  88 Luckily, the "all the samples" part turns out to be quite easy to compute.
  89 If sample values are considered as coordinates in (multi-dimensional)
  90 Euclidean space, fixing stdev means the point with allowed coordinates
  91 lays on a sphere. Fixing average intersects the sphere with a (hyper)-plane,
  92 and Gaussian probability density on the resulting sphere is constant.
  93 So the only contribution is the "area" of the sphere, which only depends
  94 on the number of samples and stdev.
  95
  96 A somehow ambiguous part is in choosing which encoding
  97 is used for group size, average and stdev.
  98 Diferent encodings cause different biases to large or small values.
  99 In our implementation we have chosen probability density
 100 corresponding to uniform distribution (from zero to maximal sample value)
 101 for stdev and average of the first group,
 102 but for averages of subsequent groups we have chosen a distribution
 103 which disourages deliminating groups with averages close together.
 104
 105 One part of our implementation which is not precise enough
 106 is handling of measurement precision.
 107 The minimal difference in MRR values is currently 0.1 pps
 108 (the difference of one packet over 10 second trial),
 109 but the code assumes the precision is 1.0.
 110 Also, all the calculations assume 1.0 is totally negligible,
 111 compared to stdev value.
 112
 113 The group selection algorithm currently has no parameters,
 114 all the aforementioned encodings and handling of precision is hardcoded.
 115 In principle, every group selection is examined, and the one encodable
 116 with least amount of bits is selected.
 117 As the bit amount for a selection is just sum of bits for every group,
 118 finding the best selection takes number of comparisons
 119 quadratically increasing with the size of data,
 120 the overall time complexity being probably cubic.
 121
 122 The resulting group distribution looks good
 123 if samples are distributed normally enough within a group.
 124 But for obviously different distributions (for example `bimodal distribution`_)
 125 the groups tend to focus on less relevant factors (such as "outlier" density).
 126
 127 Anomaly Detection
 128 `````````````````
 129
 130 Once the trend data is divided into groups, each group has its population average.
 131 The start of the following group is marked as a regression (or progression)
 132 if the new group's average is lower (higher) then the previous group's.
 133
 134 Trend Compliance
 135 ````````````````
 136
 137 Trend compliance metrics are targeted to provide an indication of trend
 138 changes over a short-term (i.e. weekly) and a long-term (i.e.
 139 quarterly), comparing the last group average AVG[last], to the one from week
 140 ago, AVG[last - 1week] and to the maximum of trend values over last
 141 quarter except last week, max(AVG[last - 3mths]..ANV[last - 1week]),
 142 respectively. This results in following trend compliance calculations:
 143
 144 +-------------------------+---------------------------------+-----------+-------------------------------------------+
 145 | Trend Compliance Metric | Trend Change Formula            | Value     | Reference                                 |
 146 +=========================+=================================+===========+===========================================+
 147 | Short-Term Change       | (Value - Reference) / Reference | AVG[last] | AVG[last - 1week]                         |
 148 +-------------------------+---------------------------------+-----------+-------------------------------------------+
 149 | Long-Term Change        | (Value - Reference) / Reference | AVG[last] | max(AVG[last - 3mths]..AVG[last - 1week]) |
 150 +-------------------------+---------------------------------+-----------+-------------------------------------------+
 151
 152 Trend Presentation
 153 ------------------
 154
 155 Performance Dashboard
 156 `````````````````````
 157
 158 Dashboard tables list a summary of per test-case VPP MRR performance
 159 trend and trend compliance metrics and detected number of anomalies.
 160
 161 Separate tables are generated for tested VPP worker-thread-core
 162 combinations (1t1c, 2t2c, 4t4c). Test case names are linked to
 163 respective trending graphs for ease of navigation thru the test data.
 164
 165 Trendline Graphs
 166 ````````````````
 167
 168 Trendline graphs show per test case measured MRR throughput values with
 169 associated gruop averages. The graphs are constructed as follows:
 170
 171 - X-axis represents performance trend job build Id (csit-vpp-perf-mrr-
 172   daily-master-build).
 173 - Y-axis represents MRR throughput in Mpps.
 174 - Markers to indicate anomaly classification:
 175
 176   - Regression - red circle.
 177   - Progression - green circle.
 178
 179 - The line shows average of each group.
 180
 181 In addition the graphs show dynamic labels while hovering over graph
 182 data points, representing (trend job build Id, MRR value) and the actual
 183 vpp build number (b<XXX>) tested.
 184
 185
 186 Jenkins Jobs
 187 ------------
 188
 189 Performance Trending (PT)
 190 `````````````````````````
 191
 192 CSIT PT runs regular performance test jobs measuring and collecting MRR
 193 data per test case. PT is designed as follows:
 194
 195 1. PT job triggers:
 196
 197    a) Periodic e.g. daily.
 198    b) On-demand gerrit triggered.
 199
 200 2. Measurements and data calculations per test case:
 201
 202   a) Max Received Rate (MRR) - send packets at link rate over a trial
 203      period, count total received packets, divide by trial period.
 204
 205 3. Archive MRR per test case.
 206 4. Archive all counters collected at MRR.
 207
 208 Performance Analysis (PA)
 209 `````````````````````````
 210
 211 CSIT PA runs performance analysis including trendline calculation, trend
 212 compliance and anomaly detection using specified trend analysis metrics
 213 over the rolling window of last <N> sets of historical measurement data.
 214 PA is defined as follows:
 215
 216 1. PA job triggers:
 217
 218    a) By PT job at its completion.
 219    b) On-demand gerrit triggered.
 220
 221 2. Download and parse archived historical data and the new data:
 222
 223    a) Download RF output.xml files from latest PT job and compressed
 224       archived data.
 225    b) Parse out the data filtering test cases listed in PA specification
 226       (part of CSIT PAL specification file).
 227
 228 3. Re-calculate new groups and their averages.
 229
 230 4. Evaluate new test data:
 231
 232    a) If the existing group is prolonged => Result = Pass,
 233       Reason = Normal. (to be updated base on the final Jenkins code).
 234    b) If a new group is detected with lower average => Result = Fail, Reason = Regression.
 235    c) If a new group is detected with higher average => Result = Pass, Reason = Progression.
 236
 237 5. Generate and publish results
 238
 239    a) Relay evaluation result to job result. (to be updated base on the
 240       final Jenkins code).
 241    b) Generate a new set of trend summary dashboard and graphs.
 242    c) Publish trend dashboard and graphs in html format on
 243       https://docs.fd.io/.
 244
 245 Testbed HW configuration
 246 ------------------------
 247
 248 The testbed HW configuration is described on
 249 `this FD.IO wiki page <https://wiki.fd.io/view/CSIT/CSIT_LF_testbed#FD.IO_CSIT_testbed_-_Server_HW_Configuration>`_.
 250
 251 .. _Minimum Description Length: https://en.wikipedia.org/wiki/Minimum_description_length
 252 .. _Occam's razor: https://en.wikipedia.org/wiki/Occam%27s_razor
 253 .. _bimodal distribution: https://en.wikipedia.org/wiki/Bimodal_distribution