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