1 /*
2  *  Copyright (c) 2013 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 #ifndef WEBRTC_MODULES_REMOTE_BITRATE_ESTIMATOR_TEST_BWE_TEST_FRAMEWORK_H_
12 #define WEBRTC_MODULES_REMOTE_BITRATE_ESTIMATOR_TEST_BWE_TEST_FRAMEWORK_H_
13 
14 #include <assert.h>
15 #include <math.h>
16 
17 #include <algorithm>
18 #include <list>
19 #include <numeric>
20 #include <set>
21 #include <sstream>
22 #include <string>
23 #include <utility>
24 #include <vector>
25 
26 #include "webrtc/base/common.h"
27 #include "webrtc/base/random.h"
28 #include "webrtc/base/scoped_ptr.h"
29 #include "webrtc/modules/bitrate_controller/include/bitrate_controller.h"
30 #include "webrtc/modules/include/module_common_types.h"
31 #include "webrtc/modules/pacing/paced_sender.h"
32 #include "webrtc/modules/remote_bitrate_estimator/include/remote_bitrate_estimator.h"
33 #include "webrtc/modules/remote_bitrate_estimator/test/bwe_test_logging.h"
34 #include "webrtc/modules/remote_bitrate_estimator/test/packet.h"
35 #include "webrtc/modules/rtp_rtcp/include/rtp_rtcp_defines.h"
36 #include "webrtc/system_wrappers/include/clock.h"
37 
38 namespace webrtc {
39 
40 class RtcpBandwidthObserver;
41 
42 namespace testing {
43 namespace bwe {
44 
45 class DelayCapHelper;
46 
47 class RateCounter {
48  public:
RateCounter(int64_t window_size_ms)49   explicit RateCounter(int64_t window_size_ms)
50       : window_size_us_(1000 * window_size_ms),
51         recently_received_packets_(0),
52         recently_received_bytes_(0),
53         last_accumulated_us_(0),
54         window_() {}
55 
RateCounter()56   RateCounter() : RateCounter(1000) {}
57 
58   void UpdateRates(int64_t send_time_us, uint32_t payload_size);
59 
window_size_ms()60   int64_t window_size_ms() const { return (window_size_us_ + 500) / 1000; }
61   uint32_t packets_per_second() const;
62   uint32_t bits_per_second() const;
63 
64   double BitrateWindowS() const;
65 
66  private:
67   typedef std::pair<int64_t, uint32_t> TimeSizePair;
68 
69   int64_t window_size_us_;
70   uint32_t recently_received_packets_;
71   uint32_t recently_received_bytes_;
72   int64_t last_accumulated_us_;
73   std::list<TimeSizePair> window_;
74 };
75 
76 typedef std::set<int> FlowIds;
77 const FlowIds CreateFlowIds(const int *flow_ids_array, size_t num_flow_ids);
78 const FlowIds CreateFlowIdRange(int initial_value, int last_value);
79 
80 template <typename T>
DereferencingComparator(const T * const & a,const T * const & b)81 bool DereferencingComparator(const T* const& a, const T* const& b) {
82   assert(a != NULL);
83   assert(b != NULL);
84   return *a < *b;
85 }
86 
87 template<typename T> class Stats {
88  public:
Stats()89   Stats()
90       : data_(),
91         last_mean_count_(0),
92         last_variance_count_(0),
93         last_minmax_count_(0),
94         mean_(0),
95         variance_(0),
96         min_(0),
97         max_(0) {
98   }
99 
Push(T data_point)100   void Push(T data_point) {
101     data_.push_back(data_point);
102   }
103 
GetMean()104   T GetMean() {
105     if (last_mean_count_ != data_.size()) {
106       last_mean_count_ = data_.size();
107       mean_ = std::accumulate(data_.begin(), data_.end(), static_cast<T>(0));
108       assert(last_mean_count_ != 0);
109       mean_ /= static_cast<T>(last_mean_count_);
110     }
111     return mean_;
112   }
GetVariance()113   T GetVariance() {
114     if (last_variance_count_ != data_.size()) {
115       last_variance_count_ = data_.size();
116       T mean = GetMean();
117       variance_ = 0;
118       for (const auto& sample : data_) {
119         T diff = (sample - mean);
120         variance_ += diff * diff;
121       }
122       assert(last_variance_count_ != 0);
123       variance_ /= static_cast<T>(last_variance_count_);
124     }
125     return variance_;
126   }
GetStdDev()127   T GetStdDev() {
128     return sqrt(static_cast<double>(GetVariance()));
129   }
GetMin()130   T GetMin() {
131     RefreshMinMax();
132     return min_;
133   }
GetMax()134   T GetMax() {
135     RefreshMinMax();
136     return max_;
137   }
138 
AsString()139   std::string AsString() {
140     std::stringstream ss;
141     ss << (GetMean() >= 0 ? GetMean() : -1) << ", " <<
142         (GetStdDev() >= 0 ? GetStdDev() : -1);
143     return ss.str();
144   }
145 
Log(const std::string & units)146   void Log(const std::string& units) {
147     BWE_TEST_LOGGING_LOG5("", "%f %s\t+/-%f\t[%f,%f]",
148         GetMean(), units.c_str(), GetStdDev(), GetMin(), GetMax());
149   }
150 
151  private:
RefreshMinMax()152   void RefreshMinMax() {
153     if (last_minmax_count_ != data_.size()) {
154       last_minmax_count_ = data_.size();
155       min_ = max_ = 0;
156       if (data_.empty()) {
157         return;
158       }
159       typename std::vector<T>::const_iterator it = data_.begin();
160       min_ = max_ = *it;
161       while (++it != data_.end()) {
162         min_ = std::min(min_, *it);
163         max_ = std::max(max_, *it);
164       }
165     }
166   }
167 
168   std::vector<T> data_;
169   typename std::vector<T>::size_type last_mean_count_;
170   typename std::vector<T>::size_type last_variance_count_;
171   typename std::vector<T>::size_type last_minmax_count_;
172   T mean_;
173   T variance_;
174   T min_;
175   T max_;
176 };
177 
178 bool IsTimeSorted(const Packets& packets);
179 
180 class PacketProcessor;
181 
182 enum ProcessorType { kSender, kReceiver, kRegular };
183 
184 class PacketProcessorListener {
185  public:
~PacketProcessorListener()186   virtual ~PacketProcessorListener() {}
187 
188   virtual void AddPacketProcessor(PacketProcessor* processor,
189                                   ProcessorType type) = 0;
190   virtual void RemovePacketProcessor(PacketProcessor* processor) = 0;
191 };
192 
193 class PacketProcessor {
194  public:
195   PacketProcessor(PacketProcessorListener* listener,
196                   int flow_id,
197                   ProcessorType type);
198   PacketProcessor(PacketProcessorListener* listener,
199                   const FlowIds& flow_ids,
200                   ProcessorType type);
201   virtual ~PacketProcessor();
202 
203   // Called after each simulation batch to allow the processor to plot any
204   // internal data.
Plot(int64_t timestamp_ms)205   virtual void Plot(int64_t timestamp_ms) {}
206 
207   // Run simulation for |time_ms| milliseconds, consuming packets from, and
208   // producing packets into in_out. The outgoing packet list must be sorted on
209   // |send_time_us_|. The simulation time |time_ms| is optional to use.
210   virtual void RunFor(int64_t time_ms, Packets* in_out) = 0;
211 
flow_ids()212   const FlowIds& flow_ids() const { return flow_ids_; }
213 
214   uint32_t packets_per_second() const;
215   uint32_t bits_per_second() const;
216 
217  protected:
218   RateCounter rate_counter_;
219 
220  private:
221   PacketProcessorListener* listener_;
222   const FlowIds flow_ids_;
223 
224   RTC_DISALLOW_COPY_AND_ASSIGN(PacketProcessor);
225 };
226 
227 class RateCounterFilter : public PacketProcessor {
228  public:
229   RateCounterFilter(PacketProcessorListener* listener,
230                     int flow_id,
231                     const char* name,
232                     const std::string& plot_name);
233   RateCounterFilter(PacketProcessorListener* listener,
234                     const FlowIds& flow_ids,
235                     const char* name,
236                     const std::string& plot_name);
237   RateCounterFilter(PacketProcessorListener* listener,
238                     const FlowIds& flow_ids,
239                     const char* name,
240                     int64_t start_plotting_time_ms,
241                     const std::string& plot_name);
242   virtual ~RateCounterFilter();
243 
244   void LogStats();
245   Stats<double> GetBitrateStats() const;
246   virtual void Plot(int64_t timestamp_ms);
247   virtual void RunFor(int64_t time_ms, Packets* in_out);
248 
249  private:
250   Stats<double> packets_per_second_stats_;
251   Stats<double> kbps_stats_;
252   std::string name_;
253   int64_t start_plotting_time_ms_;
254   // Algorithm name if single flow, Total link utilization if all flows.
255   std::string plot_name_;
256 
257   RTC_DISALLOW_IMPLICIT_CONSTRUCTORS(RateCounterFilter);
258 };
259 
260 class LossFilter : public PacketProcessor {
261  public:
262   LossFilter(PacketProcessorListener* listener, int flow_id);
263   LossFilter(PacketProcessorListener* listener, const FlowIds& flow_ids);
~LossFilter()264   virtual ~LossFilter() {}
265 
266   void SetLoss(float loss_percent);
267   virtual void RunFor(int64_t time_ms, Packets* in_out);
268 
269  private:
270   Random random_;
271   float loss_fraction_;
272 
273   RTC_DISALLOW_IMPLICIT_CONSTRUCTORS(LossFilter);
274 };
275 
276 class DelayFilter : public PacketProcessor {
277  public:
278   DelayFilter(PacketProcessorListener* listener, int flow_id);
279   DelayFilter(PacketProcessorListener* listener, const FlowIds& flow_ids);
~DelayFilter()280   virtual ~DelayFilter() {}
281 
282   void SetOneWayDelayMs(int64_t one_way_delay_ms);
283   virtual void RunFor(int64_t time_ms, Packets* in_out);
284 
285  private:
286   int64_t one_way_delay_us_;
287   int64_t last_send_time_us_;
288 
289   RTC_DISALLOW_IMPLICIT_CONSTRUCTORS(DelayFilter);
290 };
291 
292 class JitterFilter : public PacketProcessor {
293  public:
294   JitterFilter(PacketProcessorListener* listener, int flow_id);
295   JitterFilter(PacketProcessorListener* listener, const FlowIds& flow_ids);
~JitterFilter()296   virtual ~JitterFilter() {}
297 
298   void SetMaxJitter(int64_t stddev_jitter_ms);
299   virtual void RunFor(int64_t time_ms, Packets* in_out);
set_reorderdering(bool reordering)300   void set_reorderdering(bool reordering) { reordering_ = reordering; }
301   int64_t MeanUs();
302 
303  private:
304   Random random_;
305   int64_t stddev_jitter_us_;
306   int64_t last_send_time_us_;
307   bool reordering_;  // False by default.
308 
309   RTC_DISALLOW_IMPLICIT_CONSTRUCTORS(JitterFilter);
310 };
311 
312 // Reorders two consecutive packets with a probability of reorder_percent.
313 class ReorderFilter : public PacketProcessor {
314  public:
315   ReorderFilter(PacketProcessorListener* listener, int flow_id);
316   ReorderFilter(PacketProcessorListener* listener, const FlowIds& flow_ids);
~ReorderFilter()317   virtual ~ReorderFilter() {}
318 
319   void SetReorder(float reorder_percent);
320   virtual void RunFor(int64_t time_ms, Packets* in_out);
321 
322  private:
323   Random random_;
324   float reorder_fraction_;
325 
326   RTC_DISALLOW_IMPLICIT_CONSTRUCTORS(ReorderFilter);
327 };
328 
329 // Apply a bitrate choke with an infinite queue on the packet stream.
330 class ChokeFilter : public PacketProcessor {
331  public:
332   ChokeFilter(PacketProcessorListener* listener, int flow_id);
333   ChokeFilter(PacketProcessorListener* listener, const FlowIds& flow_ids);
334   virtual ~ChokeFilter();
335 
336   void set_capacity_kbps(uint32_t kbps);
337   void set_max_delay_ms(int64_t max_queueing_delay_ms);
338 
339   uint32_t capacity_kbps();
340 
341   virtual void RunFor(int64_t time_ms, Packets* in_out);
342 
343   Stats<double> GetDelayStats() const;
344 
345  private:
346   uint32_t capacity_kbps_;
347   int64_t last_send_time_us_;
348   rtc::scoped_ptr<DelayCapHelper> delay_cap_helper_;
349 
350   RTC_DISALLOW_IMPLICIT_CONSTRUCTORS(ChokeFilter);
351 };
352 
353 class TraceBasedDeliveryFilter : public PacketProcessor {
354  public:
355   TraceBasedDeliveryFilter(PacketProcessorListener* listener, int flow_id);
356   TraceBasedDeliveryFilter(PacketProcessorListener* listener,
357                            const FlowIds& flow_ids);
358   TraceBasedDeliveryFilter(PacketProcessorListener* listener,
359                            int flow_id,
360                            const char* name);
361   virtual ~TraceBasedDeliveryFilter();
362 
363   // The file should contain nanosecond timestamps corresponding to the time
364   // when the network can accept another packet. The timestamps should be
365   // separated by new lines, e.g., "100000000\n125000000\n321000000\n..."
366   bool Init(const std::string& filename);
367   virtual void Plot(int64_t timestamp_ms);
368   virtual void RunFor(int64_t time_ms, Packets* in_out);
369 
370   void set_max_delay_ms(int64_t max_delay_ms);
371   Stats<double> GetDelayStats() const;
372   Stats<double> GetBitrateStats() const;
373 
374  private:
375   void ProceedToNextSlot();
376 
377   typedef std::vector<int64_t> TimeList;
378   int64_t current_offset_us_;
379   TimeList delivery_times_us_;
380   TimeList::const_iterator next_delivery_it_;
381   int64_t local_time_us_;
382   rtc::scoped_ptr<RateCounter> rate_counter_;
383   std::string name_;
384   rtc::scoped_ptr<DelayCapHelper> delay_cap_helper_;
385   Stats<double> packets_per_second_stats_;
386   Stats<double> kbps_stats_;
387 
388   RTC_DISALLOW_COPY_AND_ASSIGN(TraceBasedDeliveryFilter);
389 };
390 
391 class VideoSource {
392  public:
393   VideoSource(int flow_id,
394               float fps,
395               uint32_t kbps,
396               uint32_t ssrc,
397               int64_t first_frame_offset_ms);
~VideoSource()398   virtual ~VideoSource() {}
399 
400   virtual void RunFor(int64_t time_ms, Packets* in_out);
401 
flow_id()402   virtual int flow_id() const { return flow_id_; }
SetBitrateBps(int bitrate_bps)403   virtual void SetBitrateBps(int bitrate_bps) {}
bits_per_second()404   uint32_t bits_per_second() const { return bits_per_second_; }
max_payload_size_bytes()405   uint32_t max_payload_size_bytes() const { return kMaxPayloadSizeBytes; }
406   int64_t GetTimeUntilNextFrameMs() const;
407 
408  protected:
409   virtual uint32_t NextFrameSize();
410   virtual uint32_t NextPacketSize(uint32_t frame_size,
411                                   uint32_t remaining_payload);
412 
413   const uint32_t kMaxPayloadSizeBytes;
414   const uint32_t kTimestampBase;
415   const double frame_period_ms_;
416   uint32_t bits_per_second_;
417   uint32_t frame_size_bytes_;
418 
419  private:
420   Random random_;
421   const int flow_id_;
422   int64_t next_frame_ms_;
423   int64_t next_frame_rand_ms_;
424   int64_t now_ms_;
425   RTPHeader prototype_header_;
426 
427   RTC_DISALLOW_IMPLICIT_CONSTRUCTORS(VideoSource);
428 };
429 
430 class AdaptiveVideoSource : public VideoSource {
431  public:
432   AdaptiveVideoSource(int flow_id,
433                       float fps,
434                       uint32_t kbps,
435                       uint32_t ssrc,
436                       int64_t first_frame_offset_ms);
~AdaptiveVideoSource()437   virtual ~AdaptiveVideoSource() {}
438 
439   void SetBitrateBps(int bitrate_bps) override;
440 
441  private:
442   RTC_DISALLOW_IMPLICIT_CONSTRUCTORS(AdaptiveVideoSource);
443 };
444 
445 class PeriodicKeyFrameSource : public AdaptiveVideoSource {
446  public:
447   PeriodicKeyFrameSource(int flow_id,
448                          float fps,
449                          uint32_t kbps,
450                          uint32_t ssrc,
451                          int64_t first_frame_offset_ms,
452                          int key_frame_interval);
~PeriodicKeyFrameSource()453   virtual ~PeriodicKeyFrameSource() {}
454 
455  protected:
456   uint32_t NextFrameSize() override;
457   uint32_t NextPacketSize(uint32_t frame_size,
458                           uint32_t remaining_payload) override;
459 
460  private:
461   int key_frame_interval_;
462   uint32_t frame_counter_;
463   int compensation_bytes_;
464   int compensation_per_frame_;
465   RTC_DISALLOW_IMPLICIT_CONSTRUCTORS(PeriodicKeyFrameSource);
466 };
467 }  // namespace bwe
468 }  // namespace testing
469 }  // namespace webrtc
470 
471 #endif  // WEBRTC_MODULES_REMOTE_BITRATE_ESTIMATOR_TEST_BWE_TEST_FRAMEWORK_H_
472