1 /*
2 * Copyright (c) 2012 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 "webrtc/modules/bitrate_controller/send_side_bandwidth_estimation.h"
12
13 #include <cmath>
14
15 #include "webrtc/system_wrappers/interface/logging.h"
16
17 namespace webrtc {
18 namespace {
19 enum { kBweIncreaseIntervalMs = 1000 };
20 enum { kBweDecreaseIntervalMs = 300 };
21 enum { kLimitNumPackets = 20 };
22 enum { kAvgPacketSizeBytes = 1000 };
23
24 // Calculate the rate that TCP-Friendly Rate Control (TFRC) would apply.
25 // The formula in RFC 3448, Section 3.1, is used.
CalcTfrcBps(uint16_t rtt,uint8_t loss)26 uint32_t CalcTfrcBps(uint16_t rtt, uint8_t loss) {
27 if (rtt == 0 || loss == 0) {
28 // Input variables out of range.
29 return 0;
30 }
31 double R = static_cast<double>(rtt) / 1000; // RTT in seconds.
32 int b = 1; // Number of packets acknowledged by a single TCP acknowledgement:
33 // recommended = 1.
34 double t_RTO = 4.0 * R; // TCP retransmission timeout value in seconds
35 // recommended = 4*R.
36 double p = static_cast<double>(loss) / 255; // Packet loss rate in [0, 1).
37 double s = static_cast<double>(kAvgPacketSizeBytes);
38
39 // Calculate send rate in bytes/second.
40 double X =
41 s / (R * std::sqrt(2 * b * p / 3) +
42 (t_RTO * (3 * std::sqrt(3 * b * p / 8) * p * (1 + 32 * p * p))));
43
44 // Convert to bits/second.
45 return (static_cast<uint32_t>(X * 8));
46 }
47 }
48
SendSideBandwidthEstimation()49 SendSideBandwidthEstimation::SendSideBandwidthEstimation()
50 : accumulate_lost_packets_Q8_(0),
51 accumulate_expected_packets_(0),
52 bitrate_(0),
53 min_bitrate_configured_(0),
54 max_bitrate_configured_(0),
55 time_last_receiver_block_ms_(0),
56 last_fraction_loss_(0),
57 last_round_trip_time_ms_(0),
58 bwe_incoming_(0),
59 time_last_decrease_ms_(0) {}
60
~SendSideBandwidthEstimation()61 SendSideBandwidthEstimation::~SendSideBandwidthEstimation() {}
62
SetSendBitrate(uint32_t bitrate)63 void SendSideBandwidthEstimation::SetSendBitrate(uint32_t bitrate) {
64 bitrate_ = bitrate;
65
66 // Clear last sent bitrate history so the new value can be used directly
67 // and not capped.
68 min_bitrate_history_.clear();
69 }
70
SetMinMaxBitrate(uint32_t min_bitrate,uint32_t max_bitrate)71 void SendSideBandwidthEstimation::SetMinMaxBitrate(uint32_t min_bitrate,
72 uint32_t max_bitrate) {
73 min_bitrate_configured_ = min_bitrate;
74 max_bitrate_configured_ = max_bitrate;
75 }
76
SetMinBitrate(uint32_t min_bitrate)77 void SendSideBandwidthEstimation::SetMinBitrate(uint32_t min_bitrate) {
78 min_bitrate_configured_ = min_bitrate;
79 }
80
CurrentEstimate(uint32_t * bitrate,uint8_t * loss,uint32_t * rtt) const81 void SendSideBandwidthEstimation::CurrentEstimate(uint32_t* bitrate,
82 uint8_t* loss,
83 uint32_t* rtt) const {
84 *bitrate = bitrate_;
85 *loss = last_fraction_loss_;
86 *rtt = last_round_trip_time_ms_;
87 }
88
UpdateReceiverEstimate(uint32_t bandwidth)89 void SendSideBandwidthEstimation::UpdateReceiverEstimate(uint32_t bandwidth) {
90 bwe_incoming_ = bandwidth;
91 CapBitrateToThresholds();
92 }
93
UpdateReceiverBlock(uint8_t fraction_loss,uint32_t rtt,int number_of_packets,uint32_t now_ms)94 void SendSideBandwidthEstimation::UpdateReceiverBlock(uint8_t fraction_loss,
95 uint32_t rtt,
96 int number_of_packets,
97 uint32_t now_ms) {
98 // Update RTT.
99 last_round_trip_time_ms_ = rtt;
100
101 // Check sequence number diff and weight loss report
102 if (number_of_packets > 0) {
103 // Calculate number of lost packets.
104 const int num_lost_packets_Q8 = fraction_loss * number_of_packets;
105 // Accumulate reports.
106 accumulate_lost_packets_Q8_ += num_lost_packets_Q8;
107 accumulate_expected_packets_ += number_of_packets;
108
109 // Report loss if the total report is based on sufficiently many packets.
110 if (accumulate_expected_packets_ >= kLimitNumPackets) {
111 last_fraction_loss_ =
112 accumulate_lost_packets_Q8_ / accumulate_expected_packets_;
113
114 // Reset accumulators.
115 accumulate_lost_packets_Q8_ = 0;
116 accumulate_expected_packets_ = 0;
117 } else {
118 // Early return without updating estimate.
119 return;
120 }
121 }
122 time_last_receiver_block_ms_ = now_ms;
123 UpdateEstimate(now_ms);
124 }
125
UpdateEstimate(uint32_t now_ms)126 void SendSideBandwidthEstimation::UpdateEstimate(uint32_t now_ms) {
127 UpdateMinHistory(now_ms);
128
129 // Only start updating bitrate when receiving receiver blocks.
130 if (time_last_receiver_block_ms_ != 0) {
131 if (last_fraction_loss_ <= 5) {
132 // Loss < 2%: Increase rate by 8% of the min bitrate in the last
133 // kBweIncreaseIntervalMs.
134 // Note that by remembering the bitrate over the last second one can
135 // rampup up one second faster than if only allowed to start ramping
136 // at 8% per second rate now. E.g.:
137 // If sending a constant 100kbps it can rampup immediatly to 108kbps
138 // whenever a receiver report is received with lower packet loss.
139 // If instead one would do: bitrate_ *= 1.08^(delta time), it would
140 // take over one second since the lower packet loss to achieve 108kbps.
141 bitrate_ = static_cast<uint32_t>(
142 min_bitrate_history_.front().second * 1.08 + 0.5);
143
144 // Add 1 kbps extra, just to make sure that we do not get stuck
145 // (gives a little extra increase at low rates, negligible at higher
146 // rates).
147 bitrate_ += 1000;
148
149 } else if (last_fraction_loss_ <= 26) {
150 // Loss between 2% - 10%: Do nothing.
151
152 } else {
153 // Loss > 10%: Limit the rate decreases to once a kBweDecreaseIntervalMs +
154 // rtt.
155 if ((now_ms - time_last_decrease_ms_) >=
156 static_cast<uint32_t>(kBweDecreaseIntervalMs +
157 last_round_trip_time_ms_)) {
158 time_last_decrease_ms_ = now_ms;
159
160 // Reduce rate:
161 // newRate = rate * (1 - 0.5*lossRate);
162 // where packetLoss = 256*lossRate;
163 bitrate_ = static_cast<uint32_t>(
164 (bitrate_ * static_cast<double>(512 - last_fraction_loss_)) /
165 512.0);
166
167 // Calculate what rate TFRC would apply in this situation and to not
168 // reduce further than it.
169 bitrate_ = std::max(
170 bitrate_,
171 CalcTfrcBps(last_round_trip_time_ms_, last_fraction_loss_));
172 }
173 }
174 }
175 CapBitrateToThresholds();
176 }
177
UpdateMinHistory(uint32_t now_ms)178 void SendSideBandwidthEstimation::UpdateMinHistory(uint32_t now_ms) {
179 // Remove old data points from history.
180 // Since history precision is in ms, add one so it is able to increase
181 // bitrate if it is off by as little as 0.5ms.
182 while (!min_bitrate_history_.empty() &&
183 now_ms - min_bitrate_history_.front().first + 1 >
184 kBweIncreaseIntervalMs) {
185 min_bitrate_history_.pop_front();
186 }
187
188 // Typical minimum sliding-window algorithm: Pop values higher than current
189 // bitrate before pushing it.
190 while (!min_bitrate_history_.empty() &&
191 bitrate_ <= min_bitrate_history_.back().second) {
192 min_bitrate_history_.pop_back();
193 }
194
195 min_bitrate_history_.push_back(std::make_pair(now_ms, bitrate_));
196 }
197
CapBitrateToThresholds()198 void SendSideBandwidthEstimation::CapBitrateToThresholds() {
199 if (bwe_incoming_ > 0 && bitrate_ > bwe_incoming_) {
200 bitrate_ = bwe_incoming_;
201 }
202 if (bitrate_ > max_bitrate_configured_) {
203 bitrate_ = max_bitrate_configured_;
204 }
205 if (bitrate_ < min_bitrate_configured_) {
206 LOG(LS_WARNING) << "Estimated available bandwidth " << bitrate_ / 1000
207 << " kbps is below configured min bitrate "
208 << min_bitrate_configured_ / 1000 << " kbps.";
209 bitrate_ = min_bitrate_configured_;
210 }
211 }
212
213 } // namespace webrtc
214