1 /* 2 * Copyright (c) 2017 The WebRTC project authors. All Rights Reserved. 3 * 4 * Use of this source code is governed by a BSD-style license 5 * that can be found in the LICENSE file in the root of the source 6 * tree. An additional intellectual property rights grant can be found 7 * in the file PATENTS. All contributing project authors may 8 * be found in the AUTHORS file in the root of the source tree. 9 * 10 */ 11 12 #ifndef MODULES_REMOTE_BITRATE_ESTIMATOR_TEST_ESTIMATORS_BBR_H_ 13 #define MODULES_REMOTE_BITRATE_ESTIMATOR_TEST_ESTIMATORS_BBR_H_ 14 15 #include <list> 16 #include <map> 17 #include <memory> 18 #include <vector> 19 20 #include "api/optional.h" 21 #include "modules/remote_bitrate_estimator/test/bwe.h" 22 #include "rtc_base/numerics/sequence_number_util.h" 23 #include "rtc_base/random.h" 24 25 namespace webrtc { 26 namespace testing { 27 namespace bwe { 28 class MaxBandwidthFilter; 29 class MinRttFilter; 30 class CongestionWindow; 31 class BbrBweSender : public BweSender { 32 public: 33 explicit BbrBweSender(BitrateObserver* observer, Clock* clock); 34 virtual ~BbrBweSender(); 35 enum Mode { 36 // Startup phase. 37 STARTUP, 38 // Queue draining phase, which where created during startup. 39 DRAIN, 40 // Cruising, probing new bandwidth. 41 PROBE_BW, 42 // Temporarily limiting congestion window size in order to measure 43 // minimum RTT. 44 PROBE_RTT, 45 // Temporarily reducing pacing rate and congestion window, in order to 46 // ensure no queues are built. 47 RECOVERY 48 }; 49 50 struct PacketStats { PacketStatsPacketStats51 PacketStats() {} PacketStatsPacketStats52 PacketStats(uint16_t sequence_number_, 53 int64_t last_sent_packet_send_time_ms_, 54 int64_t send_time_ms_, 55 int64_t ack_time_ms_, 56 int64_t last_acked_packet_ack_time_ms_, 57 size_t payload_size_bytes_, 58 size_t data_sent_bytes_, 59 size_t data_sent_before_last_sent_packet_bytes_, 60 size_t data_acked_bytes_, 61 size_t data_acked_before_last_acked_packet_bytes_) 62 : sequence_number(sequence_number_), 63 last_sent_packet_send_time_ms(last_sent_packet_send_time_ms_), 64 send_time_ms(send_time_ms_), 65 ack_time_ms(ack_time_ms_), 66 last_acked_packet_ack_time_ms(last_acked_packet_ack_time_ms_), 67 payload_size_bytes(payload_size_bytes_), 68 data_sent_bytes(data_sent_bytes_), 69 data_sent_before_last_sent_packet_bytes( 70 data_sent_before_last_sent_packet_bytes_), 71 data_acked_bytes(data_acked_bytes_), 72 data_acked_before_last_acked_packet_bytes( 73 data_acked_before_last_acked_packet_bytes_) {} 74 // Sequence number of this packet. 75 uint16_t sequence_number; 76 // Send time of the last sent packet at ack time of this packet. 77 int64_t last_sent_packet_send_time_ms; 78 // Send time of this packet. 79 int64_t send_time_ms; 80 // Ack time of this packet. 81 int64_t ack_time_ms; 82 // Ack time of the last acked packet at send time of this packet. 83 int64_t last_acked_packet_ack_time_ms; 84 // Payload size of this packet. 85 size_t payload_size_bytes; 86 // Amount of data sent before this packet was sent. 87 size_t data_sent_bytes; 88 // Amount of data sent, before last sent packet. 89 size_t data_sent_before_last_sent_packet_bytes; 90 // Amount of data acked, before this packet was acked. 91 size_t data_acked_bytes; 92 // Amount of data acked, before last acked packet. 93 size_t data_acked_before_last_acked_packet_bytes; 94 }; 95 struct AverageRtt { AverageRttAverageRtt96 AverageRtt() {} AverageRttAverageRtt97 AverageRtt(int64_t sum_of_rtts_ms_, int64_t num_samples_, uint64_t round_) 98 : sum_of_rtts_ms(sum_of_rtts_ms_), 99 num_samples(num_samples_), 100 round(round_) {} 101 // Sum of RTTs over the round. 102 int64_t sum_of_rtts_ms; 103 // Number of RTT samples over the round. 104 int64_t num_samples; 105 // The number of the round average RTT is recorded for. 106 uint64_t round; 107 }; 108 void OnPacketsSent(const Packets& packets) override; 109 int GetFeedbackIntervalMs() const override; 110 void GiveFeedback(const FeedbackPacket& feedback) override; 111 int64_t TimeUntilNextProcess() override; 112 void Process() override; 113 114 private: 115 void EnterStartup(); 116 void UpdateBandwidthAndMinRtt(int64_t now_ms, 117 const std::vector<uint16_t>& feedback_vector, 118 int64_t bytes_acked); 119 void TryExitingStartup(); 120 void TryExitingDrain(int64_t now_ms); 121 void EnterProbeBw(int64_t now_ms); 122 void TryUpdatingCyclePhase(int64_t now_ms); 123 void TryEnteringProbeRtt(int64_t now_ms); 124 void TryExitingProbeRtt(int64_t now_ms, int64_t round); 125 void TryEnteringRecovery(bool new_round_started); 126 void TryExitingRecovery(bool new_round_started); 127 size_t TargetCongestionWindow(float gain); 128 void CalculatePacingRate(); 129 130 // Calculates and returns bandwidth sample as minimum between send rate and 131 // ack rate, returns nothing if sample cannot be calculated. 132 rtc::Optional<int64_t> CalculateBandwidthSample(size_t data_sent, 133 int64_t send_time_delta_ms, 134 size_t data_acked, 135 int64_t ack_time_delta_ms); 136 137 // Calculate and add bandwidth sample only for packets' sent during high gain 138 // phase. Motivation of having a seperate bucket for high gain phase is to 139 // achieve quicker ramp up. Slight overestimations may happen due to window 140 // not being as large as usual. 141 void AddSampleForHighGain(); 142 143 // Declares lost packets as acked. Implements simple logic by looking at the 144 // gap between sequence numbers. If there is a gap between sequence numbers we 145 // declare those packets as lost immediately. 146 void HandleLoss(uint64_t last_acked_packet, uint64_t recently_acked_packet); 147 void AddToPastRtts(int64_t rtt_sample_ms); 148 BitrateObserver* observer_; 149 Clock* const clock_; 150 Mode mode_; 151 std::unique_ptr<MaxBandwidthFilter> max_bandwidth_filter_; 152 std::unique_ptr<MinRttFilter> min_rtt_filter_; 153 std::unique_ptr<CongestionWindow> congestion_window_; 154 std::unique_ptr<Random> rand_; 155 uint64_t round_count_; 156 uint64_t round_trip_end_; 157 float pacing_gain_; 158 float congestion_window_gain_; 159 160 // If optimal bandwidth has been discovered and reached, (for example after 161 // Startup mode) set this variable to true. 162 bool full_bandwidth_reached_; 163 164 // Entering time for PROBE_BW mode's cycle phase. 165 int64_t cycle_start_time_ms_; 166 167 // Index number of the currently used gain value in PROBE_BW mode, from 0 to 168 // kGainCycleLength - 1. 169 int64_t cycle_index_; 170 size_t bytes_acked_; 171 172 // Time we entered PROBE_RTT mode. 173 int64_t probe_rtt_start_time_ms_; 174 175 // First moment of time when data inflight decreased below 176 // kMinimumCongestionWindow in PROBE_RTT mode. 177 rtc::Optional<int64_t> minimum_congestion_window_start_time_ms_; 178 179 // First round when data inflight decreased below kMinimumCongestionWindow in 180 // PROBE_RTT mode. 181 int64_t minimum_congestion_window_start_round_; 182 size_t bytes_sent_; 183 uint16_t last_packet_sent_sequence_number_; 184 uint16_t last_packet_acked_sequence_number_; 185 int64_t last_packet_ack_time_; 186 int64_t last_packet_send_time_; 187 int64_t pacing_rate_bps_; 188 189 // Send time of a packet sent first during high gain phase. Also serves as a 190 // flag, holding value means that we are already in high gain. 191 rtc::Optional<int64_t> first_packet_send_time_during_high_gain_ms_; 192 193 // Send time of a packet sent last during high gain phase. 194 int64_t last_packet_send_time_during_high_gain_ms_; 195 196 // Amount of data sent, before first packet was sent during high gain phase. 197 int64_t data_sent_before_high_gain_started_bytes_; 198 199 // Amount of data sent, before last packet was sent during high gain phase. 200 int64_t data_sent_before_high_gain_ended_bytes_; 201 202 // Ack time of a packet acked first during high gain phase. 203 int64_t first_packet_ack_time_during_high_gain_ms_; 204 205 // Ack time of a packet acked last during high gain phase. 206 int64_t last_packet_ack_time_during_high_gain_ms_; 207 208 // Amount of data acked, before the first packet was acked during high gain 209 // phase. 210 int64_t data_acked_before_high_gain_started_bytes_; 211 212 // Amount of data acked, before the last packet was acked during high gain 213 // phase. 214 int64_t data_acked_before_high_gain_ended_bytes_; 215 216 // Sequence number of the first packet sent during high gain phase. 217 uint16_t first_packet_seq_num_during_high_gain_; 218 219 // Sequence number of the last packet sent during high gain phase. 220 uint16_t last_packet_seq_num_during_high_gain_; 221 bool high_gain_over_; 222 std::map<int64_t, PacketStats> packet_stats_; 223 std::list<AverageRtt> past_rtts_; 224 }; 225 226 class BbrBweReceiver : public BweReceiver { 227 public: 228 explicit BbrBweReceiver(int flow_id); 229 virtual ~BbrBweReceiver(); 230 void ReceivePacket(int64_t arrival_time_ms, 231 const MediaPacket& media_packet) override; 232 FeedbackPacket* GetFeedback(int64_t now_ms) override; 233 private: 234 SimulatedClock clock_; 235 std::vector<uint16_t> packet_feedbacks_; 236 int64_t last_feedback_ms_; 237 }; 238 } // namespace bwe 239 } // namespace testing 240 } // namespace webrtc 241 242 #endif // MODULES_REMOTE_BITRATE_ESTIMATOR_TEST_ESTIMATORS_BBR_H_ 243