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
VCMJitterEstimator(const Clock * clock,int32_t vcmId,int32_t receiverId)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
~VCMJitterEstimator()53 VCMJitterEstimator::~VCMJitterEstimator() {}
54
operator =(const VCMJitterEstimator & rhs)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
Reset()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
ResetNackCount()112 void VCMJitterEstimator::ResetNackCount() {
113 _nackCount = 0;
114 }
115
116 // Updates the estimates with the new measurements
UpdateEstimate(int64_t frameDelayMS,uint32_t frameSizeBytes,bool incompleteFrame)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
FrameNacked()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.
KalmanEstimateChannel(int64_t frameDelayMS,int32_t deltaFSBytes)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
DeviationFromExpectedDelay(int64_t frameDelayMS,int32_t deltaFSBytes) const286 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.
EstimateRandomJitter(double d_dT,bool incompleteFrame)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
NoiseThreshold() const344 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
CalculateEstimate()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
PostProcessEstimate()371 void VCMJitterEstimator::PostProcessEstimate() {
372 _filterJitterEstimate = CalculateEstimate();
373 }
374
UpdateRtt(int64_t rttMs)375 void VCMJitterEstimator::UpdateRtt(int64_t rttMs) {
376 _rttFilter.Update(rttMs);
377 }
378
UpdateMaxFrameSize(uint32_t frameSizeBytes)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.
GetJitterEstimate(double rttMultiplier)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
LowRateExperimentEnabled()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
GetFrameRate() const431 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