Source code
Revision control
Copy as Markdown
Other Tools
/*
* 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/timing/jitter_estimator.h"
#include <math.h>
#include <string.h>
#include <algorithm>
#include <cstdint>
#include "absl/types/optional.h"
#include "api/field_trials_view.h"
#include "api/units/data_size.h"
#include "api/units/frequency.h"
#include "api/units/time_delta.h"
#include "api/units/timestamp.h"
#include "modules/video_coding/timing/rtt_filter.h"
#include "rtc_base/checks.h"
#include "rtc_base/logging.h"
#include "rtc_base/numerics/safe_conversions.h"
#include "system_wrappers/include/clock.h"
namespace webrtc {
namespace {
// Number of frames to wait for before post processing estimate. Also used in
// the frame rate estimator ramp-up.
constexpr size_t kFrameProcessingStartupCount = 30;
// Number of frames to wait for before enabling the frame size filters.
constexpr size_t kFramesUntilSizeFiltering = 5;
// Initial value for frame size filters.
constexpr double kInitialAvgAndMaxFrameSizeBytes = 500.0;
// Time constant for average frame size filter.
constexpr double kPhi = 0.97;
// Time constant for max frame size filter.
constexpr double kPsi = 0.9999;
// Default constants for percentile frame size filter.
constexpr double kDefaultMaxFrameSizePercentile = 0.95;
constexpr int kDefaultFrameSizeWindow = 30 * 10;
// Outlier rejection constants.
constexpr double kNumStdDevDelayClamp = 3.5;
constexpr double kNumStdDevDelayOutlier = 15.0;
constexpr double kNumStdDevSizeOutlier = 3.0;
constexpr double kCongestionRejectionFactor = -0.25;
// Rampup constant for deviation noise filters.
constexpr size_t kAlphaCountMax = 400;
// Noise threshold constants.
// ~Less than 1% chance (look up in normal distribution table)...
constexpr double kNoiseStdDevs = 2.33;
// ...of getting 30 ms freezes
constexpr double kNoiseStdDevOffset = 30.0;
// Jitter estimate clamping limits.
constexpr TimeDelta kMinJitterEstimate = TimeDelta::Millis(1);
constexpr TimeDelta kMaxJitterEstimate = TimeDelta::Seconds(10);
// A constant describing the delay from the jitter buffer to the delay on the
// receiving side which is not accounted for by the jitter buffer nor the
// decoding delay estimate.
constexpr TimeDelta OPERATING_SYSTEM_JITTER = TimeDelta::Millis(10);
// Time constant for reseting the NACK count.
constexpr TimeDelta kNackCountTimeout = TimeDelta::Seconds(60);
// RTT mult activation.
constexpr size_t kNackLimit = 3;
// Frame rate estimate clamping limit.
constexpr Frequency kMaxFramerateEstimate = Frequency::Hertz(200);
} // namespace
constexpr char JitterEstimator::Config::kFieldTrialsKey[];
JitterEstimator::Config JitterEstimator::Config::ParseAndValidate(
absl::string_view field_trial) {
Config config;
config.Parser()->Parse(field_trial);
// The `MovingPercentileFilter` RTC_CHECKs on the validity of the
// percentile and window length, so we'd better validate the field trial
// provided values here.
if (config.max_frame_size_percentile) {
double original = *config.max_frame_size_percentile;
config.max_frame_size_percentile = std::min(std::max(0.0, original), 1.0);
if (config.max_frame_size_percentile != original) {
RTC_LOG(LS_ERROR) << "Skipping invalid max_frame_size_percentile="
<< original;
}
}
if (config.frame_size_window && config.frame_size_window < 1) {
RTC_LOG(LS_ERROR) << "Skipping invalid frame_size_window="
<< *config.frame_size_window;
config.frame_size_window = 1;
}
// General sanity checks.
if (config.num_stddev_delay_clamp && config.num_stddev_delay_clamp < 0.0) {
RTC_LOG(LS_ERROR) << "Skipping invalid num_stddev_delay_clamp="
<< *config.num_stddev_delay_clamp;
config.num_stddev_delay_clamp = 0.0;
}
if (config.num_stddev_delay_outlier &&
config.num_stddev_delay_outlier < 0.0) {
RTC_LOG(LS_ERROR) << "Skipping invalid num_stddev_delay_outlier="
<< *config.num_stddev_delay_outlier;
config.num_stddev_delay_outlier = 0.0;
}
if (config.num_stddev_size_outlier && config.num_stddev_size_outlier < 0.0) {
RTC_LOG(LS_ERROR) << "Skipping invalid num_stddev_size_outlier="
<< *config.num_stddev_size_outlier;
config.num_stddev_size_outlier = 0.0;
}
return config;
}
JitterEstimator::JitterEstimator(Clock* clock,
const FieldTrialsView& field_trials)
: config_(Config::ParseAndValidate(
field_trials.Lookup(Config::kFieldTrialsKey))),
avg_frame_size_median_bytes_(static_cast<size_t>(
config_.frame_size_window.value_or(kDefaultFrameSizeWindow))),
max_frame_size_bytes_percentile_(
config_.max_frame_size_percentile.value_or(
kDefaultMaxFrameSizePercentile),
static_cast<size_t>(
config_.frame_size_window.value_or(kDefaultFrameSizeWindow))),
fps_counter_(30), // TODO(sprang): Use an estimator with limit based
// on time, rather than number of samples.
clock_(clock) {
Reset();
}
JitterEstimator::~JitterEstimator() = default;
// Resets the JitterEstimate.
void JitterEstimator::Reset() {
avg_frame_size_bytes_ = kInitialAvgAndMaxFrameSizeBytes;
max_frame_size_bytes_ = kInitialAvgAndMaxFrameSizeBytes;
var_frame_size_bytes2_ = 100;
avg_frame_size_median_bytes_.Reset();
max_frame_size_bytes_percentile_.Reset();
last_update_time_ = absl::nullopt;
prev_estimate_ = absl::nullopt;
prev_frame_size_ = absl::nullopt;
avg_noise_ms_ = 0.0;
var_noise_ms2_ = 4.0;
alpha_count_ = 1;
filter_jitter_estimate_ = TimeDelta::Zero();
latest_nack_ = Timestamp::Zero();
nack_count_ = 0;
startup_frame_size_sum_bytes_ = 0;
startup_frame_size_count_ = 0;
startup_count_ = 0;
rtt_filter_.Reset();
fps_counter_.Reset();
kalman_filter_ = FrameDelayVariationKalmanFilter();
}
// Updates the estimates with the new measurements.
void JitterEstimator::UpdateEstimate(TimeDelta frame_delay,
DataSize frame_size) {
if (frame_size.IsZero()) {
return;
}
// Can't use DataSize since this can be negative.
double delta_frame_bytes =
frame_size.bytes() - prev_frame_size_.value_or(DataSize::Zero()).bytes();
if (startup_frame_size_count_ < kFramesUntilSizeFiltering) {
startup_frame_size_sum_bytes_ += frame_size.bytes();
startup_frame_size_count_++;
} else if (startup_frame_size_count_ == kFramesUntilSizeFiltering) {
// Give the frame size filter.
avg_frame_size_bytes_ = startup_frame_size_sum_bytes_ /
static_cast<double>(startup_frame_size_count_);
startup_frame_size_count_++;
}
double avg_frame_size_bytes =
kPhi * avg_frame_size_bytes_ + (1 - kPhi) * frame_size.bytes();
double deviation_size_bytes = 2 * sqrt(var_frame_size_bytes2_);
if (frame_size.bytes() < avg_frame_size_bytes_ + deviation_size_bytes) {
// Only update the average frame size if this sample wasn't a key frame.
avg_frame_size_bytes_ = avg_frame_size_bytes;
}
double delta_bytes = frame_size.bytes() - avg_frame_size_bytes;
var_frame_size_bytes2_ = std::max(
kPhi * var_frame_size_bytes2_ + (1 - kPhi) * (delta_bytes * delta_bytes),
1.0);
// Update non-linear IIR estimate of max frame size.
max_frame_size_bytes_ =
std::max<double>(kPsi * max_frame_size_bytes_, frame_size.bytes());
// Maybe update percentile estimates of frame sizes.
if (config_.avg_frame_size_median) {
avg_frame_size_median_bytes_.Insert(frame_size.bytes());
}
if (config_.MaxFrameSizePercentileEnabled()) {
max_frame_size_bytes_percentile_.Insert(frame_size.bytes());
}
if (!prev_frame_size_) {
prev_frame_size_ = frame_size;
return;
}
prev_frame_size_ = frame_size;
// Cap frame_delay based on the current time deviation noise.
double num_stddev_delay_clamp =
config_.num_stddev_delay_clamp.value_or(kNumStdDevDelayClamp);
TimeDelta max_time_deviation =
TimeDelta::Millis(num_stddev_delay_clamp * sqrt(var_noise_ms2_) + 0.5);
frame_delay.Clamp(-max_time_deviation, max_time_deviation);
double delay_deviation_ms =
frame_delay.ms() -
kalman_filter_.GetFrameDelayVariationEstimateTotal(delta_frame_bytes);
// Outlier rejection: these conditions depend on filtered versions of the
// delay and frame size _means_, respectively, together with a configurable
// number of standard deviations. If a sample is large with respect to the
// corresponding mean and dispersion (defined by the number of
// standard deviations and the sample standard deviation), it is deemed an
// outlier. This "empirical rule" is further described in
// estimated means are true sample means, which implies that they are possibly
// not normally distributed. Hence, this rejection method is just a heuristic.
double num_stddev_delay_outlier =
config_.num_stddev_delay_outlier.value_or(kNumStdDevDelayOutlier);
// Delay outlier rejection is two-sided.
bool abs_delay_is_not_outlier =
fabs(delay_deviation_ms) <
num_stddev_delay_outlier * sqrt(var_noise_ms2_);
// The reasoning above means, in particular, that we should use the sample
// mean-style `avg_frame_size_bytes_` estimate, as opposed to the
// median-filtered version, even if configured to use latter for the
// calculation in `CalculateEstimate()`.
// Size outlier rejection is one-sided.
double num_stddev_size_outlier =
config_.num_stddev_size_outlier.value_or(kNumStdDevSizeOutlier);
bool size_is_positive_outlier =
frame_size.bytes() >
avg_frame_size_bytes_ +
num_stddev_size_outlier * sqrt(var_frame_size_bytes2_);
// 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.
if (abs_delay_is_not_outlier || size_is_positive_outlier) {
// 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.
double congestion_rejection_factor =
config_.congestion_rejection_factor.value_or(
kCongestionRejectionFactor);
double filtered_max_frame_size_bytes =
config_.MaxFrameSizePercentileEnabled()
? max_frame_size_bytes_percentile_.GetFilteredValue()
: max_frame_size_bytes_;
bool is_not_congested =
delta_frame_bytes >
congestion_rejection_factor * filtered_max_frame_size_bytes;
if (is_not_congested || config_.estimate_noise_when_congested) {
// Update the variance of the deviation from the line given by the Kalman
// filter.
EstimateRandomJitter(delay_deviation_ms);
}
if (is_not_congested) {
// Neither a delay outlier nor a congested frame, so we can safely update
// the Kalman filter with the sample.
kalman_filter_.PredictAndUpdate(frame_delay.ms(), delta_frame_bytes,
filtered_max_frame_size_bytes,
var_noise_ms2_);
}
} else {
// Delay outliers affect the noise estimate through a value equal to the
// outlier rejection threshold.
double num_stddev = (delay_deviation_ms >= 0) ? num_stddev_delay_outlier
: -num_stddev_delay_outlier;
EstimateRandomJitter(num_stddev * sqrt(var_noise_ms2_));
}
// Post process the total estimated jitter
if (startup_count_ >= kFrameProcessingStartupCount) {
PostProcessEstimate();
} else {
startup_count_++;
}
}
// Updates the nack/packet ratio.
void JitterEstimator::FrameNacked() {
if (nack_count_ < kNackLimit) {
nack_count_++;
}
latest_nack_ = clock_->CurrentTime();
}
void JitterEstimator::UpdateRtt(TimeDelta rtt) {
rtt_filter_.Update(rtt);
}
JitterEstimator::Config JitterEstimator::GetConfigForTest() const {
return config_;
}
// Estimates the random jitter by calculating the variance of the sample
// distance from the line given by the Kalman filter.
void JitterEstimator::EstimateRandomJitter(double d_dT) {
Timestamp now = clock_->CurrentTime();
if (last_update_time_.has_value()) {
fps_counter_.AddSample((now - *last_update_time_).us());
}
last_update_time_ = now;
if (alpha_count_ == 0) {
RTC_DCHECK_NOTREACHED();
return;
}
double alpha =
static_cast<double>(alpha_count_ - 1) / static_cast<double>(alpha_count_);
alpha_count_++;
if (alpha_count_ > kAlphaCountMax)
alpha_count_ = kAlphaCountMax;
// In order to avoid a low frame rate stream to react slower to changes,
// scale the alpha weight relative a 30 fps stream.
Frequency fps = GetFrameRate();
if (fps > Frequency::Zero()) {
constexpr Frequency k30Fps = Frequency::Hertz(30);
double rate_scale = k30Fps / 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 #kFrameProcessingStartupCount.
if (alpha_count_ < kFrameProcessingStartupCount) {
rate_scale = (alpha_count_ * rate_scale +
(kFrameProcessingStartupCount - alpha_count_)) /
kFrameProcessingStartupCount;
}
alpha = pow(alpha, rate_scale);
}
double avg_noise_ms = alpha * avg_noise_ms_ + (1 - alpha) * d_dT;
double var_noise_ms2 = alpha * var_noise_ms2_ + (1 - alpha) *
(d_dT - avg_noise_ms_) *
(d_dT - avg_noise_ms_);
avg_noise_ms_ = avg_noise_ms;
var_noise_ms2_ = var_noise_ms2;
if (var_noise_ms2_ < 1.0) {
// The variance should never be zero, since we might get stuck and consider
// all samples as outliers.
var_noise_ms2_ = 1.0;
}
}
double JitterEstimator::NoiseThreshold() const {
double noise_threshold_ms =
kNoiseStdDevs * sqrt(var_noise_ms2_) - kNoiseStdDevOffset;
if (noise_threshold_ms < 1.0) {
noise_threshold_ms = 1.0;
}
return noise_threshold_ms;
}
// Calculates the current jitter estimate from the filtered estimates.
TimeDelta JitterEstimator::CalculateEstimate() {
// Using median- and percentile-filtered versions of the frame sizes may be
// more robust than using sample mean-style estimates.
double filtered_avg_frame_size_bytes =
config_.avg_frame_size_median
? avg_frame_size_median_bytes_.GetFilteredValue()
: avg_frame_size_bytes_;
double filtered_max_frame_size_bytes =
config_.MaxFrameSizePercentileEnabled()
? max_frame_size_bytes_percentile_.GetFilteredValue()
: max_frame_size_bytes_;
double worst_case_frame_size_deviation_bytes =
filtered_max_frame_size_bytes - filtered_avg_frame_size_bytes;
double ret_ms = kalman_filter_.GetFrameDelayVariationEstimateSizeBased(
worst_case_frame_size_deviation_bytes) +
NoiseThreshold();
TimeDelta ret = TimeDelta::Millis(ret_ms);
// A very low estimate (or negative) is neglected.
if (ret < kMinJitterEstimate) {
ret = prev_estimate_.value_or(kMinJitterEstimate);
// Sanity check to make sure that no other method has set `prev_estimate_`
// to a value lower than `kMinJitterEstimate`.
RTC_DCHECK_GE(ret, kMinJitterEstimate);
} else if (ret > kMaxJitterEstimate) { // Sanity
ret = kMaxJitterEstimate;
}
prev_estimate_ = ret;
return ret;
}
void JitterEstimator::PostProcessEstimate() {
filter_jitter_estimate_ = CalculateEstimate();
}
// Returns the current filtered estimate if available,
// otherwise tries to calculate an estimate.
TimeDelta JitterEstimator::GetJitterEstimate(
double rtt_multiplier,
absl::optional<TimeDelta> rtt_mult_add_cap) {
TimeDelta jitter = CalculateEstimate() + OPERATING_SYSTEM_JITTER;
Timestamp now = clock_->CurrentTime();
if (now - latest_nack_ > kNackCountTimeout)
nack_count_ = 0;
if (filter_jitter_estimate_ > jitter)
jitter = filter_jitter_estimate_;
if (nack_count_ >= kNackLimit) {
if (rtt_mult_add_cap.has_value()) {
jitter += std::min(rtt_filter_.Rtt() * rtt_multiplier,
rtt_mult_add_cap.value());
} else {
jitter += rtt_filter_.Rtt() * rtt_multiplier;
}
}
static const Frequency kJitterScaleLowThreshold = Frequency::Hertz(5);
static const Frequency kJitterScaleHighThreshold = Frequency::Hertz(10);
Frequency fps = GetFrameRate();
// Ignore jitter for very low fps streams.
if (fps < kJitterScaleLowThreshold) {
if (fps.IsZero()) {
return std::max(TimeDelta::Zero(), jitter);
}
return TimeDelta::Zero();
}
// Semi-low frame rate; scale by factor linearly interpolated from 0.0 at
// kJitterScaleLowThreshold to 1.0 at kJitterScaleHighThreshold.
if (fps < kJitterScaleHighThreshold) {
jitter = (1.0 / (kJitterScaleHighThreshold - kJitterScaleLowThreshold)) *
(fps - kJitterScaleLowThreshold) * jitter;
}
return std::max(TimeDelta::Zero(), jitter);
}
Frequency JitterEstimator::GetFrameRate() const {
TimeDelta mean_frame_period = TimeDelta::Micros(fps_counter_.ComputeMean());
if (mean_frame_period <= TimeDelta::Zero())
return Frequency::Zero();
Frequency fps = 1 / mean_frame_period;
// Sanity check.
RTC_DCHECK_GE(fps, Frequency::Zero());
return std::min(fps, kMaxFramerateEstimate);
}
} // namespace webrtc