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
22namespace media {
23namespace cast {
24
25class 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
91class 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
121CongestionControl* 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
132CongestionControl* 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.
140static 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.
144static const size_t kHistorySize = 100;
145
146AdaptiveCongestionControl::FrameStats::FrameStats() : frame_size(0) {
147}
148
149AdaptiveCongestionControl::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
171CongestionControl::~CongestionControl() {}
172AdaptiveCongestionControl::~AdaptiveCongestionControl() {}
173
174void AdaptiveCongestionControl::UpdateRtt(base::TimeDelta rtt) {
175  rtt_ = (7 * rtt_ + rtt) / 8;
176}
177
178// Calculate how much "dead air" there is between two frames.
179base::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
188double 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
199AdaptiveCongestionControl::FrameStats*
200AdaptiveCongestionControl::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
225void 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
246void 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
256base::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
281base::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
295uint32 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