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 #include "webrtc/modules/remote_bitrate_estimator/test/bwe.h"
12
13 #include <limits>
14
15 #include "webrtc/base/common.h"
16 #include "webrtc/modules/remote_bitrate_estimator/test/estimators/nada.h"
17 #include "webrtc/modules/remote_bitrate_estimator/test/estimators/remb.h"
18 #include "webrtc/modules/remote_bitrate_estimator/test/estimators/send_side.h"
19 #include "webrtc/modules/remote_bitrate_estimator/test/estimators/tcp.h"
20
21 namespace webrtc {
22 namespace testing {
23 namespace bwe {
24
25 // With the assumption that packet loss is lower than 97%, the max gap
26 // between elements in the set is lower than 0x8000, hence we have a
27 // total order in the set. For (x,y,z) subset of the LinkedSet,
28 // (x<=y and y<=z) ==> x<=z so the set can be sorted.
29 const int kSetCapacity = 1000;
30
BweReceiver(int flow_id)31 BweReceiver::BweReceiver(int flow_id)
32 : flow_id_(flow_id),
33 received_packets_(kSetCapacity),
34 rate_counter_(),
35 loss_account_() {
36 }
37
BweReceiver(int flow_id,int64_t window_size_ms)38 BweReceiver::BweReceiver(int flow_id, int64_t window_size_ms)
39 : flow_id_(flow_id),
40 received_packets_(kSetCapacity),
41 rate_counter_(window_size_ms),
42 loss_account_() {
43 }
44
ReceivePacket(int64_t arrival_time_ms,const MediaPacket & media_packet)45 void BweReceiver::ReceivePacket(int64_t arrival_time_ms,
46 const MediaPacket& media_packet) {
47 if (received_packets_.size() == kSetCapacity) {
48 RelieveSetAndUpdateLoss();
49 }
50
51 received_packets_.Insert(media_packet.sequence_number(),
52 media_packet.send_time_ms(), arrival_time_ms,
53 media_packet.payload_size());
54
55 rate_counter_.UpdateRates(media_packet.send_time_ms() * 1000,
56 static_cast<uint32_t>(media_packet.payload_size()));
57 }
58
59 class NullBweSender : public BweSender {
60 public:
NullBweSender()61 NullBweSender() {}
~NullBweSender()62 virtual ~NullBweSender() {}
63
GetFeedbackIntervalMs() const64 int GetFeedbackIntervalMs() const override { return 1000; }
GiveFeedback(const FeedbackPacket & feedback)65 void GiveFeedback(const FeedbackPacket& feedback) override {}
OnPacketsSent(const Packets & packets)66 void OnPacketsSent(const Packets& packets) override {}
TimeUntilNextProcess()67 int64_t TimeUntilNextProcess() override {
68 return std::numeric_limits<int64_t>::max();
69 }
Process()70 int Process() override { return 0; }
71
72 private:
73 RTC_DISALLOW_COPY_AND_ASSIGN(NullBweSender);
74 };
75
GetAbsSendTimeInMs(uint32_t abs_send_time)76 int64_t GetAbsSendTimeInMs(uint32_t abs_send_time) {
77 const int kInterArrivalShift = 26;
78 const int kAbsSendTimeInterArrivalUpshift = 8;
79 const double kTimestampToMs =
80 1000.0 / static_cast<double>(1 << kInterArrivalShift);
81 uint32_t timestamp = abs_send_time << kAbsSendTimeInterArrivalUpshift;
82 return static_cast<int64_t>(timestamp) * kTimestampToMs;
83 }
84
CreateBweSender(BandwidthEstimatorType estimator,int kbps,BitrateObserver * observer,Clock * clock)85 BweSender* CreateBweSender(BandwidthEstimatorType estimator,
86 int kbps,
87 BitrateObserver* observer,
88 Clock* clock) {
89 switch (estimator) {
90 case kRembEstimator:
91 return new RembBweSender(kbps, observer, clock);
92 case kFullSendSideEstimator:
93 return new FullBweSender(kbps, observer, clock);
94 case kNadaEstimator:
95 return new NadaBweSender(kbps, observer, clock);
96 case kTcpEstimator:
97 FALLTHROUGH();
98 case kNullEstimator:
99 return new NullBweSender();
100 }
101 assert(false);
102 return NULL;
103 }
104
CreateBweReceiver(BandwidthEstimatorType type,int flow_id,bool plot)105 BweReceiver* CreateBweReceiver(BandwidthEstimatorType type,
106 int flow_id,
107 bool plot) {
108 switch (type) {
109 case kRembEstimator:
110 return new RembReceiver(flow_id, plot);
111 case kFullSendSideEstimator:
112 return new SendSideBweReceiver(flow_id);
113 case kNadaEstimator:
114 return new NadaBweReceiver(flow_id);
115 case kTcpEstimator:
116 return new TcpBweReceiver(flow_id);
117 case kNullEstimator:
118 return new BweReceiver(flow_id);
119 }
120 assert(false);
121 return NULL;
122 }
123
124 // Take into account all LinkedSet content.
UpdateLoss()125 void BweReceiver::UpdateLoss() {
126 loss_account_.Add(LinkedSetPacketLossRatio());
127 }
128
129 // Preserve 10% latest packets and update packet loss based on the oldest
130 // 90%, that will be removed.
RelieveSetAndUpdateLoss()131 void BweReceiver::RelieveSetAndUpdateLoss() {
132 // Compute Loss for the whole LinkedSet and updates loss_account_.
133 UpdateLoss();
134
135 size_t num_preserved_elements = received_packets_.size() / 10;
136 PacketNodeIt it = received_packets_.begin();
137 std::advance(it, num_preserved_elements);
138
139 while (it != received_packets_.end()) {
140 received_packets_.Erase(it++);
141 }
142
143 // Compute Loss for the preserved elements
144 loss_account_.Subtract(LinkedSetPacketLossRatio());
145 }
146
GlobalReceiverPacketLossRatio()147 float BweReceiver::GlobalReceiverPacketLossRatio() {
148 UpdateLoss();
149 return loss_account_.LossRatio();
150 }
151
152 // This function considers at most kSetCapacity = 1000 packets.
LinkedSetPacketLossRatio()153 LossAccount BweReceiver::LinkedSetPacketLossRatio() {
154 if (received_packets_.empty()) {
155 return LossAccount();
156 }
157
158 uint16_t oldest_seq_num = received_packets_.OldestSeqNumber();
159 uint16_t newest_seq_num = received_packets_.NewestSeqNumber();
160
161 size_t set_total_packets =
162 static_cast<uint16_t>(newest_seq_num - oldest_seq_num + 1);
163
164 size_t set_received_packets = received_packets_.size();
165 size_t set_lost_packets = set_total_packets - set_received_packets;
166
167 return LossAccount(set_total_packets, set_lost_packets);
168 }
169
RecentKbps() const170 uint32_t BweReceiver::RecentKbps() const {
171 return (rate_counter_.bits_per_second() + 500) / 1000;
172 }
173
174 // Go through a fixed time window of most recent packets received and
175 // counts packets missing to obtain the packet loss ratio. If an unordered
176 // packet falls out of the timewindow it will be counted as missing.
177 // E.g.: for a timewindow covering 5 packets of the following arrival sequence
178 // {10 7 9 5 6} 8 3 2 4 1, the output will be 1/6 (#8 is considered as missing).
RecentPacketLossRatio()179 float BweReceiver::RecentPacketLossRatio() {
180 if (received_packets_.empty()) {
181 return 0.0f;
182 }
183 int number_packets_received = 0;
184
185 PacketNodeIt node_it = received_packets_.begin(); // Latest.
186
187 // Lowest timestamp limit, oldest one that should be checked.
188 int64_t time_limit_ms = (*node_it)->arrival_time_ms - kPacketLossTimeWindowMs;
189 // Oldest and newest values found within the given time window.
190 uint16_t oldest_seq_num = (*node_it)->sequence_number;
191 uint16_t newest_seq_num = oldest_seq_num;
192
193 while (node_it != received_packets_.end()) {
194 if ((*node_it)->arrival_time_ms < time_limit_ms) {
195 break;
196 }
197 uint16_t seq_num = (*node_it)->sequence_number;
198 if (IsNewerSequenceNumber(seq_num, newest_seq_num)) {
199 newest_seq_num = seq_num;
200 }
201 if (IsNewerSequenceNumber(oldest_seq_num, seq_num)) {
202 oldest_seq_num = seq_num;
203 }
204 ++node_it;
205 ++number_packets_received;
206 }
207 // Interval width between oldest and newest sequence number.
208 // There was an overflow if newest_seq_num < oldest_seq_num.
209 int gap = static_cast<uint16_t>(newest_seq_num - oldest_seq_num + 1);
210
211 return static_cast<float>(gap - number_packets_received) / gap;
212 }
213
~LinkedSet()214 LinkedSet::~LinkedSet() {
215 while (!empty())
216 RemoveTail();
217 }
218
Insert(uint16_t sequence_number,int64_t send_time_ms,int64_t arrival_time_ms,size_t payload_size)219 void LinkedSet::Insert(uint16_t sequence_number,
220 int64_t send_time_ms,
221 int64_t arrival_time_ms,
222 size_t payload_size) {
223 auto it = map_.find(sequence_number);
224 if (it != map_.end()) {
225 PacketNodeIt node_it = it->second;
226 PacketIdentifierNode* node = *node_it;
227 node->arrival_time_ms = arrival_time_ms;
228 if (node_it != list_.begin()) {
229 list_.erase(node_it);
230 list_.push_front(node);
231 map_[sequence_number] = list_.begin();
232 }
233 } else {
234 if (size() == capacity_) {
235 RemoveTail();
236 }
237 UpdateHead(new PacketIdentifierNode(sequence_number, send_time_ms,
238 arrival_time_ms, payload_size));
239 }
240 }
241
Insert(PacketIdentifierNode packet_identifier)242 void LinkedSet::Insert(PacketIdentifierNode packet_identifier) {
243 Insert(packet_identifier.sequence_number, packet_identifier.send_time_ms,
244 packet_identifier.arrival_time_ms, packet_identifier.payload_size);
245 }
246
RemoveTail()247 void LinkedSet::RemoveTail() {
248 map_.erase(list_.back()->sequence_number);
249 delete list_.back();
250 list_.pop_back();
251 }
UpdateHead(PacketIdentifierNode * new_head)252 void LinkedSet::UpdateHead(PacketIdentifierNode* new_head) {
253 list_.push_front(new_head);
254 map_[new_head->sequence_number] = list_.begin();
255 }
256
Erase(PacketNodeIt node_it)257 void LinkedSet::Erase(PacketNodeIt node_it) {
258 map_.erase((*node_it)->sequence_number);
259 delete (*node_it);
260 list_.erase(node_it);
261 }
262
Add(LossAccount rhs)263 void LossAccount::Add(LossAccount rhs) {
264 num_total += rhs.num_total;
265 num_lost += rhs.num_lost;
266 }
Subtract(LossAccount rhs)267 void LossAccount::Subtract(LossAccount rhs) {
268 num_total -= rhs.num_total;
269 num_lost -= rhs.num_lost;
270 }
271
LossRatio()272 float LossAccount::LossRatio() {
273 if (num_total == 0)
274 return 0.0f;
275 return static_cast<float>(num_lost) / num_total;
276 }
277
278 } // namespace bwe
279 } // namespace testing
280 } // namespace webrtc
281