send_side_bandwidth_estimation.cc revision 53805324c0fa904d796cc0b333868c591f2c5f2c 
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/base/checks.h"
16#include "webrtc/base/logging.h"
17#include "webrtc/system_wrappers/include/field_trial.h"
18#include "webrtc/system_wrappers/include/metrics.h"
19#include "webrtc/call/rtc_event_log.h"
20
21namespace webrtc {
22namespace {
23const int64_t kBweIncreaseIntervalMs = 1000;
24const int64_t kBweDecreaseIntervalMs = 300;
25const int64_t kStartPhaseMs = 2000;
26const int64_t kBweConverganceTimeMs = 20000;
27const int kLimitNumPackets = 20;
28const int kDefaultMinBitrateBps = 10000;
29const int kDefaultMaxBitrateBps = 1000000000;
30const int64_t kLowBitrateLogPeriodMs = 10000;
31
32struct UmaRampUpMetric {
33  const char* metric_name;
34  int bitrate_kbps;
35};
36
37const UmaRampUpMetric kUmaRampupMetrics[] = {
38    {"WebRTC.BWE.RampUpTimeTo500kbpsInMs", 500},
39    {"WebRTC.BWE.RampUpTimeTo1000kbpsInMs", 1000},
40    {"WebRTC.BWE.RampUpTimeTo2000kbpsInMs", 2000}};
41const size_t kNumUmaRampupMetrics =
42    sizeof(kUmaRampupMetrics) / sizeof(kUmaRampupMetrics[0]);
43
44}
45
46SendSideBandwidthEstimation::SendSideBandwidthEstimation()
47    : lost_packets_since_last_loss_update_Q8_(0),
48      expected_packets_since_last_loss_update_(0),
49      bitrate_(0),
50      min_bitrate_configured_(kDefaultMinBitrateBps),
51      max_bitrate_configured_(kDefaultMaxBitrateBps),
52      last_low_bitrate_log_ms_(-1),
53      has_decreased_since_last_fraction_loss_(false),
54      time_last_receiver_block_ms_(-1),
55      last_fraction_loss_(0),
56      last_round_trip_time_ms_(0),
57      bwe_incoming_(0),
58      time_last_decrease_ms_(0),
59      first_report_time_ms_(-1),
60      initially_lost_packets_(0),
61      bitrate_at_2_seconds_kbps_(0),
62      uma_update_state_(kNoUpdate),
63      rampup_uma_stats_updated_(kNumUmaRampupMetrics, false),
64      event_log_(nullptr) {}
65
66SendSideBandwidthEstimation::~SendSideBandwidthEstimation() {}
67
68void SendSideBandwidthEstimation::SetSendBitrate(int bitrate) {
69  RTC_DCHECK_GT(bitrate, 0);
70  bitrate_ = bitrate;
71
72  // Clear last sent bitrate history so the new value can be used directly
73  // and not capped.
74  min_bitrate_history_.clear();
75}
76
77void SendSideBandwidthEstimation::SetMinMaxBitrate(int min_bitrate,
78                                                   int max_bitrate) {
79  RTC_DCHECK_GE(min_bitrate, 0);
80  min_bitrate_configured_ = std::max(min_bitrate, kDefaultMinBitrateBps);
81  if (max_bitrate > 0) {
82    max_bitrate_configured_ =
83        std::max<uint32_t>(min_bitrate_configured_, max_bitrate);
84  } else {
85    max_bitrate_configured_ = kDefaultMaxBitrateBps;
86  }
87}
88
89int SendSideBandwidthEstimation::GetMinBitrate() const {
90  return min_bitrate_configured_;
91}
92
93void SendSideBandwidthEstimation::CurrentEstimate(int* bitrate,
94                                                  uint8_t* loss,
95                                                  int64_t* rtt) const {
96  *bitrate = bitrate_;
97  *loss = last_fraction_loss_;
98  *rtt = last_round_trip_time_ms_;
99}
100
101void SendSideBandwidthEstimation::UpdateReceiverEstimate(
102    int64_t now_ms, uint32_t bandwidth) {
103  bwe_incoming_ = bandwidth;
104  bitrate_ = CapBitrateToThresholds(now_ms, bitrate_);
105}
106
107void SendSideBandwidthEstimation::UpdateReceiverBlock(uint8_t fraction_loss,
108                                                      int64_t rtt,
109                                                      int number_of_packets,
110                                                      int64_t now_ms) {
111  if (first_report_time_ms_ == -1)
112    first_report_time_ms_ = now_ms;
113
114  // Update RTT.
115  last_round_trip_time_ms_ = rtt;
116
117  // Check sequence number diff and weight loss report
118  if (number_of_packets > 0) {
119    // Calculate number of lost packets.
120    const int num_lost_packets_Q8 = fraction_loss * number_of_packets;
121    // Accumulate reports.
122    lost_packets_since_last_loss_update_Q8_ += num_lost_packets_Q8;
123    expected_packets_since_last_loss_update_ += number_of_packets;
124
125    // Don't generate a loss rate until it can be based on enough packets.
126    if (expected_packets_since_last_loss_update_ < kLimitNumPackets)
127      return;
128
129    has_decreased_since_last_fraction_loss_ = false;
130    last_fraction_loss_ = lost_packets_since_last_loss_update_Q8_ /
131                          expected_packets_since_last_loss_update_;
132
133    // Reset accumulators.
134    lost_packets_since_last_loss_update_Q8_ = 0;
135    expected_packets_since_last_loss_update_ = 0;
136  }
137  time_last_receiver_block_ms_ = now_ms;
138  UpdateEstimate(now_ms);
139  UpdateUmaStats(now_ms, rtt, (fraction_loss * number_of_packets) >> 8);
140}
141
142void SendSideBandwidthEstimation::UpdateUmaStats(int64_t now_ms,
143                                                 int64_t rtt,
144                                                 int lost_packets) {
145  int bitrate_kbps = static_cast<int>((bitrate_ + 500) / 1000);
146  for (size_t i = 0; i < kNumUmaRampupMetrics; ++i) {
147    if (!rampup_uma_stats_updated_[i] &&
148        bitrate_kbps >= kUmaRampupMetrics[i].bitrate_kbps) {
149      RTC_HISTOGRAM_COUNTS_SPARSE_100000(kUmaRampupMetrics[i].metric_name,
150                                         now_ms - first_report_time_ms_);
151      rampup_uma_stats_updated_[i] = true;
152    }
153  }
154  if (IsInStartPhase(now_ms)) {
155    initially_lost_packets_ += lost_packets;
156  } else if (uma_update_state_ == kNoUpdate) {
157    uma_update_state_ = kFirstDone;
158    bitrate_at_2_seconds_kbps_ = bitrate_kbps;
159    RTC_HISTOGRAM_COUNTS_SPARSE("WebRTC.BWE.InitiallyLostPackets",
160                                initially_lost_packets_, 0, 100, 50);
161    RTC_HISTOGRAM_COUNTS_SPARSE("WebRTC.BWE.InitialRtt", static_cast<int>(rtt),
162                                0, 2000, 50);
163    RTC_HISTOGRAM_COUNTS_SPARSE("WebRTC.BWE.InitialBandwidthEstimate",
164                                bitrate_at_2_seconds_kbps_, 0, 2000, 50);
165  } else if (uma_update_state_ == kFirstDone &&
166             now_ms - first_report_time_ms_ >= kBweConverganceTimeMs) {
167    uma_update_state_ = kDone;
168    int bitrate_diff_kbps =
169        std::max(bitrate_at_2_seconds_kbps_ - bitrate_kbps, 0);
170    RTC_HISTOGRAM_COUNTS_SPARSE("WebRTC.BWE.InitialVsConvergedDiff",
171                                bitrate_diff_kbps, 0, 2000, 50);
172  }
173}
174
175void SendSideBandwidthEstimation::UpdateEstimate(int64_t now_ms) {
176  // We trust the REMB during the first 2 seconds if we haven't had any
177  // packet loss reported, to allow startup bitrate probing.
178  if (last_fraction_loss_ == 0 && IsInStartPhase(now_ms) &&
179      bwe_incoming_ > bitrate_) {
180    bitrate_ = CapBitrateToThresholds(now_ms, bwe_incoming_);
181    min_bitrate_history_.clear();
182    min_bitrate_history_.push_back(std::make_pair(now_ms, bitrate_));
183    return;
184  }
185  UpdateMinHistory(now_ms);
186  // Only start updating bitrate when receiving receiver blocks.
187  // TODO(pbos): Handle the case when no receiver report is received for a very
188  // long time.
189  if (time_last_receiver_block_ms_ != -1) {
190    if (last_fraction_loss_ <= 5) {
191      // Loss < 2%: Increase rate by 8% of the min bitrate in the last
192      // kBweIncreaseIntervalMs.
193      // Note that by remembering the bitrate over the last second one can
194      // rampup up one second faster than if only allowed to start ramping
195      // at 8% per second rate now. E.g.:
196      //   If sending a constant 100kbps it can rampup immediatly to 108kbps
197      //   whenever a receiver report is received with lower packet loss.
198      //   If instead one would do: bitrate_ *= 1.08^(delta time), it would
199      //   take over one second since the lower packet loss to achieve 108kbps.
200      bitrate_ = static_cast<uint32_t>(
201          min_bitrate_history_.front().second * 1.08 + 0.5);
202
203      // Add 1 kbps extra, just to make sure that we do not get stuck
204      // (gives a little extra increase at low rates, negligible at higher
205      // rates).
206      bitrate_ += 1000;
207
208      if (event_log_) {
209        event_log_->LogBwePacketLossEvent(
210            bitrate_, last_fraction_loss_,
211            expected_packets_since_last_loss_update_);
212      }
213    } else if (last_fraction_loss_ <= 26) {
214      // Loss between 2% - 10%: Do nothing.
215    } else {
216      // Loss > 10%: Limit the rate decreases to once a kBweDecreaseIntervalMs +
217      // rtt.
218      if (!has_decreased_since_last_fraction_loss_ &&
219          (now_ms - time_last_decrease_ms_) >=
220              (kBweDecreaseIntervalMs + last_round_trip_time_ms_)) {
221        time_last_decrease_ms_ = now_ms;
222
223        // Reduce rate:
224        //   newRate = rate * (1 - 0.5*lossRate);
225        //   where packetLoss = 256*lossRate;
226        bitrate_ = static_cast<uint32_t>(
227            (bitrate_ * static_cast<double>(512 - last_fraction_loss_)) /
228            512.0);
229        has_decreased_since_last_fraction_loss_ = true;
230      }
231      if (event_log_) {
232        event_log_->LogBwePacketLossEvent(
233            bitrate_, last_fraction_loss_,
234            expected_packets_since_last_loss_update_);
235      }
236    }
237  }
238  bitrate_ = CapBitrateToThresholds(now_ms, bitrate_);
239}
240
241bool SendSideBandwidthEstimation::IsInStartPhase(int64_t now_ms) const {
242  return first_report_time_ms_ == -1 ||
243         now_ms - first_report_time_ms_ < kStartPhaseMs;
244}
245
246void SendSideBandwidthEstimation::UpdateMinHistory(int64_t now_ms) {
247  // Remove old data points from history.
248  // Since history precision is in ms, add one so it is able to increase
249  // bitrate if it is off by as little as 0.5ms.
250  while (!min_bitrate_history_.empty() &&
251         now_ms - min_bitrate_history_.front().first + 1 >
252             kBweIncreaseIntervalMs) {
253    min_bitrate_history_.pop_front();
254  }
255
256  // Typical minimum sliding-window algorithm: Pop values higher than current
257  // bitrate before pushing it.
258  while (!min_bitrate_history_.empty() &&
259         bitrate_ <= min_bitrate_history_.back().second) {
260    min_bitrate_history_.pop_back();
261  }
262
263  min_bitrate_history_.push_back(std::make_pair(now_ms, bitrate_));
264}
265
266uint32_t SendSideBandwidthEstimation::CapBitrateToThresholds(
267    int64_t now_ms, uint32_t bitrate) {
268  if (bwe_incoming_ > 0 && bitrate > bwe_incoming_) {
269    bitrate = bwe_incoming_;
270  }
271  if (bitrate > max_bitrate_configured_) {
272    bitrate = max_bitrate_configured_;
273  }
274  if (bitrate < min_bitrate_configured_) {
275    if (last_low_bitrate_log_ms_ == -1 ||
276        now_ms - last_low_bitrate_log_ms_ > kLowBitrateLogPeriodMs) {
277      LOG(LS_WARNING) << "Estimated available bandwidth " << bitrate / 1000
278                      << " kbps is below configured min bitrate "
279                      << min_bitrate_configured_ / 1000 << " kbps.";
280      last_low_bitrate_log_ms_ = now_ms;
281    }
282    bitrate = min_bitrate_configured_;
283  }
284  return bitrate;
285}
286
287void SendSideBandwidthEstimation::SetEventLog(RtcEventLog* event_log) {
288  event_log_ = event_log;
289}
290
291}  // namespace webrtc
292