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