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
21namespace webrtc {
22namespace testing {
23namespace 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.
29const int kSetCapacity = 1000;
30
31BweReceiver::BweReceiver(int flow_id)
32    : flow_id_(flow_id),
33      received_packets_(kSetCapacity),
34      rate_counter_(),
35      loss_account_() {
36}
37
38BweReceiver::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
45void 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
59class NullBweSender : public BweSender {
60 public:
61  NullBweSender() {}
62  virtual ~NullBweSender() {}
63
64  int GetFeedbackIntervalMs() const override { return 1000; }
65  void GiveFeedback(const FeedbackPacket& feedback) override {}
66  void OnPacketsSent(const Packets& packets) override {}
67  int64_t TimeUntilNextProcess() override {
68    return std::numeric_limits<int64_t>::max();
69  }
70  int Process() override { return 0; }
71
72 private:
73  RTC_DISALLOW_COPY_AND_ASSIGN(NullBweSender);
74};
75
76int64_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
85BweSender* 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
105BweReceiver* 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.
125void 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.
131void 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
147float BweReceiver::GlobalReceiverPacketLossRatio() {
148  UpdateLoss();
149  return loss_account_.LossRatio();
150}
151
152// This function considers at most kSetCapacity = 1000 packets.
153LossAccount 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
170uint32_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).
179float 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
214LinkedSet::~LinkedSet() {
215  while (!empty())
216    RemoveTail();
217}
218
219void 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
242void 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
247void LinkedSet::RemoveTail() {
248  map_.erase(list_.back()->sequence_number);
249  delete list_.back();
250  list_.pop_back();
251}
252void LinkedSet::UpdateHead(PacketIdentifierNode* new_head) {
253  list_.push_front(new_head);
254  map_[new_head->sequence_number] = list_.begin();
255}
256
257void LinkedSet::Erase(PacketNodeIt node_it) {
258  map_.erase((*node_it)->sequence_number);
259  delete (*node_it);
260  list_.erase(node_it);
261}
262
263void LossAccount::Add(LossAccount rhs) {
264  num_total += rhs.num_total;
265  num_lost += rhs.num_lost;
266}
267void LossAccount::Subtract(LossAccount rhs) {
268  num_total -= rhs.num_total;
269  num_lost -= rhs.num_lost;
270}
271
272float 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