1 /*
2 * Copyright (c) 2011 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 "modules/video_coding/timing/rtt_filter.h"
12
13 #include <math.h>
14 #include <stdlib.h>
15 #include <string.h>
16
17 #include <algorithm>
18
19 #include "absl/algorithm/container.h"
20 #include "absl/container/inlined_vector.h"
21 #include "api/units/time_delta.h"
22
23 namespace webrtc {
24
25 namespace {
26
27 constexpr TimeDelta kMaxRtt = TimeDelta::Seconds(3);
28 constexpr uint32_t kFilterFactorMax = 35;
29 constexpr double kJumpStddev = 2.5;
30 constexpr double kDriftStdDev = 3.5;
31
32 } // namespace
33
RttFilter()34 RttFilter::RttFilter()
35 : avg_rtt_(TimeDelta::Zero()),
36 var_rtt_(0),
37 max_rtt_(TimeDelta::Zero()),
38 jump_buf_(kMaxDriftJumpCount, TimeDelta::Zero()),
39 drift_buf_(kMaxDriftJumpCount, TimeDelta::Zero()) {
40 Reset();
41 }
42
Reset()43 void RttFilter::Reset() {
44 got_non_zero_update_ = false;
45 avg_rtt_ = TimeDelta::Zero();
46 var_rtt_ = 0;
47 max_rtt_ = TimeDelta::Zero();
48 filt_fact_count_ = 1;
49 absl::c_fill(jump_buf_, TimeDelta::Zero());
50 absl::c_fill(drift_buf_, TimeDelta::Zero());
51 }
52
Update(TimeDelta rtt)53 void RttFilter::Update(TimeDelta rtt) {
54 if (!got_non_zero_update_) {
55 if (rtt.IsZero()) {
56 return;
57 }
58 got_non_zero_update_ = true;
59 }
60
61 // Sanity check
62 if (rtt > kMaxRtt) {
63 rtt = kMaxRtt;
64 }
65
66 double filt_factor = 0;
67 if (filt_fact_count_ > 1) {
68 filt_factor = static_cast<double>(filt_fact_count_ - 1) / filt_fact_count_;
69 }
70 filt_fact_count_++;
71 if (filt_fact_count_ > kFilterFactorMax) {
72 // This prevents filt_factor from going above
73 // (_filt_fact_max - 1) / filt_fact_max_,
74 // e.g., filt_fact_max_ = 50 => filt_factor = 49/50 = 0.98
75 filt_fact_count_ = kFilterFactorMax;
76 }
77 TimeDelta old_avg = avg_rtt_;
78 int64_t old_var = var_rtt_;
79 avg_rtt_ = filt_factor * avg_rtt_ + (1 - filt_factor) * rtt;
80 int64_t delta_ms = (rtt - avg_rtt_).ms();
81 var_rtt_ = filt_factor * var_rtt_ + (1 - filt_factor) * (delta_ms * delta_ms);
82 max_rtt_ = std::max(rtt, max_rtt_);
83 if (!JumpDetection(rtt) || !DriftDetection(rtt)) {
84 // In some cases we don't want to update the statistics
85 avg_rtt_ = old_avg;
86 var_rtt_ = old_var;
87 }
88 }
89
JumpDetection(TimeDelta rtt)90 bool RttFilter::JumpDetection(TimeDelta rtt) {
91 TimeDelta diff_from_avg = avg_rtt_ - rtt;
92 // Unit of var_rtt_ is ms^2.
93 TimeDelta jump_threshold = TimeDelta::Millis(kJumpStddev * sqrt(var_rtt_));
94 if (diff_from_avg.Abs() > jump_threshold) {
95 bool positive_diff = diff_from_avg >= TimeDelta::Zero();
96 if (!jump_buf_.empty() && positive_diff != last_jump_positive_) {
97 // Since the signs differ the samples currently
98 // in the buffer is useless as they represent a
99 // jump in a different direction.
100 jump_buf_.clear();
101 }
102 if (jump_buf_.size() < kMaxDriftJumpCount) {
103 // Update the buffer used for the short time statistics.
104 // The sign of the diff is used for updating the counter since
105 // we want to use the same buffer for keeping track of when
106 // the RTT jumps down and up.
107 jump_buf_.push_back(rtt);
108 last_jump_positive_ = positive_diff;
109 }
110 if (jump_buf_.size() >= kMaxDriftJumpCount) {
111 // Detected an RTT jump
112 ShortRttFilter(jump_buf_);
113 filt_fact_count_ = kMaxDriftJumpCount + 1;
114 jump_buf_.clear();
115 } else {
116 return false;
117 }
118 } else {
119 jump_buf_.clear();
120 }
121 return true;
122 }
123
DriftDetection(TimeDelta rtt)124 bool RttFilter::DriftDetection(TimeDelta rtt) {
125 // Unit of sqrt of var_rtt_ is ms.
126 TimeDelta drift_threshold = TimeDelta::Millis(kDriftStdDev * sqrt(var_rtt_));
127 if (max_rtt_ - avg_rtt_ > drift_threshold) {
128 if (drift_buf_.size() < kMaxDriftJumpCount) {
129 // Update the buffer used for the short time statistics.
130 drift_buf_.push_back(rtt);
131 }
132 if (drift_buf_.size() >= kMaxDriftJumpCount) {
133 // Detected an RTT drift
134 ShortRttFilter(drift_buf_);
135 filt_fact_count_ = kMaxDriftJumpCount + 1;
136 drift_buf_.clear();
137 }
138 } else {
139 drift_buf_.clear();
140 }
141 return true;
142 }
143
ShortRttFilter(const BufferList & buf)144 void RttFilter::ShortRttFilter(const BufferList& buf) {
145 RTC_DCHECK_EQ(buf.size(), kMaxDriftJumpCount);
146 max_rtt_ = TimeDelta::Zero();
147 avg_rtt_ = TimeDelta::Zero();
148 for (const TimeDelta& rtt : buf) {
149 if (rtt > max_rtt_) {
150 max_rtt_ = rtt;
151 }
152 avg_rtt_ += rtt;
153 }
154 avg_rtt_ = avg_rtt_ / static_cast<double>(buf.size());
155 }
156
Rtt() const157 TimeDelta RttFilter::Rtt() const {
158 return max_rtt_;
159 }
160
161 } // namespace webrtc
162