1 /*
2  *  Copyright (c) 2015 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_H_
12 #define WEBRTC_MODULES_REMOTE_BITRATE_ESTIMATOR_TEST_BWE_H_
13 
14 #include <list>
15 #include <map>
16 #include <sstream>
17 #include <string>
18 
19 #include "webrtc/test/testsupport/gtest_prod_util.h"
20 #include "webrtc/modules/remote_bitrate_estimator/test/packet.h"
21 #include "webrtc/modules/bitrate_controller/include/bitrate_controller.h"
22 #include "webrtc/modules/remote_bitrate_estimator/test/bwe_test_framework.h"
23 
24 namespace webrtc {
25 namespace testing {
26 namespace bwe {
27 
28 // Overload map comparator.
29 class SequenceNumberOlderThan {
30  public:
operator()31   bool operator()(uint16_t seq_num_1, uint16_t seq_num_2) const {
32     return IsNewerSequenceNumber(seq_num_2, seq_num_1);
33   }
34 };
35 
36 // Holds information for computing global packet loss.
37 struct LossAccount {
LossAccountLossAccount38   LossAccount() : num_total(0), num_lost(0) {}
LossAccountLossAccount39   LossAccount(size_t num_total, size_t num_lost)
40       : num_total(num_total), num_lost(num_lost) {}
41   void Add(LossAccount rhs);
42   void Subtract(LossAccount rhs);
43   float LossRatio();
44   size_t num_total;
45   size_t num_lost;
46 };
47 
48 // Holds only essential information about packets to be saved for
49 // further use, e.g. for calculating packet loss and receiving rate.
50 struct PacketIdentifierNode {
PacketIdentifierNodePacketIdentifierNode51   PacketIdentifierNode(uint16_t sequence_number,
52                        int64_t send_time_ms,
53                        int64_t arrival_time_ms,
54                        size_t payload_size)
55       : sequence_number(sequence_number),
56         send_time_ms(send_time_ms),
57         arrival_time_ms(arrival_time_ms),
58         payload_size(payload_size) {}
59 
60   uint16_t sequence_number;
61   int64_t send_time_ms;
62   int64_t arrival_time_ms;
63   size_t payload_size;
64 };
65 
66 typedef std::list<PacketIdentifierNode*>::iterator PacketNodeIt;
67 
68 // FIFO implementation for a limited capacity set.
69 // Used for keeping the latest arrived packets while avoiding duplicates.
70 // Allows efficient insertion, deletion and search.
71 class LinkedSet {
72  public:
LinkedSet(int capacity)73   explicit LinkedSet(int capacity) : capacity_(capacity) {}
74   ~LinkedSet();
75 
76   // If the arriving packet (identified by its sequence number) is already
77   // in the LinkedSet, move its Node to the head of the list. Else, create
78   // a PacketIdentifierNode n_ and then UpdateHead(n_), calling RemoveTail()
79   // if the LinkedSet reached its maximum capacity.
80   void Insert(uint16_t sequence_number,
81               int64_t send_time_ms,
82               int64_t arrival_time_ms,
83               size_t payload_size);
84 
85   void Insert(PacketIdentifierNode packet_identifier);
86 
begin()87   PacketNodeIt begin() { return list_.begin(); }
end()88   PacketNodeIt end() { return list_.end(); }
89 
empty()90   bool empty() const { return list_.empty(); }
size()91   size_t size() const { return list_.size(); }
capacity()92   size_t capacity() const { return capacity_; }
93 
OldestSeqNumber()94   uint16_t OldestSeqNumber() const { return empty() ? 0 : map_.begin()->first; }
NewestSeqNumber()95   uint16_t NewestSeqNumber() const {
96     return empty() ? 0 : map_.rbegin()->first;
97   }
98 
99   void Erase(PacketNodeIt node_it);
100 
101  private:
102   // Pop oldest element from the back of the list and remove it from the map.
103   void RemoveTail();
104   // Add new element to the front of the list and insert it in the map.
105   void UpdateHead(PacketIdentifierNode* new_head);
106   size_t capacity_;
107   std::map<uint16_t, PacketNodeIt, SequenceNumberOlderThan> map_;
108   std::list<PacketIdentifierNode*> list_;
109 };
110 
111 const int kMinBitrateKbps = 50;
112 const int kMaxBitrateKbps = 2500;
113 
114 class BweSender : public Module {
115  public:
BweSender()116   BweSender() {}
BweSender(int bitrate_kbps)117   explicit BweSender(int bitrate_kbps) : bitrate_kbps_(bitrate_kbps) {}
~BweSender()118   virtual ~BweSender() {}
119 
120   virtual int GetFeedbackIntervalMs() const = 0;
121   virtual void GiveFeedback(const FeedbackPacket& feedback) = 0;
122   virtual void OnPacketsSent(const Packets& packets) = 0;
123 
124  protected:
125   int bitrate_kbps_;
126 
127  private:
128   RTC_DISALLOW_COPY_AND_ASSIGN(BweSender);
129 };
130 
131 class BweReceiver {
132  public:
133   explicit BweReceiver(int flow_id);
134   BweReceiver(int flow_id, int64_t window_size_ms);
135 
~BweReceiver()136   virtual ~BweReceiver() {}
137 
138   virtual void ReceivePacket(int64_t arrival_time_ms,
139                              const MediaPacket& media_packet);
GetFeedback(int64_t now_ms)140   virtual FeedbackPacket* GetFeedback(int64_t now_ms) { return NULL; }
141 
GetSetCapacity()142   size_t GetSetCapacity() { return received_packets_.capacity(); }
BitrateWindowS()143   double BitrateWindowS() const { return rate_counter_.BitrateWindowS(); }
144   uint32_t RecentKbps() const;  // Receiving Rate.
145 
146   // Computes packet loss during an entire simulation, up to 4 billion packets.
147   float GlobalReceiverPacketLossRatio();  // Plot histogram.
148   float RecentPacketLossRatio();          // Plot dynamics.
149 
150   static const int64_t kPacketLossTimeWindowMs = 500;
151   static const int64_t kReceivingRateTimeWindowMs = 1000;
152 
153  protected:
154   int flow_id_;
155   // Deals with packets sent more than once.
156   LinkedSet received_packets_;
157   // Used for calculating recent receiving rate.
158   RateCounter rate_counter_;
159 
160  private:
161   FRIEND_TEST_ALL_PREFIXES(BweReceiverTest, RecentKbps);
162   FRIEND_TEST_ALL_PREFIXES(BweReceiverTest, Loss);
163 
164   void UpdateLoss();
165   void RelieveSetAndUpdateLoss();
166   // Packet loss for packets stored in the LinkedSet, up to 1000 packets.
167   // Used to update global loss account whenever the set is filled and cleared.
168   LossAccount LinkedSetPacketLossRatio();
169 
170   // Used for calculating global packet loss ratio.
171   LossAccount loss_account_;
172 };
173 
174 enum BandwidthEstimatorType {
175   kNullEstimator,
176   kNadaEstimator,
177   kRembEstimator,
178   kFullSendSideEstimator,
179   kTcpEstimator
180 };
181 
182 const std::string bwe_names[] = {"Null", "NADA", "REMB", "GCC", "TCP"};
183 
184 int64_t GetAbsSendTimeInMs(uint32_t abs_send_time);
185 
186 BweSender* CreateBweSender(BandwidthEstimatorType estimator,
187                            int kbps,
188                            BitrateObserver* observer,
189                            Clock* clock);
190 
191 BweReceiver* CreateBweReceiver(BandwidthEstimatorType type,
192                                int flow_id,
193                                bool plot);
194 }  // namespace bwe
195 }  // namespace testing
196 }  // namespace webrtc
197 #endif  // WEBRTC_MODULES_REMOTE_BITRATE_ESTIMATOR_TEST_BWE_H_
198