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. 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 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 61 SendSideBandwidthEstimation::~SendSideBandwidthEstimation() {} 62 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 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 77 void SendSideBandwidthEstimation::SetMinBitrate(uint32_t min_bitrate) { 78 min_bitrate_configured_ = min_bitrate; 79 } 80 81 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 89 void SendSideBandwidthEstimation::UpdateReceiverEstimate(uint32_t bandwidth) { 90 bwe_incoming_ = bandwidth; 91 CapBitrateToThresholds(); 92 } 93 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 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 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 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