blob: 8f9d76dfe3c2268ade21b2e718753c5a88d8482a [file] [log] [blame]
Sebastian Janssonf96b1ca2018-08-07 16:58:051/*
2 * Copyright 2018 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 "call/simulated_network.h"
12
13#include <algorithm>
14#include <cmath>
Mirko Bonadei248fdb12022-10-13 13:06:0815#include <cstdint>
Sebastian Janssonf96b1ca2018-08-07 16:58:0516#include <utility>
Yves Gerey3e707812018-11-28 15:47:4917
Sebastian Jansson2cd3b4c2018-11-06 18:18:2818#include "api/units/data_rate.h"
Yves Gerey3e707812018-11-28 15:47:4919#include "api/units/data_size.h"
20#include "api/units/time_delta.h"
21#include "rtc_base/checks.h"
Sebastian Janssonf96b1ca2018-08-07 16:58:0522
23namespace webrtc {
Sebastian Jansson836fee12019-02-08 15:08:1024namespace {
Mirko Bonadei248fdb12022-10-13 13:06:0825
26// Calculate the time (in microseconds) that takes to send N `bits` on a
27// network with link capacity equal to `capacity_kbps` starting at time
28// `start_time_us`.
29int64_t CalculateArrivalTimeUs(int64_t start_time_us,
30 int64_t bits,
31 int capacity_kbps) {
32 // If capacity is 0, the link capacity is assumed to be infinite.
33 if (capacity_kbps == 0) {
34 return start_time_us;
35 }
36 // Adding `capacity - 1` to the numerator rounds the extra delay caused by
37 // capacity constraints up to an integral microsecond. Sending 0 bits takes 0
38 // extra time, while sending 1 bit gets rounded up to 1 (the multiplication by
39 // 1000 is because capacity is in kbps).
40 // The factor 1000 comes from 10^6 / 10^3, where 10^6 is due to the time unit
41 // being us and 10^3 is due to the rate unit being kbps.
42 return start_time_us + ((1000 * bits + capacity_kbps - 1) / capacity_kbps);
43}
44
Sebastian Jansson2b08e312019-02-25 09:24:4645} // namespace
46
Sebastian Janssoncec24332019-12-04 13:26:5047SimulatedNetwork::SimulatedNetwork(Config config, uint64_t random_seed)
Mirko Bonadei248fdb12022-10-13 13:06:0848 : random_(random_seed),
49 bursting_(false),
50 last_enqueue_time_us_(0),
51 last_capacity_link_exit_time_(0) {
Sebastian Janssonf96b1ca2018-08-07 16:58:0552 SetConfig(config);
53}
54
55SimulatedNetwork::~SimulatedNetwork() = default;
56
Sebastian Janssoncec24332019-12-04 13:26:5057void SimulatedNetwork::SetConfig(const Config& config) {
Markus Handell8fe932a2020-07-06 15:41:3558 MutexLock lock(&config_lock_);
Sebastian Janssoneceea312019-01-31 10:50:0459 config_state_.config = config; // Shallow copy of the struct.
Sebastian Janssonf96b1ca2018-08-07 16:58:0560 double prob_loss = config.loss_percent / 100.0;
Sebastian Janssoneceea312019-01-31 10:50:0461 if (config_state_.config.avg_burst_loss_length == -1) {
Sebastian Janssonf96b1ca2018-08-07 16:58:0562 // Uniform loss
Sebastian Janssoneceea312019-01-31 10:50:0463 config_state_.prob_loss_bursting = prob_loss;
64 config_state_.prob_start_bursting = prob_loss;
Sebastian Janssonf96b1ca2018-08-07 16:58:0565 } else {
66 // Lose packets according to a gilbert-elliot model.
67 int avg_burst_loss_length = config.avg_burst_loss_length;
68 int min_avg_burst_loss_length = std::ceil(prob_loss / (1 - prob_loss));
69
70 RTC_CHECK_GT(avg_burst_loss_length, min_avg_burst_loss_length)
Jonas Olssonb2b20312020-01-14 11:11:3171 << "For a total packet loss of " << config.loss_percent
72 << "%% then"
73 " avg_burst_loss_length must be "
74 << min_avg_burst_loss_length + 1 << " or higher.";
Sebastian Janssonf96b1ca2018-08-07 16:58:0575
Sebastian Janssoneceea312019-01-31 10:50:0476 config_state_.prob_loss_bursting = (1.0 - 1.0 / avg_burst_loss_length);
77 config_state_.prob_start_bursting =
78 prob_loss / (1 - prob_loss) / avg_burst_loss_length;
Sebastian Janssonf96b1ca2018-08-07 16:58:0579 }
80}
81
Sebastian Jansson89eb0bb2020-03-13 16:47:3882void SimulatedNetwork::UpdateConfig(
83 std::function<void(BuiltInNetworkBehaviorConfig*)> config_modifier) {
Markus Handell8fe932a2020-07-06 15:41:3584 MutexLock lock(&config_lock_);
Sebastian Jansson89eb0bb2020-03-13 16:47:3885 config_modifier(&config_state_.config);
86}
87
Sebastian Janssonf96b1ca2018-08-07 16:58:0588void SimulatedNetwork::PauseTransmissionUntil(int64_t until_us) {
Markus Handell8fe932a2020-07-06 15:41:3589 MutexLock lock(&config_lock_);
Sebastian Janssoneceea312019-01-31 10:50:0490 config_state_.pause_transmission_until_us = until_us;
Sebastian Janssonf96b1ca2018-08-07 16:58:0591}
92
93bool SimulatedNetwork::EnqueuePacket(PacketInFlightInfo packet) {
Sebastian Janssoneceea312019-01-31 10:50:0494 RTC_DCHECK_RUNS_SERIALIZED(&process_checker_);
Mirko Bonadei248fdb12022-10-13 13:06:0895
96 // Check that old packets don't get enqueued, the SimulatedNetwork expect that
97 // the packets' send time is monotonically increasing. The tolerance for
98 // non-monotonic enqueue events is 0.5 ms because on multi core systems
99 // clock_gettime(CLOCK_MONOTONIC) can show non-monotonic behaviour between
100 // theads running on different cores.
101 // TODO(bugs.webrtc.org/14525): Open a bug on this with the goal to re-enable
102 // the DCHECK.
103 // At the moment, we see more than 130ms between non-monotonic events, which
104 // is more than expected.
105 // RTC_DCHECK_GE(packet.send_time_us - last_enqueue_time_us_, -2000);
106
Sebastian Janssoneceea312019-01-31 10:50:04107 ConfigState state = GetConfigState();
Christoffer Rodbro813c79b2019-01-31 08:25:12108
Mirko Bonadei248fdb12022-10-13 13:06:08109 // If the network config requires packet overhead, let's apply it as early as
110 // possible.
Sebastian Janssoneceea312019-01-31 10:50:04111 packet.size += state.config.packet_overhead;
112
Mirko Bonadei248fdb12022-10-13 13:06:08113 // If `queue_length_packets` is 0, the queue size is infinite.
Sebastian Janssoneceea312019-01-31 10:50:04114 if (state.config.queue_length_packets > 0 &&
115 capacity_link_.size() >= state.config.queue_length_packets) {
Sebastian Janssonf96b1ca2018-08-07 16:58:05116 // Too many packet on the link, drop this one.
117 return false;
118 }
Sebastian Jansson2cd3b4c2018-11-06 18:18:28119
Mirko Bonadei248fdb12022-10-13 13:06:08120 // If the packet has been sent before the previous packet in the network left
121 // the capacity queue, let's ensure the new packet will start its trip in the
122 // network after the last bit of the previous packet has left it.
123 int64_t packet_send_time_us = packet.send_time_us;
124 if (!capacity_link_.empty()) {
125 packet_send_time_us =
126 std::max(packet_send_time_us, capacity_link_.back().arrival_time_us);
127 }
128 capacity_link_.push({.packet = packet,
129 .arrival_time_us = CalculateArrivalTimeUs(
130 packet_send_time_us, packet.size * 8,
131 state.config.link_capacity_kbps)});
132
133 // Only update `next_process_time_us_` if not already set (if set, there is no
134 // way that a new packet will make the `next_process_time_us_` change).
Sebastian Jansson836fee12019-02-08 15:08:10135 if (!next_process_time_us_) {
Mirko Bonadei248fdb12022-10-13 13:06:08136 RTC_DCHECK_EQ(capacity_link_.size(), 1);
137 next_process_time_us_ = capacity_link_.front().arrival_time_us;
Sebastian Jansson836fee12019-02-08 15:08:10138 }
Sebastian Jansson2cd3b4c2018-11-06 18:18:28139
Mirko Bonadei248fdb12022-10-13 13:06:08140 last_enqueue_time_us_ = packet.send_time_us;
Sebastian Janssonf96b1ca2018-08-07 16:58:05141 return true;
142}
143
144absl::optional<int64_t> SimulatedNetwork::NextDeliveryTimeUs() const {
Sebastian Janssoneceea312019-01-31 10:50:04145 RTC_DCHECK_RUNS_SERIALIZED(&process_checker_);
Sebastian Jansson836fee12019-02-08 15:08:10146 return next_process_time_us_;
Sebastian Janssonf96b1ca2018-08-07 16:58:05147}
Christoffer Rodbro813c79b2019-01-31 08:25:12148
Sebastian Janssoneceea312019-01-31 10:50:04149void SimulatedNetwork::UpdateCapacityQueue(ConfigState state,
150 int64_t time_now_us) {
Mirko Bonadei248fdb12022-10-13 13:06:08151 // If there is at least one packet in the `capacity_link_`, let's update its
152 // arrival time to take into account changes in the network configuration
153 // since the last call to UpdateCapacityQueue.
154 if (!capacity_link_.empty()) {
155 capacity_link_.front().arrival_time_us = CalculateArrivalTimeUs(
156 std::max(capacity_link_.front().packet.send_time_us,
157 last_capacity_link_exit_time_),
158 capacity_link_.front().packet.size * 8,
159 state.config.link_capacity_kbps);
160 }
Christoffer Rodbro813c79b2019-01-31 08:25:12161
Mirko Bonadei248fdb12022-10-13 13:06:08162 // The capacity link is empty or the first packet is not expected to exit yet.
163 if (capacity_link_.empty() ||
164 time_now_us < capacity_link_.front().arrival_time_us) {
Sebastian Janssoneceea312019-01-31 10:50:04165 return;
Mirko Bonadei248fdb12022-10-13 13:06:08166 }
167 bool reorder_packets = false;
Christoffer Rodbro813c79b2019-01-31 08:25:12168
Mirko Bonadei248fdb12022-10-13 13:06:08169 do {
170 // Time to get this packet (the original or just updated arrival_time_us is
171 // smaller or equal to time_now_us).
Mirko Bonadei05cf6be2019-01-31 20:38:12172 PacketInfo packet = capacity_link_.front();
Sebastian Janssoneceea312019-01-31 10:50:04173 capacity_link_.pop();
174
Mirko Bonadei248fdb12022-10-13 13:06:08175 // If the network is paused, the pause will be implemented as an extra delay
176 // to be spent in the `delay_link_` queue.
177 if (state.pause_transmission_until_us > packet.arrival_time_us) {
178 packet.arrival_time_us = state.pause_transmission_until_us;
179 }
180
181 // Store the original arrival time, before applying packet loss or extra
182 // delay. This is needed to know when it is the first available time the
183 // next packet in the `capacity_link_` queue can start transmitting.
184 last_capacity_link_exit_time_ = packet.arrival_time_us;
Sebastian Janssoneceea312019-01-31 10:50:04185
Artem Titovcfea2182021-08-09 23:22:31186 // Drop packets at an average rate of `state.config.loss_percent` with
187 // and average loss burst length of `state.config.avg_burst_loss_length`.
Sebastian Janssoneceea312019-01-31 10:50:04188 if ((bursting_ && random_.Rand<double>() < state.prob_loss_bursting) ||
189 (!bursting_ && random_.Rand<double>() < state.prob_start_bursting)) {
190 bursting_ = true;
191 packet.arrival_time_us = PacketDeliveryInfo::kNotReceived;
192 } else {
Mirko Bonadei248fdb12022-10-13 13:06:08193 // If packets are not dropped, apply extra delay as configured.
Sebastian Janssoneceea312019-01-31 10:50:04194 bursting_ = false;
195 int64_t arrival_time_jitter_us = std::max(
196 random_.Gaussian(state.config.queue_delay_ms * 1000,
197 state.config.delay_standard_deviation_ms * 1000),
198 0.0);
199
200 // If reordering is not allowed then adjust arrival_time_jitter
201 // to make sure all packets are sent in order.
202 int64_t last_arrival_time_us =
203 delay_link_.empty() ? -1 : delay_link_.back().arrival_time_us;
204 if (!state.config.allow_reordering && !delay_link_.empty() &&
205 packet.arrival_time_us + arrival_time_jitter_us <
206 last_arrival_time_us) {
207 arrival_time_jitter_us = last_arrival_time_us - packet.arrival_time_us;
208 }
209 packet.arrival_time_us += arrival_time_jitter_us;
Mirko Bonadei248fdb12022-10-13 13:06:08210
211 // Optimization: Schedule a reorder only when a packet will exit before
212 // the one in front.
213 if (last_arrival_time_us > packet.arrival_time_us) {
214 reorder_packets = true;
Sebastian Janssoneceea312019-01-31 10:50:04215 }
216 }
Mirko Bonadei05cf6be2019-01-31 20:38:12217 delay_link_.emplace_back(packet);
Sebastian Janssoneceea312019-01-31 10:50:04218
Mirko Bonadei248fdb12022-10-13 13:06:08219 // If there are no packets in the queue, there is nothing else to do.
220 if (capacity_link_.empty()) {
221 break;
222 }
223 // If instead there is another packet in the `capacity_link_` queue, let's
224 // calculate its arrival_time_us based on the latest config (which might
225 // have been changed since it was enqueued).
226 int64_t next_start = std::max(last_capacity_link_exit_time_,
227 capacity_link_.front().packet.send_time_us);
228 capacity_link_.front().arrival_time_us = CalculateArrivalTimeUs(
229 next_start, capacity_link_.front().packet.size * 8,
230 state.config.link_capacity_kbps);
231 // And if the next packet in the queue needs to exit, let's dequeue it.
232 } while (capacity_link_.front().arrival_time_us <= time_now_us);
233
234 if (state.config.allow_reordering && reorder_packets) {
235 // Packets arrived out of order and since the network config allows
236 // reordering, let's sort them per arrival_time_us to make so they will also
237 // be delivered out of order.
238 std::stable_sort(delay_link_.begin(), delay_link_.end(),
239 [](const PacketInfo& p1, const PacketInfo& p2) {
240 return p1.arrival_time_us < p2.arrival_time_us;
241 });
Sebastian Janssoneceea312019-01-31 10:50:04242 }
243}
244
245SimulatedNetwork::ConfigState SimulatedNetwork::GetConfigState() const {
Markus Handell8fe932a2020-07-06 15:41:35246 MutexLock lock(&config_lock_);
Sebastian Janssoneceea312019-01-31 10:50:04247 return config_state_;
Sebastian Janssonf96b1ca2018-08-07 16:58:05248}
249
Christoffer Rodbro813c79b2019-01-31 08:25:12250std::vector<PacketDeliveryInfo> SimulatedNetwork::DequeueDeliverablePackets(
251 int64_t receive_time_us) {
Sebastian Janssoneceea312019-01-31 10:50:04252 RTC_DCHECK_RUNS_SERIALIZED(&process_checker_);
Mirko Bonadei248fdb12022-10-13 13:06:08253
Sebastian Janssoneceea312019-01-31 10:50:04254 UpdateCapacityQueue(GetConfigState(), receive_time_us);
Christoffer Rodbro813c79b2019-01-31 08:25:12255 std::vector<PacketDeliveryInfo> packets_to_deliver;
Mirko Bonadei248fdb12022-10-13 13:06:08256
Christoffer Rodbro813c79b2019-01-31 08:25:12257 // Check the extra delay queue.
258 while (!delay_link_.empty() &&
259 receive_time_us >= delay_link_.front().arrival_time_us) {
260 PacketInfo packet_info = delay_link_.front();
261 packets_to_deliver.emplace_back(
262 PacketDeliveryInfo(packet_info.packet, packet_info.arrival_time_us));
263 delay_link_.pop_front();
264 }
Sebastian Jansson836fee12019-02-08 15:08:10265
266 if (!delay_link_.empty()) {
267 next_process_time_us_ = delay_link_.front().arrival_time_us;
268 } else if (!capacity_link_.empty()) {
Mirko Bonadei248fdb12022-10-13 13:06:08269 next_process_time_us_ = capacity_link_.front().arrival_time_us;
Sebastian Jansson836fee12019-02-08 15:08:10270 } else {
271 next_process_time_us_.reset();
272 }
Christoffer Rodbro813c79b2019-01-31 08:25:12273 return packets_to_deliver;
274}
275
Sebastian Janssonf96b1ca2018-08-07 16:58:05276} // namespace webrtc