Home | History | Annotate | Download | only in video_coding 
      1 /*
      2  *  Copyright (c) 2011 The WebRTC project authors. All Rights Reserved.
      3  *
      4  *  Use of this source code is governed by a BSD-style license
      5  *  that can be found in the LICENSE file in the root of the source
      6  *  tree. An additional intellectual property rights grant can be found
      7  *  in the file PATENTS.  All contributing project authors may
      8  *  be found in the AUTHORS file in the root of the source tree.
      9  */
     10 
     11 #include "webrtc/modules/video_coding/jitter_estimator.h"
     12 
     13 #include <assert.h>
     14 #include <math.h>
     15 #include <stdlib.h>
     16 #include <string.h>
     17 #include <string>
     18 
     19 #include "webrtc/modules/video_coding/internal_defines.h"
     20 #include "webrtc/modules/video_coding/rtt_filter.h"
     21 #include "webrtc/system_wrappers/include/clock.h"
     22 #include "webrtc/system_wrappers/include/field_trial.h"
     23 
     24 namespace webrtc {
     25 
     26 enum { kStartupDelaySamples = 30 };
     27 enum { kFsAccuStartupSamples = 5 };
     28 enum { kMaxFramerateEstimate = 200 };
     29 
     30 VCMJitterEstimator::VCMJitterEstimator(const Clock* clock,
     31                                        int32_t vcmId,
     32                                        int32_t receiverId)
     33     : _vcmId(vcmId),
     34       _receiverId(receiverId),
     35       _phi(0.97),
     36       _psi(0.9999),
     37       _alphaCountMax(400),
     38       _thetaLow(0.000001),
     39       _nackLimit(3),
     40       _numStdDevDelayOutlier(15),
     41       _numStdDevFrameSizeOutlier(3),
     42       _noiseStdDevs(2.33),       // ~Less than 1% chance
     43                                  // (look up in normal distribution table)...
     44       _noiseStdDevOffset(30.0),  // ...of getting 30 ms freezes
     45       _rttFilter(),
     46       fps_counter_(30),  // TODO(sprang): Use an estimator with limit based on
     47                          // time, rather than number of samples.
     48       low_rate_experiment_(kInit),
     49       clock_(clock) {
     50   Reset();
     51 }
     52 
     53 VCMJitterEstimator::~VCMJitterEstimator() {}
     54 
     55 VCMJitterEstimator& VCMJitterEstimator::operator=(
     56     const VCMJitterEstimator& rhs) {
     57   if (this != &rhs) {
     58     memcpy(_thetaCov, rhs._thetaCov, sizeof(_thetaCov));
     59     memcpy(_Qcov, rhs._Qcov, sizeof(_Qcov));
     60 
     61     _vcmId = rhs._vcmId;
     62     _receiverId = rhs._receiverId;
     63     _avgFrameSize = rhs._avgFrameSize;
     64     _varFrameSize = rhs._varFrameSize;
     65     _maxFrameSize = rhs._maxFrameSize;
     66     _fsSum = rhs._fsSum;
     67     _fsCount = rhs._fsCount;
     68     _lastUpdateT = rhs._lastUpdateT;
     69     _prevEstimate = rhs._prevEstimate;
     70     _prevFrameSize = rhs._prevFrameSize;
     71     _avgNoise = rhs._avgNoise;
     72     _alphaCount = rhs._alphaCount;
     73     _filterJitterEstimate = rhs._filterJitterEstimate;
     74     _startupCount = rhs._startupCount;
     75     _latestNackTimestamp = rhs._latestNackTimestamp;
     76     _nackCount = rhs._nackCount;
     77     _rttFilter = rhs._rttFilter;
     78   }
     79   return *this;
     80 }
     81 
     82 // Resets the JitterEstimate
     83 void VCMJitterEstimator::Reset() {
     84   _theta[0] = 1 / (512e3 / 8);
     85   _theta[1] = 0;
     86   _varNoise = 4.0;
     87 
     88   _thetaCov[0][0] = 1e-4;
     89   _thetaCov[1][1] = 1e2;
     90   _thetaCov[0][1] = _thetaCov[1][0] = 0;
     91   _Qcov[0][0] = 2.5e-10;
     92   _Qcov[1][1] = 1e-10;
     93   _Qcov[0][1] = _Qcov[1][0] = 0;
     94   _avgFrameSize = 500;
     95   _maxFrameSize = 500;
     96   _varFrameSize = 100;
     97   _lastUpdateT = -1;
     98   _prevEstimate = -1.0;
     99   _prevFrameSize = 0;
    100   _avgNoise = 0.0;
    101   _alphaCount = 1;
    102   _filterJitterEstimate = 0.0;
    103   _latestNackTimestamp = 0;
    104   _nackCount = 0;
    105   _fsSum = 0;
    106   _fsCount = 0;
    107   _startupCount = 0;
    108   _rttFilter.Reset();
    109   fps_counter_.Reset();
    110 }
    111 
    112 void VCMJitterEstimator::ResetNackCount() {
    113   _nackCount = 0;
    114 }
    115 
    116 // Updates the estimates with the new measurements
    117 void VCMJitterEstimator::UpdateEstimate(int64_t frameDelayMS,
    118                                         uint32_t frameSizeBytes,
    119                                         bool incompleteFrame /* = false */) {
    120   if (frameSizeBytes == 0) {
    121     return;
    122   }
    123   int deltaFS = frameSizeBytes - _prevFrameSize;
    124   if (_fsCount < kFsAccuStartupSamples) {
    125     _fsSum += frameSizeBytes;
    126     _fsCount++;
    127   } else if (_fsCount == kFsAccuStartupSamples) {
    128     // Give the frame size filter
    129     _avgFrameSize = static_cast<double>(_fsSum) / static_cast<double>(_fsCount);
    130     _fsCount++;
    131   }
    132   if (!incompleteFrame || frameSizeBytes > _avgFrameSize) {
    133     double avgFrameSize = _phi * _avgFrameSize + (1 - _phi) * frameSizeBytes;
    134     if (frameSizeBytes < _avgFrameSize + 2 * sqrt(_varFrameSize)) {
    135       // Only update the average frame size if this sample wasn't a
    136       // key frame
    137       _avgFrameSize = avgFrameSize;
    138     }
    139     // Update the variance anyway since we want to capture cases where we only
    140     // get
    141     // key frames.
    142     _varFrameSize = VCM_MAX(_phi * _varFrameSize +
    143                                 (1 - _phi) * (frameSizeBytes - avgFrameSize) *
    144                                     (frameSizeBytes - avgFrameSize),
    145                             1.0);
    146   }
    147 
    148   // Update max frameSize estimate
    149   _maxFrameSize =
    150       VCM_MAX(_psi * _maxFrameSize, static_cast<double>(frameSizeBytes));
    151 
    152   if (_prevFrameSize == 0) {
    153     _prevFrameSize = frameSizeBytes;
    154     return;
    155   }
    156   _prevFrameSize = frameSizeBytes;
    157 
    158   // Only update the Kalman filter if the sample is not considered
    159   // an extreme outlier. Even if it is an extreme outlier from a
    160   // delay point of view, if the frame size also is large the
    161   // deviation is probably due to an incorrect line slope.
    162   double deviation = DeviationFromExpectedDelay(frameDelayMS, deltaFS);
    163 
    164   if (fabs(deviation) < _numStdDevDelayOutlier * sqrt(_varNoise) ||
    165       frameSizeBytes >
    166           _avgFrameSize + _numStdDevFrameSizeOutlier * sqrt(_varFrameSize)) {
    167     // Update the variance of the deviation from the
    168     // line given by the Kalman filter
    169     EstimateRandomJitter(deviation, incompleteFrame);
    170     // Prevent updating with frames which have been congested by a large
    171     // frame, and therefore arrives almost at the same time as that frame.
    172     // This can occur when we receive a large frame (key frame) which
    173     // has been delayed. The next frame is of normal size (delta frame),
    174     // and thus deltaFS will be << 0. This removes all frame samples
    175     // which arrives after a key frame.
    176     if ((!incompleteFrame || deviation >= 0.0) &&
    177         static_cast<double>(deltaFS) > -0.25 * _maxFrameSize) {
    178       // Update the Kalman filter with the new data
    179       KalmanEstimateChannel(frameDelayMS, deltaFS);
    180     }
    181   } else {
    182     int nStdDev =
    183         (deviation >= 0) ? _numStdDevDelayOutlier : -_numStdDevDelayOutlier;
    184     EstimateRandomJitter(nStdDev * sqrt(_varNoise), incompleteFrame);
    185   }
    186   // Post process the total estimated jitter
    187   if (_startupCount >= kStartupDelaySamples) {
    188     PostProcessEstimate();
    189   } else {
    190     _startupCount++;
    191   }
    192 }
    193 
    194 // Updates the nack/packet ratio
    195 void VCMJitterEstimator::FrameNacked() {
    196   // Wait until _nackLimit retransmissions has been received,
    197   // then always add ~1 RTT delay.
    198   // TODO(holmer): Should we ever remove the additional delay if the
    199   // the packet losses seem to have stopped? We could for instance scale
    200   // the number of RTTs to add with the amount of retransmissions in a given
    201   // time interval, or similar.
    202   if (_nackCount < _nackLimit) {
    203     _nackCount++;
    204   }
    205 }
    206 
    207 // Updates Kalman estimate of the channel
    208 // The caller is expected to sanity check the inputs.
    209 void VCMJitterEstimator::KalmanEstimateChannel(int64_t frameDelayMS,
    210                                                int32_t deltaFSBytes) {
    211   double Mh[2];
    212   double hMh_sigma;
    213   double kalmanGain[2];
    214   double measureRes;
    215   double t00, t01;
    216 
    217   // Kalman filtering
    218 
    219   // Prediction
    220   // M = M + Q
    221   _thetaCov[0][0] += _Qcov[0][0];
    222   _thetaCov[0][1] += _Qcov[0][1];
    223   _thetaCov[1][0] += _Qcov[1][0];
    224   _thetaCov[1][1] += _Qcov[1][1];
    225 
    226   // Kalman gain
    227   // K = M*h'/(sigma2n + h*M*h') = M*h'/(1 + h*M*h')
    228   // h = [dFS 1]
    229   // Mh = M*h'
    230   // hMh_sigma = h*M*h' + R
    231   Mh[0] = _thetaCov[0][0] * deltaFSBytes + _thetaCov[0][1];
    232   Mh[1] = _thetaCov[1][0] * deltaFSBytes + _thetaCov[1][1];
    233   // sigma weights measurements with a small deltaFS as noisy and
    234   // measurements with large deltaFS as good
    235   if (_maxFrameSize < 1.0) {
    236     return;
    237   }
    238   double sigma = (300.0 * exp(-fabs(static_cast<double>(deltaFSBytes)) /
    239                               (1e0 * _maxFrameSize)) +
    240                   1) *
    241                  sqrt(_varNoise);
    242   if (sigma < 1.0) {
    243     sigma = 1.0;
    244   }
    245   hMh_sigma = deltaFSBytes * Mh[0] + Mh[1] + sigma;
    246   if ((hMh_sigma < 1e-9 && hMh_sigma >= 0) ||
    247       (hMh_sigma > -1e-9 && hMh_sigma <= 0)) {
    248     assert(false);
    249     return;
    250   }
    251   kalmanGain[0] = Mh[0] / hMh_sigma;
    252   kalmanGain[1] = Mh[1] / hMh_sigma;
    253 
    254   // Correction
    255   // theta = theta + K*(dT - h*theta)
    256   measureRes = frameDelayMS - (deltaFSBytes * _theta[0] + _theta[1]);
    257   _theta[0] += kalmanGain[0] * measureRes;
    258   _theta[1] += kalmanGain[1] * measureRes;
    259 
    260   if (_theta[0] < _thetaLow) {
    261     _theta[0] = _thetaLow;
    262   }
    263 
    264   // M = (I - K*h)*M
    265   t00 = _thetaCov[0][0];
    266   t01 = _thetaCov[0][1];
    267   _thetaCov[0][0] = (1 - kalmanGain[0] * deltaFSBytes) * t00 -
    268                     kalmanGain[0] * _thetaCov[1][0];
    269   _thetaCov[0][1] = (1 - kalmanGain[0] * deltaFSBytes) * t01 -
    270                     kalmanGain[0] * _thetaCov[1][1];
    271   _thetaCov[1][0] = _thetaCov[1][0] * (1 - kalmanGain[1]) -
    272                     kalmanGain[1] * deltaFSBytes * t00;
    273   _thetaCov[1][1] = _thetaCov[1][1] * (1 - kalmanGain[1]) -
    274                     kalmanGain[1] * deltaFSBytes * t01;
    275 
    276   // Covariance matrix, must be positive semi-definite
    277   assert(_thetaCov[0][0] + _thetaCov[1][1] >= 0 &&
    278          _thetaCov[0][0] * _thetaCov[1][1] -
    279                  _thetaCov[0][1] * _thetaCov[1][0] >=
    280              0 &&
    281          _thetaCov[0][0] >= 0);
    282 }
    283 
    284 // Calculate difference in delay between a sample and the
    285 // expected delay estimated by the Kalman filter
    286 double VCMJitterEstimator::DeviationFromExpectedDelay(
    287     int64_t frameDelayMS,
    288     int32_t deltaFSBytes) const {
    289   return frameDelayMS - (_theta[0] * deltaFSBytes + _theta[1]);
    290 }
    291 
    292 // Estimates the random jitter by calculating the variance of the
    293 // sample distance from the line given by theta.
    294 void VCMJitterEstimator::EstimateRandomJitter(double d_dT,
    295                                               bool incompleteFrame) {
    296   uint64_t now = clock_->TimeInMicroseconds();
    297   if (_lastUpdateT != -1) {
    298     fps_counter_.AddSample(now - _lastUpdateT);
    299   }
    300   _lastUpdateT = now;
    301 
    302   if (_alphaCount == 0) {
    303     assert(false);
    304     return;
    305   }
    306   double alpha =
    307       static_cast<double>(_alphaCount - 1) / static_cast<double>(_alphaCount);
    308   _alphaCount++;
    309   if (_alphaCount > _alphaCountMax)
    310     _alphaCount = _alphaCountMax;
    311 
    312   if (LowRateExperimentEnabled()) {
    313     // In order to avoid a low frame rate stream to react slower to changes,
    314     // scale the alpha weight relative a 30 fps stream.
    315     double fps = GetFrameRate();
    316     if (fps > 0.0) {
    317       double rate_scale = 30.0 / fps;
    318       // At startup, there can be a lot of noise in the fps estimate.
    319       // Interpolate rate_scale linearly, from 1.0 at sample #1, to 30.0 / fps
    320       // at sample #kStartupDelaySamples.
    321       if (_alphaCount < kStartupDelaySamples) {
    322         rate_scale =
    323             (_alphaCount * rate_scale + (kStartupDelaySamples - _alphaCount)) /
    324             kStartupDelaySamples;
    325       }
    326       alpha = pow(alpha, rate_scale);
    327     }
    328   }
    329 
    330   double avgNoise = alpha * _avgNoise + (1 - alpha) * d_dT;
    331   double varNoise =
    332       alpha * _varNoise + (1 - alpha) * (d_dT - _avgNoise) * (d_dT - _avgNoise);
    333   if (!incompleteFrame || varNoise > _varNoise) {
    334     _avgNoise = avgNoise;
    335     _varNoise = varNoise;
    336   }
    337   if (_varNoise < 1.0) {
    338     // The variance should never be zero, since we might get
    339     // stuck and consider all samples as outliers.
    340     _varNoise = 1.0;
    341   }
    342 }
    343 
    344 double VCMJitterEstimator::NoiseThreshold() const {
    345   double noiseThreshold = _noiseStdDevs * sqrt(_varNoise) - _noiseStdDevOffset;
    346   if (noiseThreshold < 1.0) {
    347     noiseThreshold = 1.0;
    348   }
    349   return noiseThreshold;
    350 }
    351 
    352 // Calculates the current jitter estimate from the filtered estimates
    353 double VCMJitterEstimator::CalculateEstimate() {
    354   double ret = _theta[0] * (_maxFrameSize - _avgFrameSize) + NoiseThreshold();
    355 
    356   // A very low estimate (or negative) is neglected
    357   if (ret < 1.0) {
    358     if (_prevEstimate <= 0.01) {
    359       ret = 1.0;
    360     } else {
    361       ret = _prevEstimate;
    362     }
    363   }
    364   if (ret > 10000.0) {  // Sanity
    365     ret = 10000.0;
    366   }
    367   _prevEstimate = ret;
    368   return ret;
    369 }
    370 
    371 void VCMJitterEstimator::PostProcessEstimate() {
    372   _filterJitterEstimate = CalculateEstimate();
    373 }
    374 
    375 void VCMJitterEstimator::UpdateRtt(int64_t rttMs) {
    376   _rttFilter.Update(rttMs);
    377 }
    378 
    379 void VCMJitterEstimator::UpdateMaxFrameSize(uint32_t frameSizeBytes) {
    380   if (_maxFrameSize < frameSizeBytes) {
    381     _maxFrameSize = frameSizeBytes;
    382   }
    383 }
    384 
    385 // Returns the current filtered estimate if available,
    386 // otherwise tries to calculate an estimate.
    387 int VCMJitterEstimator::GetJitterEstimate(double rttMultiplier) {
    388   double jitterMS = CalculateEstimate() + OPERATING_SYSTEM_JITTER;
    389   if (_filterJitterEstimate > jitterMS)
    390     jitterMS = _filterJitterEstimate;
    391   if (_nackCount >= _nackLimit)
    392     jitterMS += _rttFilter.RttMs() * rttMultiplier;
    393 
    394   if (LowRateExperimentEnabled()) {
    395     static const double kJitterScaleLowThreshold = 5.0;
    396     static const double kJitterScaleHighThreshold = 10.0;
    397     double fps = GetFrameRate();
    398     // Ignore jitter for very low fps streams.
    399     if (fps < kJitterScaleLowThreshold) {
    400       if (fps == 0.0) {
    401         return jitterMS;
    402       }
    403       return 0;
    404     }
    405 
    406     // Semi-low frame rate; scale by factor linearly interpolated from 0.0 at
    407     // kJitterScaleLowThreshold to 1.0 at kJitterScaleHighThreshold.
    408     if (fps < kJitterScaleHighThreshold) {
    409       jitterMS =
    410           (1.0 / (kJitterScaleHighThreshold - kJitterScaleLowThreshold)) *
    411           (fps - kJitterScaleLowThreshold) * jitterMS;
    412     }
    413   }
    414 
    415   return static_cast<uint32_t>(jitterMS + 0.5);
    416 }
    417 
    418 bool VCMJitterEstimator::LowRateExperimentEnabled() {
    419   if (low_rate_experiment_ == kInit) {
    420     std::string group =
    421         webrtc::field_trial::FindFullName("WebRTC-ReducedJitterDelay");
    422     if (group == "Disabled") {
    423       low_rate_experiment_ = kDisabled;
    424     } else {
    425       low_rate_experiment_ = kEnabled;
    426     }
    427   }
    428   return low_rate_experiment_ == kEnabled ? true : false;
    429 }
    430 
    431 double VCMJitterEstimator::GetFrameRate() const {
    432   if (fps_counter_.count() == 0)
    433     return 0;
    434 
    435   double fps = 1000000.0 / fps_counter_.ComputeMean();
    436   // Sanity check.
    437   assert(fps >= 0.0);
    438   if (fps > kMaxFramerateEstimate) {
    439     fps = kMaxFramerateEstimate;
    440   }
    441   return fps;
    442 }
    443 }  // namespace webrtc
    444