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