1/*
2 *  Copyright (c) 2012 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/test/fake_network_pipe.h"
12
13#include <assert.h>
14#include <math.h>
15#include <string.h>
16#include <algorithm>
17
18#include "webrtc/call.h"
19#include "webrtc/system_wrappers/interface/critical_section_wrapper.h"
20#include "webrtc/system_wrappers/interface/tick_util.h"
21
22namespace webrtc {
23
24const double kPi = 3.14159265;
25const int kDefaultProcessIntervalMs = 30;
26
27static int GaussianRandom(int mean_delay_ms, int standard_deviation_ms) {
28  // Creating a Normal distribution variable from two independent uniform
29  // variables based on the Box-Muller transform.
30  double uniform1 = (rand() + 1.0) / (RAND_MAX + 1.0);  // NOLINT
31  double uniform2 = (rand() + 1.0) / (RAND_MAX + 1.0);  // NOLINT
32  return static_cast<int>(mean_delay_ms + standard_deviation_ms *
33                          sqrt(-2 * log(uniform1)) * cos(2 * kPi * uniform2));
34}
35
36static bool UniformLoss(int loss_percent) {
37  int outcome = rand() % 100;
38  return outcome < loss_percent;
39}
40
41class NetworkPacket {
42 public:
43  NetworkPacket(const uint8_t* data, size_t length, int64_t send_time,
44      int64_t arrival_time)
45      : data_(NULL),
46        data_length_(length),
47        send_time_(send_time),
48        arrival_time_(arrival_time) {
49    data_ = new uint8_t[length];
50    memcpy(data_, data, length);
51  }
52  ~NetworkPacket() {
53    delete [] data_;
54  }
55
56  uint8_t* data() const { return data_; }
57  size_t data_length() const { return data_length_; }
58  int64_t send_time() const { return send_time_; }
59  int64_t arrival_time() const { return arrival_time_; }
60  void IncrementArrivalTime(int64_t extra_delay) {
61    arrival_time_+= extra_delay;
62  }
63
64 private:
65  // The packet data.
66  uint8_t* data_;
67  // Length of data_.
68  size_t data_length_;
69  // The time the packet was sent out on the network.
70  const int64_t send_time_;
71  // The time the packet should arrive at the reciver.
72  int64_t arrival_time_;
73};
74
75FakeNetworkPipe::FakeNetworkPipe(
76    const FakeNetworkPipe::Config& config)
77    : lock_(CriticalSectionWrapper::CreateCriticalSection()),
78      packet_receiver_(NULL),
79      config_(config),
80      dropped_packets_(0),
81      sent_packets_(0),
82      total_packet_delay_(0),
83      next_process_time_(TickTime::MillisecondTimestamp()) {
84}
85
86FakeNetworkPipe::~FakeNetworkPipe() {
87  while (!capacity_link_.empty()) {
88    delete capacity_link_.front();
89    capacity_link_.pop();
90  }
91  while (!delay_link_.empty()) {
92    delete delay_link_.front();
93    delay_link_.pop();
94  }
95}
96
97void FakeNetworkPipe::SetReceiver(PacketReceiver* receiver) {
98  packet_receiver_ = receiver;
99}
100
101void FakeNetworkPipe::SetConfig(const FakeNetworkPipe::Config& config) {
102  CriticalSectionScoped crit(lock_.get());
103  config_ = config;  // Shallow copy of the struct.
104}
105
106void FakeNetworkPipe::SendPacket(const uint8_t* data, size_t data_length) {
107  // A NULL packet_receiver_ means that this pipe will terminate the flow of
108  // packets.
109  if (packet_receiver_ == NULL)
110    return;
111  CriticalSectionScoped crit(lock_.get());
112  if (config_.queue_length_packets > 0 &&
113      capacity_link_.size() >= config_.queue_length_packets) {
114    // Too many packet on the link, drop this one.
115    ++dropped_packets_;
116    return;
117  }
118
119  int64_t time_now = TickTime::MillisecondTimestamp();
120
121  // Delay introduced by the link capacity.
122  int64_t capacity_delay_ms = 0;
123  if (config_.link_capacity_kbps > 0)
124    capacity_delay_ms = data_length / (config_.link_capacity_kbps / 8);
125  int64_t network_start_time = time_now;
126
127  // Check if there already are packets on the link and change network start
128  // time if there is.
129  if (capacity_link_.size() > 0)
130    network_start_time = capacity_link_.back()->arrival_time();
131
132  int64_t arrival_time = network_start_time + capacity_delay_ms;
133  NetworkPacket* packet = new NetworkPacket(data, data_length, time_now,
134                                            arrival_time);
135  capacity_link_.push(packet);
136}
137
138float FakeNetworkPipe::PercentageLoss() {
139  CriticalSectionScoped crit(lock_.get());
140  if (sent_packets_ == 0)
141    return 0;
142
143  return static_cast<float>(dropped_packets_) /
144      (sent_packets_ + dropped_packets_);
145}
146
147int FakeNetworkPipe::AverageDelay() {
148  CriticalSectionScoped crit(lock_.get());
149  if (sent_packets_ == 0)
150    return 0;
151
152  return total_packet_delay_ / static_cast<int>(sent_packets_);
153}
154
155void FakeNetworkPipe::Process() {
156  int64_t time_now = TickTime::MillisecondTimestamp();
157  std::queue<NetworkPacket*> packets_to_deliver;
158  {
159    CriticalSectionScoped crit(lock_.get());
160    // Check the capacity link first.
161    while (capacity_link_.size() > 0 &&
162           time_now >= capacity_link_.front()->arrival_time()) {
163      // Time to get this packet.
164      NetworkPacket* packet = capacity_link_.front();
165      capacity_link_.pop();
166
167      // Packets are randomly dropped after being affected by the bottleneck.
168      if (UniformLoss(config_.loss_percent)) {
169        delete packet;
170        continue;
171      }
172
173      // Add extra delay and jitter, but make sure the arrival time is not
174      // earlier than the last packet in the queue.
175      int extra_delay = GaussianRandom(config_.queue_delay_ms,
176                                       config_.delay_standard_deviation_ms);
177      if (delay_link_.size() > 0 &&
178          packet->arrival_time() + extra_delay <
179          delay_link_.back()->arrival_time()) {
180        extra_delay = delay_link_.back()->arrival_time() -
181            packet->arrival_time();
182      }
183      packet->IncrementArrivalTime(extra_delay);
184      if (packet->arrival_time() < next_process_time_)
185        next_process_time_ = packet->arrival_time();
186      delay_link_.push(packet);
187    }
188
189    // Check the extra delay queue.
190    while (delay_link_.size() > 0 &&
191           time_now >= delay_link_.front()->arrival_time()) {
192      // Deliver this packet.
193      NetworkPacket* packet = delay_link_.front();
194      packets_to_deliver.push(packet);
195      delay_link_.pop();
196      // |time_now| might be later than when the packet should have arrived, due
197      // to NetworkProcess being called too late. For stats, use the time it
198      // should have been on the link.
199      total_packet_delay_ += packet->arrival_time() - packet->send_time();
200    }
201    sent_packets_ += packets_to_deliver.size();
202  }
203  while (!packets_to_deliver.empty()) {
204    NetworkPacket* packet = packets_to_deliver.front();
205    packets_to_deliver.pop();
206    packet_receiver_->DeliverPacket(packet->data(), packet->data_length());
207    delete packet;
208  }
209}
210
211int FakeNetworkPipe::TimeUntilNextProcess() const {
212  CriticalSectionScoped crit(lock_.get());
213  if (capacity_link_.size() == 0 || delay_link_.size() == 0)
214    return kDefaultProcessIntervalMs;
215  return std::max(static_cast<int>(next_process_time_ -
216      TickTime::MillisecondTimestamp()), 0);
217}
218
219}  // namespace webrtc
220