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