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