Line data Source code
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 0 : VCMJitterEstimator::VCMJitterEstimator(const Clock* clock,
31 : int32_t vcmId,
32 0 : 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 0 : clock_(clock) {
50 0 : Reset();
51 0 : }
52 :
53 0 : VCMJitterEstimator::~VCMJitterEstimator() {}
54 :
55 0 : VCMJitterEstimator& VCMJitterEstimator::operator=(
56 : const VCMJitterEstimator& rhs) {
57 0 : if (this != &rhs) {
58 0 : memcpy(_thetaCov, rhs._thetaCov, sizeof(_thetaCov));
59 0 : memcpy(_Qcov, rhs._Qcov, sizeof(_Qcov));
60 :
61 0 : _vcmId = rhs._vcmId;
62 0 : _receiverId = rhs._receiverId;
63 0 : _avgFrameSize = rhs._avgFrameSize;
64 0 : _varFrameSize = rhs._varFrameSize;
65 0 : _maxFrameSize = rhs._maxFrameSize;
66 0 : _fsSum = rhs._fsSum;
67 0 : _fsCount = rhs._fsCount;
68 0 : _lastUpdateT = rhs._lastUpdateT;
69 0 : _prevEstimate = rhs._prevEstimate;
70 0 : _prevFrameSize = rhs._prevFrameSize;
71 0 : _avgNoise = rhs._avgNoise;
72 0 : _alphaCount = rhs._alphaCount;
73 0 : _filterJitterEstimate = rhs._filterJitterEstimate;
74 0 : _startupCount = rhs._startupCount;
75 0 : _latestNackTimestamp = rhs._latestNackTimestamp;
76 0 : _nackCount = rhs._nackCount;
77 0 : _rttFilter = rhs._rttFilter;
78 : }
79 0 : return *this;
80 : }
81 :
82 : // Resets the JitterEstimate
83 0 : void VCMJitterEstimator::Reset() {
84 0 : _theta[0] = 1 / (512e3 / 8);
85 0 : _theta[1] = 0;
86 0 : _varNoise = 4.0;
87 :
88 0 : _thetaCov[0][0] = 1e-4;
89 0 : _thetaCov[1][1] = 1e2;
90 0 : _thetaCov[0][1] = _thetaCov[1][0] = 0;
91 0 : _Qcov[0][0] = 2.5e-10;
92 0 : _Qcov[1][1] = 1e-10;
93 0 : _Qcov[0][1] = _Qcov[1][0] = 0;
94 0 : _avgFrameSize = 500;
95 0 : _maxFrameSize = 500;
96 0 : _varFrameSize = 100;
97 0 : _lastUpdateT = -1;
98 0 : _prevEstimate = -1.0;
99 0 : _prevFrameSize = 0;
100 0 : _avgNoise = 0.0;
101 0 : _alphaCount = 1;
102 0 : _filterJitterEstimate = 0.0;
103 0 : _latestNackTimestamp = 0;
104 0 : _nackCount = 0;
105 0 : _fsSum = 0;
106 0 : _fsCount = 0;
107 0 : _startupCount = 0;
108 0 : _rttFilter.Reset();
109 0 : fps_counter_.Reset();
110 0 : }
111 :
112 0 : void VCMJitterEstimator::ResetNackCount() {
113 0 : _nackCount = 0;
114 0 : }
115 :
116 : // Updates the estimates with the new measurements
117 0 : void VCMJitterEstimator::UpdateEstimate(int64_t frameDelayMS,
118 : uint32_t frameSizeBytes,
119 : bool incompleteFrame /* = false */) {
120 0 : if (frameSizeBytes == 0) {
121 0 : return;
122 : }
123 0 : int deltaFS = frameSizeBytes - _prevFrameSize;
124 0 : if (_fsCount < kFsAccuStartupSamples) {
125 0 : _fsSum += frameSizeBytes;
126 0 : _fsCount++;
127 0 : } else if (_fsCount == kFsAccuStartupSamples) {
128 : // Give the frame size filter
129 0 : _avgFrameSize = static_cast<double>(_fsSum) / static_cast<double>(_fsCount);
130 0 : _fsCount++;
131 : }
132 0 : if (!incompleteFrame || frameSizeBytes > _avgFrameSize) {
133 0 : double avgFrameSize = _phi * _avgFrameSize + (1 - _phi) * frameSizeBytes;
134 0 : if (frameSizeBytes < _avgFrameSize + 2 * sqrt(_varFrameSize)) {
135 : // Only update the average frame size if this sample wasn't a
136 : // key frame
137 0 : _avgFrameSize = avgFrameSize;
138 : }
139 : // Update the variance anyway since we want to capture cases where we only
140 : // get
141 : // key frames.
142 0 : _varFrameSize = VCM_MAX(_phi * _varFrameSize +
143 : (1 - _phi) * (frameSizeBytes - avgFrameSize) *
144 : (frameSizeBytes - avgFrameSize),
145 : 1.0);
146 : }
147 :
148 : // Update max frameSize estimate
149 0 : _maxFrameSize =
150 0 : VCM_MAX(_psi * _maxFrameSize, static_cast<double>(frameSizeBytes));
151 :
152 0 : if (_prevFrameSize == 0) {
153 0 : _prevFrameSize = frameSizeBytes;
154 0 : return;
155 : }
156 0 : _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 0 : double deviation = DeviationFromExpectedDelay(frameDelayMS, deltaFS);
163 :
164 0 : if (fabs(deviation) < _numStdDevDelayOutlier * sqrt(_varNoise) ||
165 0 : frameSizeBytes >
166 0 : _avgFrameSize + _numStdDevFrameSizeOutlier * sqrt(_varFrameSize)) {
167 : // Update the variance of the deviation from the
168 : // line given by the Kalman filter
169 0 : 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 0 : if ((!incompleteFrame || deviation >= 0.0) &&
177 0 : static_cast<double>(deltaFS) > -0.25 * _maxFrameSize) {
178 : // Update the Kalman filter with the new data
179 0 : KalmanEstimateChannel(frameDelayMS, deltaFS);
180 : }
181 : } else {
182 : int nStdDev =
183 0 : (deviation >= 0) ? _numStdDevDelayOutlier : -_numStdDevDelayOutlier;
184 0 : EstimateRandomJitter(nStdDev * sqrt(_varNoise), incompleteFrame);
185 : }
186 : // Post process the total estimated jitter
187 0 : if (_startupCount >= kStartupDelaySamples) {
188 0 : PostProcessEstimate();
189 : } else {
190 0 : _startupCount++;
191 : }
192 : }
193 :
194 : // Updates the nack/packet ratio
195 0 : 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 0 : if (_nackCount < _nackLimit) {
203 0 : _nackCount++;
204 : }
205 0 : }
206 :
207 : // Updates Kalman estimate of the channel
208 : // The caller is expected to sanity check the inputs.
209 0 : 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 0 : _thetaCov[0][0] += _Qcov[0][0];
222 0 : _thetaCov[0][1] += _Qcov[0][1];
223 0 : _thetaCov[1][0] += _Qcov[1][0];
224 0 : _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 0 : Mh[0] = _thetaCov[0][0] * deltaFSBytes + _thetaCov[0][1];
232 0 : 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 0 : if (_maxFrameSize < 1.0) {
236 0 : return;
237 : }
238 0 : double sigma = (300.0 * exp(-fabs(static_cast<double>(deltaFSBytes)) /
239 0 : (1e0 * _maxFrameSize)) +
240 : 1) *
241 0 : sqrt(_varNoise);
242 0 : if (sigma < 1.0) {
243 0 : sigma = 1.0;
244 : }
245 0 : hMh_sigma = deltaFSBytes * Mh[0] + Mh[1] + sigma;
246 0 : if ((hMh_sigma < 1e-9 && hMh_sigma >= 0) ||
247 0 : (hMh_sigma > -1e-9 && hMh_sigma <= 0)) {
248 0 : assert(false);
249 : return;
250 : }
251 0 : kalmanGain[0] = Mh[0] / hMh_sigma;
252 0 : kalmanGain[1] = Mh[1] / hMh_sigma;
253 :
254 : // Correction
255 : // theta = theta + K*(dT - h*theta)
256 0 : measureRes = frameDelayMS - (deltaFSBytes * _theta[0] + _theta[1]);
257 0 : _theta[0] += kalmanGain[0] * measureRes;
258 0 : _theta[1] += kalmanGain[1] * measureRes;
259 :
260 0 : if (_theta[0] < _thetaLow) {
261 0 : _theta[0] = _thetaLow;
262 : }
263 :
264 : // M = (I - K*h)*M
265 0 : t00 = _thetaCov[0][0];
266 0 : t01 = _thetaCov[0][1];
267 0 : _thetaCov[0][0] = (1 - kalmanGain[0] * deltaFSBytes) * t00 -
268 0 : kalmanGain[0] * _thetaCov[1][0];
269 0 : _thetaCov[0][1] = (1 - kalmanGain[0] * deltaFSBytes) * t01 -
270 0 : kalmanGain[0] * _thetaCov[1][1];
271 0 : _thetaCov[1][0] = _thetaCov[1][0] * (1 - kalmanGain[1]) -
272 0 : kalmanGain[1] * deltaFSBytes * t00;
273 0 : _thetaCov[1][1] = _thetaCov[1][1] * (1 - kalmanGain[1]) -
274 0 : kalmanGain[1] * deltaFSBytes * t01;
275 :
276 : // Covariance matrix, must be positive semi-definite
277 0 : 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 0 : double VCMJitterEstimator::DeviationFromExpectedDelay(
287 : int64_t frameDelayMS,
288 : int32_t deltaFSBytes) const {
289 0 : 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 0 : void VCMJitterEstimator::EstimateRandomJitter(double d_dT,
295 : bool incompleteFrame) {
296 0 : uint64_t now = clock_->TimeInMicroseconds();
297 0 : if (_lastUpdateT != -1) {
298 0 : fps_counter_.AddSample(now - _lastUpdateT);
299 : }
300 0 : _lastUpdateT = now;
301 :
302 0 : if (_alphaCount == 0) {
303 0 : assert(false);
304 : return;
305 : }
306 : double alpha =
307 0 : static_cast<double>(_alphaCount - 1) / static_cast<double>(_alphaCount);
308 0 : _alphaCount++;
309 0 : if (_alphaCount > _alphaCountMax)
310 0 : _alphaCount = _alphaCountMax;
311 :
312 0 : 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 0 : double fps = GetFrameRate();
316 0 : if (fps > 0.0) {
317 0 : 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 0 : if (_alphaCount < kStartupDelaySamples) {
322 0 : rate_scale =
323 0 : (_alphaCount * rate_scale + (kStartupDelaySamples - _alphaCount)) /
324 : kStartupDelaySamples;
325 : }
326 0 : alpha = pow(alpha, rate_scale);
327 : }
328 : }
329 :
330 0 : double avgNoise = alpha * _avgNoise + (1 - alpha) * d_dT;
331 : double varNoise =
332 0 : alpha * _varNoise + (1 - alpha) * (d_dT - _avgNoise) * (d_dT - _avgNoise);
333 0 : if (!incompleteFrame || varNoise > _varNoise) {
334 0 : _avgNoise = avgNoise;
335 0 : _varNoise = varNoise;
336 : }
337 0 : if (_varNoise < 1.0) {
338 : // The variance should never be zero, since we might get
339 : // stuck and consider all samples as outliers.
340 0 : _varNoise = 1.0;
341 : }
342 : }
343 :
344 0 : double VCMJitterEstimator::NoiseThreshold() const {
345 0 : double noiseThreshold = _noiseStdDevs * sqrt(_varNoise) - _noiseStdDevOffset;
346 0 : if (noiseThreshold < 1.0) {
347 0 : noiseThreshold = 1.0;
348 : }
349 0 : return noiseThreshold;
350 : }
351 :
352 : // Calculates the current jitter estimate from the filtered estimates
353 0 : double VCMJitterEstimator::CalculateEstimate() {
354 0 : double ret = _theta[0] * (_maxFrameSize - _avgFrameSize) + NoiseThreshold();
355 :
356 : // A very low estimate (or negative) is neglected
357 0 : if (ret < 1.0) {
358 0 : if (_prevEstimate <= 0.01) {
359 0 : ret = 1.0;
360 : } else {
361 0 : ret = _prevEstimate;
362 : }
363 : }
364 0 : if (ret > 10000.0) { // Sanity
365 0 : ret = 10000.0;
366 : }
367 0 : _prevEstimate = ret;
368 0 : return ret;
369 : }
370 :
371 0 : void VCMJitterEstimator::PostProcessEstimate() {
372 0 : _filterJitterEstimate = CalculateEstimate();
373 0 : }
374 :
375 0 : void VCMJitterEstimator::UpdateRtt(int64_t rttMs) {
376 0 : _rttFilter.Update(rttMs);
377 0 : }
378 :
379 0 : void VCMJitterEstimator::UpdateMaxFrameSize(uint32_t frameSizeBytes) {
380 0 : if (_maxFrameSize < frameSizeBytes) {
381 0 : _maxFrameSize = frameSizeBytes;
382 : }
383 0 : }
384 :
385 : // Returns the current filtered estimate if available,
386 : // otherwise tries to calculate an estimate.
387 0 : int VCMJitterEstimator::GetJitterEstimate(double rttMultiplier) {
388 0 : double jitterMS = CalculateEstimate() + OPERATING_SYSTEM_JITTER;
389 0 : if (_filterJitterEstimate > jitterMS)
390 0 : jitterMS = _filterJitterEstimate;
391 0 : if (_nackCount >= _nackLimit)
392 0 : jitterMS += _rttFilter.RttMs() * rttMultiplier;
393 :
394 0 : if (LowRateExperimentEnabled()) {
395 : static const double kJitterScaleLowThreshold = 5.0;
396 : static const double kJitterScaleHighThreshold = 10.0;
397 0 : double fps = GetFrameRate();
398 : // Ignore jitter for very low fps streams.
399 0 : if (fps < kJitterScaleLowThreshold) {
400 0 : if (fps == 0.0) {
401 0 : return jitterMS;
402 : }
403 0 : 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 0 : if (fps < kJitterScaleHighThreshold) {
409 0 : jitterMS =
410 0 : (1.0 / (kJitterScaleHighThreshold - kJitterScaleLowThreshold)) *
411 0 : (fps - kJitterScaleLowThreshold) * jitterMS;
412 : }
413 : }
414 :
415 0 : return static_cast<uint32_t>(jitterMS + 0.5);
416 : }
417 :
418 0 : bool VCMJitterEstimator::LowRateExperimentEnabled() {
419 0 : if (low_rate_experiment_ == kInit) {
420 : std::string group =
421 0 : webrtc::field_trial::FindFullName("WebRTC-ReducedJitterDelay");
422 0 : if (group == "Disabled") {
423 0 : low_rate_experiment_ = kDisabled;
424 : } else {
425 0 : low_rate_experiment_ = kEnabled;
426 : }
427 : }
428 0 : return low_rate_experiment_ == kEnabled ? true : false;
429 : }
430 :
431 0 : double VCMJitterEstimator::GetFrameRate() const {
432 0 : if (fps_counter_.ComputeMean() == 0.0)
433 0 : return 0;
434 :
435 0 : double fps = 1000000.0 / fps_counter_.ComputeMean();
436 : // Sanity check.
437 0 : assert(fps >= 0.0);
438 0 : if (fps > kMaxFramerateEstimate) {
439 0 : fps = kMaxFramerateEstimate;
440 : }
441 0 : return fps;
442 : }
443 : } // namespace webrtc
|
