| // Copyright 2014 The Chromium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| // The purpose of this file is determine what bitrate to use for mirroring. |
| // Ideally this should be as much as possible, without causing any frames to |
| // arrive late. |
| |
| // The current algorithm is to measure how much bandwidth we've been using |
| // recently. We also keep track of how much data has been queued up for sending |
| // in a virtual "buffer" (this virtual buffer represents all the buffers between |
| // the sender and the receiver, including retransmissions and so forth.) |
| // If we estimate that our virtual buffer is mostly empty, we try to use |
| // more bandwidth than our recent usage, otherwise we use less. |
| |
| #include "media/cast/sender/congestion_control.h" |
| |
| #include <algorithm> |
| #include <deque> |
| |
| #include "base/logging.h" |
| #include "base/macros.h" |
| #include "base/trace_event/trace_event.h" |
| #include "media/cast/constants.h" |
| |
| namespace media { |
| namespace cast { |
| |
| class AdaptiveCongestionControl : public CongestionControl { |
| public: |
| AdaptiveCongestionControl(const base::TickClock* clock, |
| int max_bitrate_configured, |
| int min_bitrate_configured, |
| double max_frame_rate); |
| |
| ~AdaptiveCongestionControl() final; |
| |
| // CongestionControl implementation. |
| void UpdateRtt(base::TimeDelta rtt) final; |
| void UpdateTargetPlayoutDelay(base::TimeDelta delay) final; |
| void SendFrameToTransport(FrameId frame_id, |
| size_t frame_size_in_bits, |
| base::TimeTicks when) final; |
| void AckFrame(FrameId frame_id, base::TimeTicks when) final; |
| void AckLaterFrames(std::vector<FrameId> received_frames, |
| base::TimeTicks when) final; |
| int GetBitrate(base::TimeTicks playout_time, |
| base::TimeDelta playout_delay) final; |
| |
| private: |
| struct FrameStats { |
| FrameStats(); |
| // Time this frame was first enqueued for transport. |
| base::TimeTicks enqueue_time; |
| // Time this frame was acked. |
| base::TimeTicks ack_time; |
| // Size of encoded frame in bits. |
| size_t frame_size_in_bits; |
| }; |
| |
| // Calculate how much "dead air" (idle time) there is between two frames. |
| static base::TimeDelta DeadTime(const FrameStats& a, const FrameStats& b); |
| // Get the FrameStats for a given |frame_id|, auto-creating a new FrameStats |
| // for newer frames, but possibly returning nullptr for older frames that have |
| // been pruned. Never returns nullptr for |frame_id|s equal to or greater than |
| // |last_checkpoint_frame_|. |
| // Note: Older FrameStats will be removed automatically. |
| FrameStats* GetFrameStats(FrameId frame_id); |
| // Discard old FrameStats. |
| void PruneFrameStats(); |
| // Calculate a safe bitrate. This is based on how much we've been |
| // sending in the past. |
| double CalculateSafeBitrate(); |
| |
| // Estimate when the transport will start sending the data for a given frame. |
| // |estimated_bitrate| is the current estimated transmit bitrate in bits per |
| // second. |
| base::TimeTicks EstimatedSendingTime(FrameId frame_id, |
| double estimated_bitrate); |
| |
| const base::TickClock* const clock_; // Not owned by this class. |
| const int max_bitrate_configured_; |
| const int min_bitrate_configured_; |
| const double max_frame_rate_; |
| |
| // This can not be a base::circular_deque because the AckFrame implementation |
| // preserves a FrameStats* pointing inside the deque across mutations. |
| std::deque<FrameStats> frame_stats_; |
| |
| FrameId last_frame_stats_; |
| // This is the latest known frame that all previous frames (having smaller |
| // |frame_id|) and this frame were acked by receiver. |
| FrameId last_checkpoint_frame_; |
| // This is the first time that |last_checkpoint_frame_| is marked. |
| base::TimeTicks last_checkpoint_time_; |
| FrameId last_enqueued_frame_; |
| base::TimeDelta rtt_; |
| size_t history_size_; |
| size_t acked_bits_in_history_; |
| base::TimeDelta dead_time_in_history_; |
| |
| DISALLOW_COPY_AND_ASSIGN(AdaptiveCongestionControl); |
| }; |
| |
| class FixedCongestionControl : public CongestionControl { |
| public: |
| explicit FixedCongestionControl(int bitrate) : bitrate_(bitrate) {} |
| ~FixedCongestionControl() final = default; |
| |
| // CongestionControl implementation. |
| void UpdateRtt(base::TimeDelta rtt) final {} |
| void UpdateTargetPlayoutDelay(base::TimeDelta delay) final {} |
| void SendFrameToTransport(FrameId frame_id, |
| size_t frame_size_in_bits, |
| base::TimeTicks when) final {} |
| void AckFrame(FrameId frame_id, base::TimeTicks when) final {} |
| void AckLaterFrames(std::vector<FrameId> received_frames, |
| base::TimeTicks when) final {} |
| int GetBitrate(base::TimeTicks playout_time, |
| base::TimeDelta playout_delay) final { |
| return bitrate_; |
| } |
| |
| private: |
| const int bitrate_; |
| |
| DISALLOW_COPY_AND_ASSIGN(FixedCongestionControl); |
| }; |
| |
| CongestionControl* NewAdaptiveCongestionControl(const base::TickClock* clock, |
| int max_bitrate_configured, |
| int min_bitrate_configured, |
| double max_frame_rate) { |
| return new AdaptiveCongestionControl(clock, |
| max_bitrate_configured, |
| min_bitrate_configured, |
| max_frame_rate); |
| } |
| |
| CongestionControl* NewFixedCongestionControl(int bitrate) { |
| return new FixedCongestionControl(bitrate); |
| } |
| |
| // This means that we *try* to keep our buffer 90% empty. |
| // If it is less full, we increase the bandwidth, if it is more |
| // we decrease the bandwidth. Making this smaller makes the |
| // congestion control more aggressive. |
| static const double kTargetEmptyBufferFraction = 0.9; |
| |
| // This is the size of our history in frames. Larger values makes the |
| // congestion control adapt slower. |
| static const size_t kHistorySize = 100; |
| |
| AdaptiveCongestionControl::FrameStats::FrameStats() : frame_size_in_bits(0) { |
| } |
| |
| AdaptiveCongestionControl::AdaptiveCongestionControl( |
| const base::TickClock* clock, |
| int max_bitrate_configured, |
| int min_bitrate_configured, |
| double max_frame_rate) |
| : clock_(clock), |
| max_bitrate_configured_(max_bitrate_configured), |
| min_bitrate_configured_(min_bitrate_configured), |
| max_frame_rate_(max_frame_rate), |
| last_frame_stats_(FrameId::first() - 1), |
| last_checkpoint_frame_(FrameId::first() - 1), |
| last_enqueued_frame_(FrameId::first() - 1), |
| history_size_(kHistorySize), |
| acked_bits_in_history_(0) { |
| DCHECK_GE(max_bitrate_configured, min_bitrate_configured) << "Invalid config"; |
| DCHECK_GT(min_bitrate_configured, 0); |
| frame_stats_.resize(2); |
| base::TimeTicks now = clock->NowTicks(); |
| frame_stats_[0].ack_time = now; |
| frame_stats_[0].enqueue_time = now; |
| frame_stats_[1].ack_time = now; |
| frame_stats_[1].enqueue_time = now; |
| last_checkpoint_time_ = now; |
| DCHECK(!frame_stats_[0].ack_time.is_null()); |
| } |
| |
| CongestionControl::~CongestionControl() = default; |
| AdaptiveCongestionControl::~AdaptiveCongestionControl() = default; |
| |
| void AdaptiveCongestionControl::UpdateRtt(base::TimeDelta rtt) { |
| rtt_ = (7 * rtt_ + rtt) / 8; |
| } |
| |
| void AdaptiveCongestionControl::UpdateTargetPlayoutDelay( |
| base::TimeDelta delay) { |
| const int max_unacked_frames = std::min<int>( |
| kMaxUnackedFrames, 1 + static_cast<int>(delay * max_frame_rate_ / |
| base::TimeDelta::FromSeconds(1))); |
| DCHECK_GT(max_unacked_frames, 0); |
| history_size_ = max_unacked_frames + kHistorySize; |
| PruneFrameStats(); |
| } |
| |
| // Calculate how much "dead air" there is between two frames. |
| base::TimeDelta AdaptiveCongestionControl::DeadTime(const FrameStats& a, |
| const FrameStats& b) { |
| if (b.enqueue_time > a.ack_time) { |
| return b.enqueue_time - a.ack_time; |
| } else { |
| return base::TimeDelta(); |
| } |
| } |
| |
| double AdaptiveCongestionControl::CalculateSafeBitrate() { |
| DCHECK(!frame_stats_.empty()); |
| const double transmit_time = |
| (GetFrameStats(last_checkpoint_frame_)->ack_time - |
| frame_stats_.front().enqueue_time - dead_time_in_history_) |
| .InSecondsF(); |
| |
| if (acked_bits_in_history_ == 0 || transmit_time <= 0.0) { |
| return min_bitrate_configured_; |
| } |
| return acked_bits_in_history_ / std::max(transmit_time, 1E-3); |
| } |
| |
| AdaptiveCongestionControl::FrameStats* AdaptiveCongestionControl::GetFrameStats( |
| FrameId frame_id) { |
| int offset = frame_id - last_frame_stats_; |
| if (offset > 0) { |
| // Sanity-check: Make sure the new |frame_id| will not cause an unreasonably |
| // large increase in the history dataset. |
| DCHECK_LE(offset, kMaxUnackedFrames + 1); |
| |
| frame_stats_.resize(frame_stats_.size() + offset); |
| last_frame_stats_ = frame_id; |
| offset = 0; |
| } |
| PruneFrameStats(); |
| offset += frame_stats_.size() - 1; |
| if (offset < 0) { |
| DCHECK_LT(frame_id, last_checkpoint_frame_); |
| return nullptr; // Old frame has been pruned from the dataset. |
| } |
| return &frame_stats_[offset]; |
| } |
| |
| void AdaptiveCongestionControl::PruneFrameStats() { |
| // Maintain a minimal amount of history, specified by |history_size_|, that |
| // MUST also include all frames from the last ACK'ed frame. |
| const size_t retention_count = std::max<size_t>( |
| history_size_, last_frame_stats_ - last_checkpoint_frame_ + 1); |
| |
| // Sanity-check: At least one entry must be kept, but the dataset should not |
| // grow indefinitely. |
| DCHECK_GE(retention_count, 1u); |
| constexpr size_t kMaxInFlightRangeSize = |
| kMaxUnackedFrames + // Maximum unACKed frames. |
| 1 + // The last ACKed frame. |
| 1; // One not-yet-enqueued frame (see call to EstimatedSendingTime()). |
| DCHECK_LE(retention_count, std::max(history_size_, kMaxInFlightRangeSize)); |
| |
| while (frame_stats_.size() > retention_count) { |
| DCHECK(!frame_stats_[0].ack_time.is_null()); |
| acked_bits_in_history_ -= frame_stats_[0].frame_size_in_bits; |
| dead_time_in_history_ -= DeadTime(frame_stats_[0], frame_stats_[1]); |
| DCHECK_GE(acked_bits_in_history_, 0UL); |
| VLOG(2) << "DT: " << dead_time_in_history_.InSecondsF(); |
| DCHECK_GE(dead_time_in_history_.InSecondsF(), 0.0); |
| frame_stats_.pop_front(); |
| } |
| } |
| |
| void AdaptiveCongestionControl::AckFrame(FrameId frame_id, |
| base::TimeTicks when) { |
| FrameStats* frame_stats = GetFrameStats(last_checkpoint_frame_); |
| while (last_checkpoint_frame_ < frame_id) { |
| FrameStats* last_frame_stats = frame_stats; |
| frame_stats = GetFrameStats(last_checkpoint_frame_ + 1); |
| // Note: This increment must happen AFTER the GetFrameStats() call to |
| // prevent the |last_frame_stats| pointer from being invalidated. |
| last_checkpoint_frame_++; |
| // When ACKing a frame that was never sent, just pretend it was sent and |
| // ACKed at the same point-in-time. |
| if (frame_stats->enqueue_time.is_null()) |
| frame_stats->enqueue_time = when; |
| else if (when < frame_stats->enqueue_time) |
| when = frame_stats->enqueue_time; |
| // Don't overwrite the ack time for those frames that were already acked in |
| // previous extended ACKs. |
| if (frame_stats->ack_time.is_null()) |
| frame_stats->ack_time = when; |
| DCHECK_GE(when, frame_stats->ack_time); |
| acked_bits_in_history_ += frame_stats->frame_size_in_bits; |
| dead_time_in_history_ += DeadTime(*last_frame_stats, *frame_stats); |
| last_checkpoint_time_ = when; |
| } |
| } |
| |
| void AdaptiveCongestionControl::AckLaterFrames( |
| std::vector<FrameId> received_frames, |
| base::TimeTicks when) { |
| DCHECK(std::is_sorted(received_frames.begin(), received_frames.end())); |
| for (FrameId frame_id : received_frames) { |
| if (frame_id <= last_checkpoint_frame_) |
| continue; |
| FrameStats* frame_stats = GetFrameStats(frame_id); |
| // When ACKing a frame that was never sent, just pretend it was sent and |
| // ACKed at the same point-in-time. |
| if (frame_stats->enqueue_time.is_null()) |
| frame_stats->enqueue_time = when; |
| else if (when < frame_stats->enqueue_time) |
| when = frame_stats->enqueue_time; |
| // Don't overwrite the ack time for those frames that were acked before. |
| if (frame_stats->ack_time.is_null()) |
| frame_stats->ack_time = when; |
| DCHECK_GE(when, frame_stats->ack_time); |
| } |
| } |
| |
| void AdaptiveCongestionControl::SendFrameToTransport(FrameId frame_id, |
| size_t frame_size_in_bits, |
| base::TimeTicks when) { |
| last_enqueued_frame_ = frame_id; |
| FrameStats* frame_stats = GetFrameStats(frame_id); |
| DCHECK(frame_stats); |
| frame_stats->enqueue_time = when; |
| frame_stats->frame_size_in_bits = frame_size_in_bits; |
| } |
| |
| base::TimeTicks AdaptiveCongestionControl::EstimatedSendingTime( |
| FrameId frame_id, |
| double estimated_bitrate) { |
| const base::TimeTicks now = clock_->NowTicks(); |
| |
| // Starting with the time of the latest acknowledgement, extrapolate forward |
| // to determine an estimated sending time for |frame_id|. |
| // |
| // |estimated_sending_time| will contain the estimated sending time for each |
| // frame after the last ACK'ed frame. It is possible for multiple frames to |
| // be in-flight; and therefore it is common for the |estimated_sending_time| |
| // for those frames to be before |now|. The initial estimate is based on the |
| // last ACKed frame and the RTT. |
| base::TimeTicks estimated_sending_time = last_checkpoint_time_ - rtt_; |
| for (FrameId f = last_checkpoint_frame_ + 1; f < frame_id; ++f) { |
| FrameStats* const stats = GetFrameStats(f); |
| |
| // |estimated_ack_time| is the local time when the sender receives the ACK, |
| // and not the time when the ACK left the receiver. |
| base::TimeTicks estimated_ack_time = stats->ack_time; |
| |
| // Do not update the estimate if this frame's packets will never again enter |
| // the packet send queue; unless there is no estimate yet. |
| if (!estimated_ack_time.is_null()) |
| continue; |
| |
| // Model: The |estimated_sending_time| is the time at which the first byte |
| // of the encoded frame is transmitted. Then, assume the transmission of |
| // the remaining bytes is paced such that the last byte has just left the |
| // sender at |frame_transmit_time| later. This last byte then takes |
| // ~RTT/2 amount of time to travel to the receiver. Finally, the ACK from |
| // the receiver is sent and this takes another ~RTT/2 amount of time to |
| // reach the sender. |
| const base::TimeDelta frame_transmit_time = base::TimeDelta::FromSecondsD( |
| stats->frame_size_in_bits / estimated_bitrate); |
| estimated_ack_time = std::max(estimated_sending_time, stats->enqueue_time) + |
| frame_transmit_time + rtt_; |
| |
| if (estimated_ack_time < now) { |
| // The current frame has not yet been ACK'ed and the yet the computed |
| // |estimated_ack_time| is before |now|. This contradiction must be |
| // resolved. |
| // |
| // The solution below is a little counter-intuitive, but it seems to |
| // work. Basically, when we estimate that the ACK should have already |
| // happened, we figure out how long ago it should have happened and |
| // guess that the ACK will happen half of that time in the future. This |
| // will cause some over-estimation when acks are late, which is actually |
| // the desired behavior. |
| estimated_ack_time = now + (now - estimated_ack_time) / 2; |
| } |
| |
| // Since we [in the common case] do not wait for an ACK before we start |
| // sending the next frame, estimate the next frame's sending time as the |
| // time just after the last byte of the current frame left the sender (see |
| // Model comment above). |
| estimated_sending_time = |
| std::max(estimated_sending_time, estimated_ack_time - rtt_); |
| } |
| |
| FrameStats* const frame_stats = GetFrameStats(frame_id); |
| DCHECK(frame_stats); |
| if (frame_stats->enqueue_time.is_null()) { |
| // The frame has not yet been enqueued for transport. Since it cannot be |
| // enqueued in the past, ensure the result is lower-bounded by |now|. |
| estimated_sending_time = std::max(estimated_sending_time, now); |
| } else { |
| // |frame_stats->enqueue_time| is the time the frame was enqueued for |
| // transport. The frame may not actually start being sent until a |
| // point-in-time after that, because the transport is waiting for prior |
| // frames to be acknowledged. |
| estimated_sending_time = |
| std::max(estimated_sending_time, frame_stats->enqueue_time); |
| } |
| |
| return estimated_sending_time; |
| } |
| |
| int AdaptiveCongestionControl::GetBitrate(base::TimeTicks playout_time, |
| base::TimeDelta playout_delay) { |
| double safe_bitrate = CalculateSafeBitrate(); |
| // Estimate when we might start sending the next frame. |
| base::TimeDelta time_to_catch_up = |
| playout_time - |
| EstimatedSendingTime(last_enqueued_frame_ + 1, safe_bitrate); |
| |
| double empty_buffer_fraction = |
| time_to_catch_up.InSecondsF() / playout_delay.InSecondsF(); |
| empty_buffer_fraction = std::min(empty_buffer_fraction, 1.0); |
| empty_buffer_fraction = std::max(empty_buffer_fraction, 0.0); |
| |
| int bits_per_second = static_cast<int>( |
| safe_bitrate * empty_buffer_fraction / kTargetEmptyBufferFraction); |
| VLOG(3) << " FBR:" << (bits_per_second / 1E6) |
| << " EBF:" << empty_buffer_fraction |
| << " SBR:" << (safe_bitrate / 1E6); |
| TRACE_COUNTER_ID1("cast.stream", "Empty Buffer Fraction", this, |
| empty_buffer_fraction); |
| bits_per_second = std::max(bits_per_second, min_bitrate_configured_); |
| bits_per_second = std::min(bits_per_second, max_bitrate_configured_); |
| |
| return bits_per_second; |
| } |
| |
| } // namespace cast |
| } // namespace media |