Debian Codegraph @

third_party/rust/neqo-transport/src/connection/tests/cc.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 use std::time::Duration;
8
9 use neqo_common::{qdebug, qinfo, Datagram, IpTosEcn};
10
11 use super::{
12 super::Output, ack_bytes, assert_full_cwnd, connect_rtt_idle, cwnd, cwnd_avail, cwnd_packets,
13 default_client, default_server, fill_cwnd, induce_persistent_congestion, send_something,
14 CLIENT_HANDSHAKE_1RTT_PACKETS, DEFAULT_RTT, POST_HANDSHAKE_CWND,
15 };
16 use crate::{
17 connection::tests::{connect_with_rtt, new_client, new_server, now},
18 packet::PacketNumber,
19 recovery::{ACK_ONLY_SIZE_LIMIT, PACKET_THRESHOLD},
20 sender::PACING_BURST_SIZE,
21 stream_id::StreamType,
22 CongestionControlAlgorithm, ConnectionParameters,
23 };
24
25 #[test]
26 /// Verify initial CWND is honored.
27 fn cc_slow_start() {
28 let mut client = default_client();
29 let mut server = default_server();
30 let now = connect_rtt_idle(&mut client, &mut server, DEFAULT_RTT);
31
32 // Try to send a lot of data
33 let stream_id = client.stream_create(StreamType::UniDi).unwrap();
34 let (c_tx_dgrams, _) = fill_cwnd(&mut client, stream_id, now);
35 assert_full_cwnd(&c_tx_dgrams, POST_HANDSHAKE_CWND, client.plpmtu());
36 assert!(cwnd_avail(&client) < ACK_ONLY_SIZE_LIMIT);
37 }
38
39 #[test]
40 fn cc_slow_start_pmtud() {
41 let mut client = new_client(ConnectionParameters::default().pmtud(true));
42 let mut server = new_server(ConnectionParameters::default().pmtud(true));
43 let now = connect_with_rtt(&mut client, &mut server, now(), DEFAULT_RTT);
44
45 // Try to send a lot of data
46 let stream_id = client.stream_create(StreamType::UniDi).unwrap();
47 let cwnd = cwnd_avail(&client);
48 let (dgrams, _) = fill_cwnd(&mut client, stream_id, now);
49 let dgrams_len = dgrams.iter().map(Datagram::len).sum::<usize>();
50 assert_eq!(dgrams_len, cwnd);
51 assert!(cwnd_avail(&client) < ACK_ONLY_SIZE_LIMIT);
52 }
53
54 #[derive(PartialEq, Eq, Clone, Copy)]
55 enum CongestionSignal {
56 PacketLoss,
57 EcnCe,
58 }
59
60 fn cc_slow_start_to_cong_avoidance_recovery_period(congestion_signal: CongestionSignal) {
61 let mut client = default_client();
62 let mut server = default_server();
63 let now = connect_rtt_idle(&mut client, &mut server, DEFAULT_RTT);
64
65 // Create stream 0
66 let stream_id = client.stream_create(StreamType::BiDi).unwrap();
67 assert_eq!(stream_id, 0);
68
69 // Buffer up lot of data and generate packets
70 let (c_tx_dgrams, mut now) = fill_cwnd(&mut client, stream_id, now);
71 assert_full_cwnd(&c_tx_dgrams, POST_HANDSHAKE_CWND, client.plpmtu());
72 // Predict the packet number of the last packet sent.
73 // We have already sent packets in `connect_rtt_idle`,
74 // so include a fudge factor.
75 let flight1_largest =
76 PacketNumber::try_from(c_tx_dgrams.len() + CLIENT_HANDSHAKE_1RTT_PACKETS).unwrap();
77
78 // Server: Receive and generate ack
79 now += DEFAULT_RTT / 2;
80 let s_ack = ack_bytes(&mut server, stream_id, c_tx_dgrams, now);
81 assert_eq!(
82 server.stats().frame_tx.largest_acknowledged,
83 flight1_largest
84 );
85
86 // Client: Process ack
87 now += DEFAULT_RTT / 2;
88 client.process_input(s_ack, now);
89 assert_eq!(
90 client.stats().frame_rx.largest_acknowledged,
91 flight1_largest
92 );
93 let cwnd_before_cong = cwnd(&client);
94
95 // Client: send more
96 let (mut c_tx_dgrams, mut now) = fill_cwnd(&mut client, stream_id, now);
97 assert_full_cwnd(&c_tx_dgrams, POST_HANDSHAKE_CWND * 2, client.plpmtu());
98 let flight2_largest = flight1_largest + u64::try_from(c_tx_dgrams.len()).unwrap();
99
100 // Server: Receive and generate ack again, but this time add congestion
101 // signal first.
102 now += DEFAULT_RTT / 2;
103 match congestion_signal {
104 CongestionSignal::PacketLoss => {
105 c_tx_dgrams.remove(0);
106 }
107 CongestionSignal::EcnCe => {
108 c_tx_dgrams.last_mut().unwrap().set_tos(IpTosEcn::Ce.into());
109 }
110 }
111 let s_ack = ack_bytes(&mut server, stream_id, c_tx_dgrams, now);
112 assert_eq!(
113 server.stats().frame_tx.largest_acknowledged,
114 flight2_largest
115 );
116
117 // Client: Process ack
118 now += DEFAULT_RTT / 2;
119 client.process_input(s_ack, now);
120 assert_eq!(
121 client.stats().frame_rx.largest_acknowledged,
122 flight2_largest
123 );
124 assert!(cwnd(&client) < cwnd_before_cong);
125 }
126
127 #[test]
128 /// Verify that CC moves to cong avoidance when a packet is marked lost.
129 fn cc_slow_start_to_cong_avoidance_recovery_period_due_to_packet_loss() {
130 cc_slow_start_to_cong_avoidance_recovery_period(CongestionSignal::PacketLoss);
131 }
132
133 /// Verify that CC moves to cong avoidance when ACK is marked with ECN CE.
134 #[test]
135 fn cc_slow_start_to_cong_avoidance_recovery_period_due_to_ecn_ce() {
136 cc_slow_start_to_cong_avoidance_recovery_period(CongestionSignal::EcnCe);
137 }
138
139 #[test]
140 /// Verify that CC stays in recovery period when packet sent before start of
141 /// recovery period is acked.
142 fn cc_cong_avoidance_recovery_period_unchanged() {
143 let mut client = default_client();
144 let mut server = default_server();
145 let now = connect_rtt_idle(&mut client, &mut server, DEFAULT_RTT);
146
147 // Create stream 0
148 let stream_id = client.stream_create(StreamType::BiDi).unwrap();
149 assert_eq!(stream_id, 0);
150
151 // Buffer up lot of data and generate packets
152 let (mut c_tx_dgrams, now) = fill_cwnd(&mut client, stream_id, now);
153 assert_full_cwnd(&c_tx_dgrams, POST_HANDSHAKE_CWND, client.plpmtu());
154
155 // Drop 0th packet. When acked, this should put client into CARP.
156 c_tx_dgrams.remove(0);
157
158 let c_tx_dgrams2 = c_tx_dgrams.split_off(5);
159
160 // Server: Receive and generate ack
161 let s_ack = ack_bytes(&mut server, stream_id, c_tx_dgrams, now);
162 client.process_input(s_ack, now);
163
164 let cwnd1 = cwnd(&client);
165
166 // Generate ACK for more received packets
167 let s_ack = ack_bytes(&mut server, stream_id, c_tx_dgrams2, now);
168
169 // ACK more packets but they were sent before end of recovery period
170 client.process_input(s_ack, now);
171
172 // cwnd should not have changed since ACKed packets were sent before
173 // recovery period expired
174 let cwnd2 = cwnd(&client);
175 assert_eq!(cwnd1, cwnd2);
176 }
177
178 #[test]
179 /// Ensure that a single packet is sent after entering recovery, even
180 /// when that exceeds the available congestion window.
181 fn single_packet_on_recovery() {
182 let mut client = default_client();
183 let mut server = default_server();
184 let now = connect_rtt_idle(&mut client, &mut server, DEFAULT_RTT);
185
186 // Drop a few packets, up to the reordering threshold.
187 for _ in 0..PACKET_THRESHOLD {
188 let _dropped = send_something(&mut client, now);
189 }
190 let delivered = send_something(&mut client, now);
191
192 // Now fill the congestion window.
193 let stream_id = client.stream_create(StreamType::BiDi).unwrap();
194 assert_eq!(stream_id, 0);
195 let (_, now) = fill_cwnd(&mut client, stream_id, now);
196 assert!(cwnd_avail(&client) < ACK_ONLY_SIZE_LIMIT);
197
198 // Acknowledge just one packet and cause one packet to be declared lost.
199 // The length is the amount of credit the client should have.
200 let ack = server.process(Some(delivered), now).dgram();
201 assert!(ack.is_some());
202
203 // The client should see the loss and enter recovery.
204 // As there are many outstanding packets, there should be no available cwnd.
205 client.process_input(ack.unwrap(), now);
206 assert_eq!(cwnd_avail(&client), 0);
207
208 // The client should send one packet, ignoring the cwnd.
209 let dgram = client.process_output(now).dgram();
210 assert!(dgram.is_some());
211 }
212
213 /// Verify that CC moves out of recovery period when packet sent after start
214 /// of recovery period is acked.
215 fn cc_cong_avoidance_recovery_period_to_cong_avoidance(cc_algorithm: CongestionControlAlgorithm) {
216 let mut client = new_client(ConnectionParameters::default().cc_algorithm(cc_algorithm));
217 let mut server = new_server(ConnectionParameters::default().cc_algorithm(cc_algorithm));
218 let now = connect_rtt_idle(&mut client, &mut server, DEFAULT_RTT);
219
220 // Create stream 0
221 let stream_id = client.stream_create(StreamType::BiDi).unwrap();
222 assert_eq!(stream_id, 0);
223
224 // Buffer up lot of data and generate packets
225 let (mut c_tx_dgrams, mut now) = fill_cwnd(&mut client, stream_id, now);
226
227 // Drop 0th packet. When acked, this should put client into CARP.
228 c_tx_dgrams.remove(0);
229
230 // Server: Receive and generate ack
231 now += DEFAULT_RTT / 2;
232 let s_ack = ack_bytes(&mut server, stream_id, c_tx_dgrams, now);
233
234 let cwnd_before_loss = cwnd(&client);
235
236 // Client: Process ack
237 now += DEFAULT_RTT / 2;
238 client.process_input(s_ack, now);
239
240 let cwnd_after_loss = cwnd(&client);
241
242 // Should be in CARP now.
243 now += DEFAULT_RTT / 2;
244 assert!(cwnd_before_loss > cwnd_after_loss);
245 qinfo!("moving to congestion avoidance {}", cwnd(&client));
246
247 for i in 0..6 {
248 qinfo!("iteration {i}");
249
250 let (c_tx_dgrams, next_now) = fill_cwnd(&mut client, stream_id, now);
251 qinfo!(
252 "client sending {} bytes into cwnd of {}",
253 c_tx_dgrams.iter().map(Datagram::len).sum::<usize>(),
254 cwnd(&client)
255 );
256 now = next_now;
257
258 let s_ack = ack_bytes(&mut server, stream_id, c_tx_dgrams, now);
259 client.process_input(s_ack, now);
260 }
261
262 assert!(cwnd_before_loss < cwnd(&client));
263 }
264
265 #[test]
266 fn cc_cong_avoidance_recovery_period_to_cong_avoidance_new_reno() {
267 cc_cong_avoidance_recovery_period_to_cong_avoidance(CongestionControlAlgorithm::NewReno);
268 }
269
270 #[test]
271 fn cc_cong_avoidance_recovery_period_to_cong_avoidance_cubic() {
272 cc_cong_avoidance_recovery_period_to_cong_avoidance(CongestionControlAlgorithm::Cubic);
273 }
274
275 #[test]
276 /// Verify transition to persistent congestion state if conditions are met.
277 fn cc_slow_start_to_persistent_congestion_no_acks() {
278 let mut client = default_client();
279 let mut server = default_server();
280 let now = connect_rtt_idle(&mut client, &mut server, DEFAULT_RTT);
281
282 let stream = client.stream_create(StreamType::BiDi).unwrap();
283
284 // Buffer up lot of data and generate packets
285 let (c_tx_dgrams, mut now) = fill_cwnd(&mut client, stream, now);
286 assert_full_cwnd(&c_tx_dgrams, POST_HANDSHAKE_CWND, client.plpmtu());
287
288 // Server: Receive and generate ack
289 now += DEFAULT_RTT / 2;
290 drop(ack_bytes(&mut server, stream, c_tx_dgrams, now));
291
292 // ACK lost.
293 induce_persistent_congestion(&mut client, &mut server, stream, now);
294 }
295
296 #[test]
297 /// Verify transition to persistent congestion state if conditions are met.
298 fn cc_slow_start_to_persistent_congestion_some_acks() {
299 let mut client = default_client();
300 let mut server = default_server();
301 let now = connect_rtt_idle(&mut client, &mut server, DEFAULT_RTT);
302
303 // Create stream 0
304 let stream = client.stream_create(StreamType::BiDi).unwrap();
305
306 // Buffer up lot of data and generate packets
307 let (c_tx_dgrams, mut now) = fill_cwnd(&mut client, stream, now);
308 assert_full_cwnd(&c_tx_dgrams, POST_HANDSHAKE_CWND, client.plpmtu());
309
310 // Server: Receive and generate ack
311 now += Duration::from_millis(100);
312 let s_ack = ack_bytes(&mut server, stream, c_tx_dgrams, now);
313
314 now += Duration::from_millis(100);
315 client.process_input(s_ack, now);
316
317 // send bytes that will be lost
318 let (_, next_now) = fill_cwnd(&mut client, stream, now);
319 now = next_now + Duration::from_millis(100);
320
321 induce_persistent_congestion(&mut client, &mut server, stream, now);
322 }
323
324 #[test]
325 /// Verify persistent congestion moves to slow start after recovery period
326 /// ends.
327 fn cc_persistent_congestion_to_slow_start() {
328 let mut client = default_client();
329 let mut server = default_server();
330 let now = connect_rtt_idle(&mut client, &mut server, DEFAULT_RTT);
331
332 // Create stream 0
333 let stream = client.stream_create(StreamType::BiDi).unwrap();
334
335 // Buffer up lot of data and generate packets
336 let (c_tx_dgrams, mut now) = fill_cwnd(&mut client, stream, now);
337 assert_full_cwnd(&c_tx_dgrams, POST_HANDSHAKE_CWND, client.plpmtu());
338
339 // Server: Receive and generate ack
340 now += Duration::from_millis(10);
341 drop(ack_bytes(&mut server, stream, c_tx_dgrams, now));
342
343 // ACK lost.
344
345 now = induce_persistent_congestion(&mut client, &mut server, stream, now);
346
347 // New part of test starts here
348
349 now += Duration::from_millis(10);
350
351 // Send packets from after start of CARP
352 let (c_tx_dgrams, next_now) = fill_cwnd(&mut client, stream, now);
353 assert_eq!(c_tx_dgrams.len(), 2);
354
355 // Server: Receive and generate ack
356 now = next_now + Duration::from_millis(100);
357 let s_ack = ack_bytes(&mut server, stream, c_tx_dgrams, now);
358
359 // No longer in CARP. (pkts acked from after start of CARP)
360 // Should be in slow start now.
361 client.process_input(s_ack, now);
362
363 // ACKing 2 packets should let client send 4.
364 let (c_tx_dgrams, _) = fill_cwnd(&mut client, stream, now);
365 assert_eq!(c_tx_dgrams.len(), 4);
366 }
367
368 #[test]
369 fn ack_are_not_cc() {
370 let mut client = default_client();
371 let mut server = default_server();
372 let now = connect_rtt_idle(&mut client, &mut server, DEFAULT_RTT);
373
374 // Create a stream
375 let stream = client.stream_create(StreamType::BiDi).unwrap();
376 assert_eq!(stream, 0);
377
378 // Buffer up lot of data and generate packets, so that cc window is filled.
379 let (c_tx_dgrams, now) = fill_cwnd(&mut client, stream, now);
380 assert_full_cwnd(&c_tx_dgrams, POST_HANDSHAKE_CWND, client.plpmtu());
381
382 // The server hasn't received any of these packets yet, the server
383 // won't ACK, but if it sends an ack-eliciting packet instead.
384 qdebug!("[{server}] Sending ack-eliciting");
385 let other_stream = server.stream_create(StreamType::BiDi).unwrap();
386 assert_eq!(other_stream, 1);
387 server.stream_send(other_stream, b"dropped").unwrap();
388 let dropped_packet = server.process_output(now).dgram();
389 assert!(dropped_packet.is_some()); // Now drop this one.
390
391 // Now the server sends a packet that will force an ACK,
392 // because the client will detect a gap.
393 server.stream_send(other_stream, b"sent").unwrap();
394 let ack_eliciting_packet = server.process_output(now).dgram();
395 assert!(ack_eliciting_packet.is_some());
396
397 // The client can ack the server packet even if cc windows is full.
398 qdebug!("[{client}] Process ack-eliciting");
399 let ack_pkt = client.process(ack_eliciting_packet, now).dgram();
400 assert!(ack_pkt.is_some());
401 qdebug!("[{server}] Handle ACK");
402 let prev_ack_count = server.stats().frame_rx.ack;
403 server.process_input(ack_pkt.unwrap(), now);
404 assert_eq!(server.stats().frame_rx.ack, prev_ack_count + 1);
405 }
406
407 #[test]
408 fn pace() {
409 const DATA: &[u8] = &[0xcc; 4_096];
410 let mut client = default_client();
411 let mut server = default_server();
412 let mut now = connect_rtt_idle(&mut client, &mut server, DEFAULT_RTT);
413
414 // Now fill up the pipe and watch it trickle out.
415 let stream = client.stream_create(StreamType::BiDi).unwrap();
416 loop {
417 let written = client.stream_send(stream, DATA).unwrap();
418 if written < DATA.len() {
419 break;
420 }
421 }
422 let mut count = 0;
423 // We should get a burst at first.
424 // The first packet is not subject to pacing as there are no bytes in flight.
425 // After that we allow the burst to continue up to a number of packets (2).
426 for _ in 0..=PACING_BURST_SIZE {
427 let dgram = client.process_output(now).dgram();
428 assert!(dgram.is_some());
429 count += 1;
430 }
431 let gap = client.process_output(now).callback();
432 assert_ne!(gap, Duration::new(0, 0));
433 for _ in (1 + PACING_BURST_SIZE)..cwnd_packets(POST_HANDSHAKE_CWND, client.plpmtu()) {
434 match client.process_output(now) {
435 Output::Callback(t) => assert_eq!(t, gap),
436 Output::Datagram(_) => {
437 // The last packet might not be paced.
438 count += 1;
439 break;
440 }
441 Output::None => panic!(),
442 }
443 now += gap;
444 let dgram = client.process_output(now).dgram();
445 assert!(dgram.is_some());
446 count += 1;
447 }
448 let dgram = client.process_output(now).dgram();
449 assert!(dgram.is_none());
450 assert_eq!(count, cwnd_packets(POST_HANDSHAKE_CWND, client.plpmtu()));
451 let fin = client.process_output(now).callback();
452 assert_ne!(fin, Duration::new(0, 0));
453 assert_ne!(fin, gap);
454 }