Sebastian Jansson | f96b1ca | 2018-08-07 16:58:05 | [diff] [blame] | 1 | /* |
| 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 Bonadei | 248fdb1 | 2022-10-13 13:06:08 | [diff] [blame] | 15 | #include <cstdint> |
Sebastian Jansson | f96b1ca | 2018-08-07 16:58:05 | [diff] [blame] | 16 | #include <utility> |
Yves Gerey | 3e70781 | 2018-11-28 15:47:49 | [diff] [blame] | 17 | |
Sebastian Jansson | 2cd3b4c | 2018-11-06 18:18:28 | [diff] [blame] | 18 | #include "api/units/data_rate.h" |
Yves Gerey | 3e70781 | 2018-11-28 15:47:49 | [diff] [blame] | 19 | #include "api/units/data_size.h" |
| 20 | #include "api/units/time_delta.h" |
| 21 | #include "rtc_base/checks.h" |
Sebastian Jansson | f96b1ca | 2018-08-07 16:58:05 | [diff] [blame] | 22 | |
| 23 | namespace webrtc { |
Sebastian Jansson | 836fee1 | 2019-02-08 15:08:10 | [diff] [blame] | 24 | namespace { |
Mirko Bonadei | 248fdb1 | 2022-10-13 13:06:08 | [diff] [blame] | 25 | |
| 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`. |
| 29 | int64_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 Jansson | 2b08e31 | 2019-02-25 09:24:46 | [diff] [blame] | 45 | } // namespace |
| 46 | |
Sebastian Jansson | cec2433 | 2019-12-04 13:26:50 | [diff] [blame] | 47 | SimulatedNetwork::SimulatedNetwork(Config config, uint64_t random_seed) |
Mirko Bonadei | 248fdb1 | 2022-10-13 13:06:08 | [diff] [blame] | 48 | : random_(random_seed), |
| 49 | bursting_(false), |
| 50 | last_enqueue_time_us_(0), |
| 51 | last_capacity_link_exit_time_(0) { |
Sebastian Jansson | f96b1ca | 2018-08-07 16:58:05 | [diff] [blame] | 52 | SetConfig(config); |
| 53 | } |
| 54 | |
| 55 | SimulatedNetwork::~SimulatedNetwork() = default; |
| 56 | |
Sebastian Jansson | cec2433 | 2019-12-04 13:26:50 | [diff] [blame] | 57 | void SimulatedNetwork::SetConfig(const Config& config) { |
Markus Handell | 8fe932a | 2020-07-06 15:41:35 | [diff] [blame] | 58 | MutexLock lock(&config_lock_); |
Sebastian Jansson | eceea31 | 2019-01-31 10:50:04 | [diff] [blame] | 59 | config_state_.config = config; // Shallow copy of the struct. |
Sebastian Jansson | f96b1ca | 2018-08-07 16:58:05 | [diff] [blame] | 60 | double prob_loss = config.loss_percent / 100.0; |
Sebastian Jansson | eceea31 | 2019-01-31 10:50:04 | [diff] [blame] | 61 | if (config_state_.config.avg_burst_loss_length == -1) { |
Sebastian Jansson | f96b1ca | 2018-08-07 16:58:05 | [diff] [blame] | 62 | // Uniform loss |
Sebastian Jansson | eceea31 | 2019-01-31 10:50:04 | [diff] [blame] | 63 | config_state_.prob_loss_bursting = prob_loss; |
| 64 | config_state_.prob_start_bursting = prob_loss; |
Sebastian Jansson | f96b1ca | 2018-08-07 16:58:05 | [diff] [blame] | 65 | } 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 Olsson | b2b2031 | 2020-01-14 11:11:31 | [diff] [blame] | 71 | << "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 Jansson | f96b1ca | 2018-08-07 16:58:05 | [diff] [blame] | 75 | |
Sebastian Jansson | eceea31 | 2019-01-31 10:50:04 | [diff] [blame] | 76 | 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 Jansson | f96b1ca | 2018-08-07 16:58:05 | [diff] [blame] | 79 | } |
| 80 | } |
| 81 | |
Sebastian Jansson | 89eb0bb | 2020-03-13 16:47:38 | [diff] [blame] | 82 | void SimulatedNetwork::UpdateConfig( |
| 83 | std::function<void(BuiltInNetworkBehaviorConfig*)> config_modifier) { |
Markus Handell | 8fe932a | 2020-07-06 15:41:35 | [diff] [blame] | 84 | MutexLock lock(&config_lock_); |
Sebastian Jansson | 89eb0bb | 2020-03-13 16:47:38 | [diff] [blame] | 85 | config_modifier(&config_state_.config); |
| 86 | } |
| 87 | |
Sebastian Jansson | f96b1ca | 2018-08-07 16:58:05 | [diff] [blame] | 88 | void SimulatedNetwork::PauseTransmissionUntil(int64_t until_us) { |
Markus Handell | 8fe932a | 2020-07-06 15:41:35 | [diff] [blame] | 89 | MutexLock lock(&config_lock_); |
Sebastian Jansson | eceea31 | 2019-01-31 10:50:04 | [diff] [blame] | 90 | config_state_.pause_transmission_until_us = until_us; |
Sebastian Jansson | f96b1ca | 2018-08-07 16:58:05 | [diff] [blame] | 91 | } |
| 92 | |
| 93 | bool SimulatedNetwork::EnqueuePacket(PacketInFlightInfo packet) { |
Sebastian Jansson | eceea31 | 2019-01-31 10:50:04 | [diff] [blame] | 94 | RTC_DCHECK_RUNS_SERIALIZED(&process_checker_); |
Mirko Bonadei | 248fdb1 | 2022-10-13 13:06:08 | [diff] [blame] | 95 | |
| 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 Jansson | eceea31 | 2019-01-31 10:50:04 | [diff] [blame] | 107 | ConfigState state = GetConfigState(); |
Christoffer Rodbro | 813c79b | 2019-01-31 08:25:12 | [diff] [blame] | 108 | |
Mirko Bonadei | 248fdb1 | 2022-10-13 13:06:08 | [diff] [blame] | 109 | // If the network config requires packet overhead, let's apply it as early as |
| 110 | // possible. |
Sebastian Jansson | eceea31 | 2019-01-31 10:50:04 | [diff] [blame] | 111 | packet.size += state.config.packet_overhead; |
| 112 | |
Mirko Bonadei | 248fdb1 | 2022-10-13 13:06:08 | [diff] [blame] | 113 | // If `queue_length_packets` is 0, the queue size is infinite. |
Sebastian Jansson | eceea31 | 2019-01-31 10:50:04 | [diff] [blame] | 114 | if (state.config.queue_length_packets > 0 && |
| 115 | capacity_link_.size() >= state.config.queue_length_packets) { |
Sebastian Jansson | f96b1ca | 2018-08-07 16:58:05 | [diff] [blame] | 116 | // Too many packet on the link, drop this one. |
| 117 | return false; |
| 118 | } |
Sebastian Jansson | 2cd3b4c | 2018-11-06 18:18:28 | [diff] [blame] | 119 | |
Mirko Bonadei | 248fdb1 | 2022-10-13 13:06:08 | [diff] [blame] | 120 | // 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 Jansson | 836fee1 | 2019-02-08 15:08:10 | [diff] [blame] | 135 | if (!next_process_time_us_) { |
Mirko Bonadei | 248fdb1 | 2022-10-13 13:06:08 | [diff] [blame] | 136 | RTC_DCHECK_EQ(capacity_link_.size(), 1); |
| 137 | next_process_time_us_ = capacity_link_.front().arrival_time_us; |
Sebastian Jansson | 836fee1 | 2019-02-08 15:08:10 | [diff] [blame] | 138 | } |
Sebastian Jansson | 2cd3b4c | 2018-11-06 18:18:28 | [diff] [blame] | 139 | |
Mirko Bonadei | 248fdb1 | 2022-10-13 13:06:08 | [diff] [blame] | 140 | last_enqueue_time_us_ = packet.send_time_us; |
Sebastian Jansson | f96b1ca | 2018-08-07 16:58:05 | [diff] [blame] | 141 | return true; |
| 142 | } |
| 143 | |
| 144 | absl::optional<int64_t> SimulatedNetwork::NextDeliveryTimeUs() const { |
Sebastian Jansson | eceea31 | 2019-01-31 10:50:04 | [diff] [blame] | 145 | RTC_DCHECK_RUNS_SERIALIZED(&process_checker_); |
Sebastian Jansson | 836fee1 | 2019-02-08 15:08:10 | [diff] [blame] | 146 | return next_process_time_us_; |
Sebastian Jansson | f96b1ca | 2018-08-07 16:58:05 | [diff] [blame] | 147 | } |
Christoffer Rodbro | 813c79b | 2019-01-31 08:25:12 | [diff] [blame] | 148 | |
Sebastian Jansson | eceea31 | 2019-01-31 10:50:04 | [diff] [blame] | 149 | void SimulatedNetwork::UpdateCapacityQueue(ConfigState state, |
| 150 | int64_t time_now_us) { |
Mirko Bonadei | 248fdb1 | 2022-10-13 13:06:08 | [diff] [blame] | 151 | // 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 Rodbro | 813c79b | 2019-01-31 08:25:12 | [diff] [blame] | 161 | |
Mirko Bonadei | 248fdb1 | 2022-10-13 13:06:08 | [diff] [blame] | 162 | // 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 Jansson | eceea31 | 2019-01-31 10:50:04 | [diff] [blame] | 165 | return; |
Mirko Bonadei | 248fdb1 | 2022-10-13 13:06:08 | [diff] [blame] | 166 | } |
| 167 | bool reorder_packets = false; |
Christoffer Rodbro | 813c79b | 2019-01-31 08:25:12 | [diff] [blame] | 168 | |
Mirko Bonadei | 248fdb1 | 2022-10-13 13:06:08 | [diff] [blame] | 169 | 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 Bonadei | 05cf6be | 2019-01-31 20:38:12 | [diff] [blame] | 172 | PacketInfo packet = capacity_link_.front(); |
Sebastian Jansson | eceea31 | 2019-01-31 10:50:04 | [diff] [blame] | 173 | capacity_link_.pop(); |
| 174 | |
Mirko Bonadei | 248fdb1 | 2022-10-13 13:06:08 | [diff] [blame] | 175 | // 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 Jansson | eceea31 | 2019-01-31 10:50:04 | [diff] [blame] | 185 | |
Artem Titov | cfea218 | 2021-08-09 23:22:31 | [diff] [blame] | 186 | // 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 Jansson | eceea31 | 2019-01-31 10:50:04 | [diff] [blame] | 188 | 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 Bonadei | 248fdb1 | 2022-10-13 13:06:08 | [diff] [blame] | 193 | // If packets are not dropped, apply extra delay as configured. |
Sebastian Jansson | eceea31 | 2019-01-31 10:50:04 | [diff] [blame] | 194 | 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 Bonadei | 248fdb1 | 2022-10-13 13:06:08 | [diff] [blame] | 210 | |
| 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 Jansson | eceea31 | 2019-01-31 10:50:04 | [diff] [blame] | 215 | } |
| 216 | } |
Mirko Bonadei | 05cf6be | 2019-01-31 20:38:12 | [diff] [blame] | 217 | delay_link_.emplace_back(packet); |
Sebastian Jansson | eceea31 | 2019-01-31 10:50:04 | [diff] [blame] | 218 | |
Mirko Bonadei | 248fdb1 | 2022-10-13 13:06:08 | [diff] [blame] | 219 | // 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 Jansson | eceea31 | 2019-01-31 10:50:04 | [diff] [blame] | 242 | } |
| 243 | } |
| 244 | |
| 245 | SimulatedNetwork::ConfigState SimulatedNetwork::GetConfigState() const { |
Markus Handell | 8fe932a | 2020-07-06 15:41:35 | [diff] [blame] | 246 | MutexLock lock(&config_lock_); |
Sebastian Jansson | eceea31 | 2019-01-31 10:50:04 | [diff] [blame] | 247 | return config_state_; |
Sebastian Jansson | f96b1ca | 2018-08-07 16:58:05 | [diff] [blame] | 248 | } |
| 249 | |
Christoffer Rodbro | 813c79b | 2019-01-31 08:25:12 | [diff] [blame] | 250 | std::vector<PacketDeliveryInfo> SimulatedNetwork::DequeueDeliverablePackets( |
| 251 | int64_t receive_time_us) { |
Sebastian Jansson | eceea31 | 2019-01-31 10:50:04 | [diff] [blame] | 252 | RTC_DCHECK_RUNS_SERIALIZED(&process_checker_); |
Mirko Bonadei | 248fdb1 | 2022-10-13 13:06:08 | [diff] [blame] | 253 | |
Sebastian Jansson | eceea31 | 2019-01-31 10:50:04 | [diff] [blame] | 254 | UpdateCapacityQueue(GetConfigState(), receive_time_us); |
Christoffer Rodbro | 813c79b | 2019-01-31 08:25:12 | [diff] [blame] | 255 | std::vector<PacketDeliveryInfo> packets_to_deliver; |
Mirko Bonadei | 248fdb1 | 2022-10-13 13:06:08 | [diff] [blame] | 256 | |
Christoffer Rodbro | 813c79b | 2019-01-31 08:25:12 | [diff] [blame] | 257 | // 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 Jansson | 836fee1 | 2019-02-08 15:08:10 | [diff] [blame] | 265 | |
| 266 | if (!delay_link_.empty()) { |
| 267 | next_process_time_us_ = delay_link_.front().arrival_time_us; |
| 268 | } else if (!capacity_link_.empty()) { |
Mirko Bonadei | 248fdb1 | 2022-10-13 13:06:08 | [diff] [blame] | 269 | next_process_time_us_ = capacity_link_.front().arrival_time_us; |
Sebastian Jansson | 836fee1 | 2019-02-08 15:08:10 | [diff] [blame] | 270 | } else { |
| 271 | next_process_time_us_.reset(); |
| 272 | } |
Christoffer Rodbro | 813c79b | 2019-01-31 08:25:12 | [diff] [blame] | 273 | return packets_to_deliver; |
| 274 | } |
| 275 | |
Sebastian Jansson | f96b1ca | 2018-08-07 16:58:05 | [diff] [blame] | 276 | } // namespace webrtc |