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 } 406