src/media/cast/sender/congestion_control.cc

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 // The purpose of this file is determine what bitrate to use for mirroring.
   6 // Ideally this should be as much as possible, without causing any frames to
   7 // arrive late.
   8
   9 // The current algorithm is to measure how much bandwidth we've been using
  10 // recently. We also keep track of how much data has been queued up for sending
  11 // in a virtual "buffer" (this virtual buffer represents all the buffers between
  12 // the sender and the receiver, including retransmissions and so forth.)
  13 // If we estimate that our virtual buffer is mostly empty, we try to use
  14 // more bandwidth than our recent usage, otherwise we use less.
  15
  16 #include "media/cast/sender/congestion_control.h"
  17
  18 #include "base/logging.h"
  19 #include "media/cast/cast_config.h"
  20 #include "media/cast/cast_defines.h"
  21
  22 namespace media {
  23 namespace cast {
  24
  25 // This means that we *try* to keep our buffer 90% empty.
  26 // If it is less full, we increase the bandwidth, if it is more
  27 // we decrease the bandwidth. Making this smaller makes the
  28 // congestion control more aggressive.
  29 static const double kTargetEmptyBufferFraction = 0.9;
  30
  31 // This is the size of our history in frames. Larger values makes the
  32 // congestion control adapt slower.
  33 static const size_t kHistorySize = 100;
  34
  35 CongestionControl::FrameStats::FrameStats() : frame_size(0) {
  36 }
  37
  38 CongestionControl::CongestionControl(base::TickClock* clock,
  39                                      uint32 max_bitrate_configured,
  40                                      uint32 min_bitrate_configured,
  41                                      size_t max_unacked_frames)
  42     : clock_(clock),
  43       max_bitrate_configured_(max_bitrate_configured),
  44       min_bitrate_configured_(min_bitrate_configured),
  45       last_frame_stats_(static_cast<uint32>(-1)),
  46       last_acked_frame_(static_cast<uint32>(-1)),
  47       last_encoded_frame_(static_cast<uint32>(-1)),
  48       history_size_(max_unacked_frames + kHistorySize),
  49       acked_bits_in_history_(0) {
  50   DCHECK_GE(max_bitrate_configured, min_bitrate_configured) << "Invalid config";
  51   frame_stats_.resize(2);
  52   base::TimeTicks now = clock->NowTicks();
  53   frame_stats_[0].ack_time = now;
  54   frame_stats_[0].sent_time = now;
  55   frame_stats_[1].ack_time = now;
  56   DCHECK(!frame_stats_[0].ack_time.is_null());
  57 }
  58
  59 CongestionControl::~CongestionControl() {}
  60
  61 void CongestionControl::UpdateRtt(base::TimeDelta rtt) {
  62   rtt_ = (7 * rtt_ + rtt) / 8;
  63 }
  64
  65 // Calculate how much "dead air" there is between two frames.
  66 base::TimeDelta CongestionControl::DeadTime(const FrameStats& a,
  67                                             const FrameStats& b) {
  68   if (b.sent_time > a.ack_time) {
  69     return b.sent_time - a.ack_time;
  70   } else {
  71     return base::TimeDelta();
  72   }
  73 }
  74
  75 double CongestionControl::CalculateSafeBitrate() {
  76   double transmit_time =
  77       (GetFrameStats(last_acked_frame_)->ack_time -
  78        frame_stats_.front().sent_time - dead_time_in_history_).InSecondsF();
  79
  80   if (acked_bits_in_history_ == 0 || transmit_time <= 0.0) {
  81     return min_bitrate_configured_;
  82   }
  83   return acked_bits_in_history_ / std::max(transmit_time, 1E-3);
  84 }
  85
  86 CongestionControl::FrameStats* CongestionControl::GetFrameStats(
  87     uint32 frame_id) {
  88   int32 offset = static_cast<int32>(frame_id - last_frame_stats_);
  89   DCHECK_LT(offset, static_cast<int32>(kHistorySize));
  90   if (offset > 0) {
  91     frame_stats_.resize(frame_stats_.size() + offset);
  92     last_frame_stats_ += offset;
  93     offset = 0;
  94   }
  95   while (frame_stats_.size() > history_size_) {
  96     DCHECK_GT(frame_stats_.size(), 1UL);
  97     DCHECK(!frame_stats_[0].ack_time.is_null());
  98     acked_bits_in_history_ -= frame_stats_[0].frame_size;
  99     dead_time_in_history_ -= DeadTime(frame_stats_[0], frame_stats_[1]);
 100     DCHECK_GE(acked_bits_in_history_, 0UL);
 101     VLOG(2) << "DT: " << dead_time_in_history_.InSecondsF();
 102     DCHECK_GE(dead_time_in_history_.InSecondsF(), 0.0);
 103     frame_stats_.pop_front();
 104   }
 105   offset += frame_stats_.size() - 1;
 106   if (offset < 0 || offset >= static_cast<int32>(frame_stats_.size())) {
 107     return NULL;
 108   }
 109   return &frame_stats_[offset];
 110 }
 111
 112 void CongestionControl::AckFrame(uint32 frame_id, base::TimeTicks when) {
 113   FrameStats* frame_stats = GetFrameStats(last_acked_frame_);
 114   while (IsNewerFrameId(frame_id, last_acked_frame_)) {
 115     FrameStats* last_frame_stats = frame_stats;
 116     frame_stats = GetFrameStats(last_acked_frame_ + 1);
 117     DCHECK(frame_stats);
 118     if (frame_stats->sent_time.is_null()) {
 119       // Can't ack a frame that hasn't been sent yet.
 120       return;
 121     }
 122     last_acked_frame_++;
 123     if (when < frame_stats->sent_time)
 124       when = frame_stats->sent_time;
 125
 126     frame_stats->ack_time = when;
 127     acked_bits_in_history_ += frame_stats->frame_size;
 128     dead_time_in_history_ += DeadTime(*last_frame_stats, *frame_stats);
 129   }
 130 }
 131
 132 void CongestionControl::SendFrameToTransport(uint32 frame_id,
 133                                              size_t frame_size,
 134                                              base::TimeTicks when) {
 135   last_encoded_frame_ = frame_id;
 136   FrameStats* frame_stats = GetFrameStats(frame_id);
 137   DCHECK(frame_stats);
 138   frame_stats->frame_size = frame_size;
 139   frame_stats->sent_time = when;
 140 }
 141
 142 base::TimeTicks CongestionControl::EstimatedAckTime(uint32 frame_id,
 143                                                     double bitrate) {
 144   FrameStats* frame_stats = GetFrameStats(frame_id);
 145   DCHECK(frame_stats);
 146   if (frame_stats->ack_time.is_null()) {
 147     DCHECK(frame_stats->frame_size) << "frame_id: " << frame_id;
 148     base::TimeTicks ret = EstimatedSendingTime(frame_id, bitrate);
 149     ret += base::TimeDelta::FromSecondsD(frame_stats->frame_size / bitrate);
 150     ret += rtt_;
 151     base::TimeTicks now = clock_->NowTicks();
 152     if (ret < now) {
 153       // This is a little counter-intuitive, but it seems to work.
 154       // Basically, when we estimate that the ACK should have already happened,
 155       // we figure out how long ago it should have happened and guess that the
 156       // ACK will happen half of that time in the future. This will cause some
 157       // over-estimation when acks are late, which is actually what we want.
 158       return now + (now - ret) / 2;
 159     } else {
 160       return ret;
 161     }
 162   } else {
 163     return frame_stats->ack_time;
 164   }
 165 }
 166
 167 base::TimeTicks CongestionControl::EstimatedSendingTime(uint32 frame_id,
 168                                                         double bitrate) {
 169   FrameStats* frame_stats = GetFrameStats(frame_id);
 170   DCHECK(frame_stats);
 171   base::TimeTicks ret = EstimatedAckTime(frame_id - 1, bitrate) - rtt_;
 172   if (frame_stats->sent_time.is_null()) {
 173     // Not sent yet, but we can't start sending it in the past.
 174     return std::max(ret, clock_->NowTicks());
 175   } else {
 176     return std::max(ret, frame_stats->sent_time);
 177   }
 178 }
 179
 180 uint32 CongestionControl::GetBitrate(base::TimeTicks playout_time,
 181                                      base::TimeDelta playout_delay) {
 182   double safe_bitrate = CalculateSafeBitrate();
 183   // Estimate when we might start sending the next frame.
 184   base::TimeDelta time_to_catch_up =
 185       playout_time -
 186       EstimatedSendingTime(last_encoded_frame_ + 1, safe_bitrate);
 187
 188   double empty_buffer_fraction =
 189       time_to_catch_up.InSecondsF() / playout_delay.InSecondsF();
 190   empty_buffer_fraction = std::min(empty_buffer_fraction, 1.0);
 191   empty_buffer_fraction = std::max(empty_buffer_fraction, 0.0);
 192
 193   uint32 bits_per_second = static_cast<uint32>(
 194       safe_bitrate * empty_buffer_fraction / kTargetEmptyBufferFraction);
 195   VLOG(3) << " FBR:" << (bits_per_second / 1E6)
 196           << " EBF:" << empty_buffer_fraction
 197           << " SBR:" << (safe_bitrate / 1E6);
 198   bits_per_second = std::max(bits_per_second, min_bitrate_configured_);
 199   bits_per_second = std::min(bits_per_second, max_bitrate_configured_);
 200   return bits_per_second;
 201 }
 202
 203 }  // namespace cast
 204 }  // namespace media