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.
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
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.
16 #include "media/cast/sender/congestion_control.h"
18 #include "base/logging.h"
19 #include "media/cast/cast_config.h"
20 #include "media/cast/cast_defines.h"
25 class AdaptiveCongestionControl : public CongestionControl {
27 AdaptiveCongestionControl(base::TickClock* clock,
28 uint32 max_bitrate_configured,
29 uint32 min_bitrate_configured,
30 size_t max_unacked_frames);
32 virtual ~AdaptiveCongestionControl() OVERRIDE;
34 virtual void UpdateRtt(base::TimeDelta rtt) OVERRIDE;
36 // Called when an encoded frame is sent to the transport.
37 virtual void SendFrameToTransport(uint32 frame_id,
39 base::TimeTicks when) OVERRIDE;
41 // Called when we receive an ACK for a frame.
42 virtual void AckFrame(uint32 frame_id, base::TimeTicks when) OVERRIDE;
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;
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.
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();
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);
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_;
85 size_t acked_bits_in_history_;
86 base::TimeDelta dead_time_in_history_;
88 DISALLOW_COPY_AND_ASSIGN(AdaptiveCongestionControl);
91 class FixedCongestionControl : public CongestionControl {
93 FixedCongestionControl(uint32 bitrate) : bitrate_(bitrate) {}
94 virtual ~FixedCongestionControl() OVERRIDE {}
96 virtual void UpdateRtt(base::TimeDelta rtt) OVERRIDE {
99 // Called when an encoded frame is sent to the transport.
100 virtual void SendFrameToTransport(uint32 frame_id,
102 base::TimeTicks when) OVERRIDE {
105 // Called when we receive an ACK for a frame.
106 virtual void AckFrame(uint32 frame_id, base::TimeTicks when) OVERRIDE {
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 {
117 DISALLOW_COPY_AND_ASSIGN(FixedCongestionControl);
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,
132 CongestionControl* NewFixedCongestionControl(uint32 bitrate) {
133 return new FixedCongestionControl(bitrate);
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;
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;
146 AdaptiveCongestionControl::FrameStats::FrameStats() : frame_size(0) {
149 AdaptiveCongestionControl::AdaptiveCongestionControl(
150 base::TickClock* clock,
151 uint32 max_bitrate_configured,
152 uint32 min_bitrate_configured,
153 size_t max_unacked_frames)
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());
171 CongestionControl::~CongestionControl() {}
172 AdaptiveCongestionControl::~AdaptiveCongestionControl() {}
174 void AdaptiveCongestionControl::UpdateRtt(base::TimeDelta rtt) {
175 rtt_ = (7 * rtt_ + rtt) / 8;
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;
184 return base::TimeDelta();
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();
193 if (acked_bits_in_history_ == 0 || transmit_time <= 0.0) {
194 return min_bitrate_configured_;
196 return acked_bits_in_history_ / std::max(transmit_time, 1E-3);
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));
204 frame_stats_.resize(frame_stats_.size() + offset);
205 last_frame_stats_ += offset;
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();
218 offset += frame_stats_.size() - 1;
219 if (offset < 0 || offset >= static_cast<int32>(frame_stats_.size())) {
222 return &frame_stats_[offset];
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);
232 if (frame_stats->sent_time.is_null()) {
233 // Can't ack a frame that hasn't been sent yet.
237 if (when < frame_stats->sent_time)
238 when = frame_stats->sent_time;
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);
246 void AdaptiveCongestionControl::SendFrameToTransport(uint32 frame_id,
248 base::TimeTicks when) {
249 last_encoded_frame_ = frame_id;
250 FrameStats* frame_stats = GetFrameStats(frame_id);
252 frame_stats->frame_size = frame_size;
253 frame_stats->sent_time = when;
256 base::TimeTicks AdaptiveCongestionControl::EstimatedAckTime(uint32 frame_id,
258 FrameStats* frame_stats = GetFrameStats(frame_id);
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);
265 base::TimeTicks now = clock_->NowTicks();
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;
277 return frame_stats->ack_time;
281 base::TimeTicks AdaptiveCongestionControl::EstimatedSendingTime(
284 FrameStats* frame_stats = GetFrameStats(frame_id);
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());
291 return std::max(ret, frame_stats->sent_time);
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 =
301 EstimatedSendingTime(last_encoded_frame_ + 1, safe_bitrate);
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);
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;