Add a new overuse estimator for the delay based BWE behind experiment.

webrtc/modules/congestion_controller/trendline_estimator.h

Index: webrtc/modules/congestion_controller/trendline_estimator.h
diff --git a/webrtc/modules/congestion_controller/trendline_estimator.h b/webrtc/modules/congestion_controller/trendline_estimator.h
new file mode 100644
index 0000000000000000000000000000000000000000..bc1b471314bab414bb425587779c2fdd7b781f5b
--- /dev/null
+++ b/webrtc/modules/congestion_controller/trendline_estimator.h
@@ -0,0 +1,69 @@
+/*
+ *  Copyright (c) 2016 The WebRTC project authors. All Rights Reserved.
+ *
+ *  Use of this source code is governed by a BSD-style license
+ *  that can be found in the LICENSE file in the root of the source
+ *  tree. An additional intellectual property rights grant can be found
+ *  in the file PATENTS.  All contributing project authors may
+ *  be found in the AUTHORS file in the root of the source tree.
+ */
+#ifndef WEBRTC_MODULES_CONGESTION_CONTROLLER_TRENDLINE_ESTIMATOR_H_
+#define WEBRTC_MODULES_CONGESTION_CONTROLLER_TRENDLINE_ESTIMATOR_H_
+
+#include <list>
+#include <utility>
+
+#include "webrtc/base/constructormagic.h"
+#include "webrtc/common_types.h"
+#include "webrtc/modules/remote_bitrate_estimator/include/bwe_defines.h"
+
+namespace webrtc {
+
+class TrendlineEstimator {
+ public:
+  // |window_size| is the number of points required to compute a trend_line
+  // |smoothing_coef| controls how the much we smooth out the delay

[stefan-webrtc, 2016/11/13 13:09:53]

how much

[terelius, 2016/11/14 13:21:39]

Done.

+  // before fitting the trendline. |threashold_gain| is used to scale the

[stefan-webrtc, 2016/11/13 13:09:53]

threshold_gain

[terelius, 2016/11/14 13:21:39]

Done.

+  // trendline slope for comparison to the old threshold.

[stefan-webrtc, 2016/11/13 13:09:53]

Maybe add a comment that the threshold gain perhaps should be removed once the
old estimator is fully replaced?

[terelius, 2016/11/14 13:21:39]

Done.

+  TrendlineEstimator(size_t window_size,
+                     double smoothing_coef,
+                     double threshold_gain);
+  ~TrendlineEstimator();
+
+  // Update the estimator with a new sample. The deltas should represent deltas
+  // between timestamp groups as defined by the InterArrival class.
+  void Update(double recv_delta_ms, double send_delta_ms, int64_t now_ms);
+
+  // Returns the estimated trend k multiplied by some gain.
+  // 0 < k < 1   ->  the delay increases, queues are filling up
+  //   k == 0    ->  the delay does not change
+  // -1 < k < 0  ->  the delay decreases, queues are being emptied
+  double trendline_slope() const { return trendline_ * threshold_gain_; }
+
+  // Returns the number of deltas which the current estimator state is based on.
+  unsigned int num_of_deltas() const { return num_of_deltas_; }
+
+ private:
+  // Parameters.
+  const size_t window_size_;
+  const double smoothing_coef_;
+  const double threshold_gain_;
+  // Used by the existing threshold.
+  unsigned int num_of_deltas_;

[stefan-webrtc, 2016/11/13 13:09:53]

Can we use an int instead?

[terelius, 2016/11/14 13:21:39]

Yes except that the Kalman filter uses an unsigned int, and I want to have the
same types in both estimators. Should I change both to int?

[stefan-webrtc, 2016/11/14 13:30:58]

Ah, feel free to keep for now.

+  // Exponential backoff filtering.
+  double accumulated_delay_;
+  double smoothed_delay_;
+  double last_smoothed_delay_;
+  // Linear least squares regression.
+  std::list<std::pair<int64_t, double>> accumulated_delay_hist_;
+  double sum_x_;
+  double sum_y_;
+  double sum_xy_;
+  double sum_x2_;
+  double trendline_;
+
+  RTC_DISALLOW_COPY_AND_ASSIGN(TrendlineEstimator);
+};
+}  // namespace webrtc
+
+#endif  // WEBRTC_MODULES_CONGESTION_CONTROLLER_TRENDLINE_ESTIMATOR_H_