Implement Theil-Sen's method for fitting a line to noisy data (used in bandwidth estimation).

webrtc/modules/congestion_controller/theil_sen_estimator.h

Index: webrtc/modules/congestion_controller/theil_sen_estimator.h
diff --git a/webrtc/modules/congestion_controller/theil_sen_estimator.h b/webrtc/modules/congestion_controller/theil_sen_estimator.h
new file mode 100644
index 0000000000000000000000000000000000000000..d6797acbaf90331c7eeabafcbbf1680464db7c5b
--- /dev/null
+++ b/webrtc/modules/congestion_controller/theil_sen_estimator.h
@@ -0,0 +1,61 @@
+/*
+ *  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_THEIL_SEN_ESTIMATOR_H_
+#define WEBRTC_MODULES_CONGESTION_CONTROLLER_THEIL_SEN_ESTIMATOR_H_
+
+#include <list>
+#include <utility>
+
+#include "webrtc/base/analytics/percentile_filter.h"
+#include "webrtc/base/constructormagic.h"
+#include "webrtc/common_types.h"
+
+namespace webrtc {
+
+class TheilSenEstimator {
+ public:
+  // |window_size| is the number of points required to compute a trend line.
+  // |threshold_gain| is used to scale the trendline slope for comparison to
+  // the old threshold. Once the old estimator has been removed (or the
+  // thresholds been merged into the estimators), we can just set the
+  // threshold instead of setting a gain.

[brandtr, 2016/11/28 16:27:19]

I.e., the gain would be unity when the old estimator has been removed?

[terelius, 2016/12/02 16:45:52]

Yes, but we might want a parameter to set the initial threshold instead.

[brandtr, 2016/12/05 12:34:44]

Right.

+  TheilSenEstimator(size_t window_size, double threshold_gain);
+  ~TheilSenEstimator();
+
+  // 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, double 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
+  //   k <  0    ->  the delay decreases, queues are being emptied

[brandtr, 2016/11/28 16:27:20]

Why is |k| not lower bounded by -1, when it is upper bounded by 1?

[terelius, 2016/12/02 16:45:52]

It depends on whose clock we are using for the x-axis. Here we are using the
receiver's clock, and from the receiver's point of view the delay can't increase
faster than 1 second per second. On the other, the receiver might receive
packets back-to-back which gives a slope < -1.

+  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_; }

[brandtr, 2016/11/28 16:27:19]

size_t?

[terelius, 2016/12/02 16:45:52]

I agree that size_t would be better, but the result is capped at 1000 so it
makes no difference in practice. My reasoning for choosing unsigned int is that
I want to preserve the same interface as the Kalman filter.

[brandtr, 2016/12/05 12:34:44]

Acknowledged.

+
+ private:
+  // Parameters.
+  const size_t window_size_;
+  const double threshold_gain_;
+  // Used by the existing threshold.
+  unsigned int num_of_deltas_;
+  // Theil-Sen robust line fitting
+  double accumulated_delay_;
+  std::list<std::pair<double, double>> delay_hist_;
+  PercentileFilter<double> median_filter_;
+  double trendline_;
+
+  RTC_DISALLOW_COPY_AND_ASSIGN(TheilSenEstimator);
+};
+}  // namespace webrtc
+
+#endif  // WEBRTC_MODULES_CONGESTION_CONTROLLER_THEIL_SEN_ESTIMATOR_H_