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 <deque>
  19
  20 #include "base/logging.h"
  21 #include "base/trace_event/trace_event.h"
  22 #include "media/cast/cast_config.h"
  23 #include "media/cast/cast_defines.h"
  24
  25 namespace media {
  26 namespace cast {
  27
  28 class AdaptiveCongestionControl : public CongestionControl {
  29  public:
  30   AdaptiveCongestionControl(base::TickClock* clock,
  31                             int max_bitrate_configured,
  32                             int min_bitrate_configured,
  33                             double max_frame_rate);
  34
  35   ~AdaptiveCongestionControl() final;
  36
  37   // CongestionControl implementation.
  38   void UpdateRtt(base::TimeDelta rtt) final;
  39   void UpdateTargetPlayoutDelay(base::TimeDelta delay) final;
  40   void SendFrameToTransport(uint32 frame_id,
  41                             size_t frame_size_in_bits,
  42                             base::TimeTicks when) final;
  43   void AckFrame(uint32 frame_id, base::TimeTicks when) final;
  44   int GetBitrate(base::TimeTicks playout_time,
  45                  base::TimeDelta playout_delay,
  46                  int soft_max_bitrate) final;
  47
  48  private:
  49   struct FrameStats {
  50     FrameStats();
  51     // Time this frame was first enqueued for transport.
  52     base::TimeTicks enqueue_time;
  53     // Time this frame was acked.
  54     base::TimeTicks ack_time;
  55     // Size of encoded frame in bits.
  56     size_t frame_size_in_bits;
  57   };
  58
  59   // Calculate how much "dead air" (idle time) there is between two frames.
  60   static base::TimeDelta DeadTime(const FrameStats& a, const FrameStats& b);
  61   // Get the FrameStats for a given |frame_id|.  Never returns nullptr.
  62   // Note: Older FrameStats will be removed automatically.
  63   FrameStats* GetFrameStats(uint32 frame_id);
  64   // Discard old FrameStats.
  65   void PruneFrameStats();
  66   // Calculate a safe bitrate. This is based on how much we've been
  67   // sending in the past.
  68   double CalculateSafeBitrate();
  69
  70   // Estimate when the transport will start sending the data for a given frame.
  71   // |estimated_bitrate| is the current estimated transmit bitrate in bits per
  72   // second.
  73   base::TimeTicks EstimatedSendingTime(uint32 frame_id,
  74                                        double estimated_bitrate);
  75
  76   base::TickClock* const clock_;  // Not owned by this class.
  77   const int max_bitrate_configured_;
  78   const int min_bitrate_configured_;
  79   const double max_frame_rate_;
  80   std::deque<FrameStats> frame_stats_;
  81   uint32 last_frame_stats_;
  82   uint32 last_acked_frame_;
  83   uint32 last_enqueued_frame_;
  84   base::TimeDelta rtt_;
  85   size_t history_size_;
  86   size_t acked_bits_in_history_;
  87   base::TimeDelta dead_time_in_history_;
  88
  89   DISALLOW_COPY_AND_ASSIGN(AdaptiveCongestionControl);
  90 };
  91
  92 class FixedCongestionControl : public CongestionControl {
  93  public:
  94   explicit FixedCongestionControl(int bitrate) : bitrate_(bitrate) {}
  95   ~FixedCongestionControl() final {}
  96
  97   // CongestionControl implementation.
  98   void UpdateRtt(base::TimeDelta rtt) final {}
  99   void UpdateTargetPlayoutDelay(base::TimeDelta delay) final {}
 100   void SendFrameToTransport(uint32 frame_id,
 101                             size_t frame_size_in_bits,
 102                             base::TimeTicks when) final {}
 103   void AckFrame(uint32 frame_id, base::TimeTicks when) final {}
 104   int GetBitrate(base::TimeTicks playout_time,
 105                  base::TimeDelta playout_delay,
 106                  int soft_max_bitrate) final {
 107     return bitrate_;
 108   }
 109
 110  private:
 111   const int bitrate_;
 112
 113   DISALLOW_COPY_AND_ASSIGN(FixedCongestionControl);
 114 };
 115
 116
 117 CongestionControl* NewAdaptiveCongestionControl(
 118     base::TickClock* clock,
 119     int max_bitrate_configured,
 120     int min_bitrate_configured,
 121     double max_frame_rate) {
 122   return new AdaptiveCongestionControl(clock,
 123                                        max_bitrate_configured,
 124                                        min_bitrate_configured,
 125                                        max_frame_rate);
 126 }
 127
 128 CongestionControl* NewFixedCongestionControl(int bitrate) {
 129   return new FixedCongestionControl(bitrate);
 130 }
 131
 132 // This means that we *try* to keep our buffer 90% empty.
 133 // If it is less full, we increase the bandwidth, if it is more
 134 // we decrease the bandwidth. Making this smaller makes the
 135 // congestion control more aggressive.
 136 static const double kTargetEmptyBufferFraction = 0.9;
 137
 138 // This is the size of our history in frames. Larger values makes the
 139 // congestion control adapt slower.
 140 static const size_t kHistorySize = 100;
 141
 142 AdaptiveCongestionControl::FrameStats::FrameStats() : frame_size_in_bits(0) {
 143 }
 144
 145 AdaptiveCongestionControl::AdaptiveCongestionControl(
 146     base::TickClock* clock,
 147     int max_bitrate_configured,
 148     int min_bitrate_configured,
 149     double max_frame_rate)
 150     : clock_(clock),
 151       max_bitrate_configured_(max_bitrate_configured),
 152       min_bitrate_configured_(min_bitrate_configured),
 153       max_frame_rate_(max_frame_rate),
 154       last_frame_stats_(static_cast<uint32>(-1)),
 155       last_acked_frame_(static_cast<uint32>(-1)),
 156       last_enqueued_frame_(static_cast<uint32>(-1)),
 157       history_size_(kHistorySize),
 158       acked_bits_in_history_(0) {
 159   DCHECK_GE(max_bitrate_configured, min_bitrate_configured) << "Invalid config";
 160   DCHECK_GT(min_bitrate_configured, 0);
 161   frame_stats_.resize(2);
 162   base::TimeTicks now = clock->NowTicks();
 163   frame_stats_[0].ack_time = now;
 164   frame_stats_[0].enqueue_time = now;
 165   frame_stats_[1].ack_time = now;
 166   DCHECK(!frame_stats_[0].ack_time.is_null());
 167 }
 168
 169 CongestionControl::~CongestionControl() {}
 170 AdaptiveCongestionControl::~AdaptiveCongestionControl() {}
 171
 172 void AdaptiveCongestionControl::UpdateRtt(base::TimeDelta rtt) {
 173   rtt_ = (7 * rtt_ + rtt) / 8;
 174 }
 175
 176 void AdaptiveCongestionControl::UpdateTargetPlayoutDelay(
 177     base::TimeDelta delay) {
 178   const int max_unacked_frames =
 179       std::min(kMaxUnackedFrames,
 180                1 + static_cast<int>(delay * max_frame_rate_ /
 181                                     base::TimeDelta::FromSeconds(1)));
 182   DCHECK_GT(max_unacked_frames, 0);
 183   history_size_ = max_unacked_frames + kHistorySize;
 184   PruneFrameStats();
 185 }
 186
 187 // Calculate how much "dead air" there is between two frames.
 188 base::TimeDelta AdaptiveCongestionControl::DeadTime(const FrameStats& a,
 189                                                     const FrameStats& b) {
 190   if (b.enqueue_time > a.ack_time) {
 191     return b.enqueue_time - a.ack_time;
 192   } else {
 193     return base::TimeDelta();
 194   }
 195 }
 196
 197 double AdaptiveCongestionControl::CalculateSafeBitrate() {
 198   double transmit_time =
 199       (GetFrameStats(last_acked_frame_)->ack_time -
 200        frame_stats_.front().enqueue_time - dead_time_in_history_).InSecondsF();
 201
 202   if (acked_bits_in_history_ == 0 || transmit_time <= 0.0) {
 203     return min_bitrate_configured_;
 204   }
 205   return acked_bits_in_history_ / std::max(transmit_time, 1E-3);
 206 }
 207
 208 AdaptiveCongestionControl::FrameStats*
 209 AdaptiveCongestionControl::GetFrameStats(uint32 frame_id) {
 210   int32 offset = static_cast<int32>(frame_id - last_frame_stats_);
 211   DCHECK_LT(offset, static_cast<int32>(kHistorySize));
 212   if (offset > 0) {
 213     frame_stats_.resize(frame_stats_.size() + offset);
 214     last_frame_stats_ += offset;
 215     offset = 0;
 216   }
 217   PruneFrameStats();
 218   offset += frame_stats_.size() - 1;
 219   // TODO(miu): Change the following to DCHECK once crash fix is confirmed.
 220   // http://crbug.com/517145
 221   CHECK(offset >= 0 && offset < static_cast<int32>(frame_stats_.size()));
 222   return &frame_stats_[offset];
 223 }
 224
 225 void AdaptiveCongestionControl::PruneFrameStats() {
 226  while (frame_stats_.size() > history_size_) {
 227     DCHECK_GT(frame_stats_.size(), 1UL);
 228     DCHECK(!frame_stats_[0].ack_time.is_null());
 229     acked_bits_in_history_ -= frame_stats_[0].frame_size_in_bits;
 230     dead_time_in_history_ -= DeadTime(frame_stats_[0], frame_stats_[1]);
 231     DCHECK_GE(acked_bits_in_history_, 0UL);
 232     VLOG(2) << "DT: " << dead_time_in_history_.InSecondsF();
 233     DCHECK_GE(dead_time_in_history_.InSecondsF(), 0.0);
 234     frame_stats_.pop_front();
 235   }
 236 }
 237
 238 void AdaptiveCongestionControl::AckFrame(uint32 frame_id,
 239                                          base::TimeTicks when) {
 240   FrameStats* frame_stats = GetFrameStats(last_acked_frame_);
 241   while (IsNewerFrameId(frame_id, last_acked_frame_)) {
 242     FrameStats* last_frame_stats = frame_stats;
 243     frame_stats = GetFrameStats(last_acked_frame_ + 1);
 244     if (frame_stats->enqueue_time.is_null()) {
 245       // Can't ack a frame that hasn't been sent yet.
 246       return;
 247     }
 248     last_acked_frame_++;
 249     if (when < frame_stats->enqueue_time)
 250       when = frame_stats->enqueue_time;
 251
 252     frame_stats->ack_time = when;
 253     acked_bits_in_history_ += frame_stats->frame_size_in_bits;
 254     dead_time_in_history_ += DeadTime(*last_frame_stats, *frame_stats);
 255   }
 256 }
 257
 258 void AdaptiveCongestionControl::SendFrameToTransport(uint32 frame_id,
 259                                                      size_t frame_size_in_bits,
 260                                                      base::TimeTicks when) {
 261   last_enqueued_frame_ = frame_id;
 262   FrameStats* frame_stats = GetFrameStats(frame_id);
 263   frame_stats->enqueue_time = when;
 264   frame_stats->frame_size_in_bits = frame_size_in_bits;
 265 }
 266
 267 base::TimeTicks AdaptiveCongestionControl::EstimatedSendingTime(
 268     uint32 frame_id,
 269     double estimated_bitrate) {
 270   const base::TimeTicks now = clock_->NowTicks();
 271
 272   // Starting with the time of the latest acknowledgement, extrapolate forward
 273   // to determine an estimated sending time for |frame_id|.
 274   //
 275   // |estimated_sending_time| will contain the estimated sending time for each
 276   // frame after the last ACK'ed frame.  It is possible for multiple frames to
 277   // be in-flight; and therefore it is common for the |estimated_sending_time|
 278   // for those frames to be before |now|.
 279   base::TimeTicks estimated_sending_time;
 280   for (uint32 f = last_acked_frame_; IsNewerFrameId(frame_id, f); ++f) {
 281     FrameStats* const stats = GetFrameStats(f);
 282
 283     // |estimated_ack_time| is the local time when the sender receives the ACK,
 284     // and not the time when the ACK left the receiver.
 285     base::TimeTicks estimated_ack_time = stats->ack_time;
 286
 287     // If |estimated_ack_time| is not null, then we already have the actual ACK
 288     // time, so we'll just use it.  Otherwise, we need to estimate when the ACK
 289     // will arrive.
 290     if (estimated_ack_time.is_null()) {
 291       // Model: The |estimated_sending_time| is the time at which the first byte
 292       // of the encoded frame is transmitted.  Then, assume the transmission of
 293       // the remaining bytes is paced such that the last byte has just left the
 294       // sender at |frame_transmit_time| later.  This last byte then takes
 295       // ~RTT/2 amount of time to travel to the receiver.  Finally, the ACK from
 296       // the receiver is sent and this takes another ~RTT/2 amount of time to
 297       // reach the sender.
 298       const base::TimeDelta frame_transmit_time =
 299           base::TimeDelta::FromSecondsD(stats->frame_size_in_bits /
 300                                             estimated_bitrate);
 301       estimated_ack_time =
 302           std::max(estimated_sending_time, stats->enqueue_time) +
 303               frame_transmit_time + rtt_;
 304
 305       if (estimated_ack_time < now) {
 306         // The current frame has not yet been ACK'ed and the yet the computed
 307         // |estimated_ack_time| is before |now|.  This contradiction must be
 308         // resolved.
 309         //
 310         // The solution below is a little counter-intuitive, but it seems to
 311         // work.  Basically, when we estimate that the ACK should have already
 312         // happened, we figure out how long ago it should have happened and
 313         // guess that the ACK will happen half of that time in the future.  This
 314         // will cause some over-estimation when acks are late, which is actually
 315         // the desired behavior.
 316         estimated_ack_time = now + (now - estimated_ack_time) / 2;
 317       }
 318     }
 319
 320     // Since we [in the common case] do not wait for an ACK before we start
 321     // sending the next frame, estimate the next frame's sending time as the
 322     // time just after the last byte of the current frame left the sender (see
 323     // Model comment above).
 324     estimated_sending_time =
 325         std::max(estimated_sending_time, estimated_ack_time - rtt_);
 326   }
 327
 328   FrameStats* const frame_stats = GetFrameStats(frame_id);
 329   if (frame_stats->enqueue_time.is_null()) {
 330     // The frame has not yet been enqueued for transport.  Since it cannot be
 331     // enqueued in the past, ensure the result is lower-bounded by |now|.
 332     estimated_sending_time = std::max(estimated_sending_time, now);
 333   } else {
 334     // |frame_stats->enqueue_time| is the time the frame was enqueued for
 335     // transport.  The frame may not actually start being sent until a
 336     // point-in-time after that, because the transport is waiting for prior
 337     // frames to be acknowledged.
 338     estimated_sending_time =
 339         std::max(estimated_sending_time, frame_stats->enqueue_time);
 340   }
 341
 342   return estimated_sending_time;
 343 }
 344
 345 int AdaptiveCongestionControl::GetBitrate(base::TimeTicks playout_time,
 346                                           base::TimeDelta playout_delay,
 347                                           int soft_max_bitrate) {
 348   double safe_bitrate = CalculateSafeBitrate();
 349   // Estimate when we might start sending the next frame.
 350   base::TimeDelta time_to_catch_up =
 351       playout_time -
 352       EstimatedSendingTime(last_enqueued_frame_ + 1, safe_bitrate);
 353
 354   double empty_buffer_fraction =
 355       time_to_catch_up.InSecondsF() / playout_delay.InSecondsF();
 356   empty_buffer_fraction = std::min(empty_buffer_fraction, 1.0);
 357   empty_buffer_fraction = std::max(empty_buffer_fraction, 0.0);
 358
 359   int bits_per_second = static_cast<int>(
 360       safe_bitrate * empty_buffer_fraction / kTargetEmptyBufferFraction);
 361   VLOG(3) << " FBR:" << (bits_per_second / 1E6)
 362           << " EBF:" << empty_buffer_fraction
 363           << " SBR:" << (safe_bitrate / 1E6);
 364   TRACE_COUNTER_ID1("cast.stream", "Empty Buffer Fraction", this,
 365                     empty_buffer_fraction);
 366   bits_per_second = std::min(bits_per_second, soft_max_bitrate);
 367   bits_per_second = std::max(bits_per_second, min_bitrate_configured_);
 368   bits_per_second = std::min(bits_per_second, max_bitrate_configured_);
 369
 370   return bits_per_second;
 371 }
 372
 373 }  // namespace cast
 374 }  // namespace media