Home | History | Annotate | Download | only in bitrate_controller 
      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