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