src/third_party/webrtc/modules/video_coding/main/source/jitter_estimator.cc

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