send_side_bandwidth_estimation.cc revision da07737e68e23e283466ae21965e43edfe621a12 
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/trace.h"
16
17namespace webrtc {
18namespace {
19enum { kBweIncreaseIntervalMs = 1000 };
20enum { kBweDecreaseIntervalMs = 300 };
21enum { kLimitNumPackets = 20 };
22enum { 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.
26uint32_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
49SendSideBandwidthEstimation::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
61SendSideBandwidthEstimation::~SendSideBandwidthEstimation() {}
62
63void 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
71void 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
77void SendSideBandwidthEstimation::SetMinBitrate(uint32_t min_bitrate) {
78  min_bitrate_configured_ = min_bitrate;
79}
80
81void 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
89void SendSideBandwidthEstimation::UpdateReceiverEstimate(uint32_t bandwidth) {
90  bwe_incoming_ = bandwidth;
91  CapBitrateToThresholds();
92}
93
94void 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
126void 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
178void 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
198void 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    WEBRTC_TRACE(kTraceWarning,
207                 kTraceRtpRtcp,
208                 -1,
209                 "The configured min bitrate (%u kbps) is greater than the "
210                 "estimated available bandwidth (%u kbps).\n",
211                 min_bitrate_configured_ / 1000,
212                 bitrate_ / 1000);
213    bitrate_ = min_bitrate_configured_;
214  }
215}
216
217}  // namespace webrtc
218