CSIT/PerformanceTrendingAnalysis

Purpose

With increasing number of features and code changes in the FD.io VPP data plane codebase, it is increasingly difficult to measure and detect VPP data plane performance changes. Similarly, once degradation is detected, it is getting harder to bisect the source code in search of the Bad code change or addition. The problem is further escalated by a large combination of compute platforms that VPP is running and used on, including Intel Xeon, Intel Atom, ARM Aarch64.

Existing FD.io CSIT continuous performance trending test jobs help, but they rely on human factors for anomaly detection, and as such are error prone and unreliable, as the volume of data generated by these jobs is growing exponentially.

Proposed solution is to eliminate human factor and fully automate performance trending, regression and progression detection, as well as bisecting.

This document describes a high-level design of a system for continuous measuring, trending and performance change detection for FD.io VPP SW data plane. It builds upon the existing CSIT framework with extensions to its throughput testing methodology, CSIT data analytics engine (PAL – Presentation-and-Analytics-Layer) and associated Jenkins jobs definitions.

Continuous Performance Trending and Analysis

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 analysing, detecting and reporting any performance anomalies using historical trending data and statistical metrics. PA does also produce trending graphs with summary and drill-down views across all specified tests that can be reviewed and inspected regularly by FD.io developers and users community.

Trend Analysis

All measured performance trend data is treated as time-series data that can be modelled using normal distribution. After trimming the outliers, the average and deviations from average are used for detecting performance change anomalies following the three-sigma rule of thumb (a.k.a. 68-95-99.7 rule).

Analysis Metrics

Following statistical metrics are proposed as performance trend indicators over the rolling window of last <N> sets of historical measurement data:

1. Quartiles Q1, Q2, Q3 – three points dividing a ranked set of data set into four equal parts, Q2 is the median of the data.
2. Inter Quartile Range IQR=Q3-Q1 – measure of variability, used here to eliminate outliers.
3. Outliers – extreme values that are at least 1.5*IQR below Q1, or at least 1.5*IQR above Q3.
4. Trimmed Moving Average (TMA) – average across the data set of the rolling window of <N> values without the outliers. Used here to calculate TMSD.
5. Trimmed Moving Standard Deviation (TMSD) – standard deviation over the data set of the rolling window of <N> values without the outliers, requires calculating TMA. Used here for anomaly detection.
6. Moving Median (MM) - median across the data set of the rolling window of <N> values with all data points, including the outliers. Used here for anomaly detection.

The relation between IQR and Standard Deviation (denoted by sigma) is shown in figure below.

598px-Boxplot_vs_PDF.png

Anomaly Detection

Based on the assumption that all performance measurements can be modelled using normal distribution, a three-sigma rule of thumb is proposed as the main criteria for anomaly detection.

Three-sigma rule of thumb, aka 68–95–99.7 rule, is a shorthand used to capture the percentage of values that lie within a band around the average (mean) in a normal distribution within a width of two, four and six standard deviations. More accurately 68.27%, 95.45% and 99.73% of the result values should lie within one, two or three standard deviations of the mean, see figure below.

To verify compliance of test result with value X against defined trend analysis metric and detect anomalies, three simple evaluation criteria are proposed:

 Evaluation Criteria                 Compliance Confidence Level     Evaluation Result
 =====================================================================================
 (MM-3*TMSD) <= X <= (MM+3*TMSD)               99.73%                    Normal
 X < (MM-3*TMSD)                               Anomaly                   Regression
 X > (MM+3*TMSD)                               Anomaly                   Progression

MM is used for the central trend reference point instead of TMA as it is more robust to anomalies.

Reporting

Analysis results are reported in text format per test case result, in graphical format with trending graphs and as a cumulative Jenkins job result, as follows:

 Test Result Evaluation      Reported Result     Reported Reason     Trending Graph Markers
 ==========================================================================================
       Normal                      Pass              Normal            Part of plot line
       Regression                  Fail              Regression        Red circle
       Progression                 Pass              Progression       Green circle

Jenkins job cumulative results:

1. Pass - if all detection results are Pass or Warning.
2. Fail - if any detection result is Fail.

Performance Trending (PT)

CSIT PT runs regular performance test jobs finding MRR, PDR and NDR per test cases. PT is designed as follows:

1. PT job triggers:
   1. Periodic e.g. daily.
   2. On-demand gerrit triggered.
   3. Other periodic TBD.
2. Measurements and calculations per test case:
   1. MRR Max Received Rate
      1. Measured: Unlimited tolerance of packet loss.
      2. Send packets at link rate, count total received packets, divide by test trial period.
   2. Optimized binary search bounds for PDR and NDR tests:
      1. Calculated: High and low bounds for binary search based on MRR and pre-defined Packet Loss Ratio (PLR).
      2. HighBound=MRR, LowBound=to-be-determined.
      3. PLR – acceptable loss ratio for PDR tests, currently set to 0.5% for all performance tests.
   3. PDR and NDR:
      1. Run binary search within the calculated bounds, find PDR and NDR.
      2. Measured: PDR Partial Drop Rate – limited non-zero tolerance of packet loss.
      3. Measured: NDR Non Drop Rate - zero packet loss.
3. Archive MRR, PDR and NDR per test case.
4. Archive counters collected at MRR, PDR and NDR.

Performance Analysis (PA)

CSIT PA runs performance analysis, change detection and trending using specified trend analysis metrics over the rolling window of last <N> sets of historical measurement data. PA is defined as follows:

1. PA job triggers:
   1. By PT job at its completion.
   2. On-demand gerrit triggered.
   3. Other periodic TBD.
2. Download and parse archived historical data and the new data:
   1. New data from latest PT job is evaluated against the rolling window of <N> sets of historical data.
   2. Download RF output.xml files and compressed archived data.
   3. Parse out the data filtering test cases listed in PA specification (part of CSIT PAL specification file).
3. Calculate trend metrics for the rolling window of <N> sets of historical data:
   1. Calculate quartiles Q1, Q2, Q3.
   2. Trim outliers using IQR.
   3. Calculate TMA and TMSD.
   4. Calculate normal trending range per test case based on TMA and TMSD.
4. Evaluate new test data against trend metrics:
   1. If within the range of (TMA +/- 3*TMSD) => Result = Pass, Reason = Normal.
   2. If below the range => Result = Fail, Reason = Regression.
   3. If above the range => Result = Pass, Reason = Progression.
5. Generate and publish results
   1. Relay evaluation result to job result.
   2. Generate a new set of trend analysis summary graphs and drill-down graphs.
      1. Summary graphs to include measured values with Normal, Progression and Regression markers. MM shown in the background if possible.
      2. Drill-down graphs to include MM, TMA and TMSD.
   3. Publish trend analysis graphs in html format on https://docs.fd.io/.