• Home
  • History
  • Annotate
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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