1 // Copyright 2013 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/congestion_control/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 // This means that we *try* to keep our buffer 90% empty.
26 // If it is less full, we increase the bandwidth, if it is more
27 // we decrease the bandwidth. Making this smaller makes the
28 // congestion control more aggressive.
29 static const double kTargetEmptyBufferFraction = 0.9;
30
31 // This is the size of our history in frames. Larger values makes the
32 // congestion control adapt slower.
33 static const size_t kHistorySize = 100;
34
FrameStats()35 CongestionControl::FrameStats::FrameStats() : frame_size(0) {
36 }
37
CongestionControl(base::TickClock * clock,uint32 max_bitrate_configured,uint32 min_bitrate_configured,size_t max_unacked_frames)38 CongestionControl::CongestionControl(base::TickClock* clock,
39 uint32 max_bitrate_configured,
40 uint32 min_bitrate_configured,
41 size_t max_unacked_frames)
42 : clock_(clock),
43 max_bitrate_configured_(max_bitrate_configured),
44 min_bitrate_configured_(min_bitrate_configured),
45 last_frame_stats_(static_cast<uint32>(-1)),
46 last_acked_frame_(static_cast<uint32>(-1)),
47 last_encoded_frame_(static_cast<uint32>(-1)),
48 history_size_(max_unacked_frames + kHistorySize),
49 acked_bits_in_history_(0) {
50 DCHECK_GE(max_bitrate_configured, min_bitrate_configured) << "Invalid config";
51 frame_stats_.resize(2);
52 base::TimeTicks now = clock->NowTicks();
53 frame_stats_[0].ack_time = now;
54 frame_stats_[0].sent_time = now;
55 frame_stats_[1].ack_time = now;
56 DCHECK(!frame_stats_[0].ack_time.is_null());
57 }
58
~CongestionControl()59 CongestionControl::~CongestionControl() {}
60
UpdateRtt(base::TimeDelta rtt)61 void CongestionControl::UpdateRtt(base::TimeDelta rtt) {
62 rtt_ = base::TimeDelta::FromSecondsD(
63 (rtt_.InSecondsF() * 7 + rtt.InSecondsF()) / 8);
64 }
65
66 // Calculate how much "dead air" there is between two frames.
DeadTime(const FrameStats & a,const FrameStats & b)67 base::TimeDelta CongestionControl::DeadTime(const FrameStats& a,
68 const FrameStats& b) {
69 if (b.sent_time > a.ack_time) {
70 return b.sent_time - a.ack_time;
71 } else {
72 return base::TimeDelta();
73 }
74 }
75
CalculateSafeBitrate()76 double CongestionControl::CalculateSafeBitrate() {
77 double transmit_time =
78 (GetFrameStats(last_acked_frame_)->ack_time -
79 frame_stats_.front().sent_time - dead_time_in_history_).InSecondsF();
80
81 if (acked_bits_in_history_ == 0 || transmit_time <= 0.0) {
82 return min_bitrate_configured_;
83 }
84 return acked_bits_in_history_ / std::max(transmit_time, 1E-3);
85 }
86
GetFrameStats(uint32 frame_id)87 CongestionControl::FrameStats* CongestionControl::GetFrameStats(
88 uint32 frame_id) {
89 int32 offset = static_cast<int32>(frame_id - last_frame_stats_);
90 DCHECK_LT(offset, static_cast<int32>(kHistorySize));
91 if (offset > 0) {
92 frame_stats_.resize(frame_stats_.size() + offset);
93 last_frame_stats_ += offset;
94 offset = 0;
95 }
96 while (frame_stats_.size() > history_size_) {
97 DCHECK_GT(frame_stats_.size(), 1UL);
98 DCHECK(!frame_stats_[0].ack_time.is_null());
99 acked_bits_in_history_ -= frame_stats_[0].frame_size;
100 dead_time_in_history_ -= DeadTime(frame_stats_[0], frame_stats_[1]);
101 DCHECK_GE(acked_bits_in_history_, 0UL);
102 VLOG(2) << "DT: " << dead_time_in_history_.InSecondsF();
103 DCHECK_GE(dead_time_in_history_.InSecondsF(), 0.0);
104 frame_stats_.pop_front();
105 }
106 offset += frame_stats_.size() - 1;
107 if (offset < 0 || offset >= static_cast<int32>(frame_stats_.size())) {
108 return NULL;
109 }
110 return &frame_stats_[offset];
111 }
112
AckFrame(uint32 frame_id,base::TimeTicks when)113 void CongestionControl::AckFrame(uint32 frame_id, base::TimeTicks when) {
114 FrameStats* frame_stats = GetFrameStats(last_acked_frame_);
115 while (IsNewerFrameId(frame_id, last_acked_frame_)) {
116 FrameStats* last_frame_stats = frame_stats;
117 last_acked_frame_++;
118 frame_stats = GetFrameStats(last_acked_frame_);
119 DCHECK(frame_stats);
120 frame_stats->ack_time = when;
121 acked_bits_in_history_ += frame_stats->frame_size;
122 dead_time_in_history_ += DeadTime(*last_frame_stats, *frame_stats);
123 }
124 }
125
SendFrameToTransport(uint32 frame_id,size_t frame_size,base::TimeTicks when)126 void CongestionControl::SendFrameToTransport(uint32 frame_id,
127 size_t frame_size,
128 base::TimeTicks when) {
129 last_encoded_frame_ = frame_id;
130 FrameStats* frame_stats = GetFrameStats(frame_id);
131 DCHECK(frame_stats);
132 frame_stats->frame_size = frame_size;
133 frame_stats->sent_time = when;
134 }
135
EstimatedAckTime(uint32 frame_id,double bitrate)136 base::TimeTicks CongestionControl::EstimatedAckTime(uint32 frame_id,
137 double bitrate) {
138 FrameStats* frame_stats = GetFrameStats(frame_id);
139 DCHECK(frame_stats);
140 if (frame_stats->ack_time.is_null()) {
141 DCHECK(frame_stats->frame_size) << "frame_id: " << frame_id;
142 base::TimeTicks ret = EstimatedSendingTime(frame_id, bitrate);
143 ret += base::TimeDelta::FromSecondsD(frame_stats->frame_size / bitrate);
144 ret += rtt_;
145 base::TimeTicks now = clock_->NowTicks();
146 if (ret < now) {
147 // This is a little counter-intuitive, but it seems to work.
148 // Basically, when we estimate that the ACK should have already happened,
149 // we figure out how long ago it should have happened and guess that the
150 // ACK will happen half of that time in the future. This will cause some
151 // over-estimation when acks are late, which is actually what we want.
152 return now + (now - ret) / 2;
153 } else {
154 return ret;
155 }
156 } else {
157 return frame_stats->ack_time;
158 }
159 }
160
EstimatedSendingTime(uint32 frame_id,double bitrate)161 base::TimeTicks CongestionControl::EstimatedSendingTime(uint32 frame_id,
162 double bitrate) {
163 FrameStats* frame_stats = GetFrameStats(frame_id);
164 DCHECK(frame_stats);
165 base::TimeTicks ret = EstimatedAckTime(frame_id - 1, bitrate) - rtt_;
166 if (frame_stats->sent_time.is_null()) {
167 // Not sent yet, but we can't start sending it in the past.
168 return std::max(ret, clock_->NowTicks());
169 } else {
170 return std::max(ret, frame_stats->sent_time);
171 }
172 }
173
GetBitrate(base::TimeTicks playout_time,base::TimeDelta playout_delay)174 uint32 CongestionControl::GetBitrate(base::TimeTicks playout_time,
175 base::TimeDelta playout_delay) {
176 double safe_bitrate = CalculateSafeBitrate();
177 // Estimate when we might start sending the next frame.
178 base::TimeDelta time_to_catch_up =
179 playout_time -
180 EstimatedSendingTime(last_encoded_frame_ + 1, safe_bitrate);
181
182 double empty_buffer_fraction =
183 time_to_catch_up.InSecondsF() / playout_delay.InSecondsF();
184 empty_buffer_fraction = std::min(empty_buffer_fraction, 1.0);
185 empty_buffer_fraction = std::max(empty_buffer_fraction, 0.0);
186
187 uint32 bits_per_second = static_cast<uint32>(
188 safe_bitrate * empty_buffer_fraction / kTargetEmptyBufferFraction);
189 VLOG(3) << " FBR:" << (bits_per_second / 1E6)
190 << " EBF:" << empty_buffer_fraction
191 << " SBR:" << (safe_bitrate / 1E6);
192 bits_per_second = std::max(bits_per_second, min_bitrate_configured_);
193 bits_per_second = std::min(bits_per_second, max_bitrate_configured_);
194 return bits_per_second;
195 }
196
197 } // namespace cast
198 } // namespace media
199