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 class AdaptiveCongestionControl : public CongestionControl {
  26  public:
  27   AdaptiveCongestionControl(base::TickClock* clock,
  28                             uint32 max_bitrate_configured,
  29                             uint32 min_bitrate_configured,
  30                             double max_frame_rate);
  31
  32   ~AdaptiveCongestionControl() override;
  33
  34   void UpdateRtt(base::TimeDelta rtt) override;
  35
  36   void UpdateTargetPlayoutDelay(base::TimeDelta delay) override;
  37
  38   // Called when an encoded frame is sent to the transport.
  39   void SendFrameToTransport(uint32 frame_id,
  40                             size_t frame_size,
  41                             base::TimeTicks when) override;
  42
  43   // Called when we receive an ACK for a frame.
  44   void AckFrame(uint32 frame_id, base::TimeTicks when) override;
  45
  46   // Returns the bitrate we should use for the next frame.
  47   uint32 GetBitrate(base::TimeTicks playout_time,
  48                     base::TimeDelta playout_delay) override;
  49
  50  private:
  51   struct FrameStats {
  52     FrameStats();
  53     // Time this frame was sent to the transport.
  54     base::TimeTicks sent_time;
  55     // Time this frame was acked.
  56     base::TimeTicks ack_time;
  57     // Size of encoded frame in bits.
  58     size_t frame_size;
  59   };
  60
  61   // Calculate how much "dead air" (idle time) there is between two frames.
  62   static base::TimeDelta DeadTime(const FrameStats& a, const FrameStats& b);
  63   // Get the FrameStats for a given |frame_id|.
  64   // Note: Older FrameStats will be removed automatically.
  65   FrameStats* GetFrameStats(uint32 frame_id);
  66   // Discard old FrameStats.
  67   void PruneFrameStats();
  68   // Calculate a safe bitrate. This is based on how much we've been
  69   // sending in the past.
  70   double CalculateSafeBitrate();
  71
  72   // For a given frame, calculate when it might be acked.
  73   // (Or return the time it was acked, if it was.)
  74   base::TimeTicks EstimatedAckTime(uint32 frame_id, double bitrate);
  75   // Calculate when we start sending the data for a given frame.
  76   // This is done by calculating when we were done sending the previous
  77   // frame, but obviously can't be less than |sent_time| (if known).
  78   base::TimeTicks EstimatedSendingTime(uint32 frame_id, double bitrate);
  79
  80   base::TickClock* const clock_;  // Not owned by this class.
  81   const uint32 max_bitrate_configured_;
  82   const uint32 min_bitrate_configured_;
  83   const double max_frame_rate_;
  84   std::deque<FrameStats> frame_stats_;
  85   uint32 last_frame_stats_;
  86   uint32 last_acked_frame_;
  87   uint32 last_encoded_frame_;
  88   base::TimeDelta rtt_;
  89   size_t history_size_;
  90   size_t acked_bits_in_history_;
  91   base::TimeDelta dead_time_in_history_;
  92
  93   DISALLOW_COPY_AND_ASSIGN(AdaptiveCongestionControl);
  94 };
  95
  96 class FixedCongestionControl : public CongestionControl {
  97  public:
  98   FixedCongestionControl(uint32 bitrate) : bitrate_(bitrate) {}
  99   ~FixedCongestionControl() override {}
 100
 101   void UpdateRtt(base::TimeDelta rtt) override {}
 102
 103   void UpdateTargetPlayoutDelay(base::TimeDelta delay) override {}
 104
 105   // Called when an encoded frame is sent to the transport.
 106   void SendFrameToTransport(uint32 frame_id,
 107                             size_t frame_size,
 108                             base::TimeTicks when) override {}
 109
 110   // Called when we receive an ACK for a frame.
 111   void AckFrame(uint32 frame_id, base::TimeTicks when) override {}
 112
 113   // Returns the bitrate we should use for the next frame.
 114   uint32 GetBitrate(base::TimeTicks playout_time,
 115                     base::TimeDelta playout_delay) override {
 116     return bitrate_;
 117   }
 118
 119  private:
 120   uint32 bitrate_;
 121   DISALLOW_COPY_AND_ASSIGN(FixedCongestionControl);
 122 };
 123
 124
 125 CongestionControl* NewAdaptiveCongestionControl(
 126     base::TickClock* clock,
 127     uint32 max_bitrate_configured,
 128     uint32 min_bitrate_configured,
 129     double max_frame_rate) {
 130   return new AdaptiveCongestionControl(clock,
 131                                        max_bitrate_configured,
 132                                        min_bitrate_configured,
 133                                        max_frame_rate);
 134 }
 135
 136 CongestionControl* NewFixedCongestionControl(uint32 bitrate) {
 137   return new FixedCongestionControl(bitrate);
 138 }
 139
 140 // This means that we *try* to keep our buffer 90% empty.
 141 // If it is less full, we increase the bandwidth, if it is more
 142 // we decrease the bandwidth. Making this smaller makes the
 143 // congestion control more aggressive.
 144 static const double kTargetEmptyBufferFraction = 0.9;
 145
 146 // This is the size of our history in frames. Larger values makes the
 147 // congestion control adapt slower.
 148 static const size_t kHistorySize = 100;
 149
 150 AdaptiveCongestionControl::FrameStats::FrameStats() : frame_size(0) {
 151 }
 152
 153 AdaptiveCongestionControl::AdaptiveCongestionControl(
 154     base::TickClock* clock,
 155     uint32 max_bitrate_configured,
 156     uint32 min_bitrate_configured,
 157     double max_frame_rate)
 158     : clock_(clock),
 159       max_bitrate_configured_(max_bitrate_configured),
 160       min_bitrate_configured_(min_bitrate_configured),
 161       max_frame_rate_(max_frame_rate),
 162       last_frame_stats_(static_cast<uint32>(-1)),
 163       last_acked_frame_(static_cast<uint32>(-1)),
 164       last_encoded_frame_(static_cast<uint32>(-1)),
 165       history_size_(kHistorySize),
 166       acked_bits_in_history_(0) {
 167   DCHECK_GE(max_bitrate_configured, min_bitrate_configured) << "Invalid config";
 168   frame_stats_.resize(2);
 169   base::TimeTicks now = clock->NowTicks();
 170   frame_stats_[0].ack_time = now;
 171   frame_stats_[0].sent_time = now;
 172   frame_stats_[1].ack_time = now;
 173   DCHECK(!frame_stats_[0].ack_time.is_null());
 174 }
 175
 176 CongestionControl::~CongestionControl() {}
 177 AdaptiveCongestionControl::~AdaptiveCongestionControl() {}
 178
 179 void AdaptiveCongestionControl::UpdateRtt(base::TimeDelta rtt) {
 180   rtt_ = (7 * rtt_ + rtt) / 8;
 181 }
 182
 183 void AdaptiveCongestionControl::UpdateTargetPlayoutDelay(
 184     base::TimeDelta delay) {
 185   const int max_unacked_frames =
 186       std::min(kMaxUnackedFrames,
 187                1 + static_cast<int>(delay * max_frame_rate_ /
 188                                     base::TimeDelta::FromSeconds(1)));
 189   DCHECK_GT(max_unacked_frames, 0);
 190   history_size_ = max_unacked_frames + kHistorySize;
 191   PruneFrameStats();
 192 }
 193
 194 // Calculate how much "dead air" there is between two frames.
 195 base::TimeDelta AdaptiveCongestionControl::DeadTime(const FrameStats& a,
 196                                                     const FrameStats& b) {
 197   if (b.sent_time > a.ack_time) {
 198     return b.sent_time - a.ack_time;
 199   } else {
 200     return base::TimeDelta();
 201   }
 202 }
 203
 204 double AdaptiveCongestionControl::CalculateSafeBitrate() {
 205   double transmit_time =
 206       (GetFrameStats(last_acked_frame_)->ack_time -
 207        frame_stats_.front().sent_time - dead_time_in_history_).InSecondsF();
 208
 209   if (acked_bits_in_history_ == 0 || transmit_time <= 0.0) {
 210     return min_bitrate_configured_;
 211   }
 212   return acked_bits_in_history_ / std::max(transmit_time, 1E-3);
 213 }
 214
 215 AdaptiveCongestionControl::FrameStats*
 216 AdaptiveCongestionControl::GetFrameStats(uint32 frame_id) {
 217   int32 offset = static_cast<int32>(frame_id - last_frame_stats_);
 218   DCHECK_LT(offset, static_cast<int32>(kHistorySize));
 219   if (offset > 0) {
 220     frame_stats_.resize(frame_stats_.size() + offset);
 221     last_frame_stats_ += offset;
 222     offset = 0;
 223   }
 224   PruneFrameStats();
 225   offset += frame_stats_.size() - 1;
 226   if (offset < 0 || offset >= static_cast<int32>(frame_stats_.size())) {
 227     return NULL;
 228   }
 229   return &frame_stats_[offset];
 230 }
 231
 232 void AdaptiveCongestionControl::PruneFrameStats() {
 233  while (frame_stats_.size() > history_size_) {
 234     DCHECK_GT(frame_stats_.size(), 1UL);
 235     DCHECK(!frame_stats_[0].ack_time.is_null());
 236     acked_bits_in_history_ -= frame_stats_[0].frame_size;
 237     dead_time_in_history_ -= DeadTime(frame_stats_[0], frame_stats_[1]);
 238     DCHECK_GE(acked_bits_in_history_, 0UL);
 239     VLOG(2) << "DT: " << dead_time_in_history_.InSecondsF();
 240     DCHECK_GE(dead_time_in_history_.InSecondsF(), 0.0);
 241     frame_stats_.pop_front();
 242   }
 243 }
 244
 245 void AdaptiveCongestionControl::AckFrame(uint32 frame_id,
 246                                          base::TimeTicks when) {
 247   FrameStats* frame_stats = GetFrameStats(last_acked_frame_);
 248   while (IsNewerFrameId(frame_id, last_acked_frame_)) {
 249     FrameStats* last_frame_stats = frame_stats;
 250     frame_stats = GetFrameStats(last_acked_frame_ + 1);
 251     DCHECK(frame_stats);
 252     if (frame_stats->sent_time.is_null()) {
 253       // Can't ack a frame that hasn't been sent yet.
 254       return;
 255     }
 256     last_acked_frame_++;
 257     if (when < frame_stats->sent_time)
 258       when = frame_stats->sent_time;
 259
 260     frame_stats->ack_time = when;
 261     acked_bits_in_history_ += frame_stats->frame_size;
 262     dead_time_in_history_ += DeadTime(*last_frame_stats, *frame_stats);
 263   }
 264 }
 265
 266 void AdaptiveCongestionControl::SendFrameToTransport(uint32 frame_id,
 267                                                      size_t frame_size,
 268                                                      base::TimeTicks when) {
 269   last_encoded_frame_ = frame_id;
 270   FrameStats* frame_stats = GetFrameStats(frame_id);
 271   DCHECK(frame_stats);
 272   frame_stats->frame_size = frame_size;
 273   frame_stats->sent_time = when;
 274 }
 275
 276 base::TimeTicks AdaptiveCongestionControl::EstimatedAckTime(uint32 frame_id,
 277                                                             double bitrate) {
 278   FrameStats* frame_stats = GetFrameStats(frame_id);
 279   DCHECK(frame_stats);
 280   if (frame_stats->ack_time.is_null()) {
 281     DCHECK(frame_stats->frame_size) << "frame_id: " << frame_id;
 282     base::TimeTicks ret = EstimatedSendingTime(frame_id, bitrate);
 283     ret += base::TimeDelta::FromSecondsD(frame_stats->frame_size / bitrate);
 284     ret += rtt_;
 285     base::TimeTicks now = clock_->NowTicks();
 286     if (ret < now) {
 287       // This is a little counter-intuitive, but it seems to work.
 288       // Basically, when we estimate that the ACK should have already happened,
 289       // we figure out how long ago it should have happened and guess that the
 290       // ACK will happen half of that time in the future. This will cause some
 291       // over-estimation when acks are late, which is actually what we want.
 292       return now + (now - ret) / 2;
 293     } else {
 294       return ret;
 295     }
 296   } else {
 297     return frame_stats->ack_time;
 298   }
 299 }
 300
 301 base::TimeTicks AdaptiveCongestionControl::EstimatedSendingTime(
 302     uint32 frame_id,
 303     double bitrate) {
 304   FrameStats* frame_stats = GetFrameStats(frame_id);
 305   DCHECK(frame_stats);
 306   base::TimeTicks ret = EstimatedAckTime(frame_id - 1, bitrate) - rtt_;
 307   if (frame_stats->sent_time.is_null()) {
 308     // Not sent yet, but we can't start sending it in the past.
 309     return std::max(ret, clock_->NowTicks());
 310   } else {
 311     return std::max(ret, frame_stats->sent_time);
 312   }
 313 }
 314
 315 uint32 AdaptiveCongestionControl::GetBitrate(base::TimeTicks playout_time,
 316                                              base::TimeDelta playout_delay) {
 317   double safe_bitrate = CalculateSafeBitrate();
 318   // Estimate when we might start sending the next frame.
 319   base::TimeDelta time_to_catch_up =
 320       playout_time -
 321       EstimatedSendingTime(last_encoded_frame_ + 1, safe_bitrate);
 322
 323   double empty_buffer_fraction =
 324       time_to_catch_up.InSecondsF() / playout_delay.InSecondsF();
 325   empty_buffer_fraction = std::min(empty_buffer_fraction, 1.0);
 326   empty_buffer_fraction = std::max(empty_buffer_fraction, 0.0);
 327
 328   uint32 bits_per_second = static_cast<uint32>(
 329       safe_bitrate * empty_buffer_fraction / kTargetEmptyBufferFraction);
 330   VLOG(3) << " FBR:" << (bits_per_second / 1E6)
 331           << " EBF:" << empty_buffer_fraction
 332           << " SBR:" << (safe_bitrate / 1E6);
 333   bits_per_second = std::max(bits_per_second, min_bitrate_configured_);
 334   bits_per_second = std::min(bits_per_second, max_bitrate_configured_);
 335   return bits_per_second;
 336 }
 337
 338 }  // namespace cast
 339 }  // namespace media