blob: 7f54aad8087fb08909a9ff9ff2f8a8d4c8bfdd98 [file] [log] [blame]
/*
* Copyright (c) 2011 The WebRTC project authors. All Rights Reserved.
*
* Use of this source code is governed by a BSD-style license
* that can be found in the LICENSE file in the root of the source
* tree. An additional intellectual property rights grant can be found
* in the file PATENTS. All contributing project authors may
* be found in the AUTHORS file in the root of the source tree.
*/
#include "modules/video_coding/jitter_estimator.h"
#include <assert.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <cstdint>
#include "absl/types/optional.h"
#include "modules/video_coding/internal_defines.h"
#include "modules/video_coding/rtt_filter.h"
#include "rtc_base/experiments/jitter_upper_bound_experiment.h"
#include "rtc_base/numerics/safe_conversions.h"
#include "system_wrappers/include/clock.h"
namespace webrtc {
namespace {
static constexpr uint32_t kStartupDelaySamples = 30;
static constexpr int64_t kFsAccuStartupSamples = 5;
static constexpr double kMaxFramerateEstimate = 200.0;
static constexpr int64_t kNackCountTimeoutMs = 60000;
static constexpr double kDefaultMaxTimestampDeviationInSigmas = 3.5;
} // namespace
VCMJitterEstimator::VCMJitterEstimator(Clock* clock)
: _phi(0.97),
_psi(0.9999),
_alphaCountMax(400),
_thetaLow(0.000001),
_nackLimit(3),
_numStdDevDelayOutlier(15),
_numStdDevFrameSizeOutlier(3),
_noiseStdDevs(2.33), // ~Less than 1% chance
// (look up in normal distribution table)...
_noiseStdDevOffset(30.0), // ...of getting 30 ms freezes
_rttFilter(),
fps_counter_(30), // TODO(sprang): Use an estimator with limit based on
// time, rather than number of samples.
time_deviation_upper_bound_(
JitterUpperBoundExperiment::GetUpperBoundSigmas().value_or(
kDefaultMaxTimestampDeviationInSigmas)),
clock_(clock) {
Reset();
}
VCMJitterEstimator::~VCMJitterEstimator() {}
VCMJitterEstimator& VCMJitterEstimator::operator=(
const VCMJitterEstimator& rhs) {
if (this != &rhs) {
memcpy(_thetaCov, rhs._thetaCov, sizeof(_thetaCov));
memcpy(_Qcov, rhs._Qcov, sizeof(_Qcov));
_avgFrameSize = rhs._avgFrameSize;
_varFrameSize = rhs._varFrameSize;
_maxFrameSize = rhs._maxFrameSize;
_fsSum = rhs._fsSum;
_fsCount = rhs._fsCount;
_lastUpdateT = rhs._lastUpdateT;
_prevEstimate = rhs._prevEstimate;
_prevFrameSize = rhs._prevFrameSize;
_avgNoise = rhs._avgNoise;
_alphaCount = rhs._alphaCount;
_filterJitterEstimate = rhs._filterJitterEstimate;
_startupCount = rhs._startupCount;
_latestNackTimestamp = rhs._latestNackTimestamp;
_nackCount = rhs._nackCount;
_rttFilter = rhs._rttFilter;
clock_ = rhs.clock_;
}
return *this;
}
// Resets the JitterEstimate.
void VCMJitterEstimator::Reset() {
_theta[0] = 1 / (512e3 / 8);
_theta[1] = 0;
_varNoise = 4.0;
_thetaCov[0][0] = 1e-4;
_thetaCov[1][1] = 1e2;
_thetaCov[0][1] = _thetaCov[1][0] = 0;
_Qcov[0][0] = 2.5e-10;
_Qcov[1][1] = 1e-10;
_Qcov[0][1] = _Qcov[1][0] = 0;
_avgFrameSize = 500;
_maxFrameSize = 500;
_varFrameSize = 100;
_lastUpdateT = -1;
_prevEstimate = -1.0;
_prevFrameSize = 0;
_avgNoise = 0.0;
_alphaCount = 1;
_filterJitterEstimate = 0.0;
_latestNackTimestamp = 0;
_nackCount = 0;
_latestNackTimestamp = 0;
_fsSum = 0;
_fsCount = 0;
_startupCount = 0;
_rttFilter.Reset();
fps_counter_.Reset();
}
// Updates the estimates with the new measurements.
void VCMJitterEstimator::UpdateEstimate(int64_t frameDelayMS,
uint32_t frameSizeBytes,
bool incompleteFrame /* = false */) {
if (frameSizeBytes == 0) {
return;
}
int deltaFS = frameSizeBytes - _prevFrameSize;
if (_fsCount < kFsAccuStartupSamples) {
_fsSum += frameSizeBytes;
_fsCount++;
} else if (_fsCount == kFsAccuStartupSamples) {
// Give the frame size filter.
_avgFrameSize = static_cast<double>(_fsSum) / static_cast<double>(_fsCount);
_fsCount++;
}
if (!incompleteFrame || frameSizeBytes > _avgFrameSize) {
double avgFrameSize = _phi * _avgFrameSize + (1 - _phi) * frameSizeBytes;
if (frameSizeBytes < _avgFrameSize + 2 * sqrt(_varFrameSize)) {
// Only update the average frame size if this sample wasn't a key frame.
_avgFrameSize = avgFrameSize;
}
// Update the variance anyway since we want to capture cases where we only
// get key frames.
_varFrameSize = VCM_MAX(
_phi * _varFrameSize + (1 - _phi) * (frameSizeBytes - avgFrameSize) *
(frameSizeBytes - avgFrameSize),
1.0);
}
// Update max frameSize estimate.
_maxFrameSize =
VCM_MAX(_psi * _maxFrameSize, static_cast<double>(frameSizeBytes));
if (_prevFrameSize == 0) {
_prevFrameSize = frameSizeBytes;
return;
}
_prevFrameSize = frameSizeBytes;
// Cap frameDelayMS based on the current time deviation noise.
int64_t max_time_deviation_ms =
static_cast<int64_t>(time_deviation_upper_bound_ * sqrt(_varNoise) + 0.5);
frameDelayMS = std::max(std::min(frameDelayMS, max_time_deviation_ms),
-max_time_deviation_ms);
// Only update the Kalman filter if the sample is not considered an extreme
// outlier. Even if it is an extreme outlier from a delay point of view, if
// the frame size also is large the deviation is probably due to an incorrect
// line slope.
double deviation = DeviationFromExpectedDelay(frameDelayMS, deltaFS);
if (fabs(deviation) < _numStdDevDelayOutlier * sqrt(_varNoise) ||
frameSizeBytes >
_avgFrameSize + _numStdDevFrameSizeOutlier * sqrt(_varFrameSize)) {
// Update the variance of the deviation from the line given by the Kalman
// filter.
EstimateRandomJitter(deviation, incompleteFrame);
// Prevent updating with frames which have been congested by a large frame,
// and therefore arrives almost at the same time as that frame.
// This can occur when we receive a large frame (key frame) which has been
// delayed. The next frame is of normal size (delta frame), and thus deltaFS
// will be << 0. This removes all frame samples which arrives after a key
// frame.
if ((!incompleteFrame || deviation >= 0.0) &&
static_cast<double>(deltaFS) > -0.25 * _maxFrameSize) {
// Update the Kalman filter with the new data
KalmanEstimateChannel(frameDelayMS, deltaFS);
}
} else {
int nStdDev =
(deviation >= 0) ? _numStdDevDelayOutlier : -_numStdDevDelayOutlier;
EstimateRandomJitter(nStdDev * sqrt(_varNoise), incompleteFrame);
}
// Post process the total estimated jitter
if (_startupCount >= kStartupDelaySamples) {
PostProcessEstimate();
} else {
_startupCount++;
}
}
// Updates the nack/packet ratio.
void VCMJitterEstimator::FrameNacked() {
if (_nackCount < _nackLimit) {
_nackCount++;
}
_latestNackTimestamp = clock_->TimeInMicroseconds();
}
// Updates Kalman estimate of the channel.
// The caller is expected to sanity check the inputs.
void VCMJitterEstimator::KalmanEstimateChannel(int64_t frameDelayMS,
int32_t deltaFSBytes) {
double Mh[2];
double hMh_sigma;
double kalmanGain[2];
double measureRes;
double t00, t01;
// Kalman filtering
// Prediction
// M = M + Q
_thetaCov[0][0] += _Qcov[0][0];
_thetaCov[0][1] += _Qcov[0][1];
_thetaCov[1][0] += _Qcov[1][0];
_thetaCov[1][1] += _Qcov[1][1];
// Kalman gain
// K = M*h'/(sigma2n + h*M*h') = M*h'/(1 + h*M*h')
// h = [dFS 1]
// Mh = M*h'
// hMh_sigma = h*M*h' + R
Mh[0] = _thetaCov[0][0] * deltaFSBytes + _thetaCov[0][1];
Mh[1] = _thetaCov[1][0] * deltaFSBytes + _thetaCov[1][1];
// sigma weights measurements with a small deltaFS as noisy and
// measurements with large deltaFS as good
if (_maxFrameSize < 1.0) {
return;
}
double sigma = (300.0 * exp(-fabs(static_cast<double>(deltaFSBytes)) /
(1e0 * _maxFrameSize)) +
1) *
sqrt(_varNoise);
if (sigma < 1.0) {
sigma = 1.0;
}
hMh_sigma = deltaFSBytes * Mh[0] + Mh[1] + sigma;
if ((hMh_sigma < 1e-9 && hMh_sigma >= 0) ||
(hMh_sigma > -1e-9 && hMh_sigma <= 0)) {
assert(false);
return;
}
kalmanGain[0] = Mh[0] / hMh_sigma;
kalmanGain[1] = Mh[1] / hMh_sigma;
// Correction
// theta = theta + K*(dT - h*theta)
measureRes = frameDelayMS - (deltaFSBytes * _theta[0] + _theta[1]);
_theta[0] += kalmanGain[0] * measureRes;
_theta[1] += kalmanGain[1] * measureRes;
if (_theta[0] < _thetaLow) {
_theta[0] = _thetaLow;
}
// M = (I - K*h)*M
t00 = _thetaCov[0][0];
t01 = _thetaCov[0][1];
_thetaCov[0][0] = (1 - kalmanGain[0] * deltaFSBytes) * t00 -
kalmanGain[0] * _thetaCov[1][0];
_thetaCov[0][1] = (1 - kalmanGain[0] * deltaFSBytes) * t01 -
kalmanGain[0] * _thetaCov[1][1];
_thetaCov[1][0] = _thetaCov[1][0] * (1 - kalmanGain[1]) -
kalmanGain[1] * deltaFSBytes * t00;
_thetaCov[1][1] = _thetaCov[1][1] * (1 - kalmanGain[1]) -
kalmanGain[1] * deltaFSBytes * t01;
// Covariance matrix, must be positive semi-definite.
assert(_thetaCov[0][0] + _thetaCov[1][1] >= 0 &&
_thetaCov[0][0] * _thetaCov[1][1] -
_thetaCov[0][1] * _thetaCov[1][0] >=
0 &&
_thetaCov[0][0] >= 0);
}
// Calculate difference in delay between a sample and the expected delay
// estimated by the Kalman filter
double VCMJitterEstimator::DeviationFromExpectedDelay(
int64_t frameDelayMS,
int32_t deltaFSBytes) const {
return frameDelayMS - (_theta[0] * deltaFSBytes + _theta[1]);
}
// Estimates the random jitter by calculating the variance of the sample
// distance from the line given by theta.
void VCMJitterEstimator::EstimateRandomJitter(double d_dT,
bool incompleteFrame) {
uint64_t now = clock_->TimeInMicroseconds();
if (_lastUpdateT != -1) {
fps_counter_.AddSample(now - _lastUpdateT);
}
_lastUpdateT = now;
if (_alphaCount == 0) {
assert(false);
return;
}
double alpha =
static_cast<double>(_alphaCount - 1) / static_cast<double>(_alphaCount);
_alphaCount++;
if (_alphaCount > _alphaCountMax)
_alphaCount = _alphaCountMax;
// In order to avoid a low frame rate stream to react slower to changes,
// scale the alpha weight relative a 30 fps stream.
double fps = GetFrameRate();
if (fps > 0.0) {
double rate_scale = 30.0 / fps;
// At startup, there can be a lot of noise in the fps estimate.
// Interpolate rate_scale linearly, from 1.0 at sample #1, to 30.0 / fps
// at sample #kStartupDelaySamples.
if (_alphaCount < kStartupDelaySamples) {
rate_scale =
(_alphaCount * rate_scale + (kStartupDelaySamples - _alphaCount)) /
kStartupDelaySamples;
}
alpha = pow(alpha, rate_scale);
}
double avgNoise = alpha * _avgNoise + (1 - alpha) * d_dT;
double varNoise =
alpha * _varNoise + (1 - alpha) * (d_dT - _avgNoise) * (d_dT - _avgNoise);
if (!incompleteFrame || varNoise > _varNoise) {
_avgNoise = avgNoise;
_varNoise = varNoise;
}
if (_varNoise < 1.0) {
// The variance should never be zero, since we might get stuck and consider
// all samples as outliers.
_varNoise = 1.0;
}
}
double VCMJitterEstimator::NoiseThreshold() const {
double noiseThreshold = _noiseStdDevs * sqrt(_varNoise) - _noiseStdDevOffset;
if (noiseThreshold < 1.0) {
noiseThreshold = 1.0;
}
return noiseThreshold;
}
// Calculates the current jitter estimate from the filtered estimates.
double VCMJitterEstimator::CalculateEstimate() {
double ret = _theta[0] * (_maxFrameSize - _avgFrameSize) + NoiseThreshold();
// A very low estimate (or negative) is neglected.
if (ret < 1.0) {
if (_prevEstimate <= 0.01) {
ret = 1.0;
} else {
ret = _prevEstimate;
}
}
if (ret > 10000.0) { // Sanity
ret = 10000.0;
}
_prevEstimate = ret;
return ret;
}
void VCMJitterEstimator::PostProcessEstimate() {
_filterJitterEstimate = CalculateEstimate();
}
void VCMJitterEstimator::UpdateRtt(int64_t rttMs) {
_rttFilter.Update(rttMs);
}
// Returns the current filtered estimate if available,
// otherwise tries to calculate an estimate.
int VCMJitterEstimator::GetJitterEstimate(
double rttMultiplier,
absl::optional<double> rttMultAddCapMs) {
double jitterMS = CalculateEstimate() + OPERATING_SYSTEM_JITTER;
uint64_t now = clock_->TimeInMicroseconds();
if (now - _latestNackTimestamp > kNackCountTimeoutMs * 1000)
_nackCount = 0;
if (_filterJitterEstimate > jitterMS)
jitterMS = _filterJitterEstimate;
if (_nackCount >= _nackLimit) {
if (rttMultAddCapMs.has_value()) {
jitterMS +=
std::min(_rttFilter.RttMs() * rttMultiplier, rttMultAddCapMs.value());
} else {
jitterMS += _rttFilter.RttMs() * rttMultiplier;
}
}
static const double kJitterScaleLowThreshold = 5.0;
static const double kJitterScaleHighThreshold = 10.0;
double fps = GetFrameRate();
// Ignore jitter for very low fps streams.
if (fps < kJitterScaleLowThreshold) {
if (fps == 0.0) {
return rtc::checked_cast<int>(std::max(0.0, jitterMS) + 0.5);
}
return 0;
}
// Semi-low frame rate; scale by factor linearly interpolated from 0.0 at
// kJitterScaleLowThreshold to 1.0 at kJitterScaleHighThreshold.
if (fps < kJitterScaleHighThreshold) {
jitterMS = (1.0 / (kJitterScaleHighThreshold - kJitterScaleLowThreshold)) *
(fps - kJitterScaleLowThreshold) * jitterMS;
}
return rtc::checked_cast<int>(std::max(0.0, jitterMS) + 0.5);
}
double VCMJitterEstimator::GetFrameRate() const {
if (fps_counter_.ComputeMean() <= 0.0)
return 0;
double fps = 1000000.0 / fps_counter_.ComputeMean();
// Sanity check.
assert(fps >= 0.0);
if (fps > kMaxFramerateEstimate) {
fps = kMaxFramerateEstimate;
}
return fps;
}
} // namespace webrtc