1 // Copyright 2020 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 #ifndef CAST_STREAMING_BANDWIDTH_ESTIMATOR_H_ 6 #define CAST_STREAMING_BANDWIDTH_ESTIMATOR_H_ 7 8 #include <stdint.h> 9 10 #include <limits> 11 12 #include "platform/api/time.h" 13 14 namespace openscreen { 15 namespace cast { 16 17 // Tracks send attempts and successful receives, and then computes a total 18 // network bandwith estimate. 19 // 20 // Two metrics are tracked by the BandwidthEstimator, over a "recent history" 21 // time window: 22 // 23 // 1. The number of packets sent during bursts (see SenderPacketRouter for 24 // explanation of what a "burst" is). These track when the network was 25 // actually in-use for transmission and the magnitude of each burst. When 26 // computing bandwidth, the estimator assumes the timeslices where the 27 // network was not in-use could have been used to send even more bytes at 28 // the same rate. 29 // 30 // 2. Successful receipt of payload bytes over time, or a lack thereof. 31 // Packets that include acknowledgements from the Receivers are providing 32 // proof of the successful receipt of payload bytes. All other packets 33 // provide proof of network connectivity over time, and are used to 34 // identify periods of time where nothing was received. 35 // 36 // The BandwidthEstimator assumes a simplified model for streaming over the 37 // network. The model does not include any detailed knowledge about things like 38 // protocol overhead, packet re-transmits, parasitic bufferring, network 39 // reliability, etc. Instead, it automatically accounts for all such things by 40 // looking at what's actually leaving the Senders and what's actually making it 41 // to the Receivers. 42 // 43 // This simplified model does produce some known inaccuracies in the resulting 44 // estimations. If no data has recently been transmitted (or been received), 45 // estimations cannot be provided. If the transmission rate is near (or 46 // exceeding) the network's capacity, the estimations will be very accurate. In 47 // between those two extremes, the logic will tend to under-estimate the 48 // network's capacity. However, those under-estimates will still be far larger 49 // than the current transmission rate. 50 // 51 // Thus, these estimates can be used effectively as a control signal for 52 // congestion control in upstream code modules. The logic computing the media's 53 // encoding target bitrate should be adjusted in realtime using a TCP-like 54 // congestion control algorithm: 55 // 56 // 1. When the estimated bitrate is less than the current encoding target 57 // bitrate, aggressively and immediately decrease the encoding bitrate. 58 // 59 // 2. When the estimated bitrate is more than the current encoding target 60 // bitrate, gradually increase the encoding bitrate (up to the maximum 61 // that is reasonable for the application). 62 class BandwidthEstimator { 63 public: 64 // |max_packets_per_timeslice| and |timeslice_duration| should match the burst 65 // configuration in SenderPacketRouter. |start_time| should be a recent 66 // point-in-time before the first packet is sent. 67 BandwidthEstimator(int max_packets_per_timeslice, 68 Clock::duration timeslice_duration, 69 Clock::time_point start_time); 70 71 ~BandwidthEstimator(); 72 73 // Returns the duration of the fixed, recent-history time window over which 74 // data flows are being tracked. history_window()75 Clock::duration history_window() const { return history_window_; } 76 77 // Records |when| burst-sending was active or inactive. For the active case, 78 // |num_packets_sent| should include all network packets sent, including 79 // non-payload packets (since both affect the modeled utilization/capacity). 80 // For the inactive case, this method should be called with zero for 81 // |num_packets_sent|. 82 void OnBurstComplete(int num_packets_sent, Clock::time_point when); 83 84 // Records when a RTCP packet was received. It's important for Senders to call 85 // this any time a packet comes in from the Receivers, even if no payload is 86 // being acknowledged, since the time windows of "nothing successfully 87 // received" is also important information to track. 88 void OnRtcpReceived(Clock::time_point arrival_time, 89 Clock::duration estimated_round_trip_time); 90 91 // Records that some number of payload bytes has been acknowledged (i.e., 92 // successfully received). 93 void OnPayloadReceived(int payload_bytes_acknowledged, 94 Clock::time_point ack_arrival_time, 95 Clock::duration estimated_round_trip_time); 96 97 // Computes the current network bandwith estimate. Returns 0 if this cannot be 98 // determined due to a lack of sufficiently-recent data. 99 int ComputeNetworkBandwidth() const; 100 101 private: 102 // FlowTracker (below) manages a ring buffer of size 256. It simplifies the 103 // index calculations to use an integer data type where all arithmetic is mod 104 // 256. 105 using index_mod_256_t = uint8_t; 106 static constexpr int kNumTimeslices = 107 static_cast<int>(std::numeric_limits<index_mod_256_t>::max()) + 1; 108 109 // Tracks volume (e.g., the total number of payload bytes) over a fixed 110 // recent-history time window. The time window is divided up into a number of 111 // identical timeslices, each of which represents the total number of bytes 112 // that flowed during a certain period of time. The data is accumulated in 113 // ring buffer elements so that old data points drop-off as newer ones (that 114 // move the history window forward) are added. 115 class FlowTracker { 116 public: 117 FlowTracker(Clock::duration timeslice_duration, 118 Clock::time_point begin_time); 119 ~FlowTracker(); 120 begin_time()121 Clock::time_point begin_time() const { return begin_time_; } end_time()122 Clock::time_point end_time() const { 123 return begin_time_ + timeslice_duration_ * kNumTimeslices; 124 } 125 126 // Advance the end of the time window being tracked such that the 127 // most-recent timeslice includes |until|. Too-old timeslices are dropped 128 // and new ones are initialized to a zero amount. 129 void AdvanceToIncludeTime(Clock::time_point until); 130 131 // Accumulate the given |amount| into the timeslice that includes |when|. 132 void Accumulate(int32_t amount, Clock::time_point when); 133 134 // Return the sum of all the amounts in recent history. This clamps to the 135 // valid range of int32_t, if necessary. 136 int32_t Sum() const; 137 138 private: 139 const Clock::duration timeslice_duration_; 140 141 // The beginning of the oldest timeslice in the recent-history time window, 142 // the one pointed to by |tail_|. 143 Clock::time_point begin_time_; 144 145 // A ring buffer tracking the accumulated amount for each timeslice. 146 int32_t history_ring_[kNumTimeslices]{}; 147 148 // The index of the oldest timeslice in the |history_ring_|. This can also 149 // be thought of, equivalently, as the index just after the most-recent 150 // timeslice. 151 index_mod_256_t tail_ = 0; 152 }; 153 154 // The maximum number of packet sends that could possibly be attempted during 155 // the recent-history time window. 156 const int max_packets_per_history_window_; 157 158 // The range of time being tracked. 159 const Clock::duration history_window_; 160 161 // History tracking for send attempts, and success feeback. These timeseries 162 // are in terms of when packets have left the Senders. 163 FlowTracker burst_history_; 164 FlowTracker feedback_history_; 165 }; 166 167 } // namespace cast 168 } // namespace openscreen 169 170 #endif // CAST_STREAMING_BANDWIDTH_ESTIMATOR_H_ 171