blob: d6a7369ebe4a573faadf00d2b495dcbce090ac95 [file] [log] [blame]
Sebastian Janssonf96b1ca2018-08-07 18:58:05 +02001/*
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>
15#include <utility>
Yves Gerey3e707812018-11-28 16:47:49 +010016
Sebastian Jansson2cd3b4c2018-11-06 19:18:28 +010017#include "api/units/data_rate.h"
Yves Gerey3e707812018-11-28 16:47:49 +010018#include "api/units/data_size.h"
19#include "api/units/time_delta.h"
20#include "rtc_base/checks.h"
Sebastian Janssonf96b1ca2018-08-07 18:58:05 +020021
22namespace webrtc {
Sebastian Jansson836fee12019-02-08 16:08:10 +010023namespace {
Sebastian Jansson2b08e312019-02-25 10:24:46 +010024constexpr TimeDelta kDefaultProcessDelay = TimeDelta::Millis<5>();
25} // namespace
26
27CoDelSimulation::CoDelSimulation() = default;
28CoDelSimulation::~CoDelSimulation() = default;
29
30bool CoDelSimulation::DropDequeuedPacket(Timestamp now,
31 Timestamp enqueing_time,
32 DataSize packet_size,
33 DataSize queue_size) {
34 constexpr TimeDelta kWindow = TimeDelta::Millis<100>();
35 constexpr TimeDelta kDelayThreshold = TimeDelta::Millis<5>();
36 constexpr TimeDelta kDropCountMemory = TimeDelta::Millis<1600>();
37 constexpr DataSize kMaxPacketSize = DataSize::Bytes<1500>();
38
39 // Compensates for process interval in simulation; not part of standard CoDel.
40 TimeDelta queuing_time = now - enqueing_time - kDefaultProcessDelay;
41
42 if (queue_size < kMaxPacketSize || queuing_time < kDelayThreshold) {
43 enter_drop_state_at_ = Timestamp::PlusInfinity();
44 state_ = kNormal;
45 return false;
46 }
47 switch (state_) {
48 case kNormal:
49 enter_drop_state_at_ = now + kWindow;
50 state_ = kPending;
51 return false;
52
53 case kPending:
54 if (now >= enter_drop_state_at_) {
55 state_ = kDropping;
56 // Starting the drop counter with the drops made during the most recent
57 // drop state period.
58 drop_count_ = drop_count_ - previous_drop_count_;
59 if (now >= last_drop_at_ + kDropCountMemory)
60 drop_count_ = 0;
61 previous_drop_count_ = drop_count_;
62 last_drop_at_ = now;
63 ++drop_count_;
64 return true;
65 }
66 return false;
67
68 case kDropping:
69 TimeDelta drop_delay = kWindow / sqrt(static_cast<double>(drop_count_));
70 Timestamp next_drop_at = last_drop_at_ + drop_delay;
71 if (now >= next_drop_at) {
72 if (queue_size - packet_size < kMaxPacketSize)
73 state_ = kPending;
74 last_drop_at_ = next_drop_at;
75 ++drop_count_;
76 return true;
77 }
78 return false;
79 }
Sebastian Jansson836fee12019-02-08 16:08:10 +010080}
Sebastian Janssonf96b1ca2018-08-07 18:58:05 +020081
Sebastian Janssoncec24332019-12-04 14:26:50 +010082SimulatedNetwork::SimulatedNetwork(Config config, uint64_t random_seed)
Sebastian Janssonf96b1ca2018-08-07 18:58:05 +020083 : random_(random_seed), bursting_(false) {
84 SetConfig(config);
85}
86
87SimulatedNetwork::~SimulatedNetwork() = default;
88
Sebastian Janssoncec24332019-12-04 14:26:50 +010089void SimulatedNetwork::SetConfig(const Config& config) {
Sebastian Janssonf96b1ca2018-08-07 18:58:05 +020090 rtc::CritScope crit(&config_lock_);
Sebastian Janssoneceea312019-01-31 11:50:04 +010091 config_state_.config = config; // Shallow copy of the struct.
Sebastian Janssonf96b1ca2018-08-07 18:58:05 +020092 double prob_loss = config.loss_percent / 100.0;
Sebastian Janssoneceea312019-01-31 11:50:04 +010093 if (config_state_.config.avg_burst_loss_length == -1) {
Sebastian Janssonf96b1ca2018-08-07 18:58:05 +020094 // Uniform loss
Sebastian Janssoneceea312019-01-31 11:50:04 +010095 config_state_.prob_loss_bursting = prob_loss;
96 config_state_.prob_start_bursting = prob_loss;
Sebastian Janssonf96b1ca2018-08-07 18:58:05 +020097 } else {
98 // Lose packets according to a gilbert-elliot model.
99 int avg_burst_loss_length = config.avg_burst_loss_length;
100 int min_avg_burst_loss_length = std::ceil(prob_loss / (1 - prob_loss));
101
102 RTC_CHECK_GT(avg_burst_loss_length, min_avg_burst_loss_length)
103 << "For a total packet loss of " << config.loss_percent << "%% then"
104 << " avg_burst_loss_length must be " << min_avg_burst_loss_length + 1
105 << " or higher.";
106
Sebastian Janssoneceea312019-01-31 11:50:04 +0100107 config_state_.prob_loss_bursting = (1.0 - 1.0 / avg_burst_loss_length);
108 config_state_.prob_start_bursting =
109 prob_loss / (1 - prob_loss) / avg_burst_loss_length;
Sebastian Janssonf96b1ca2018-08-07 18:58:05 +0200110 }
111}
112
113void SimulatedNetwork::PauseTransmissionUntil(int64_t until_us) {
114 rtc::CritScope crit(&config_lock_);
Sebastian Janssoneceea312019-01-31 11:50:04 +0100115 config_state_.pause_transmission_until_us = until_us;
Sebastian Janssonf96b1ca2018-08-07 18:58:05 +0200116}
117
118bool SimulatedNetwork::EnqueuePacket(PacketInFlightInfo packet) {
Sebastian Janssoneceea312019-01-31 11:50:04 +0100119 RTC_DCHECK_RUNS_SERIALIZED(&process_checker_);
120 ConfigState state = GetConfigState();
Christoffer Rodbro813c79b2019-01-31 09:25:12 +0100121
Sebastian Janssoneceea312019-01-31 11:50:04 +0100122 UpdateCapacityQueue(state, packet.send_time_us);
Christoffer Rodbro813c79b2019-01-31 09:25:12 +0100123
Sebastian Janssoneceea312019-01-31 11:50:04 +0100124 packet.size += state.config.packet_overhead;
125
126 if (state.config.queue_length_packets > 0 &&
127 capacity_link_.size() >= state.config.queue_length_packets) {
Sebastian Janssonf96b1ca2018-08-07 18:58:05 +0200128 // Too many packet on the link, drop this one.
129 return false;
130 }
Sebastian Jansson2cd3b4c2018-11-06 19:18:28 +0100131
Christoffer Rodbro813c79b2019-01-31 09:25:12 +0100132 // Set arrival time = send time for now; actual arrival time will be
133 // calculated in UpdateCapacityQueue.
134 queue_size_bytes_ += packet.size;
135 capacity_link_.push({packet, packet.send_time_us});
Sebastian Jansson836fee12019-02-08 16:08:10 +0100136 if (!next_process_time_us_) {
Sebastian Jansson2b08e312019-02-25 10:24:46 +0100137 next_process_time_us_ = packet.send_time_us + kDefaultProcessDelay.us();
Sebastian Jansson836fee12019-02-08 16:08:10 +0100138 }
Sebastian Jansson2cd3b4c2018-11-06 19:18:28 +0100139
Sebastian Janssonf96b1ca2018-08-07 18:58:05 +0200140 return true;
141}
142
143absl::optional<int64_t> SimulatedNetwork::NextDeliveryTimeUs() const {
Sebastian Janssoneceea312019-01-31 11:50:04 +0100144 RTC_DCHECK_RUNS_SERIALIZED(&process_checker_);
Sebastian Jansson836fee12019-02-08 16:08:10 +0100145 return next_process_time_us_;
Sebastian Janssonf96b1ca2018-08-07 18:58:05 +0200146}
Christoffer Rodbro813c79b2019-01-31 09:25:12 +0100147
Sebastian Janssoneceea312019-01-31 11:50:04 +0100148void SimulatedNetwork::UpdateCapacityQueue(ConfigState state,
149 int64_t time_now_us) {
150 bool needs_sort = false;
Christoffer Rodbro813c79b2019-01-31 09:25:12 +0100151
Sebastian Janssoneceea312019-01-31 11:50:04 +0100152 // Catch for thread races.
153 if (time_now_us < last_capacity_link_visit_us_.value_or(time_now_us))
154 return;
Christoffer Rodbro813c79b2019-01-31 09:25:12 +0100155
Sebastian Janssoneceea312019-01-31 11:50:04 +0100156 int64_t time_us = last_capacity_link_visit_us_.value_or(time_now_us);
157 // Check the capacity link first.
158 while (!capacity_link_.empty()) {
159 int64_t time_until_front_exits_us = 0;
160 if (state.config.link_capacity_kbps > 0) {
161 int64_t remaining_bits =
162 capacity_link_.front().packet.size * 8 - pending_drain_bits_;
163 RTC_DCHECK(remaining_bits > 0);
164 // Division rounded up - packet not delivered until its last bit is.
165 time_until_front_exits_us =
166 (1000 * remaining_bits + state.config.link_capacity_kbps - 1) /
167 state.config.link_capacity_kbps;
Sebastian Janssonf96b1ca2018-08-07 18:58:05 +0200168 }
169
Sebastian Janssoneceea312019-01-31 11:50:04 +0100170 if (time_us + time_until_front_exits_us > time_now_us) {
171 // Packet at front will not exit yet. Will not enter here on infinite
172 // capacity(=0) so no special handling needed.
173 pending_drain_bits_ +=
174 ((time_now_us - time_us) * state.config.link_capacity_kbps) / 1000;
175 break;
Sebastian Janssonf96b1ca2018-08-07 18:58:05 +0200176 }
Sebastian Janssoneceea312019-01-31 11:50:04 +0100177 if (state.config.link_capacity_kbps > 0) {
178 pending_drain_bits_ +=
179 (time_until_front_exits_us * state.config.link_capacity_kbps) / 1000;
180 } else {
181 // Enough to drain the whole queue.
182 pending_drain_bits_ = queue_size_bytes_ * 8;
183 }
184
185 // Time to get this packet.
Mirko Bonadei05cf6be2019-01-31 21:38:12 +0100186 PacketInfo packet = capacity_link_.front();
Sebastian Janssoneceea312019-01-31 11:50:04 +0100187 capacity_link_.pop();
188
189 time_us += time_until_front_exits_us;
Sebastian Jansson2b08e312019-02-25 10:24:46 +0100190 if (state.config.codel_active_queue_management) {
191 while (!capacity_link_.empty() &&
192 codel_controller_.DropDequeuedPacket(
193 Timestamp::us(time_us),
194 Timestamp::us(capacity_link_.front().packet.send_time_us),
195 DataSize::bytes(capacity_link_.front().packet.size),
196 DataSize::bytes(queue_size_bytes_))) {
197 PacketInfo dropped = capacity_link_.front();
198 capacity_link_.pop();
199 queue_size_bytes_ -= dropped.packet.size;
200 dropped.arrival_time_us = PacketDeliveryInfo::kNotReceived;
201 delay_link_.emplace_back(dropped);
202 }
203 }
Sebastian Janssoneceea312019-01-31 11:50:04 +0100204 RTC_DCHECK(time_us >= packet.packet.send_time_us);
205 packet.arrival_time_us =
206 std::max(state.pause_transmission_until_us, time_us);
207 queue_size_bytes_ -= packet.packet.size;
208 pending_drain_bits_ -= packet.packet.size * 8;
209 RTC_DCHECK(pending_drain_bits_ >= 0);
210
211 // Drop packets at an average rate of |state.config.loss_percent| with
212 // and average loss burst length of |state.config.avg_burst_loss_length|.
213 if ((bursting_ && random_.Rand<double>() < state.prob_loss_bursting) ||
214 (!bursting_ && random_.Rand<double>() < state.prob_start_bursting)) {
215 bursting_ = true;
216 packet.arrival_time_us = PacketDeliveryInfo::kNotReceived;
217 } else {
218 bursting_ = false;
219 int64_t arrival_time_jitter_us = std::max(
220 random_.Gaussian(state.config.queue_delay_ms * 1000,
221 state.config.delay_standard_deviation_ms * 1000),
222 0.0);
223
224 // If reordering is not allowed then adjust arrival_time_jitter
225 // to make sure all packets are sent in order.
226 int64_t last_arrival_time_us =
227 delay_link_.empty() ? -1 : delay_link_.back().arrival_time_us;
228 if (!state.config.allow_reordering && !delay_link_.empty() &&
229 packet.arrival_time_us + arrival_time_jitter_us <
230 last_arrival_time_us) {
231 arrival_time_jitter_us = last_arrival_time_us - packet.arrival_time_us;
232 }
233 packet.arrival_time_us += arrival_time_jitter_us;
234 if (packet.arrival_time_us >= last_arrival_time_us) {
235 last_arrival_time_us = packet.arrival_time_us;
236 } else {
237 needs_sort = true;
238 }
239 }
Mirko Bonadei05cf6be2019-01-31 21:38:12 +0100240 delay_link_.emplace_back(packet);
Sebastian Janssonf96b1ca2018-08-07 18:58:05 +0200241 }
Sebastian Janssoneceea312019-01-31 11:50:04 +0100242 last_capacity_link_visit_us_ = time_now_us;
243 // Cannot save unused capacity for later.
244 pending_drain_bits_ = std::min(pending_drain_bits_, queue_size_bytes_ * 8);
245
246 if (needs_sort) {
247 // Packet(s) arrived out of order, make sure list is sorted.
248 std::sort(delay_link_.begin(), delay_link_.end(),
249 [](const PacketInfo& p1, const PacketInfo& p2) {
250 return p1.arrival_time_us < p2.arrival_time_us;
251 });
252 }
253}
254
255SimulatedNetwork::ConfigState SimulatedNetwork::GetConfigState() const {
256 rtc::CritScope crit(&config_lock_);
257 return config_state_;
Sebastian Janssonf96b1ca2018-08-07 18:58:05 +0200258}
259
Christoffer Rodbro813c79b2019-01-31 09:25:12 +0100260std::vector<PacketDeliveryInfo> SimulatedNetwork::DequeueDeliverablePackets(
261 int64_t receive_time_us) {
Sebastian Janssoneceea312019-01-31 11:50:04 +0100262 RTC_DCHECK_RUNS_SERIALIZED(&process_checker_);
263 UpdateCapacityQueue(GetConfigState(), receive_time_us);
Christoffer Rodbro813c79b2019-01-31 09:25:12 +0100264 std::vector<PacketDeliveryInfo> packets_to_deliver;
265 // Check the extra delay queue.
266 while (!delay_link_.empty() &&
267 receive_time_us >= delay_link_.front().arrival_time_us) {
268 PacketInfo packet_info = delay_link_.front();
269 packets_to_deliver.emplace_back(
270 PacketDeliveryInfo(packet_info.packet, packet_info.arrival_time_us));
271 delay_link_.pop_front();
272 }
Sebastian Jansson836fee12019-02-08 16:08:10 +0100273
274 if (!delay_link_.empty()) {
275 next_process_time_us_ = delay_link_.front().arrival_time_us;
276 } else if (!capacity_link_.empty()) {
Sebastian Jansson2b08e312019-02-25 10:24:46 +0100277 next_process_time_us_ = receive_time_us + kDefaultProcessDelay.us();
Sebastian Jansson836fee12019-02-08 16:08:10 +0100278 } else {
279 next_process_time_us_.reset();
280 }
Christoffer Rodbro813c79b2019-01-31 09:25:12 +0100281 return packets_to_deliver;
282}
283
Sebastian Janssonf96b1ca2018-08-07 18:58:05 +0200284} // namespace webrtc