1 /* 2 * Copyright (c) 2012 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 <math.h> 12 #include <stdlib.h> // fabsf 13 14 #include "webrtc/modules/remote_bitrate_estimator/overuse_detector.h" 15 #include "webrtc/modules/remote_bitrate_estimator/remote_rate_control.h" 16 #include "webrtc/modules/rtp_rtcp/source/rtp_utility.h" 17 #include "webrtc/system_wrappers/interface/trace.h" 18 19 enum { kOverUsingTimeThreshold = 100 }; 20 enum { kMinFramePeriodHistoryLength = 60 }; 21 22 namespace webrtc { 23 OveruseDetector::OveruseDetector(const OverUseDetectorOptions& options) 24 : options_(options), 25 current_frame_(), 26 prev_frame_(), 27 num_of_deltas_(0), 28 slope_(options_.initial_slope), 29 offset_(options_.initial_offset), 30 E_(), 31 process_noise_(), 32 avg_noise_(options_.initial_avg_noise), 33 var_noise_(options_.initial_var_noise), 34 threshold_(options_.initial_threshold), 35 ts_delta_hist_(), 36 prev_offset_(0.0), 37 time_over_using_(-1), 38 over_use_counter_(0), 39 hypothesis_(kBwNormal) { 40 memcpy(E_, options_.initial_e, sizeof(E_)); 41 memcpy(process_noise_, options_.initial_process_noise, 42 sizeof(process_noise_)); 43 } 44 45 OveruseDetector::~OveruseDetector() { 46 ts_delta_hist_.clear(); 47 } 48 49 void OveruseDetector::Update(uint16_t packet_size, 50 int64_t timestamp_ms, 51 uint32_t timestamp, 52 const int64_t arrival_time_ms) { 53 bool new_timestamp = (timestamp != current_frame_.timestamp); 54 if (timestamp_ms >= 0) { 55 if (prev_frame_.timestamp_ms == -1 && current_frame_.timestamp_ms == -1) { 56 SwitchTimeBase(); 57 } 58 new_timestamp = (timestamp_ms != current_frame_.timestamp_ms); 59 } 60 if (current_frame_.timestamp == -1) { 61 // This is the first incoming packet. We don't have enough data to update 62 // the filter, so we store it until we have two frames of data to process. 63 current_frame_.timestamp = timestamp; 64 current_frame_.timestamp_ms = timestamp_ms; 65 } else if (!PacketInOrder(timestamp, timestamp_ms)) { 66 return; 67 } else if (new_timestamp) { 68 // First packet of a later frame, the previous frame sample is ready. 69 if (prev_frame_.complete_time_ms >= 0) { // This is our second frame. 70 int64_t t_delta = 0; 71 double ts_delta = 0; 72 TimeDeltas(current_frame_, prev_frame_, &t_delta, &ts_delta); 73 UpdateKalman(t_delta, ts_delta, current_frame_.size, prev_frame_.size); 74 } 75 prev_frame_ = current_frame_; 76 // The new timestamp is now the current frame. 77 current_frame_.timestamp = timestamp; 78 current_frame_.timestamp_ms = timestamp_ms; 79 current_frame_.size = 0; 80 } 81 // Accumulate the frame size 82 current_frame_.size += packet_size; 83 current_frame_.complete_time_ms = arrival_time_ms; 84 } 85 86 BandwidthUsage OveruseDetector::State() const { 87 return hypothesis_; 88 } 89 90 double OveruseDetector::NoiseVar() const { 91 return var_noise_; 92 } 93 94 void OveruseDetector::SetRateControlRegion(RateControlRegion region) { 95 switch (region) { 96 case kRcMaxUnknown: { 97 threshold_ = options_.initial_threshold; 98 break; 99 } 100 case kRcAboveMax: 101 case kRcNearMax: { 102 threshold_ = options_.initial_threshold / 2; 103 break; 104 } 105 } 106 } 107 108 void OveruseDetector::SwitchTimeBase() { 109 current_frame_.size = 0; 110 current_frame_.complete_time_ms = -1; 111 current_frame_.timestamp = -1; 112 prev_frame_ = current_frame_; 113 } 114 115 void OveruseDetector::TimeDeltas(const FrameSample& current_frame, 116 const FrameSample& prev_frame, 117 int64_t* t_delta, 118 double* ts_delta) { 119 assert(t_delta); 120 assert(ts_delta); 121 num_of_deltas_++; 122 if (num_of_deltas_ > 1000) { 123 num_of_deltas_ = 1000; 124 } 125 if (current_frame.timestamp_ms == -1) { 126 uint32_t timestamp_diff = current_frame.timestamp - prev_frame.timestamp; 127 *ts_delta = timestamp_diff / 90.0; 128 } else { 129 *ts_delta = current_frame.timestamp_ms - prev_frame.timestamp_ms; 130 } 131 *t_delta = current_frame.complete_time_ms - prev_frame.complete_time_ms; 132 assert(*ts_delta > 0); 133 } 134 135 bool OveruseDetector::PacketInOrder(uint32_t timestamp, int64_t timestamp_ms) { 136 if (current_frame_.timestamp_ms == -1 && current_frame_.timestamp > -1) { 137 return InOrderTimestamp(timestamp, current_frame_.timestamp); 138 } else if (current_frame_.timestamp_ms > 0) { 139 // Using timestamps converted to NTP time. 140 return timestamp_ms > current_frame_.timestamp_ms; 141 } 142 // This is the first packet. 143 return true; 144 } 145 146 bool OveruseDetector::InOrderTimestamp(uint32_t timestamp, 147 uint32_t prev_timestamp) { 148 uint32_t timestamp_diff = timestamp - prev_timestamp; 149 // Assume that a diff this big must be due to reordering. Don't update 150 // with reordered samples. 151 return (timestamp_diff < 0x80000000); 152 } 153 154 double OveruseDetector::CurrentDrift() { 155 return 1.0; 156 } 157 158 void OveruseDetector::UpdateKalman(int64_t t_delta, 159 double ts_delta, 160 uint32_t frame_size, 161 uint32_t prev_frame_size) { 162 const double min_frame_period = UpdateMinFramePeriod(ts_delta); 163 const double drift = CurrentDrift(); 164 // Compensate for drift 165 const double t_ts_delta = t_delta - ts_delta / drift; 166 double fs_delta = static_cast<double>(frame_size) - prev_frame_size; 167 168 // Update the Kalman filter 169 const double scale_factor = min_frame_period / (1000.0 / 30.0); 170 E_[0][0] += process_noise_[0] * scale_factor; 171 E_[1][1] += process_noise_[1] * scale_factor; 172 173 if ((hypothesis_ == kBwOverusing && offset_ < prev_offset_) || 174 (hypothesis_ == kBwUnderusing && offset_ > prev_offset_)) { 175 E_[1][1] += 10 * process_noise_[1] * scale_factor; 176 } 177 178 const double h[2] = {fs_delta, 1.0}; 179 const double Eh[2] = {E_[0][0]*h[0] + E_[0][1]*h[1], 180 E_[1][0]*h[0] + E_[1][1]*h[1]}; 181 182 const double residual = t_ts_delta - slope_*h[0] - offset_; 183 184 const bool stable_state = 185 (BWE_MIN(num_of_deltas_, 60) * fabs(offset_) < threshold_); 186 // We try to filter out very late frames. For instance periodic key 187 // frames doesn't fit the Gaussian model well. 188 if (fabs(residual) < 3 * sqrt(var_noise_)) { 189 UpdateNoiseEstimate(residual, min_frame_period, stable_state); 190 } else { 191 UpdateNoiseEstimate(3 * sqrt(var_noise_), min_frame_period, stable_state); 192 } 193 194 const double denom = var_noise_ + h[0]*Eh[0] + h[1]*Eh[1]; 195 196 const double K[2] = {Eh[0] / denom, 197 Eh[1] / denom}; 198 199 const double IKh[2][2] = {{1.0 - K[0]*h[0], -K[0]*h[1]}, 200 {-K[1]*h[0], 1.0 - K[1]*h[1]}}; 201 const double e00 = E_[0][0]; 202 const double e01 = E_[0][1]; 203 204 // Update state 205 E_[0][0] = e00 * IKh[0][0] + E_[1][0] * IKh[0][1]; 206 E_[0][1] = e01 * IKh[0][0] + E_[1][1] * IKh[0][1]; 207 E_[1][0] = e00 * IKh[1][0] + E_[1][0] * IKh[1][1]; 208 E_[1][1] = e01 * IKh[1][0] + E_[1][1] * IKh[1][1]; 209 210 // Covariance matrix, must be positive semi-definite 211 assert(E_[0][0] + E_[1][1] >= 0 && 212 E_[0][0] * E_[1][1] - E_[0][1] * E_[1][0] >= 0 && 213 E_[0][0] >= 0); 214 215 slope_ = slope_ + K[0] * residual; 216 prev_offset_ = offset_; 217 offset_ = offset_ + K[1] * residual; 218 219 Detect(ts_delta); 220 } 221 222 double OveruseDetector::UpdateMinFramePeriod(double ts_delta) { 223 double min_frame_period = ts_delta; 224 if (ts_delta_hist_.size() >= kMinFramePeriodHistoryLength) { 225 std::list<double>::iterator first_item = ts_delta_hist_.begin(); 226 ts_delta_hist_.erase(first_item); 227 } 228 std::list<double>::iterator it = ts_delta_hist_.begin(); 229 for (; it != ts_delta_hist_.end(); it++) { 230 min_frame_period = BWE_MIN(*it, min_frame_period); 231 } 232 ts_delta_hist_.push_back(ts_delta); 233 return min_frame_period; 234 } 235 236 void OveruseDetector::UpdateNoiseEstimate(double residual, 237 double ts_delta, 238 bool stable_state) { 239 if (!stable_state) { 240 return; 241 } 242 // Faster filter during startup to faster adapt to the jitter level 243 // of the network alpha is tuned for 30 frames per second, but 244 double alpha = 0.01; 245 if (num_of_deltas_ > 10*30) { 246 alpha = 0.002; 247 } 248 // Only update the noise estimate if we're not over-using 249 // beta is a function of alpha and the time delta since 250 // the previous update. 251 const double beta = pow(1 - alpha, ts_delta * 30.0 / 1000.0); 252 avg_noise_ = beta * avg_noise_ 253 + (1 - beta) * residual; 254 var_noise_ = beta * var_noise_ 255 + (1 - beta) * (avg_noise_ - residual) * (avg_noise_ - residual); 256 if (var_noise_ < 1e-7) { 257 var_noise_ = 1e-7; 258 } 259 } 260 261 BandwidthUsage OveruseDetector::Detect(double ts_delta) { 262 if (num_of_deltas_ < 2) { 263 return kBwNormal; 264 } 265 const double T = BWE_MIN(num_of_deltas_, 60) * offset_; 266 if (fabs(T) > threshold_) { 267 if (offset_ > 0) { 268 if (time_over_using_ == -1) { 269 // Initialize the timer. Assume that we've been 270 // over-using half of the time since the previous 271 // sample. 272 time_over_using_ = ts_delta / 2; 273 } else { 274 // Increment timer 275 time_over_using_ += ts_delta; 276 } 277 over_use_counter_++; 278 if (time_over_using_ > kOverUsingTimeThreshold 279 && over_use_counter_ > 1) { 280 if (offset_ >= prev_offset_) { 281 time_over_using_ = 0; 282 over_use_counter_ = 0; 283 hypothesis_ = kBwOverusing; 284 } 285 } 286 } else { 287 time_over_using_ = -1; 288 over_use_counter_ = 0; 289 hypothesis_ = kBwUnderusing; 290 } 291 } else { 292 time_over_using_ = -1; 293 over_use_counter_ = 0; 294 hypothesis_ = kBwNormal; 295 } 296 return hypothesis_; 297 } 298 } // namespace webrtc 299
