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
19enum { kOverUsingTimeThreshold = 100 };
20enum { kMinFramePeriodHistoryLength = 60 };
21
22namespace webrtc {
23OveruseDetector::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
45OveruseDetector::~OveruseDetector() {
46  ts_delta_hist_.clear();
47}
48
49void 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
86BandwidthUsage OveruseDetector::State() const {
87  return hypothesis_;
88}
89
90double OveruseDetector::NoiseVar() const {
91  return var_noise_;
92}
93
94void 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
108void 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
115void 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
135bool 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
146bool 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
154double OveruseDetector::CurrentDrift() {
155  return 1.0;
156}
157
158void 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
222double 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
236void 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
261BandwidthUsage 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