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; |
41 | 43 |
42 // Parameters for linear least squares fit of regression line to noisy data. | 44 // Parameters for linear least squares fit of regression line to noisy data. |
43 constexpr size_t kDefaultTrendlineWindowSize = 20; | 45 constexpr size_t kDefaultTrendlineWindowSize = 20; |
44 constexpr double kDefaultTrendlineSmoothingCoeff = 0.9; | 46 constexpr double kDefaultTrendlineSmoothingCoeff = 0.9; |
45 constexpr double kDefaultTrendlineThresholdGain = 4.0; | 47 constexpr double kDefaultTrendlineThresholdGain = 4.0; |
46 | 48 |
47 constexpr int kMaxConsecutiveFailedLookups = 5; | 49 constexpr int kMaxConsecutiveFailedLookups = 5; |
48 | 50 |
49 const char kBweSparseUpdateExperiment[] = "WebRTC-BweSparseUpdateExperiment"; | 51 const char kBweSparseUpdateExperiment[] = "WebRTC-BweSparseUpdateExperiment"; |
50 | 52 |
51 bool BweSparseUpdateExperimentIsEnabled() { | 53 bool BweSparseUpdateExperimentIsEnabled() { |
52 std::string experiment_string = | 54 std::string experiment_string = |
53 webrtc::field_trial::FindFullName(kBweSparseUpdateExperiment); | 55 webrtc::field_trial::FindFullName(kBweSparseUpdateExperiment); |
54 return experiment_string == "Enabled"; | 56 return experiment_string == "Enabled"; |
55 } | 57 } |
| 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 } |
56 } // namespace | 80 } // namespace |
57 | 81 |
58 namespace webrtc { | 82 namespace webrtc { |
59 | 83 |
| 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 |
60 DelayBasedBwe::DelayBasedBwe(RtcEventLog* event_log, const Clock* clock) | 156 DelayBasedBwe::DelayBasedBwe(RtcEventLog* event_log, const Clock* clock) |
61 : event_log_(event_log), | 157 : event_log_(event_log), |
62 clock_(clock), | 158 clock_(clock), |
63 inter_arrival_(), | 159 inter_arrival_(), |
64 trendline_estimator_(), | 160 trendline_estimator_(), |
65 detector_(), | 161 detector_(), |
| 162 receiver_incoming_bitrate_(), |
66 last_seen_packet_ms_(-1), | 163 last_seen_packet_ms_(-1), |
67 uma_recorded_(false), | 164 uma_recorded_(false), |
68 probe_bitrate_estimator_(event_log), | 165 probe_bitrate_estimator_(event_log), |
69 trendline_window_size_(kDefaultTrendlineWindowSize), | 166 trendline_window_size_(kDefaultTrendlineWindowSize), |
70 trendline_smoothing_coeff_(kDefaultTrendlineSmoothingCoeff), | 167 trendline_smoothing_coeff_(kDefaultTrendlineSmoothingCoeff), |
71 trendline_threshold_gain_(kDefaultTrendlineThresholdGain), | 168 trendline_threshold_gain_(kDefaultTrendlineThresholdGain), |
72 consecutive_delayed_feedbacks_(0), | 169 consecutive_delayed_feedbacks_(0), |
73 last_logged_bitrate_(0), | 170 last_logged_bitrate_(0), |
74 last_logged_state_(BandwidthUsage::kBwNormal), | 171 last_logged_state_(BandwidthUsage::kBwNormal), |
75 in_sparse_update_experiment_(BweSparseUpdateExperimentIsEnabled()) { | 172 in_sparse_update_experiment_(BweSparseUpdateExperimentIsEnabled()) { |
76 LOG(LS_INFO) << "Using Trendline filter for delay change estimation."; | 173 LOG(LS_INFO) << "Using Trendline filter for delay change estimation."; |
77 network_thread_.DetachFromThread(); | 174 network_thread_.DetachFromThread(); |
78 } | 175 } |
79 | 176 |
80 DelayBasedBwe::~DelayBasedBwe() {} | 177 DelayBasedBwe::~DelayBasedBwe() {} |
81 | 178 |
82 DelayBasedBwe::Result DelayBasedBwe::IncomingPacketFeedbackVector( | 179 DelayBasedBwe::Result DelayBasedBwe::IncomingPacketFeedbackVector( |
83 const std::vector<PacketFeedback>& packet_feedback_vector, | 180 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())); | |
88 RTC_DCHECK(network_thread_.CalledOnValidThread()); | 181 RTC_DCHECK(network_thread_.CalledOnValidThread()); |
89 | 182 |
| 183 std::vector<PacketFeedback> sorted_packet_feedback_vector; |
| 184 SortPacketFeedbackVector(packet_feedback_vector, |
| 185 &sorted_packet_feedback_vector); |
90 // TOOD(holmer): An empty feedback vector here likely means that | 186 // TOOD(holmer): An empty feedback vector here likely means that |
91 // all acks were too late and that the send time history had | 187 // all acks were too late and that the send time history had |
92 // timed out. We should reduce the rate when this occurs. | 188 // timed out. We should reduce the rate when this occurs. |
93 if (packet_feedback_vector.empty()) { | 189 if (sorted_packet_feedback_vector.empty()) { |
94 LOG(LS_WARNING) << "Very late feedback received."; | 190 LOG(LS_WARNING) << "Very late feedback received."; |
95 return DelayBasedBwe::Result(); | 191 return DelayBasedBwe::Result(); |
96 } | 192 } |
97 | 193 |
98 if (!uma_recorded_) { | 194 if (!uma_recorded_) { |
99 RTC_HISTOGRAM_ENUMERATION(kBweTypeHistogram, | 195 RTC_HISTOGRAM_ENUMERATION(kBweTypeHistogram, |
100 BweNames::kSendSideTransportSeqNum, | 196 BweNames::kSendSideTransportSeqNum, |
101 BweNames::kBweNamesMax); | 197 BweNames::kBweNamesMax); |
102 uma_recorded_ = true; | 198 uma_recorded_ = true; |
103 } | 199 } |
104 bool overusing = false; | 200 bool overusing = false; |
105 bool delayed_feedback = true; | 201 bool delayed_feedback = true; |
106 for (const auto& packet_feedback : packet_feedback_vector) { | 202 for (const auto& packet_feedback : sorted_packet_feedback_vector) { |
107 if (packet_feedback.send_time_ms < 0) | 203 if (packet_feedback.send_time_ms < 0) |
108 continue; | 204 continue; |
109 delayed_feedback = false; | 205 delayed_feedback = false; |
110 IncomingPacketFeedback(packet_feedback); | 206 IncomingPacketFeedback(packet_feedback); |
111 if (!in_sparse_update_experiment_) | 207 if (!in_sparse_update_experiment_) |
112 overusing |= (detector_.State() == BandwidthUsage::kBwOverusing); | 208 overusing |= (detector_.State() == BandwidthUsage::kBwOverusing); |
113 } | 209 } |
114 if (in_sparse_update_experiment_) | 210 if (in_sparse_update_experiment_) |
115 overusing = (detector_.State() == BandwidthUsage::kBwOverusing); | 211 overusing = (detector_.State() == BandwidthUsage::kBwOverusing); |
116 if (delayed_feedback) { | 212 if (delayed_feedback) { |
117 ++consecutive_delayed_feedbacks_; | 213 ++consecutive_delayed_feedbacks_; |
118 if (consecutive_delayed_feedbacks_ >= kMaxConsecutiveFailedLookups) { | 214 if (consecutive_delayed_feedbacks_ >= kMaxConsecutiveFailedLookups) { |
119 consecutive_delayed_feedbacks_ = 0; | 215 consecutive_delayed_feedbacks_ = 0; |
120 return OnLongFeedbackDelay(packet_feedback_vector.back().arrival_time_ms); | 216 return OnLongFeedbackDelay( |
| 217 sorted_packet_feedback_vector.back().arrival_time_ms); |
121 } | 218 } |
122 } else { | 219 } else { |
123 consecutive_delayed_feedbacks_ = 0; | 220 consecutive_delayed_feedbacks_ = 0; |
124 return MaybeUpdateEstimate(overusing, acked_bitrate_bps); | 221 return MaybeUpdateEstimate(overusing); |
125 } | 222 } |
126 return Result(); | 223 return Result(); |
127 } | 224 } |
128 | 225 |
129 DelayBasedBwe::Result DelayBasedBwe::OnLongFeedbackDelay( | 226 DelayBasedBwe::Result DelayBasedBwe::OnLongFeedbackDelay( |
130 int64_t arrival_time_ms) { | 227 int64_t arrival_time_ms) { |
131 // Estimate should always be valid since a start bitrate always is set in the | 228 // Estimate should always be valid since a start bitrate always is set in the |
132 // Call constructor. An alternative would be to return an empty Result here, | 229 // Call constructor. An alternative would be to return an empty Result here, |
133 // or to estimate the throughput based on the feedback we received. | 230 // or to estimate the throughput based on the feedback we received. |
134 RTC_DCHECK(rate_control_.ValidEstimate()); | 231 RTC_DCHECK(rate_control_.ValidEstimate()); |
135 rate_control_.SetEstimate(rate_control_.LatestEstimate() / 2, | 232 rate_control_.SetEstimate(rate_control_.LatestEstimate() / 2, |
136 arrival_time_ms); | 233 arrival_time_ms); |
137 Result result; | 234 Result result; |
138 result.updated = true; | 235 result.updated = true; |
139 result.probe = false; | 236 result.probe = false; |
140 result.target_bitrate_bps = rate_control_.LatestEstimate(); | 237 result.target_bitrate_bps = rate_control_.LatestEstimate(); |
141 LOG(LS_WARNING) << "Long feedback delay detected, reducing BWE to " | 238 LOG(LS_WARNING) << "Long feedback delay detected, reducing BWE to " |
142 << result.target_bitrate_bps; | 239 << result.target_bitrate_bps; |
143 return result; | 240 return result; |
144 } | 241 } |
145 | 242 |
146 void DelayBasedBwe::IncomingPacketFeedback( | 243 void DelayBasedBwe::IncomingPacketFeedback( |
147 const PacketFeedback& packet_feedback) { | 244 const PacketFeedback& packet_feedback) { |
148 int64_t now_ms = clock_->TimeInMilliseconds(); | 245 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; |
149 // Reset if the stream has timed out. | 250 // Reset if the stream has timed out. |
150 if (last_seen_packet_ms_ == -1 || | 251 if (last_seen_packet_ms_ == -1 || |
151 now_ms - last_seen_packet_ms_ > kStreamTimeOutMs) { | 252 now_ms - last_seen_packet_ms_ > kStreamTimeOutMs) { |
152 inter_arrival_.reset( | 253 inter_arrival_.reset( |
153 new InterArrival((kTimestampGroupLengthMs << kInterArrivalShift) / 1000, | 254 new InterArrival((kTimestampGroupLengthMs << kInterArrivalShift) / 1000, |
154 kTimestampToMs, true)); | 255 kTimestampToMs, true)); |
155 trendline_estimator_.reset(new TrendlineEstimator( | 256 trendline_estimator_.reset(new TrendlineEstimator( |
156 trendline_window_size_, trendline_smoothing_coeff_, | 257 trendline_window_size_, trendline_smoothing_coeff_, |
157 trendline_threshold_gain_)); | 258 trendline_threshold_gain_)); |
158 } | 259 } |
(...skipping 22 matching lines...) Expand all Loading... |
181 detector_.Detect(trendline_estimator_->trendline_slope(), ts_delta_ms, | 282 detector_.Detect(trendline_estimator_->trendline_slope(), ts_delta_ms, |
182 trendline_estimator_->num_of_deltas(), | 283 trendline_estimator_->num_of_deltas(), |
183 packet_feedback.arrival_time_ms); | 284 packet_feedback.arrival_time_ms); |
184 } | 285 } |
185 if (packet_feedback.pacing_info.probe_cluster_id != | 286 if (packet_feedback.pacing_info.probe_cluster_id != |
186 PacedPacketInfo::kNotAProbe) { | 287 PacedPacketInfo::kNotAProbe) { |
187 probe_bitrate_estimator_.HandleProbeAndEstimateBitrate(packet_feedback); | 288 probe_bitrate_estimator_.HandleProbeAndEstimateBitrate(packet_feedback); |
188 } | 289 } |
189 } | 290 } |
190 | 291 |
191 DelayBasedBwe::Result DelayBasedBwe::MaybeUpdateEstimate( | 292 DelayBasedBwe::Result DelayBasedBwe::MaybeUpdateEstimate(bool overusing) { |
192 bool overusing, | |
193 rtc::Optional<uint32_t> acked_bitrate_bps) { | |
194 Result result; | 293 Result result; |
195 int64_t now_ms = clock_->TimeInMilliseconds(); | 294 int64_t now_ms = clock_->TimeInMilliseconds(); |
196 | 295 |
| 296 rtc::Optional<uint32_t> acked_bitrate_bps = |
| 297 receiver_incoming_bitrate_.bitrate_bps(); |
197 rtc::Optional<int> probe_bitrate_bps = | 298 rtc::Optional<int> probe_bitrate_bps = |
198 probe_bitrate_estimator_.FetchAndResetLastEstimatedBitrateBps(); | 299 probe_bitrate_estimator_.FetchAndResetLastEstimatedBitrateBps(); |
199 // Currently overusing the bandwidth. | 300 // Currently overusing the bandwidth. |
200 if (overusing) { | 301 if (overusing) { |
201 if (acked_bitrate_bps && | 302 if (acked_bitrate_bps && |
202 rate_control_.TimeToReduceFurther(now_ms, *acked_bitrate_bps)) { | 303 rate_control_.TimeToReduceFurther(now_ms, *acked_bitrate_bps)) { |
203 result.updated = UpdateEstimate(now_ms, acked_bitrate_bps, overusing, | 304 result.updated = UpdateEstimate(now_ms, acked_bitrate_bps, overusing, |
204 &result.target_bitrate_bps); | 305 &result.target_bitrate_bps); |
205 } | 306 } |
206 } else { | 307 } else { |
(...skipping 59 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
266 void DelayBasedBwe::SetMinBitrate(int min_bitrate_bps) { | 367 void DelayBasedBwe::SetMinBitrate(int min_bitrate_bps) { |
267 // Called from both the configuration thread and the network thread. Shouldn't | 368 // Called from both the configuration thread and the network thread. Shouldn't |
268 // be called from the network thread in the future. | 369 // be called from the network thread in the future. |
269 rate_control_.SetMinBitrate(min_bitrate_bps); | 370 rate_control_.SetMinBitrate(min_bitrate_bps); |
270 } | 371 } |
271 | 372 |
272 int64_t DelayBasedBwe::GetExpectedBwePeriodMs() const { | 373 int64_t DelayBasedBwe::GetExpectedBwePeriodMs() const { |
273 return rate_control_.GetExpectedBandwidthPeriodMs(); | 374 return rate_control_.GetExpectedBandwidthPeriodMs(); |
274 } | 375 } |
275 } // namespace webrtc | 376 } // namespace webrtc |
OLD | NEW |