OLD | NEW |
1 /* | 1 /* |
2 * Copyright (c) 2016 The WebRTC project authors. All Rights Reserved. | 2 * Copyright (c) 2016 The WebRTC project authors. All Rights Reserved. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license | 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 | 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 | 6 * tree. An additional intellectual property rights grant can be found |
7 * in the file PATENTS. All contributing project authors may | 7 * in the file PATENTS. All contributing project authors may |
8 * be found in the AUTHORS file in the root of the source tree. | 8 * be found in the AUTHORS file in the root of the source tree. |
9 */ | 9 */ |
10 | 10 |
(...skipping 20 matching lines...) Expand all Loading... |
31 constexpr int kTimestampGroupLengthMs = 5; | 31 constexpr int kTimestampGroupLengthMs = 5; |
32 constexpr int kAbsSendTimeFraction = 18; | 32 constexpr int kAbsSendTimeFraction = 18; |
33 constexpr int kAbsSendTimeInterArrivalUpshift = 8; | 33 constexpr int kAbsSendTimeInterArrivalUpshift = 8; |
34 constexpr int kInterArrivalShift = | 34 constexpr int kInterArrivalShift = |
35 kAbsSendTimeFraction + kAbsSendTimeInterArrivalUpshift; | 35 kAbsSendTimeFraction + kAbsSendTimeInterArrivalUpshift; |
36 constexpr double kTimestampToMs = | 36 constexpr double kTimestampToMs = |
37 1000.0 / static_cast<double>(1 << kInterArrivalShift); | 37 1000.0 / static_cast<double>(1 << kInterArrivalShift); |
38 // This ssrc is used to fulfill the current API but will be removed | 38 // This ssrc is used to fulfill the current API but will be removed |
39 // after the API has been changed. | 39 // after the API has been changed. |
40 constexpr uint32_t kFixedSsrc = 0; | 40 constexpr uint32_t kFixedSsrc = 0; |
41 constexpr int kInitialRateWindowMs = 500; | |
42 constexpr int kRateWindowMs = 150; | |
43 | 41 |
44 // Parameters for linear least squares fit of regression line to noisy data. | 42 // Parameters for linear least squares fit of regression line to noisy data. |
45 constexpr size_t kDefaultTrendlineWindowSize = 20; | 43 constexpr size_t kDefaultTrendlineWindowSize = 20; |
46 constexpr double kDefaultTrendlineSmoothingCoeff = 0.9; | 44 constexpr double kDefaultTrendlineSmoothingCoeff = 0.9; |
47 constexpr double kDefaultTrendlineThresholdGain = 4.0; | 45 constexpr double kDefaultTrendlineThresholdGain = 4.0; |
48 | 46 |
49 constexpr int kMaxConsecutiveFailedLookups = 5; | 47 constexpr int kMaxConsecutiveFailedLookups = 5; |
50 | 48 |
51 const char kBweSparseUpdateExperiment[] = "WebRTC-BweSparseUpdateExperiment"; | 49 const char kBweSparseUpdateExperiment[] = "WebRTC-BweSparseUpdateExperiment"; |
52 | 50 |
53 bool BweSparseUpdateExperimentIsEnabled() { | 51 bool BweSparseUpdateExperimentIsEnabled() { |
54 std::string experiment_string = | 52 std::string experiment_string = |
55 webrtc::field_trial::FindFullName(kBweSparseUpdateExperiment); | 53 webrtc::field_trial::FindFullName(kBweSparseUpdateExperiment); |
56 return experiment_string == "Enabled"; | 54 return experiment_string == "Enabled"; |
57 } | 55 } |
58 | |
59 class PacketFeedbackComparator { | |
60 public: | |
61 inline bool operator()(const webrtc::PacketFeedback& lhs, | |
62 const webrtc::PacketFeedback& rhs) { | |
63 if (lhs.arrival_time_ms != rhs.arrival_time_ms) | |
64 return lhs.arrival_time_ms < rhs.arrival_time_ms; | |
65 if (lhs.send_time_ms != rhs.send_time_ms) | |
66 return lhs.send_time_ms < rhs.send_time_ms; | |
67 return lhs.sequence_number < rhs.sequence_number; | |
68 } | |
69 }; | |
70 | |
71 void SortPacketFeedbackVector(const std::vector<webrtc::PacketFeedback>& input, | |
72 std::vector<webrtc::PacketFeedback>* output) { | |
73 auto pred = [](const webrtc::PacketFeedback& packet_feedback) { | |
74 return packet_feedback.arrival_time_ms != | |
75 webrtc::PacketFeedback::kNotReceived; | |
76 }; | |
77 std::copy_if(input.begin(), input.end(), std::back_inserter(*output), pred); | |
78 std::sort(output->begin(), output->end(), PacketFeedbackComparator()); | |
79 } | |
80 } // namespace | 56 } // namespace |
81 | 57 |
82 namespace webrtc { | 58 namespace webrtc { |
83 | 59 |
84 DelayBasedBwe::BitrateEstimator::BitrateEstimator() | |
85 : sum_(0), | |
86 current_win_ms_(0), | |
87 prev_time_ms_(-1), | |
88 bitrate_estimate_(-1.0f), | |
89 bitrate_estimate_var_(50.0f) {} | |
90 | |
91 void DelayBasedBwe::BitrateEstimator::Update(int64_t now_ms, int bytes) { | |
92 int rate_window_ms = kRateWindowMs; | |
93 // We use a larger window at the beginning to get a more stable sample that | |
94 // we can use to initialize the estimate. | |
95 if (bitrate_estimate_ < 0.f) | |
96 rate_window_ms = kInitialRateWindowMs; | |
97 float bitrate_sample = UpdateWindow(now_ms, bytes, rate_window_ms); | |
98 if (bitrate_sample < 0.0f) | |
99 return; | |
100 if (bitrate_estimate_ < 0.0f) { | |
101 // This is the very first sample we get. Use it to initialize the estimate. | |
102 bitrate_estimate_ = bitrate_sample; | |
103 return; | |
104 } | |
105 // Define the sample uncertainty as a function of how far away it is from the | |
106 // current estimate. | |
107 float sample_uncertainty = | |
108 10.0f * std::abs(bitrate_estimate_ - bitrate_sample) / bitrate_estimate_; | |
109 float sample_var = sample_uncertainty * sample_uncertainty; | |
110 // Update a bayesian estimate of the rate, weighting it lower if the sample | |
111 // uncertainty is large. | |
112 // The bitrate estimate uncertainty is increased with each update to model | |
113 // that the bitrate changes over time. | |
114 float pred_bitrate_estimate_var = bitrate_estimate_var_ + 5.f; | |
115 bitrate_estimate_ = (sample_var * bitrate_estimate_ + | |
116 pred_bitrate_estimate_var * bitrate_sample) / | |
117 (sample_var + pred_bitrate_estimate_var); | |
118 bitrate_estimate_var_ = sample_var * pred_bitrate_estimate_var / | |
119 (sample_var + pred_bitrate_estimate_var); | |
120 } | |
121 | |
122 float DelayBasedBwe::BitrateEstimator::UpdateWindow(int64_t now_ms, | |
123 int bytes, | |
124 int rate_window_ms) { | |
125 // Reset if time moves backwards. | |
126 if (now_ms < prev_time_ms_) { | |
127 prev_time_ms_ = -1; | |
128 sum_ = 0; | |
129 current_win_ms_ = 0; | |
130 } | |
131 if (prev_time_ms_ >= 0) { | |
132 current_win_ms_ += now_ms - prev_time_ms_; | |
133 // Reset if nothing has been received for more than a full window. | |
134 if (now_ms - prev_time_ms_ > rate_window_ms) { | |
135 sum_ = 0; | |
136 current_win_ms_ %= rate_window_ms; | |
137 } | |
138 } | |
139 prev_time_ms_ = now_ms; | |
140 float bitrate_sample = -1.0f; | |
141 if (current_win_ms_ >= rate_window_ms) { | |
142 bitrate_sample = 8.0f * sum_ / static_cast<float>(rate_window_ms); | |
143 current_win_ms_ -= rate_window_ms; | |
144 sum_ = 0; | |
145 } | |
146 sum_ += bytes; | |
147 return bitrate_sample; | |
148 } | |
149 | |
150 rtc::Optional<uint32_t> DelayBasedBwe::BitrateEstimator::bitrate_bps() const { | |
151 if (bitrate_estimate_ < 0.f) | |
152 return rtc::Optional<uint32_t>(); | |
153 return rtc::Optional<uint32_t>(bitrate_estimate_ * 1000); | |
154 } | |
155 | |
156 DelayBasedBwe::DelayBasedBwe(RtcEventLog* event_log, const Clock* clock) | 60 DelayBasedBwe::DelayBasedBwe(RtcEventLog* event_log, const Clock* clock) |
157 : event_log_(event_log), | 61 : event_log_(event_log), |
158 clock_(clock), | 62 clock_(clock), |
159 inter_arrival_(), | 63 inter_arrival_(), |
160 trendline_estimator_(), | 64 trendline_estimator_(), |
161 detector_(), | 65 detector_(), |
162 receiver_incoming_bitrate_(), | |
163 last_seen_packet_ms_(-1), | 66 last_seen_packet_ms_(-1), |
164 uma_recorded_(false), | 67 uma_recorded_(false), |
165 probe_bitrate_estimator_(event_log), | 68 probe_bitrate_estimator_(event_log), |
166 trendline_window_size_(kDefaultTrendlineWindowSize), | 69 trendline_window_size_(kDefaultTrendlineWindowSize), |
167 trendline_smoothing_coeff_(kDefaultTrendlineSmoothingCoeff), | 70 trendline_smoothing_coeff_(kDefaultTrendlineSmoothingCoeff), |
168 trendline_threshold_gain_(kDefaultTrendlineThresholdGain), | 71 trendline_threshold_gain_(kDefaultTrendlineThresholdGain), |
169 consecutive_delayed_feedbacks_(0), | 72 consecutive_delayed_feedbacks_(0), |
170 last_logged_bitrate_(0), | 73 last_logged_bitrate_(0), |
171 last_logged_state_(BandwidthUsage::kBwNormal), | 74 last_logged_state_(BandwidthUsage::kBwNormal), |
172 in_sparse_update_experiment_(BweSparseUpdateExperimentIsEnabled()) { | 75 in_sparse_update_experiment_(BweSparseUpdateExperimentIsEnabled()) { |
173 LOG(LS_INFO) << "Using Trendline filter for delay change estimation."; | 76 LOG(LS_INFO) << "Using Trendline filter for delay change estimation."; |
174 network_thread_.DetachFromThread(); | 77 network_thread_.DetachFromThread(); |
175 } | 78 } |
176 | 79 |
177 DelayBasedBwe::~DelayBasedBwe() {} | 80 DelayBasedBwe::~DelayBasedBwe() {} |
178 | 81 |
179 DelayBasedBwe::Result DelayBasedBwe::IncomingPacketFeedbackVector( | 82 DelayBasedBwe::Result DelayBasedBwe::IncomingPacketFeedbackVector( |
180 const std::vector<PacketFeedback>& packet_feedback_vector) { | 83 const std::vector<PacketFeedback>& packet_feedback_vector, |
| 84 rtc::Optional<uint32_t> acked_bitrate_bps) { |
| 85 RTC_DCHECK(std::is_sorted(packet_feedback_vector.begin(), |
| 86 packet_feedback_vector.end(), |
| 87 PacketFeedbackComparator())); |
181 RTC_DCHECK(network_thread_.CalledOnValidThread()); | 88 RTC_DCHECK(network_thread_.CalledOnValidThread()); |
182 | 89 |
183 std::vector<PacketFeedback> sorted_packet_feedback_vector; | |
184 SortPacketFeedbackVector(packet_feedback_vector, | |
185 &sorted_packet_feedback_vector); | |
186 // TOOD(holmer): An empty feedback vector here likely means that | 90 // TOOD(holmer): An empty feedback vector here likely means that |
187 // all acks were too late and that the send time history had | 91 // all acks were too late and that the send time history had |
188 // timed out. We should reduce the rate when this occurs. | 92 // timed out. We should reduce the rate when this occurs. |
189 if (sorted_packet_feedback_vector.empty()) { | 93 if (packet_feedback_vector.empty()) { |
190 LOG(LS_WARNING) << "Very late feedback received."; | 94 LOG(LS_WARNING) << "Very late feedback received."; |
191 return DelayBasedBwe::Result(); | 95 return DelayBasedBwe::Result(); |
192 } | 96 } |
193 | 97 |
194 if (!uma_recorded_) { | 98 if (!uma_recorded_) { |
195 RTC_HISTOGRAM_ENUMERATION(kBweTypeHistogram, | 99 RTC_HISTOGRAM_ENUMERATION(kBweTypeHistogram, |
196 BweNames::kSendSideTransportSeqNum, | 100 BweNames::kSendSideTransportSeqNum, |
197 BweNames::kBweNamesMax); | 101 BweNames::kBweNamesMax); |
198 uma_recorded_ = true; | 102 uma_recorded_ = true; |
199 } | 103 } |
200 bool overusing = false; | 104 bool overusing = false; |
201 bool delayed_feedback = true; | 105 bool delayed_feedback = true; |
202 for (const auto& packet_feedback : sorted_packet_feedback_vector) { | 106 for (const auto& packet_feedback : packet_feedback_vector) { |
203 if (packet_feedback.send_time_ms < 0) | 107 if (packet_feedback.send_time_ms < 0) |
204 continue; | 108 continue; |
205 delayed_feedback = false; | 109 delayed_feedback = false; |
206 IncomingPacketFeedback(packet_feedback); | 110 IncomingPacketFeedback(packet_feedback); |
207 if (!in_sparse_update_experiment_) | 111 if (!in_sparse_update_experiment_) |
208 overusing |= (detector_.State() == BandwidthUsage::kBwOverusing); | 112 overusing |= (detector_.State() == BandwidthUsage::kBwOverusing); |
209 } | 113 } |
210 if (in_sparse_update_experiment_) | 114 if (in_sparse_update_experiment_) |
211 overusing = (detector_.State() == BandwidthUsage::kBwOverusing); | 115 overusing = (detector_.State() == BandwidthUsage::kBwOverusing); |
212 if (delayed_feedback) { | 116 if (delayed_feedback) { |
213 ++consecutive_delayed_feedbacks_; | 117 ++consecutive_delayed_feedbacks_; |
214 if (consecutive_delayed_feedbacks_ >= kMaxConsecutiveFailedLookups) { | 118 if (consecutive_delayed_feedbacks_ >= kMaxConsecutiveFailedLookups) { |
215 consecutive_delayed_feedbacks_ = 0; | 119 consecutive_delayed_feedbacks_ = 0; |
216 return OnLongFeedbackDelay( | 120 return OnLongFeedbackDelay(packet_feedback_vector.back().arrival_time_ms); |
217 sorted_packet_feedback_vector.back().arrival_time_ms); | |
218 } | 121 } |
219 } else { | 122 } else { |
220 consecutive_delayed_feedbacks_ = 0; | 123 consecutive_delayed_feedbacks_ = 0; |
221 return MaybeUpdateEstimate(overusing); | 124 return MaybeUpdateEstimate(overusing, acked_bitrate_bps); |
222 } | 125 } |
223 return Result(); | 126 return Result(); |
224 } | 127 } |
225 | 128 |
226 DelayBasedBwe::Result DelayBasedBwe::OnLongFeedbackDelay( | 129 DelayBasedBwe::Result DelayBasedBwe::OnLongFeedbackDelay( |
227 int64_t arrival_time_ms) { | 130 int64_t arrival_time_ms) { |
228 // Estimate should always be valid since a start bitrate always is set in the | 131 // Estimate should always be valid since a start bitrate always is set in the |
229 // Call constructor. An alternative would be to return an empty Result here, | 132 // Call constructor. An alternative would be to return an empty Result here, |
230 // or to estimate the throughput based on the feedback we received. | 133 // or to estimate the throughput based on the feedback we received. |
231 RTC_DCHECK(rate_control_.ValidEstimate()); | 134 RTC_DCHECK(rate_control_.ValidEstimate()); |
232 rate_control_.SetEstimate(rate_control_.LatestEstimate() / 2, | 135 rate_control_.SetEstimate(rate_control_.LatestEstimate() / 2, |
233 arrival_time_ms); | 136 arrival_time_ms); |
234 Result result; | 137 Result result; |
235 result.updated = true; | 138 result.updated = true; |
236 result.probe = false; | 139 result.probe = false; |
237 result.target_bitrate_bps = rate_control_.LatestEstimate(); | 140 result.target_bitrate_bps = rate_control_.LatestEstimate(); |
238 LOG(LS_WARNING) << "Long feedback delay detected, reducing BWE to " | 141 LOG(LS_WARNING) << "Long feedback delay detected, reducing BWE to " |
239 << result.target_bitrate_bps; | 142 << result.target_bitrate_bps; |
240 return result; | 143 return result; |
241 } | 144 } |
242 | 145 |
243 void DelayBasedBwe::IncomingPacketFeedback( | 146 void DelayBasedBwe::IncomingPacketFeedback( |
244 const PacketFeedback& packet_feedback) { | 147 const PacketFeedback& packet_feedback) { |
245 int64_t now_ms = clock_->TimeInMilliseconds(); | 148 int64_t now_ms = clock_->TimeInMilliseconds(); |
246 | |
247 receiver_incoming_bitrate_.Update(packet_feedback.arrival_time_ms, | |
248 packet_feedback.payload_size); | |
249 Result result; | |
250 // Reset if the stream has timed out. | 149 // Reset if the stream has timed out. |
251 if (last_seen_packet_ms_ == -1 || | 150 if (last_seen_packet_ms_ == -1 || |
252 now_ms - last_seen_packet_ms_ > kStreamTimeOutMs) { | 151 now_ms - last_seen_packet_ms_ > kStreamTimeOutMs) { |
253 inter_arrival_.reset( | 152 inter_arrival_.reset( |
254 new InterArrival((kTimestampGroupLengthMs << kInterArrivalShift) / 1000, | 153 new InterArrival((kTimestampGroupLengthMs << kInterArrivalShift) / 1000, |
255 kTimestampToMs, true)); | 154 kTimestampToMs, true)); |
256 trendline_estimator_.reset(new TrendlineEstimator( | 155 trendline_estimator_.reset(new TrendlineEstimator( |
257 trendline_window_size_, trendline_smoothing_coeff_, | 156 trendline_window_size_, trendline_smoothing_coeff_, |
258 trendline_threshold_gain_)); | 157 trendline_threshold_gain_)); |
259 } | 158 } |
(...skipping 22 matching lines...) Expand all Loading... |
282 detector_.Detect(trendline_estimator_->trendline_slope(), ts_delta_ms, | 181 detector_.Detect(trendline_estimator_->trendline_slope(), ts_delta_ms, |
283 trendline_estimator_->num_of_deltas(), | 182 trendline_estimator_->num_of_deltas(), |
284 packet_feedback.arrival_time_ms); | 183 packet_feedback.arrival_time_ms); |
285 } | 184 } |
286 if (packet_feedback.pacing_info.probe_cluster_id != | 185 if (packet_feedback.pacing_info.probe_cluster_id != |
287 PacedPacketInfo::kNotAProbe) { | 186 PacedPacketInfo::kNotAProbe) { |
288 probe_bitrate_estimator_.HandleProbeAndEstimateBitrate(packet_feedback); | 187 probe_bitrate_estimator_.HandleProbeAndEstimateBitrate(packet_feedback); |
289 } | 188 } |
290 } | 189 } |
291 | 190 |
292 DelayBasedBwe::Result DelayBasedBwe::MaybeUpdateEstimate(bool overusing) { | 191 DelayBasedBwe::Result DelayBasedBwe::MaybeUpdateEstimate( |
| 192 bool overusing, |
| 193 rtc::Optional<uint32_t> acked_bitrate_bps) { |
293 Result result; | 194 Result result; |
294 int64_t now_ms = clock_->TimeInMilliseconds(); | 195 int64_t now_ms = clock_->TimeInMilliseconds(); |
295 | 196 |
296 rtc::Optional<uint32_t> acked_bitrate_bps = | |
297 receiver_incoming_bitrate_.bitrate_bps(); | |
298 rtc::Optional<int> probe_bitrate_bps = | 197 rtc::Optional<int> probe_bitrate_bps = |
299 probe_bitrate_estimator_.FetchAndResetLastEstimatedBitrateBps(); | 198 probe_bitrate_estimator_.FetchAndResetLastEstimatedBitrateBps(); |
300 // Currently overusing the bandwidth. | 199 // Currently overusing the bandwidth. |
301 if (overusing) { | 200 if (overusing) { |
302 if (acked_bitrate_bps && | 201 if (acked_bitrate_bps && |
303 rate_control_.TimeToReduceFurther(now_ms, *acked_bitrate_bps)) { | 202 rate_control_.TimeToReduceFurther(now_ms, *acked_bitrate_bps)) { |
304 result.updated = UpdateEstimate(now_ms, acked_bitrate_bps, overusing, | 203 result.updated = UpdateEstimate(now_ms, acked_bitrate_bps, overusing, |
305 &result.target_bitrate_bps); | 204 &result.target_bitrate_bps); |
306 } | 205 } |
307 } else { | 206 } else { |
(...skipping 59 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
367 void DelayBasedBwe::SetMinBitrate(int min_bitrate_bps) { | 266 void DelayBasedBwe::SetMinBitrate(int min_bitrate_bps) { |
368 // Called from both the configuration thread and the network thread. Shouldn't | 267 // Called from both the configuration thread and the network thread. Shouldn't |
369 // be called from the network thread in the future. | 268 // be called from the network thread in the future. |
370 rate_control_.SetMinBitrate(min_bitrate_bps); | 269 rate_control_.SetMinBitrate(min_bitrate_bps); |
371 } | 270 } |
372 | 271 |
373 int64_t DelayBasedBwe::GetExpectedBwePeriodMs() const { | 272 int64_t DelayBasedBwe::GetExpectedBwePeriodMs() const { |
374 return rate_control_.GetExpectedBandwidthPeriodMs(); | 273 return rate_control_.GetExpectedBandwidthPeriodMs(); |
375 } | 274 } |
376 } // namespace webrtc | 275 } // namespace webrtc |
OLD | NEW |