Debian Codegraph @

third_party/rust/neqo-transport/src/cc/tests/cubic.rs

raw
1 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
2 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
3 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
4 // option. This file may not be copied, modified, or distributed
5 // except according to those terms.
6
7 #![expect(
8 clippy::cast_possible_truncation,
9 clippy::cast_sign_loss,
10 reason = "OK in tests."
11 )]
12
13 use std::{
14 ops::Sub,
15 time::{Duration, Instant},
16 };
17
18 use test_fixture::now;
19
20 use super::{IP_ADDR, MTU, RTT};
21 use crate::{
22 cc::{
23 classic_cc::ClassicCongestionControl,
24 cubic::{
25 convert_to_f64, Cubic, CUBIC_ALPHA, CUBIC_BETA_USIZE_DIVIDEND,
26 CUBIC_BETA_USIZE_DIVISOR, CUBIC_C, CUBIC_FAST_CONVERGENCE,
27 },
28 CongestionControl as _,
29 },
30 packet::PacketType,
31 pmtud::Pmtud,
32 recovery::SentPacket,
33 rtt::RttEstimate,
34 };
35
36 const fn cwnd_after_loss(cwnd: usize) -> usize {
37 cwnd * CUBIC_BETA_USIZE_DIVIDEND / CUBIC_BETA_USIZE_DIVISOR
38 }
39
40 const fn cwnd_after_loss_slow_start(cwnd: usize, mtu: usize) -> usize {
41 (cwnd + mtu) * CUBIC_BETA_USIZE_DIVIDEND / CUBIC_BETA_USIZE_DIVISOR
42 }
43
44 fn fill_cwnd(cc: &mut ClassicCongestionControl<Cubic>, mut next_pn: u64, now: Instant) -> u64 {
45 while cc.bytes_in_flight() < cc.cwnd() {
46 let sent = SentPacket::new(
47 PacketType::Short,
48 next_pn,
49 now,
50 true,
51 Vec::new(),
52 cc.max_datagram_size(),
53 );
54 cc.on_packet_sent(&sent, now);
55 next_pn += 1;
56 }
57 next_pn
58 }
59
60 fn ack_packet(cc: &mut ClassicCongestionControl<Cubic>, pn: u64, now: Instant) {
61 let acked = SentPacket::new(
62 PacketType::Short,
63 pn,
64 now,
65 true,
66 Vec::new(),
67 cc.max_datagram_size(),
68 );
69 cc.on_packets_acked(&[acked], &RttEstimate::from_duration(RTT), now);
70 }
71
72 fn packet_lost(cc: &mut ClassicCongestionControl<Cubic>, pn: u64) {
73 const PTO: Duration = Duration::from_millis(120);
74 let p_lost = SentPacket::new(
75 PacketType::Short,
76 pn,
77 now(),
78 true,
79 Vec::new(),
80 cc.max_datagram_size(),
81 );
82 cc.on_packets_lost(None, None, PTO, &[p_lost], now());
83 }
84
85 fn expected_tcp_acks(cwnd_rtt_start: usize, mtu: usize) -> u64 {
86 (f64::from(i32::try_from(cwnd_rtt_start).unwrap())
87 / f64::from(i32::try_from(mtu).unwrap())
88 / CUBIC_ALPHA)
89 .round() as u64
90 }
91
92 #[test]
93 fn tcp_phase() {
94 let mut cubic = ClassicCongestionControl::new(Cubic::default(), Pmtud::new(IP_ADDR, MTU));
95
96 // change to congestion avoidance state.
97 cubic.set_ssthresh(1);
98
99 let mut now = now();
100 let start_time = now;
101 // helper variables to remember the next packet number to be sent/acked.
102 let mut next_pn_send = 0;
103 let mut next_pn_ack = 0;
104
105 next_pn_send = fill_cwnd(&mut cubic, next_pn_send, now);
106
107 // This will start with TCP phase.
108 // in this phase cwnd is increase by CUBIC_ALPHA every RTT. We can look at it as
109 // increase of MAX_DATAGRAM_SIZE every 1 / CUBIC_ALPHA RTTs.
110 // The phase will end when cwnd calculated with cubic equation is equal to TCP estimate:
111 // CUBIC_C * (n * RTT / CUBIC_ALPHA)^3 * MAX_DATAGRAM_SIZE = n * MAX_DATAGRAM_SIZE
112 // from this n = sqrt(CUBIC_ALPHA^3/ (CUBIC_C * RTT^3)).
113 let num_tcp_increases = (CUBIC_ALPHA.powi(3) / (CUBIC_C * RTT.as_secs_f64().powi(3)))
114 .sqrt()
115 .floor() as u64;
116
117 for _ in 0..num_tcp_increases {
118 let cwnd_rtt_start = cubic.cwnd();
119 // Expected acks during a period of RTT / CUBIC_ALPHA.
120 let acks = expected_tcp_acks(cwnd_rtt_start, cubic.max_datagram_size());
121 // The time between acks if they are ideally paced over a RTT.
122 let time_increase =
123 RTT / u32::try_from(cwnd_rtt_start / cubic.max_datagram_size()).unwrap();
124
125 for _ in 0..acks {
126 now += time_increase;
127 ack_packet(&mut cubic, next_pn_ack, now);
128 next_pn_ack += 1;
129 next_pn_send = fill_cwnd(&mut cubic, next_pn_send, now);
130 }
131
132 assert_eq!(cubic.cwnd() - cwnd_rtt_start, cubic.max_datagram_size());
133 }
134
135 // The next increase will be according to the cubic equation.
136
137 let cwnd_rtt_start = cubic.cwnd();
138 // cwnd_rtt_start has change, therefore calculate new time_increase (the time
139 // between acks if they are ideally paced over a RTT).
140 let time_increase = RTT / u32::try_from(cwnd_rtt_start / cubic.max_datagram_size()).unwrap();
141 let mut num_acks = 0; // count the number of acks. until cwnd is increased by cubic.max_datagram_size().
142
143 while cwnd_rtt_start == cubic.cwnd() {
144 num_acks += 1;
145 now += time_increase;
146 ack_packet(&mut cubic, next_pn_ack, now);
147 next_pn_ack += 1;
148 next_pn_send = fill_cwnd(&mut cubic, next_pn_send, now);
149 }
150
151 // Make sure that the increase is not according to TCP equation, i.e., that it took
152 // less than RTT / CUBIC_ALPHA.
153 let expected_ack_tcp_increase = expected_tcp_acks(cwnd_rtt_start, cubic.max_datagram_size());
154 assert!(num_acks < expected_ack_tcp_increase);
155
156 // This first increase after a TCP phase may be shorter than what it would take by a regular
157 // cubic phase, because of the proper byte counting and the credit it already had before
158 // entering this phase. Therefore We will perform another round and compare it to expected
159 // increase using the cubic equation.
160
161 let cwnd_rtt_start_after_tcp = cubic.cwnd();
162 let elapsed_time = now - start_time;
163
164 // calculate new time_increase.
165 let time_increase =
166 RTT / u32::try_from(cwnd_rtt_start_after_tcp / cubic.max_datagram_size()).unwrap();
167 let mut num_acks2 = 0; // count the number of acks. until cwnd is increased by MAX_DATAGRAM_SIZE.
168
169 while cwnd_rtt_start_after_tcp == cubic.cwnd() {
170 num_acks2 += 1;
171 now += time_increase;
172 ack_packet(&mut cubic, next_pn_ack, now);
173 next_pn_ack += 1;
174 next_pn_send = fill_cwnd(&mut cubic, next_pn_send, now);
175 }
176
177 let expected_ack_tcp_increase2 =
178 expected_tcp_acks(cwnd_rtt_start_after_tcp, cubic.max_datagram_size());
179 assert!(num_acks2 < expected_ack_tcp_increase2);
180
181 // The time needed to increase cwnd by MAX_DATAGRAM_SIZE using the cubic equation will be
182 // calculated from: W_cubic(elapsed_time + t_to_increase) - W_cubic(elapsed_time) =
183 // MAX_DATAGRAM_SIZE => CUBIC_C * (elapsed_time + t_to_increase)^3 * MAX_DATAGRAM_SIZE +
184 // CWND_INITIAL - CUBIC_C * elapsed_time^3 * MAX_DATAGRAM_SIZE + CWND_INITIAL =
185 // MAX_DATAGRAM_SIZE => t_to_increase = cbrt((1 + CUBIC_C * elapsed_time^3) / CUBIC_C) -
186 // elapsed_time (t_to_increase is in seconds)
187 // number of ack needed is t_to_increase / time_increase.
188 let expected_ack_cubic_increase =
189 (((CUBIC_C.mul_add((elapsed_time).as_secs_f64().powi(3), 1.0) / CUBIC_C).cbrt()
190 - elapsed_time.as_secs_f64())
191 / time_increase.as_secs_f64())
192 .ceil() as u64;
193 // num_acks is very close to the calculated value. The exact value is hard to calculate
194 // because the proportional increase (i.e. curr_cwnd_f64 / (target - curr_cwnd_f64) *
195 // MAX_DATAGRAM_SIZE_F64) and the byte counting.
196 assert_eq!(num_acks2, expected_ack_cubic_increase + 2);
197 }
198
199 #[test]
200 fn cubic_phase() {
201 let mut cubic = ClassicCongestionControl::new(Cubic::default(), Pmtud::new(IP_ADDR, MTU));
202 let cwnd_initial_f64 = convert_to_f64(cubic.cwnd_initial());
203 // Set last_max_cwnd to a higher number make sure that cc is the cubic phase (cwnd is calculated
204 // by the cubic equation).
205 cubic.set_last_max_cwnd(cwnd_initial_f64 * 10.0);
206 // Set ssthresh to something small to make sure that cc is in the congection avoidance phase.
207 cubic.set_ssthresh(1);
208 let mut now = now();
209 let mut next_pn_send = 0;
210 let mut next_pn_ack = 0;
211
212 next_pn_send = fill_cwnd(&mut cubic, next_pn_send, now);
213
214 let k = (cwnd_initial_f64.mul_add(10.0, -cwnd_initial_f64)
215 / CUBIC_C
216 / convert_to_f64(cubic.max_datagram_size()))
217 .cbrt();
218 let epoch_start = now;
219
220 // The number of RTT until W_max is reached.
221 let num_rtts_w_max = (k / RTT.as_secs_f64()).round() as u64;
222 for _ in 0..num_rtts_w_max {
223 let cwnd_rtt_start = cubic.cwnd();
224 // Expected acks
225 let acks = cwnd_rtt_start / cubic.max_datagram_size();
226 let time_increase = RTT / u32::try_from(acks).unwrap();
227 for _ in 0..acks {
228 now += time_increase;
229 ack_packet(&mut cubic, next_pn_ack, now);
230 next_pn_ack += 1;
231 next_pn_send = fill_cwnd(&mut cubic, next_pn_send, now);
232 }
233
234 let expected = (CUBIC_C * ((now - epoch_start).as_secs_f64() - k).powi(3))
235 .mul_add(
236 convert_to_f64(cubic.max_datagram_size()),
237 cwnd_initial_f64 * 10.0,
238 )
239 .round() as usize;
240
241 assert_within(cubic.cwnd(), expected, cubic.max_datagram_size());
242 }
243 assert_eq!(cubic.cwnd(), cubic.cwnd_initial() * 10);
244 }
245
246 fn assert_within<T: Sub<Output = T> + PartialOrd + Copy>(value: T, expected: T, margin: T) {
247 if value >= expected {
248 assert!(value - expected < margin);
249 } else {
250 assert!(expected - value < margin);
251 }
252 }
253
254 #[test]
255 fn congestion_event_slow_start() {
256 let mut cubic = ClassicCongestionControl::new(Cubic::default(), Pmtud::new(IP_ADDR, MTU));
257
258 _ = fill_cwnd(&mut cubic, 0, now());
259 ack_packet(&mut cubic, 0, now());
260
261 assert_within(cubic.last_max_cwnd(), 0.0, f64::EPSILON);
262
263 // cwnd is increased by 1 in slow start phase, after an ack.
264 assert_eq!(
265 cubic.cwnd(),
266 cubic.cwnd_initial() + cubic.max_datagram_size()
267 );
268
269 // Trigger a congestion_event in slow start phase
270 packet_lost(&mut cubic, 1);
271
272 // last_max_cwnd is equal to cwnd before decrease.
273 let cwnd_initial_f64 = convert_to_f64(cubic.cwnd_initial());
274 assert_within(
275 cubic.last_max_cwnd(),
276 cwnd_initial_f64 + convert_to_f64(cubic.max_datagram_size()),
277 f64::EPSILON,
278 );
279 assert_eq!(
280 cubic.cwnd(),
281 cwnd_after_loss_slow_start(cubic.cwnd_initial(), cubic.max_datagram_size())
282 );
283 }
284
285 #[test]
286 fn congestion_event_congestion_avoidance() {
287 let mut cubic = ClassicCongestionControl::new(Cubic::default(), Pmtud::new(IP_ADDR, MTU));
288
289 // Set ssthresh to something small to make sure that cc is in the congection avoidance phase.
290 cubic.set_ssthresh(1);
291
292 // Set last_max_cwnd to something smaller than cwnd so that the fast convergence is not
293 // triggered.
294 cubic.set_last_max_cwnd(3.0 * convert_to_f64(cubic.max_datagram_size()));
295
296 _ = fill_cwnd(&mut cubic, 0, now());
297 ack_packet(&mut cubic, 0, now());
298
299 assert_eq!(cubic.cwnd(), cubic.cwnd_initial());
300
301 // Trigger a congestion_event in slow start phase
302 packet_lost(&mut cubic, 1);
303
304 let cwnd_initial_f64 = convert_to_f64(cubic.cwnd_initial());
305 assert_within(cubic.last_max_cwnd(), cwnd_initial_f64, f64::EPSILON);
306 assert_eq!(cubic.cwnd(), cwnd_after_loss(cubic.cwnd_initial()));
307 }
308
309 #[test]
310 fn congestion_event_congestion_avoidance_2() {
311 let mut cubic = ClassicCongestionControl::new(Cubic::default(), Pmtud::new(IP_ADDR, MTU));
312
313 // Set ssthresh to something small to make sure that cc is in the congection avoidance phase.
314 cubic.set_ssthresh(1);
315
316 // Set last_max_cwnd to something higher than cwnd so that the fast convergence is triggered.
317 let cwnd_initial_f64 = convert_to_f64(cubic.cwnd_initial());
318 cubic.set_last_max_cwnd(cwnd_initial_f64 * 10.0);
319
320 _ = fill_cwnd(&mut cubic, 0, now());
321 ack_packet(&mut cubic, 0, now());
322
323 assert_within(cubic.last_max_cwnd(), cwnd_initial_f64 * 10.0, f64::EPSILON);
324 assert_eq!(cubic.cwnd(), cubic.cwnd_initial());
325
326 // Trigger a congestion_event.
327 packet_lost(&mut cubic, 1);
328
329 assert_within(
330 cubic.last_max_cwnd(),
331 cwnd_initial_f64 * CUBIC_FAST_CONVERGENCE,
332 f64::EPSILON,
333 );
334 assert_eq!(cubic.cwnd(), cwnd_after_loss(cubic.cwnd_initial()));
335 }
336
337 #[test]
338 fn congestion_event_congestion_avoidance_no_overflow() {
339 const PTO: Duration = Duration::from_millis(120);
340 let mut cubic = ClassicCongestionControl::new(Cubic::default(), Pmtud::new(IP_ADDR, MTU));
341
342 // Set ssthresh to something small to make sure that cc is in the congection avoidance phase.
343 cubic.set_ssthresh(1);
344
345 // Set last_max_cwnd to something higher than cwnd so that the fast convergence is triggered.
346 let cwnd_initial_f64 = convert_to_f64(cubic.cwnd_initial());
347 cubic.set_last_max_cwnd(cwnd_initial_f64 * 10.0);
348
349 _ = fill_cwnd(&mut cubic, 0, now());
350 ack_packet(&mut cubic, 1, now());
351
352 assert_within(cubic.last_max_cwnd(), cwnd_initial_f64 * 10.0, f64::EPSILON);
353 assert_eq!(cubic.cwnd(), cubic.cwnd_initial());
354
355 // Now ack packet that was send earlier.
356 ack_packet(&mut cubic, 0, now().checked_sub(PTO).unwrap());
357 }