1 /*
2  *  Copyright (c) 2016 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 #ifndef MODULES_CONGESTION_CONTROLLER_MEDIAN_SLOPE_ESTIMATOR_H_
11 #define MODULES_CONGESTION_CONTROLLER_MEDIAN_SLOPE_ESTIMATOR_H_
12 
13 #include <stddef.h>
14 #include <stdint.h>
15 
16 #include <deque>
17 #include <vector>
18 
19 #include "rtc_base/constructormagic.h"
20 #include "rtc_base/numerics/percentile_filter.h"
21 
22 namespace webrtc {
23 
24 class MedianSlopeEstimator {
25  public:
26   // |window_size| is the number of points required to compute a trend line.
27   // |threshold_gain| is used to scale the trendline slope for comparison to
28   // the old threshold. Once the old estimator has been removed (or the
29   // thresholds been merged into the estimators), we can just set the
30   // threshold instead of setting a gain.
31   MedianSlopeEstimator(size_t window_size, double threshold_gain);
32   ~MedianSlopeEstimator();
33 
34   // Update the estimator with a new sample. The deltas should represent deltas
35   // between timestamp groups as defined by the InterArrival class.
36   void Update(double recv_delta_ms,
37               double send_delta_ms,
38               int64_t arrival_time_ms);
39 
40   // Returns the estimated trend k multiplied by some gain.
41   // 0 < k < 1   ->  the delay increases, queues are filling up
42   //   k == 0    ->  the delay does not change
43   //   k <  0    ->  the delay decreases, queues are being emptied
trendline_slope()44   double trendline_slope() const { return trendline_ * threshold_gain_; }
45 
46   // Returns the number of deltas which the current estimator state is based on.
num_of_deltas()47   unsigned int num_of_deltas() const { return num_of_deltas_; }
48 
49  private:
50   struct DelayInfo {
51     DelayInfo(int64_t time, double delay, size_t slope_count);
52     ~DelayInfo();
53     int64_t time;
54     double delay;
55     std::vector<double> slopes;
56   };
57   // Parameters.
58   const size_t window_size_;
59   const double threshold_gain_;
60   // Used by the existing threshold.
61   unsigned int num_of_deltas_;
62   // Theil-Sen robust line fitting
63   double accumulated_delay_;
64   std::deque<DelayInfo> delay_hist_;
65   PercentileFilter<double> median_filter_;
66   double trendline_;
67 
68   RTC_DISALLOW_COPY_AND_ASSIGN(MedianSlopeEstimator);
69 };
70 }  // namespace webrtc
71 
72 #endif  // MODULES_CONGESTION_CONTROLLER_MEDIAN_SLOPE_ESTIMATOR_H_
73