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