1 /*
2 * Copyright (c) 2018 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/congestion_controller/pcc/pcc_network_controller.h"
12
13 #include <algorithm>
14
15 #include "absl/types/optional.h"
16 #include "api/units/data_size.h"
17 #include "rtc_base/checks.h"
18
19 namespace webrtc {
20 namespace pcc {
21 namespace {
22 constexpr int64_t kInitialRttMs = 200;
23 constexpr int64_t kInitialBandwidthKbps = 300;
24 constexpr double kMonitorIntervalDurationRatio = 1;
25 constexpr double kDefaultSamplingStep = 0.05;
26 constexpr double kTimeoutRatio = 2;
27 constexpr double kAlphaForRtt = 0.9;
28 constexpr double kSlowStartModeIncrease = 1.5;
29
30 constexpr double kAlphaForPacketInterval = 0.9;
31 constexpr int64_t kMinPacketsNumberPerInterval = 20;
32 const TimeDelta kMinDurationOfMonitorInterval = TimeDelta::Millis(50);
33 const TimeDelta kStartupDuration = TimeDelta::Millis(500);
34 constexpr double kMinRateChangeBps = 4000;
35 constexpr DataRate kMinRateHaveMultiplicativeRateChange = DataRate::BitsPerSec(
36 static_cast<int64_t>(kMinRateChangeBps / kDefaultSamplingStep));
37
38 // Bitrate controller constants.
39 constexpr double kInitialConversionFactor = 5;
40 constexpr double kInitialDynamicBoundary = 0.1;
41 constexpr double kDynamicBoundaryIncrement = 0.1;
42 // Utility function parameters.
43 constexpr double kRttGradientCoefficientBps = 0.005;
44 constexpr double kLossCoefficientBps = 10;
45 constexpr double kThroughputCoefficient = 0.001;
46 constexpr double kThroughputPower = 0.9;
47 constexpr double kRttGradientThreshold = 0.01;
48 constexpr double kDelayGradientNegativeBound = 0.1;
49
50 constexpr int64_t kNumberOfPacketsToKeep = 20;
51 const uint64_t kRandomSeed = 100;
52 } // namespace
53
PccNetworkController(NetworkControllerConfig config)54 PccNetworkController::PccNetworkController(NetworkControllerConfig config)
55 : start_time_(Timestamp::PlusInfinity()),
56 last_sent_packet_time_(Timestamp::PlusInfinity()),
57 smoothed_packets_sending_interval_(TimeDelta::Zero()),
58 mode_(Mode::kStartup),
59 default_bandwidth_(DataRate::KilobitsPerSec(kInitialBandwidthKbps)),
60 bandwidth_estimate_(default_bandwidth_),
61 rtt_tracker_(TimeDelta::Millis(kInitialRttMs), kAlphaForRtt),
62 monitor_interval_timeout_(TimeDelta::Millis(kInitialRttMs) *
63 kTimeoutRatio),
64 monitor_interval_length_strategy_(MonitorIntervalLengthStrategy::kFixed),
65 monitor_interval_duration_ratio_(kMonitorIntervalDurationRatio),
66 sampling_step_(kDefaultSamplingStep),
67 monitor_interval_timeout_ratio_(kTimeoutRatio),
68 min_packets_number_per_interval_(kMinPacketsNumberPerInterval),
69 bitrate_controller_(kInitialConversionFactor,
70 kInitialDynamicBoundary,
71 kDynamicBoundaryIncrement,
72 kRttGradientCoefficientBps,
73 kLossCoefficientBps,
74 kThroughputCoefficient,
75 kThroughputPower,
76 kRttGradientThreshold,
77 kDelayGradientNegativeBound),
78 monitor_intervals_duration_(TimeDelta::Zero()),
79 complete_feedback_monitor_interval_number_(0),
80 random_generator_(kRandomSeed) {
81 if (config.constraints.starting_rate) {
82 default_bandwidth_ = *config.constraints.starting_rate;
83 bandwidth_estimate_ = default_bandwidth_;
84 }
85 }
86
~PccNetworkController()87 PccNetworkController::~PccNetworkController() {}
88
CreateRateUpdate(Timestamp at_time) const89 NetworkControlUpdate PccNetworkController::CreateRateUpdate(
90 Timestamp at_time) const {
91 DataRate sending_rate = DataRate::Zero();
92 if (monitor_intervals_.empty() ||
93 (monitor_intervals_.size() >= monitor_intervals_bitrates_.size() &&
94 at_time >= monitor_intervals_.back().GetEndTime())) {
95 sending_rate = bandwidth_estimate_;
96 } else {
97 sending_rate = monitor_intervals_.back().GetTargetSendingRate();
98 }
99 // Set up config when sending rate is computed.
100 NetworkControlUpdate update;
101
102 // Set up target rate to encoder.
103 TargetTransferRate target_rate_msg;
104 target_rate_msg.at_time = at_time;
105 target_rate_msg.network_estimate.at_time = at_time;
106 target_rate_msg.network_estimate.round_trip_time = rtt_tracker_.GetRtt();
107 // TODO(koloskova): Add correct estimate.
108 target_rate_msg.network_estimate.loss_rate_ratio = 0;
109 target_rate_msg.network_estimate.bwe_period =
110 monitor_interval_duration_ratio_ * rtt_tracker_.GetRtt();
111
112 target_rate_msg.target_rate = sending_rate;
113 update.target_rate = target_rate_msg;
114
115 // Set up pacing/padding target rate.
116 PacerConfig pacer_config;
117 pacer_config.at_time = at_time;
118 pacer_config.time_window = TimeDelta::Millis(1);
119 pacer_config.data_window = sending_rate * pacer_config.time_window;
120 pacer_config.pad_window = sending_rate * pacer_config.time_window;
121
122 update.pacer_config = pacer_config;
123 return update;
124 }
125
OnSentPacket(SentPacket msg)126 NetworkControlUpdate PccNetworkController::OnSentPacket(SentPacket msg) {
127 // Start new monitor interval if previous has finished.
128 // Monitor interval is initialized in OnProcessInterval function.
129 if (start_time_.IsInfinite()) {
130 start_time_ = msg.send_time;
131 monitor_intervals_duration_ = kStartupDuration;
132 monitor_intervals_bitrates_ = {bandwidth_estimate_};
133 monitor_intervals_.emplace_back(bandwidth_estimate_, msg.send_time,
134 monitor_intervals_duration_);
135 complete_feedback_monitor_interval_number_ = 0;
136 }
137 if (last_sent_packet_time_.IsFinite()) {
138 smoothed_packets_sending_interval_ =
139 (msg.send_time - last_sent_packet_time_) * kAlphaForPacketInterval +
140 (1 - kAlphaForPacketInterval) * smoothed_packets_sending_interval_;
141 }
142 last_sent_packet_time_ = msg.send_time;
143 if (!monitor_intervals_.empty() &&
144 msg.send_time >= monitor_intervals_.back().GetEndTime() &&
145 monitor_intervals_bitrates_.size() > monitor_intervals_.size()) {
146 // Start new monitor interval.
147 monitor_intervals_.emplace_back(
148 monitor_intervals_bitrates_[monitor_intervals_.size()], msg.send_time,
149 monitor_intervals_duration_);
150 }
151 if (IsTimeoutExpired(msg.send_time)) {
152 DataSize received_size = DataSize::Zero();
153 for (size_t i = 1; i < last_received_packets_.size(); ++i) {
154 received_size += last_received_packets_[i].sent_packet.size;
155 }
156 TimeDelta sending_time = TimeDelta::Zero();
157 if (last_received_packets_.size() > 0)
158 sending_time = last_received_packets_.back().receive_time -
159 last_received_packets_.front().receive_time;
160 DataRate receiving_rate = bandwidth_estimate_;
161 if (sending_time > TimeDelta::Zero())
162 receiving_rate = received_size / sending_time;
163 bandwidth_estimate_ =
164 std::min<DataRate>(bandwidth_estimate_ * 0.5, receiving_rate);
165 if (mode_ == Mode::kSlowStart)
166 mode_ = Mode::kOnlineLearning;
167 }
168 if (mode_ == Mode::kStartup &&
169 msg.send_time - start_time_ >= kStartupDuration) {
170 DataSize received_size = DataSize::Zero();
171 for (size_t i = 1; i < last_received_packets_.size(); ++i) {
172 received_size += last_received_packets_[i].sent_packet.size;
173 }
174 TimeDelta sending_time = TimeDelta::Zero();
175 if (last_received_packets_.size() > 0)
176 sending_time = last_received_packets_.back().receive_time -
177 last_received_packets_.front().receive_time;
178 DataRate receiving_rate = bandwidth_estimate_;
179 if (sending_time > TimeDelta::Zero())
180 receiving_rate = received_size / sending_time;
181 bandwidth_estimate_ = receiving_rate;
182 monitor_intervals_.clear();
183 mode_ = Mode::kSlowStart;
184 monitor_intervals_duration_ = ComputeMonitorIntervalsDuration();
185 monitor_intervals_bitrates_ = {bandwidth_estimate_};
186 monitor_intervals_.emplace_back(bandwidth_estimate_, msg.send_time,
187 monitor_intervals_duration_);
188 bandwidth_estimate_ = bandwidth_estimate_ * (1 / kSlowStartModeIncrease);
189 complete_feedback_monitor_interval_number_ = 0;
190 return CreateRateUpdate(msg.send_time);
191 }
192 if (IsFeedbackCollectionDone() || IsTimeoutExpired(msg.send_time)) {
193 // Creating new monitor intervals.
194 monitor_intervals_.clear();
195 monitor_interval_timeout_ =
196 rtt_tracker_.GetRtt() * monitor_interval_timeout_ratio_;
197 monitor_intervals_duration_ = ComputeMonitorIntervalsDuration();
198 complete_feedback_monitor_interval_number_ = 0;
199 // Compute bitrates and start first monitor interval.
200 if (mode_ == Mode::kSlowStart) {
201 monitor_intervals_bitrates_ = {kSlowStartModeIncrease *
202 bandwidth_estimate_};
203 monitor_intervals_.emplace_back(
204 kSlowStartModeIncrease * bandwidth_estimate_, msg.send_time,
205 monitor_intervals_duration_);
206 } else {
207 RTC_DCHECK(mode_ == Mode::kOnlineLearning || mode_ == Mode::kDoubleCheck);
208 monitor_intervals_.clear();
209 int64_t sign = 2 * (random_generator_.Rand(0, 1) % 2) - 1;
210 RTC_DCHECK_GE(sign, -1);
211 RTC_DCHECK_LE(sign, 1);
212 if (bandwidth_estimate_ >= kMinRateHaveMultiplicativeRateChange) {
213 monitor_intervals_bitrates_ = {
214 bandwidth_estimate_ * (1 + sign * sampling_step_),
215 bandwidth_estimate_ * (1 - sign * sampling_step_)};
216 } else {
217 monitor_intervals_bitrates_ = {
218 DataRate::BitsPerSec(std::max<double>(
219 bandwidth_estimate_.bps() + sign * kMinRateChangeBps, 0)),
220 DataRate::BitsPerSec(std::max<double>(
221 bandwidth_estimate_.bps() - sign * kMinRateChangeBps, 0))};
222 }
223 monitor_intervals_.emplace_back(monitor_intervals_bitrates_[0],
224 msg.send_time,
225 monitor_intervals_duration_);
226 }
227 }
228 return CreateRateUpdate(msg.send_time);
229 }
230
ComputeMonitorIntervalsDuration() const231 TimeDelta PccNetworkController::ComputeMonitorIntervalsDuration() const {
232 TimeDelta monitor_intervals_duration = TimeDelta::Zero();
233 if (monitor_interval_length_strategy_ ==
234 MonitorIntervalLengthStrategy::kAdaptive) {
235 monitor_intervals_duration = std::max(
236 rtt_tracker_.GetRtt() * monitor_interval_duration_ratio_,
237 smoothed_packets_sending_interval_ * min_packets_number_per_interval_);
238 } else {
239 RTC_DCHECK(monitor_interval_length_strategy_ ==
240 MonitorIntervalLengthStrategy::kFixed);
241 monitor_intervals_duration =
242 smoothed_packets_sending_interval_ * min_packets_number_per_interval_;
243 }
244 monitor_intervals_duration =
245 std::max(kMinDurationOfMonitorInterval, monitor_intervals_duration);
246 return monitor_intervals_duration;
247 }
248
IsTimeoutExpired(Timestamp current_time) const249 bool PccNetworkController::IsTimeoutExpired(Timestamp current_time) const {
250 if (complete_feedback_monitor_interval_number_ >= monitor_intervals_.size()) {
251 return false;
252 }
253 return current_time -
254 monitor_intervals_[complete_feedback_monitor_interval_number_]
255 .GetEndTime() >=
256 monitor_interval_timeout_;
257 }
258
IsFeedbackCollectionDone() const259 bool PccNetworkController::IsFeedbackCollectionDone() const {
260 return complete_feedback_monitor_interval_number_ >=
261 monitor_intervals_bitrates_.size();
262 }
263
OnTransportPacketsFeedback(TransportPacketsFeedback msg)264 NetworkControlUpdate PccNetworkController::OnTransportPacketsFeedback(
265 TransportPacketsFeedback msg) {
266 if (msg.packet_feedbacks.empty())
267 return NetworkControlUpdate();
268 // Save packets to last_received_packets_ array.
269 for (const PacketResult& packet_result : msg.ReceivedWithSendInfo()) {
270 last_received_packets_.push_back(packet_result);
271 }
272 while (last_received_packets_.size() > kNumberOfPacketsToKeep) {
273 last_received_packets_.pop_front();
274 }
275 rtt_tracker_.OnPacketsFeedback(msg.PacketsWithFeedback(), msg.feedback_time);
276 // Skip rate update in case when online learning mode just started, but
277 // corresponding monitor intervals were not started yet.
278 if (mode_ == Mode::kOnlineLearning &&
279 monitor_intervals_bitrates_.size() < 2) {
280 return NetworkControlUpdate();
281 }
282 if (!IsFeedbackCollectionDone() && !monitor_intervals_.empty()) {
283 while (complete_feedback_monitor_interval_number_ <
284 monitor_intervals_.size()) {
285 monitor_intervals_[complete_feedback_monitor_interval_number_]
286 .OnPacketsFeedback(msg.PacketsWithFeedback());
287 if (!monitor_intervals_[complete_feedback_monitor_interval_number_]
288 .IsFeedbackCollectionDone())
289 break;
290 ++complete_feedback_monitor_interval_number_;
291 }
292 }
293 if (IsFeedbackCollectionDone()) {
294 if (mode_ == Mode::kDoubleCheck) {
295 mode_ = Mode::kOnlineLearning;
296 } else if (NeedDoubleCheckMeasurments()) {
297 mode_ = Mode::kDoubleCheck;
298 }
299 if (mode_ != Mode::kDoubleCheck)
300 UpdateSendingRateAndMode();
301 }
302 return NetworkControlUpdate();
303 }
304
NeedDoubleCheckMeasurments() const305 bool PccNetworkController::NeedDoubleCheckMeasurments() const {
306 if (mode_ == Mode::kSlowStart) {
307 return false;
308 }
309 double first_loss_rate = monitor_intervals_[0].GetLossRate();
310 double second_loss_rate = monitor_intervals_[1].GetLossRate();
311 DataRate first_bitrate = monitor_intervals_[0].GetTargetSendingRate();
312 DataRate second_bitrate = monitor_intervals_[1].GetTargetSendingRate();
313 if ((first_bitrate.bps() - second_bitrate.bps()) *
314 (first_loss_rate - second_loss_rate) <
315 0) {
316 return true;
317 }
318 return false;
319 }
320
UpdateSendingRateAndMode()321 void PccNetworkController::UpdateSendingRateAndMode() {
322 if (monitor_intervals_.empty() || !IsFeedbackCollectionDone()) {
323 return;
324 }
325 if (mode_ == Mode::kSlowStart) {
326 DataRate old_bandwidth_estimate = bandwidth_estimate_;
327 bandwidth_estimate_ =
328 bitrate_controller_
329 .ComputeRateUpdateForSlowStartMode(monitor_intervals_[0])
330 .value_or(bandwidth_estimate_);
331 if (bandwidth_estimate_ <= old_bandwidth_estimate)
332 mode_ = Mode::kOnlineLearning;
333 } else {
334 RTC_DCHECK(mode_ == Mode::kOnlineLearning);
335 bandwidth_estimate_ =
336 bitrate_controller_.ComputeRateUpdateForOnlineLearningMode(
337 monitor_intervals_, bandwidth_estimate_);
338 }
339 }
340
OnNetworkAvailability(NetworkAvailability msg)341 NetworkControlUpdate PccNetworkController::OnNetworkAvailability(
342 NetworkAvailability msg) {
343 return NetworkControlUpdate();
344 }
345
OnNetworkRouteChange(NetworkRouteChange msg)346 NetworkControlUpdate PccNetworkController::OnNetworkRouteChange(
347 NetworkRouteChange msg) {
348 return NetworkControlUpdate();
349 }
350
OnProcessInterval(ProcessInterval msg)351 NetworkControlUpdate PccNetworkController::OnProcessInterval(
352 ProcessInterval msg) {
353 return CreateRateUpdate(msg.at_time);
354 }
355
OnTargetRateConstraints(TargetRateConstraints msg)356 NetworkControlUpdate PccNetworkController::OnTargetRateConstraints(
357 TargetRateConstraints msg) {
358 return NetworkControlUpdate();
359 }
360
OnRemoteBitrateReport(RemoteBitrateReport)361 NetworkControlUpdate PccNetworkController::OnRemoteBitrateReport(
362 RemoteBitrateReport) {
363 return NetworkControlUpdate();
364 }
365
OnRoundTripTimeUpdate(RoundTripTimeUpdate)366 NetworkControlUpdate PccNetworkController::OnRoundTripTimeUpdate(
367 RoundTripTimeUpdate) {
368 return NetworkControlUpdate();
369 }
370
OnTransportLossReport(TransportLossReport)371 NetworkControlUpdate PccNetworkController::OnTransportLossReport(
372 TransportLossReport) {
373 return NetworkControlUpdate();
374 }
375
OnStreamsConfig(StreamsConfig msg)376 NetworkControlUpdate PccNetworkController::OnStreamsConfig(StreamsConfig msg) {
377 return NetworkControlUpdate();
378 }
379
OnReceivedPacket(ReceivedPacket msg)380 NetworkControlUpdate PccNetworkController::OnReceivedPacket(
381 ReceivedPacket msg) {
382 return NetworkControlUpdate();
383 }
384
OnNetworkStateEstimate(NetworkStateEstimate msg)385 NetworkControlUpdate PccNetworkController::OnNetworkStateEstimate(
386 NetworkStateEstimate msg) {
387 return NetworkControlUpdate();
388 }
389
390 } // namespace pcc
391 } // namespace webrtc
392