Debian Codegraph @

third_party/rust/neqo-transport/src/cc/classic_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 // Congestion control
8
9 use std::{
10 cmp::{max, min},
11 fmt::{self, Debug, Display},
12 time::{Duration, Instant},
13 };
14
15 use ::qlog::events::{quic::CongestionStateUpdated, EventData};
16 use neqo_common::{const_max, const_min, qdebug, qinfo, qlog::NeqoQlog, qtrace};
17
18 use super::CongestionControl;
19 use crate::{
20 packet::PacketNumber,
21 qlog::{self, QlogMetric},
22 recovery::SentPacket,
23 rtt::RttEstimate,
24 sender::PACING_BURST_SIZE,
25 Pmtud,
26 };
27
28 pub const CWND_INITIAL_PKTS: usize = 10;
29 const PERSISTENT_CONG_THRESH: u32 = 3;
30
31 #[derive(Debug, Clone, Copy, PartialEq, Eq)]
32 enum State {
33 /// In either slow start or congestion avoidance, not recovery.
34 SlowStart,
35 /// In congestion avoidance.
36 CongestionAvoidance,
37 /// In a recovery period, but no packets have been sent yet. This is a
38 /// transient state because we want to exempt the first packet sent after
39 /// entering recovery from the congestion window.
40 RecoveryStart,
41 /// In a recovery period, with the first packet sent at this time.
42 Recovery,
43 /// Start of persistent congestion, which is transient, like `RecoveryStart`.
44 PersistentCongestion,
45 }
46
47 impl State {
48 pub const fn in_recovery(self) -> bool {
49 matches!(self, Self::RecoveryStart | Self::Recovery)
50 }
51
52 pub fn in_slow_start(self) -> bool {
53 self == Self::SlowStart
54 }
55
56 /// These states are transient, we tell qlog on entry, but not on exit.
57 pub const fn transient(self) -> bool {
58 matches!(self, Self::RecoveryStart | Self::PersistentCongestion)
59 }
60
61 /// Update a transient state to the true state.
62 pub fn update(&mut self) {
63 *self = match self {
64 Self::PersistentCongestion => Self::SlowStart,
65 Self::RecoveryStart => Self::Recovery,
66 _ => unreachable!(),
67 };
68 }
69
70 pub const fn to_qlog(self) -> &'static str {
71 match self {
72 Self::SlowStart | Self::PersistentCongestion => "slow_start",
73 Self::CongestionAvoidance => "congestion_avoidance",
74 Self::Recovery | Self::RecoveryStart => "recovery",
75 }
76 }
77 }
78
79 pub trait WindowAdjustment: Display + Debug {
80 /// This is called when an ack is received.
81 /// The function calculates the amount of acked bytes congestion controller needs
82 /// to collect before increasing its cwnd by `MAX_DATAGRAM_SIZE`.
83 fn bytes_for_cwnd_increase(
84 &mut self,
85 curr_cwnd: usize,
86 new_acked_bytes: usize,
87 min_rtt: Duration,
88 max_datagram_size: usize,
89 now: Instant,
90 ) -> usize;
91 /// This function is called when a congestion event has been detected and it
92 /// returns new (decreased) values of `curr_cwnd` and `acked_bytes`.
93 /// This value can be very small; the calling code is responsible for ensuring that the
94 /// congestion window doesn't drop below the minimum of `CWND_MIN`.
95 fn reduce_cwnd(
96 &mut self,
97 curr_cwnd: usize,
98 acked_bytes: usize,
99 max_datagram_size: usize,
100 ) -> (usize, usize);
101 /// Cubic needs this signal to reset its epoch.
102 fn on_app_limited(&mut self);
103 #[cfg(test)]
104 fn last_max_cwnd(&self) -> f64;
105 #[cfg(test)]
106 fn set_last_max_cwnd(&mut self, last_max_cwnd: f64);
107 }
108
109 #[derive(Debug)]
110 pub struct ClassicCongestionControl<T> {
111 cc_algorithm: T,
112 state: State,
113 congestion_window: usize, // = kInitialWindow
114 bytes_in_flight: usize,
115 acked_bytes: usize,
116 ssthresh: usize,
117 recovery_start: Option<PacketNumber>,
118 /// `first_app_limited` indicates the packet number after which the application might be
119 /// underutilizing the congestion window. When underutilizing the congestion window due to not
120 /// sending out enough data, we SHOULD NOT increase the congestion window.[1] Packets sent
121 /// before this point are deemed to fully utilize the congestion window and count towards
122 /// increasing the congestion window.
123 ///
124 /// [1]: https://datatracker.ietf.org/doc/html/rfc9002#section-7.8
125 first_app_limited: PacketNumber,
126 pmtud: Pmtud,
127 qlog: NeqoQlog,
128 }
129
130 impl<T> ClassicCongestionControl<T> {
131 pub const fn max_datagram_size(&self) -> usize {
132 self.pmtud.plpmtu()
133 }
134 }
135
136 impl<T: WindowAdjustment> Display for ClassicCongestionControl<T> {
137 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
138 write!(
139 f,
140 "{} CongCtrl {}/{} ssthresh {}",
141 self.cc_algorithm, self.bytes_in_flight, self.congestion_window, self.ssthresh,
142 )?;
143 Ok(())
144 }
145 }
146
147 impl<T: WindowAdjustment> CongestionControl for ClassicCongestionControl<T> {
148 fn set_qlog(&mut self, qlog: NeqoQlog) {
149 self.qlog = qlog;
150 }
151
152 fn cwnd(&self) -> usize {
153 self.congestion_window
154 }
155
156 fn bytes_in_flight(&self) -> usize {
157 self.bytes_in_flight
158 }
159
160 fn cwnd_avail(&self) -> usize {
161 // BIF can be higher than cwnd due to PTO packets, which are sent even
162 // if avail is 0, but still count towards BIF.
163 self.congestion_window.saturating_sub(self.bytes_in_flight)
164 }
165
166 fn cwnd_min(&self) -> usize {
167 self.max_datagram_size() * 2
168 }
169
170 #[cfg(test)]
171 fn cwnd_initial(&self) -> usize {
172 cwnd_initial(self.pmtud.plpmtu())
173 }
174
175 fn pmtud(&self) -> &Pmtud {
176 &self.pmtud
177 }
178
179 fn pmtud_mut(&mut self) -> &mut Pmtud {
180 &mut self.pmtud
181 }
182
183 fn on_packets_acked(&mut self, acked_pkts: &[SentPacket], rtt_est: &RttEstimate, now: Instant) {
184 let mut is_app_limited = true;
185 let mut new_acked = 0;
186 for pkt in acked_pkts {
187 qtrace!(
188 "packet_acked this={self:p}, pn={}, ps={}, ignored={}, lost={}, rtt_est={rtt_est:?}",
189 pkt.pn(),
190 pkt.len(),
191 i32::from(!pkt.cc_outstanding()),
192 i32::from(pkt.lost()),
193 );
194 if !pkt.cc_outstanding() {
195 continue;
196 }
197 if pkt.pn() < self.first_app_limited {
198 is_app_limited = false;
199 }
200 // BIF is set to 0 on a path change, but in case that was because of a simple rebinding
201 // event, we may still get ACKs for packets sent before the rebinding.
202 self.bytes_in_flight = self.bytes_in_flight.saturating_sub(pkt.len());
203
204 if !self.after_recovery_start(pkt) {
205 // Do not increase congestion window for packets sent before
206 // recovery last started.
207 continue;
208 }
209
210 if self.state.in_recovery() {
211 self.set_state(State::CongestionAvoidance, now);
212 qlog::metrics_updated(&self.qlog, &[QlogMetric::InRecovery(false)], now);
213 }
214
215 new_acked += pkt.len();
216 }
217
218 if is_app_limited {
219 self.cc_algorithm.on_app_limited();
220 qdebug!("on_packets_acked this={self:p}, limited=1, bytes_in_flight={}, cwnd={}, state={:?}, new_acked={new_acked}", self.bytes_in_flight, self.congestion_window, self.state);
221 return;
222 }
223
224 // Slow start, up to the slow start threshold.
225 if self.congestion_window < self.ssthresh {
226 self.acked_bytes += new_acked;
227 let increase = min(self.ssthresh - self.congestion_window, self.acked_bytes);
228 self.congestion_window += increase;
229 self.acked_bytes -= increase;
230 qdebug!("[{self}] slow start += {increase}");
231 if self.congestion_window == self.ssthresh {
232 // This doesn't look like it is necessary, but it can happen
233 // after persistent congestion.
234 self.set_state(State::CongestionAvoidance, now);
235 }
236 }
237 // Congestion avoidance, above the slow start threshold.
238 if self.congestion_window >= self.ssthresh {
239 // The following function return the amount acked bytes a controller needs
240 // to collect to be allowed to increase its cwnd by MAX_DATAGRAM_SIZE.
241 let bytes_for_increase = self.cc_algorithm.bytes_for_cwnd_increase(
242 self.congestion_window,
243 new_acked,
244 rtt_est.minimum(),
245 self.max_datagram_size(),
246 now,
247 );
248 debug_assert!(bytes_for_increase > 0);
249 // If enough credit has been accumulated already, apply them gradually.
250 // If we have sudden increase in allowed rate we actually increase cwnd gently.
251 if self.acked_bytes >= bytes_for_increase {
252 self.acked_bytes = 0;
253 self.congestion_window += self.max_datagram_size();
254 }
255 self.acked_bytes += new_acked;
256 if self.acked_bytes >= bytes_for_increase {
257 self.acked_bytes -= bytes_for_increase;
258 self.congestion_window += self.max_datagram_size(); // or is this the current MTU?
259 }
260 // The number of bytes we require can go down over time with Cubic.
261 // That might result in an excessive rate of increase, so limit the number of unused
262 // acknowledged bytes after increasing the congestion window twice.
263 self.acked_bytes = min(bytes_for_increase, self.acked_bytes);
264 }
265 qlog::metrics_updated(
266 &self.qlog,
267 &[
268 QlogMetric::CongestionWindow(self.congestion_window),
269 QlogMetric::BytesInFlight(self.bytes_in_flight),
270 ],
271 now,
272 );
273 qdebug!("[{self}] on_packets_acked this={self:p}, limited=0, bytes_in_flight={}, cwnd={}, state={:?}, new_acked={new_acked}", self.bytes_in_flight, self.congestion_window, self.state);
274 }
275
276 /// Update congestion controller state based on lost packets.
277 fn on_packets_lost(
278 &mut self,
279 first_rtt_sample_time: Option<Instant>,
280 prev_largest_acked_sent: Option<Instant>,
281 pto: Duration,
282 lost_packets: &[SentPacket],
283 now: Instant,
284 ) -> bool {
285 if lost_packets.is_empty() {
286 return false;
287 }
288
289 for pkt in lost_packets.iter().filter(|pkt| pkt.cc_in_flight()) {
290 qdebug!(
291 "packet_lost this={self:p}, pn={}, ps={}",
292 pkt.pn(),
293 pkt.len()
294 );
295 // BIF is set to 0 on a path change, but in case that was because of a simple rebinding
296 // event, we may still declare packets lost that were sent before the rebinding.
297 self.bytes_in_flight = self.bytes_in_flight.saturating_sub(pkt.len());
298 }
299 qlog::metrics_updated(
300 &self.qlog,
301 &[QlogMetric::BytesInFlight(self.bytes_in_flight)],
302 now,
303 );
304
305 let is_pmtud_probe = self.pmtud.is_probe_filter();
306 let mut lost_packets = lost_packets
307 .iter()
308 .filter(|pkt| !is_pmtud_probe(pkt))
309 .rev()
310 .peekable();
311
312 // Lost PMTUD probes do not elicit a congestion control reaction.
313 let Some(last_lost_packet) = lost_packets.peek() else {
314 return false;
315 };
316
317 let congestion = self.on_congestion_event(last_lost_packet, now);
318 let persistent_congestion = self.detect_persistent_congestion(
319 first_rtt_sample_time,
320 prev_largest_acked_sent,
321 pto,
322 lost_packets.rev(),
323 now,
324 );
325 qdebug!(
326 "on_packets_lost this={self:p}, bytes_in_flight={}, cwnd={}, state={:?}",
327 self.bytes_in_flight,
328 self.congestion_window,
329 self.state
330 );
331 congestion || persistent_congestion
332 }
333
334 /// Report received ECN CE mark(s) to the congestion controller as a
335 /// congestion event.
336 ///
337 /// See <https://datatracker.ietf.org/doc/html/rfc9002#section-b.7>.
338 fn on_ecn_ce_received(&mut self, largest_acked_pkt: &SentPacket, now: Instant) -> bool {
339 self.on_congestion_event(largest_acked_pkt, now)
340 }
341
342 fn discard(&mut self, pkt: &SentPacket, now: Instant) {
343 if pkt.cc_outstanding() {
344 assert!(self.bytes_in_flight >= pkt.len());
345 self.bytes_in_flight -= pkt.len();
346 qlog::metrics_updated(
347 &self.qlog,
348 &[QlogMetric::BytesInFlight(self.bytes_in_flight)],
349 now,
350 );
351 qtrace!("[{self}] Ignore pkt with size {}", pkt.len());
352 }
353 }
354
355 fn discard_in_flight(&mut self, now: Instant) {
356 self.bytes_in_flight = 0;
357 qlog::metrics_updated(
358 &self.qlog,
359 &[QlogMetric::BytesInFlight(self.bytes_in_flight)],
360 now,
361 );
362 }
363
364 fn on_packet_sent(&mut self, pkt: &SentPacket, now: Instant) {
365 // Record the recovery time and exit any transient state.
366 if self.state.transient() {
367 self.recovery_start = Some(pkt.pn());
368 self.state.update();
369 }
370
371 if !pkt.cc_in_flight() {
372 return;
373 }
374 if !self.app_limited() {
375 // Given the current non-app-limited condition, we're fully utilizing the congestion
376 // window. Assume that all in-flight packets up to this one are NOT app-limited.
377 // However, subsequent packets might be app-limited. Set `first_app_limited` to the
378 // next packet number.
379 self.first_app_limited = pkt.pn() + 1;
380 }
381
382 self.bytes_in_flight += pkt.len();
383 qdebug!(
384 "packet_sent this={self:p}, pn={}, ps={}",
385 pkt.pn(),
386 pkt.len()
387 );
388 qlog::metrics_updated(
389 &self.qlog,
390 &[QlogMetric::BytesInFlight(self.bytes_in_flight)],
391 now,
392 );
393 }
394
395 /// Whether a packet can be sent immediately as a result of entering recovery.
396 fn recovery_packet(&self) -> bool {
397 self.state == State::RecoveryStart
398 }
399 }
400
401 const fn cwnd_initial(mtu: usize) -> usize {
402 const_min(CWND_INITIAL_PKTS * mtu, const_max(2 * mtu, 14_720))
403 }
404
405 impl<T: WindowAdjustment> ClassicCongestionControl<T> {
406 pub fn new(cc_algorithm: T, pmtud: Pmtud) -> Self {
407 Self {
408 cc_algorithm,
409 state: State::SlowStart,
410 congestion_window: cwnd_initial(pmtud.plpmtu()),
411 bytes_in_flight: 0,
412 acked_bytes: 0,
413 ssthresh: usize::MAX,
414 recovery_start: None,
415 qlog: NeqoQlog::disabled(),
416 first_app_limited: 0,
417 pmtud,
418 }
419 }
420
421 #[cfg(test)]
422 #[must_use]
423 pub const fn ssthresh(&self) -> usize {
424 self.ssthresh
425 }
426
427 #[cfg(test)]
428 pub fn set_ssthresh(&mut self, v: usize) {
429 self.ssthresh = v;
430 }
431
432 #[cfg(test)]
433 pub fn last_max_cwnd(&self) -> f64 {
434 self.cc_algorithm.last_max_cwnd()
435 }
436
437 #[cfg(test)]
438 pub fn set_last_max_cwnd(&mut self, last_max_cwnd: f64) {
439 self.cc_algorithm.set_last_max_cwnd(last_max_cwnd);
440 }
441
442 #[cfg(test)]
443 pub const fn acked_bytes(&self) -> usize {
444 self.acked_bytes
445 }
446
447 fn set_state(&mut self, state: State, now: Instant) {
448 if self.state != state {
449 qdebug!("[{self}] state -> {state:?}");
450 let old_state = self.state;
451 self.qlog.add_event_data_with_instant(
452 || {
453 // No need to tell qlog about exit from transient states.
454 if old_state.transient() {
455 None
456 } else {
457 let ev_data = EventData::CongestionStateUpdated(CongestionStateUpdated {
458 old: Some(old_state.to_qlog().to_owned()),
459 new: state.to_qlog().to_owned(),
460 trigger: None,
461 });
462 Some(ev_data)
463 }
464 },
465 now,
466 );
467 self.state = state;
468 }
469 }
470
471 fn detect_persistent_congestion<'a>(
472 &mut self,
473 first_rtt_sample_time: Option<Instant>,
474 prev_largest_acked_sent: Option<Instant>,
475 pto: Duration,
476 lost_packets: impl IntoIterator<Item = &'a SentPacket>,
477 now: Instant,
478 ) -> bool {
479 if first_rtt_sample_time.is_none() {
480 return false;
481 }
482
483 let pc_period = pto * PERSISTENT_CONG_THRESH;
484
485 let mut last_pn = 1 << 62; // Impossibly large, but not enough to overflow.
486 let mut start = None;
487
488 // Look for the first lost packet after the previous largest acknowledged.
489 // Ignore packets that weren't ack-eliciting for the start of this range.
490 // Also, make sure to ignore any packets sent before we got an RTT estimate
491 // as we might not have sent PTO packets soon enough after those.
492 let cutoff = max(first_rtt_sample_time, prev_largest_acked_sent);
493 for p in lost_packets
494 .into_iter()
495 .skip_while(|p| Some(p.time_sent()) < cutoff)
496 {
497 if p.pn() != last_pn + 1 {
498 // Not a contiguous range of lost packets, start over.
499 start = None;
500 }
501 last_pn = p.pn();
502 if !p.cc_in_flight() {
503 // Not interesting, keep looking.
504 continue;
505 }
506 if let Some(t) = start {
507 let elapsed = p
508 .time_sent()
509 .checked_duration_since(t)
510 .expect("time is monotonic");
511 if elapsed > pc_period {
512 qinfo!("[{self}] persistent congestion");
513 self.congestion_window = self.cwnd_min();
514 self.acked_bytes = 0;
515 self.set_state(State::PersistentCongestion, now);
516 qlog::metrics_updated(
517 &self.qlog,
518 &[QlogMetric::CongestionWindow(self.congestion_window)],
519 now,
520 );
521 return true;
522 }
523 } else {
524 start = Some(p.time_sent());
525 }
526 }
527 false
528 }
529
530 #[must_use]
531 fn after_recovery_start(&self, packet: &SentPacket) -> bool {
532 // At the start of the recovery period, the state is transient and
533 // all packets will have been sent before recovery. When sending out
534 // the first packet we transition to the non-transient `Recovery`
535 // state and update the variable `self.recovery_start`. Before the
536 // first recovery, all packets were sent after the recovery event,
537 // allowing to reduce the cwnd on congestion events.
538 !self.state.transient() && self.recovery_start.is_none_or(|pn| packet.pn() >= pn)
539 }
540
541 /// Handle a congestion event.
542 /// Returns true if this was a true congestion event.
543 fn on_congestion_event(&mut self, last_packet: &SentPacket, now: Instant) -> bool {
544 // Start a new congestion event if lost or ECN CE marked packet was sent
545 // after the start of the previous congestion recovery period.
546 if !self.after_recovery_start(last_packet) {
547 return false;
548 }
549
550 let (cwnd, acked_bytes) = self.cc_algorithm.reduce_cwnd(
551 self.congestion_window,
552 self.acked_bytes,
553 self.max_datagram_size(),
554 );
555 self.congestion_window = max(cwnd, self.cwnd_min());
556 self.acked_bytes = acked_bytes;
557 self.ssthresh = self.congestion_window;
558 qdebug!(
559 "[{self}] Cong event -> recovery; cwnd {}, ssthresh {}",
560 self.congestion_window,
561 self.ssthresh
562 );
563 qlog::metrics_updated(
564 &self.qlog,
565 &[
566 QlogMetric::CongestionWindow(self.congestion_window),
567 QlogMetric::SsThresh(self.ssthresh),
568 QlogMetric::InRecovery(true),
569 ],
570 now,
571 );
572 self.set_state(State::RecoveryStart, now);
573 true
574 }
575
576 fn app_limited(&self) -> bool {
577 if self.bytes_in_flight >= self.congestion_window {
578 false
579 } else if self.state.in_slow_start() {
580 // Allow for potential doubling of the congestion window during slow start.
581 // That is, the application might not have been able to send enough to respond
582 // to increases to the congestion window.
583 self.bytes_in_flight < self.congestion_window / 2
584 } else {
585 // We're not limited if the in-flight data is within a single burst of the
586 // congestion window.
587 (self.bytes_in_flight + self.max_datagram_size() * PACING_BURST_SIZE)
588 < self.congestion_window
589 }
590 }
591 }
592
593 #[cfg(test)]
594 mod tests {
595 use std::time::{Duration, Instant};
596
597 use neqo_common::qinfo;
598 use test_fixture::now;
599
600 use super::{ClassicCongestionControl, WindowAdjustment, PERSISTENT_CONG_THRESH};
601 use crate::{
602 cc::{
603 classic_cc::State,
604 cubic::{Cubic, CUBIC_BETA_USIZE_DIVIDEND, CUBIC_BETA_USIZE_DIVISOR},
605 new_reno::NewReno,
606 tests::{IP_ADDR, MTU, RTT},
607 CongestionControl, CongestionControlAlgorithm, CWND_INITIAL_PKTS,
608 },
609 packet::{PacketNumber, PacketType},
610 recovery::SentPacket,
611 rtt::RttEstimate,
612 Pmtud,
613 };
614
615 const PTO: Duration = RTT;
616 const ZERO: Duration = Duration::from_secs(0);
617 const EPSILON: Duration = Duration::from_nanos(1);
618 const GAP: Duration = Duration::from_secs(1);
619 /// The largest time between packets without causing persistent congestion.
620 const SUB_PC: Duration = Duration::from_millis(100 * PERSISTENT_CONG_THRESH as u64);
621 /// The minimum time between packets to cause persistent congestion.
622 /// Uses an odd expression because `Duration` arithmetic isn't `const`.
623 const PC: Duration = Duration::from_nanos(100_000_000 * (PERSISTENT_CONG_THRESH as u64) + 1);
624
625 fn cwnd_is_default(cc: &ClassicCongestionControl<NewReno>) {
626 assert_eq!(cc.cwnd(), cc.cwnd_initial());
627 assert_eq!(cc.ssthresh(), usize::MAX);
628 }
629
630 fn cwnd_is_halved(cc: &ClassicCongestionControl<NewReno>) {
631 assert_eq!(cc.cwnd(), cc.cwnd_initial() / 2);
632 assert_eq!(cc.ssthresh(), cc.cwnd_initial() / 2);
633 }
634
635 fn lost(pn: PacketNumber, ack_eliciting: bool, t: Duration) -> SentPacket {
636 SentPacket::new(
637 PacketType::Short,
638 pn,
639 now() + t,
640 ack_eliciting,
641 Vec::new(),
642 100,
643 )
644 }
645
646 fn congestion_control(cc: CongestionControlAlgorithm) -> Box<dyn CongestionControl> {
647 match cc {
648 CongestionControlAlgorithm::NewReno => Box::new(ClassicCongestionControl::new(
649 NewReno::default(),
650 Pmtud::new(IP_ADDR, MTU),
651 )),
652 CongestionControlAlgorithm::Cubic => Box::new(ClassicCongestionControl::new(
653 Cubic::default(),
654 Pmtud::new(IP_ADDR, MTU),
655 )),
656 }
657 }
658
659 fn persistent_congestion_by_algorithm(
660 mut cc: Box<dyn CongestionControl>,
661 reduced_cwnd: usize,
662 lost_packets: &[SentPacket],
663 persistent_expected: bool,
664 ) {
665 for p in lost_packets {
666 cc.on_packet_sent(p, now());
667 }
668
669 cc.on_packets_lost(Some(now()), None, PTO, lost_packets, Instant::now());
670
671 let persistent = if cc.cwnd() == reduced_cwnd {
672 false
673 } else if cc.cwnd() == cc.cwnd_min() {
674 true
675 } else {
676 panic!("unexpected cwnd");
677 };
678 assert_eq!(persistent, persistent_expected);
679 }
680
681 fn persistent_congestion(lost_packets: &[SentPacket], persistent_expected: bool) {
682 let cc = congestion_control(CongestionControlAlgorithm::NewReno);
683 let cwnd_initial = cc.cwnd_initial();
684 persistent_congestion_by_algorithm(cc, cwnd_initial / 2, lost_packets, persistent_expected);
685
686 let cc = congestion_control(CongestionControlAlgorithm::Cubic);
687 let cwnd_initial = cc.cwnd_initial();
688 persistent_congestion_by_algorithm(
689 cc,
690 cwnd_initial * CUBIC_BETA_USIZE_DIVIDEND / CUBIC_BETA_USIZE_DIVISOR,
691 lost_packets,
692 persistent_expected,
693 );
694 }
695
696 /// A span of exactly the PC threshold only reduces the window on loss.
697 #[test]
698 fn persistent_congestion_none() {
699 persistent_congestion(&[lost(1, true, ZERO), lost(2, true, SUB_PC)], false);
700 }
701
702 /// A span of just more than the PC threshold causes persistent congestion.
703 #[test]
704 fn persistent_congestion_simple() {
705 persistent_congestion(&[lost(1, true, ZERO), lost(2, true, PC)], true);
706 }
707
708 /// Both packets need to be ack-eliciting.
709 #[test]
710 fn persistent_congestion_non_ack_eliciting() {
711 persistent_congestion(&[lost(1, false, ZERO), lost(2, true, PC)], false);
712 persistent_congestion(&[lost(1, true, ZERO), lost(2, false, PC)], false);
713 }
714
715 /// Packets in the middle, of any type, are OK.
716 #[test]
717 fn persistent_congestion_middle() {
718 persistent_congestion(
719 &[lost(1, true, ZERO), lost(2, false, RTT), lost(3, true, PC)],
720 true,
721 );
722 persistent_congestion(
723 &[lost(1, true, ZERO), lost(2, true, RTT), lost(3, true, PC)],
724 true,
725 );
726 }
727
728 /// Leading non-ack-eliciting packets are skipped.
729 #[test]
730 fn persistent_congestion_leading_non_ack_eliciting() {
731 persistent_congestion(
732 &[lost(1, false, ZERO), lost(2, true, RTT), lost(3, true, PC)],
733 false,
734 );
735 persistent_congestion(
736 &[
737 lost(1, false, ZERO),
738 lost(2, true, RTT),
739 lost(3, true, RTT + PC),
740 ],
741 true,
742 );
743 }
744
745 /// Trailing non-ack-eliciting packets aren't relevant.
746 #[test]
747 fn persistent_congestion_trailing_non_ack_eliciting() {
748 persistent_congestion(
749 &[
750 lost(1, true, ZERO),
751 lost(2, true, PC),
752 lost(3, false, PC + EPSILON),
753 ],
754 true,
755 );
756 persistent_congestion(
757 &[
758 lost(1, true, ZERO),
759 lost(2, true, SUB_PC),
760 lost(3, false, PC),
761 ],
762 false,
763 );
764 }
765
766 /// Gaps in the middle, of any type, restart the count.
767 #[test]
768 fn persistent_congestion_gap_reset() {
769 persistent_congestion(&[lost(1, true, ZERO), lost(3, true, PC)], false);
770 persistent_congestion(
771 &[
772 lost(1, true, ZERO),
773 lost(2, true, RTT),
774 lost(4, true, GAP),
775 lost(5, true, GAP + PTO * PERSISTENT_CONG_THRESH),
776 ],
777 false,
778 );
779 }
780
781 /// A span either side of a gap will cause persistent congestion.
782 #[test]
783 fn persistent_congestion_gap_or() {
784 persistent_congestion(
785 &[
786 lost(1, true, ZERO),
787 lost(2, true, PC),
788 lost(4, true, GAP),
789 lost(5, true, GAP + PTO),
790 ],
791 true,
792 );
793 persistent_congestion(
794 &[
795 lost(1, true, ZERO),
796 lost(2, true, PTO),
797 lost(4, true, GAP),
798 lost(5, true, GAP + PC),
799 ],
800 true,
801 );
802 }
803
804 /// A gap only restarts after an ack-eliciting packet.
805 #[test]
806 fn persistent_congestion_gap_non_ack_eliciting() {
807 persistent_congestion(
808 &[
809 lost(1, true, ZERO),
810 lost(2, true, PTO),
811 lost(4, false, GAP),
812 lost(5, true, GAP + PC),
813 ],
814 false,
815 );
816 persistent_congestion(
817 &[
818 lost(1, true, ZERO),
819 lost(2, true, PTO),
820 lost(4, false, GAP),
821 lost(5, true, GAP + RTT),
822 lost(6, true, GAP + RTT + SUB_PC),
823 ],
824 false,
825 );
826 persistent_congestion(
827 &[
828 lost(1, true, ZERO),
829 lost(2, true, PTO),
830 lost(4, false, GAP),
831 lost(5, true, GAP + RTT),
832 lost(6, true, GAP + RTT + PC),
833 ],
834 true,
835 );
836 }
837
838 /// Get a time, in multiples of `PTO`, relative to `now()`.
839 fn by_pto(t: u32) -> Instant {
840 now() + (PTO * t)
841 }
842
843 /// Make packets that will be made lost.
844 /// `times` is the time of sending, in multiples of `PTO`, relative to `now()`.
845 fn make_lost(times: &[u32]) -> Vec<SentPacket> {
846 times
847 .iter()
848 .enumerate()
849 .map(|(i, &t)| {
850 SentPacket::new(
851 PacketType::Short,
852 u64::try_from(i).unwrap(),
853 by_pto(t),
854 true,
855 Vec::new(),
856 1000,
857 )
858 })
859 .collect::<Vec<_>>()
860 }
861
862 /// Call `detect_persistent_congestion` using times relative to now and the fixed PTO time.
863 /// `last_ack` and `rtt_time` are times in multiples of `PTO`, relative to `now()`,
864 /// for the time of the largest acknowledged and the first RTT sample, respectively.
865 fn persistent_congestion_by_pto<T: WindowAdjustment>(
866 mut cc: ClassicCongestionControl<T>,
867 last_ack: u32,
868 rtt_time: u32,
869 lost: &[SentPacket],
870 ) -> bool {
871 let now = Instant::now();
872 assert_eq!(cc.cwnd(), cc.cwnd_initial());
873
874 let last_ack = Some(by_pto(last_ack));
875 let rtt_time = Some(by_pto(rtt_time));
876
877 // Persistent congestion is never declared if the RTT time is `None`.
878 cc.detect_persistent_congestion(None, None, PTO, lost.iter(), now);
879 assert_eq!(cc.cwnd(), cc.cwnd_initial());
880 cc.detect_persistent_congestion(None, last_ack, PTO, lost.iter(), now);
881 assert_eq!(cc.cwnd(), cc.cwnd_initial());
882
883 cc.detect_persistent_congestion(rtt_time, last_ack, PTO, lost.iter(), now);
884 cc.cwnd() == cc.cwnd_min()
885 }
886
887 /// No persistent congestion can be had if there are no lost packets.
888 #[test]
889 fn persistent_congestion_no_lost() {
890 let lost = make_lost(&[]);
891 assert!(!persistent_congestion_by_pto(
892 ClassicCongestionControl::new(NewReno::default(), Pmtud::new(IP_ADDR, MTU)),
893 0,
894 0,
895 &lost
896 ));
897 assert!(!persistent_congestion_by_pto(
898 ClassicCongestionControl::new(Cubic::default(), Pmtud::new(IP_ADDR, MTU)),
899 0,
900 0,
901 &lost
902 ));
903 }
904
905 /// No persistent congestion can be had if there is only one lost packet.
906 #[test]
907 fn persistent_congestion_one_lost() {
908 let lost = make_lost(&[1]);
909 assert!(!persistent_congestion_by_pto(
910 ClassicCongestionControl::new(NewReno::default(), Pmtud::new(IP_ADDR, MTU)),
911 0,
912 0,
913 &lost
914 ));
915 assert!(!persistent_congestion_by_pto(
916 ClassicCongestionControl::new(Cubic::default(), Pmtud::new(IP_ADDR, MTU)),
917 0,
918 0,
919 &lost
920 ));
921 }
922
923 /// Persistent congestion can't happen based on old packets.
924 #[test]
925 fn persistent_congestion_past() {
926 // Packets sent prior to either the last acknowledged or the first RTT
927 // sample are not considered. So 0 is ignored.
928 let lost = make_lost(&[0, PERSISTENT_CONG_THRESH + 1, PERSISTENT_CONG_THRESH + 2]);
929 assert!(!persistent_congestion_by_pto(
930 ClassicCongestionControl::new(NewReno::default(), Pmtud::new(IP_ADDR, MTU)),
931 1,
932 1,
933 &lost
934 ));
935 assert!(!persistent_congestion_by_pto(
936 ClassicCongestionControl::new(NewReno::default(), Pmtud::new(IP_ADDR, MTU)),
937 0,
938 1,
939 &lost
940 ));
941 assert!(!persistent_congestion_by_pto(
942 ClassicCongestionControl::new(NewReno::default(), Pmtud::new(IP_ADDR, MTU)),
943 1,
944 0,
945 &lost
946 ));
947 assert!(!persistent_congestion_by_pto(
948 ClassicCongestionControl::new(Cubic::default(), Pmtud::new(IP_ADDR, MTU)),
949 1,
950 1,
951 &lost
952 ));
953 assert!(!persistent_congestion_by_pto(
954 ClassicCongestionControl::new(Cubic::default(), Pmtud::new(IP_ADDR, MTU)),
955 0,
956 1,
957 &lost
958 ));
959 assert!(!persistent_congestion_by_pto(
960 ClassicCongestionControl::new(Cubic::default(), Pmtud::new(IP_ADDR, MTU)),
961 1,
962 0,
963 &lost
964 ));
965 }
966
967 /// Persistent congestion doesn't start unless the packet is ack-eliciting.
968 #[test]
969 fn persistent_congestion_ack_eliciting() {
970 let mut lost = make_lost(&[1, PERSISTENT_CONG_THRESH + 2]);
971 lost[0] = SentPacket::new(
972 lost[0].packet_type(),
973 lost[0].pn(),
974 lost[0].time_sent(),
975 false,
976 lost[0].tokens().to_vec(),
977 lost[0].len(),
978 );
979 assert!(!persistent_congestion_by_pto(
980 ClassicCongestionControl::new(NewReno::default(), Pmtud::new(IP_ADDR, MTU)),
981 0,
982 0,
983 &lost
984 ));
985 assert!(!persistent_congestion_by_pto(
986 ClassicCongestionControl::new(Cubic::default(), Pmtud::new(IP_ADDR, MTU)),
987 0,
988 0,
989 &lost
990 ));
991 }
992
993 /// Detect persistent congestion. Note that the first lost packet needs to have a time
994 /// greater than the previously acknowledged packet AND the first RTT sample. And the
995 /// difference in times needs to be greater than the persistent congestion threshold.
996 #[test]
997 fn persistent_congestion_min() {
998 let lost = make_lost(&[1, PERSISTENT_CONG_THRESH + 2]);
999 assert!(persistent_congestion_by_pto(
1000 ClassicCongestionControl::new(NewReno::default(), Pmtud::new(IP_ADDR, MTU)),
1001 0,
1002 0,
1003 &lost
1004 ));
1005 assert!(persistent_congestion_by_pto(
1006 ClassicCongestionControl::new(Cubic::default(), Pmtud::new(IP_ADDR, MTU)),
1007 0,
1008 0,
1009 &lost
1010 ));
1011 }
1012
1013 /// Make sure that not having a previous largest acknowledged also results
1014 /// in detecting persistent congestion. (This is not expected to happen, but
1015 /// the code permits it).
1016 #[test]
1017 fn persistent_congestion_no_prev_ack_newreno() {
1018 let lost = make_lost(&[1, PERSISTENT_CONG_THRESH + 2]);
1019 let mut cc = ClassicCongestionControl::new(NewReno::default(), Pmtud::new(IP_ADDR, MTU));
1020 cc.detect_persistent_congestion(Some(by_pto(0)), None, PTO, lost.iter(), Instant::now());
1021 assert_eq!(cc.cwnd(), cc.cwnd_min());
1022 }
1023
1024 #[test]
1025 fn persistent_congestion_no_prev_ack_cubic() {
1026 let lost = make_lost(&[1, PERSISTENT_CONG_THRESH + 2]);
1027 let mut cc = ClassicCongestionControl::new(Cubic::default(), Pmtud::new(IP_ADDR, MTU));
1028 cc.detect_persistent_congestion(Some(by_pto(0)), None, PTO, lost.iter(), Instant::now());
1029 assert_eq!(cc.cwnd(), cc.cwnd_min());
1030 }
1031
1032 /// The code asserts on ordering errors.
1033 #[test]
1034 #[should_panic(expected = "time is monotonic")]
1035 fn persistent_congestion_unsorted_newreno() {
1036 let lost = make_lost(&[PERSISTENT_CONG_THRESH + 2, 1]);
1037 assert!(!persistent_congestion_by_pto(
1038 ClassicCongestionControl::new(NewReno::default(), Pmtud::new(IP_ADDR, MTU)),
1039 0,
1040 0,
1041 &lost
1042 ));
1043 }
1044
1045 /// The code asserts on ordering errors.
1046 #[test]
1047 #[should_panic(expected = "time is monotonic")]
1048 fn persistent_congestion_unsorted_cubic() {
1049 let lost = make_lost(&[PERSISTENT_CONG_THRESH + 2, 1]);
1050 assert!(!persistent_congestion_by_pto(
1051 ClassicCongestionControl::new(Cubic::default(), Pmtud::new(IP_ADDR, MTU)),
1052 0,
1053 0,
1054 &lost
1055 ));
1056 }
1057
1058 #[test]
1059 fn app_limited_slow_start() {
1060 const BELOW_APP_LIMIT_PKTS: usize = 5;
1061 const ABOVE_APP_LIMIT_PKTS: usize = BELOW_APP_LIMIT_PKTS + 1;
1062 let mut cc = ClassicCongestionControl::new(NewReno::default(), Pmtud::new(IP_ADDR, MTU));
1063 let cwnd = cc.congestion_window;
1064 let mut now = now();
1065 let mut next_pn = 0;
1066
1067 // simulate packet bursts below app_limit
1068 for packet_burst_size in 1..=BELOW_APP_LIMIT_PKTS {
1069 // always stay below app_limit during sent.
1070 let mut pkts = Vec::new();
1071 for _ in 0..packet_burst_size {
1072 let p = SentPacket::new(
1073 PacketType::Short,
1074 next_pn,
1075 now,
1076 true,
1077 Vec::new(),
1078 cc.max_datagram_size(),
1079 );
1080 next_pn += 1;
1081 cc.on_packet_sent(&p, now);
1082 pkts.push(p);
1083 }
1084 assert_eq!(
1085 cc.bytes_in_flight(),
1086 packet_burst_size * cc.max_datagram_size()
1087 );
1088 now += RTT;
1089 cc.on_packets_acked(&pkts, &RttEstimate::default(), now);
1090 assert_eq!(cc.bytes_in_flight(), 0);
1091 assert_eq!(cc.acked_bytes, 0);
1092 assert_eq!(cwnd, cc.congestion_window); // CWND doesn't grow because we're app limited
1093 }
1094
1095 // Fully utilize the congestion window by sending enough packets to
1096 // have `bytes_in_flight` above the `app_limited` threshold.
1097 let mut pkts = Vec::new();
1098 for _ in 0..ABOVE_APP_LIMIT_PKTS {
1099 let p = SentPacket::new(
1100 PacketType::Short,
1101 next_pn,
1102 now,
1103 true,
1104 Vec::new(),
1105 cc.max_datagram_size(),
1106 );
1107 next_pn += 1;
1108 cc.on_packet_sent(&p, now);
1109 pkts.push(p);
1110 }
1111 assert_eq!(
1112 cc.bytes_in_flight(),
1113 ABOVE_APP_LIMIT_PKTS * cc.max_datagram_size()
1114 );
1115 now += RTT;
1116 // Check if congestion window gets increased for all packets currently in flight
1117 for (i, pkt) in pkts.into_iter().enumerate() {
1118 cc.on_packets_acked(&[pkt], &RttEstimate::default(), now);
1119
1120 assert_eq!(
1121 cc.bytes_in_flight(),
1122 (ABOVE_APP_LIMIT_PKTS - i - 1) * cc.max_datagram_size()
1123 );
1124 // increase acked_bytes with each packet
1125 qinfo!(
1126 "{} {}",
1127 cc.congestion_window,
1128 cwnd + i * cc.max_datagram_size()
1129 );
1130 assert_eq!(
1131 cc.congestion_window,
1132 cwnd + (i + 1) * cc.max_datagram_size()
1133 );
1134 assert_eq!(cc.acked_bytes, 0);
1135 }
1136 }
1137
1138 #[test]
1139 fn app_limited_congestion_avoidance() {
1140 const CWND_PKTS_CA: usize = CWND_INITIAL_PKTS / 2;
1141 const BELOW_APP_LIMIT_PKTS: usize = CWND_PKTS_CA - 2;
1142 const ABOVE_APP_LIMIT_PKTS: usize = BELOW_APP_LIMIT_PKTS + 1;
1143
1144 let mut cc = ClassicCongestionControl::new(NewReno::default(), Pmtud::new(IP_ADDR, MTU));
1145 let mut now = now();
1146
1147 // Change state to congestion avoidance by introducing loss.
1148
1149 let p_lost = SentPacket::new(
1150 PacketType::Short,
1151 1,
1152 now,
1153 true,
1154 Vec::new(),
1155 cc.max_datagram_size(),
1156 );
1157 cc.on_packet_sent(&p_lost, now);
1158 cwnd_is_default(&cc);
1159 now += PTO;
1160 cc.on_packets_lost(Some(now), None, PTO, &[p_lost], now);
1161 cwnd_is_halved(&cc);
1162 let p_not_lost = SentPacket::new(
1163 PacketType::Short,
1164 2,
1165 now,
1166 true,
1167 Vec::new(),
1168 cc.max_datagram_size(),
1169 );
1170 cc.on_packet_sent(&p_not_lost, now);
1171 now += RTT;
1172 cc.on_packets_acked(&[p_not_lost], &RttEstimate::default(), now);
1173 cwnd_is_halved(&cc);
1174 // cc is app limited therefore cwnd in not increased.
1175 assert_eq!(cc.acked_bytes, 0);
1176
1177 // Now we are in the congestion avoidance state.
1178 assert_eq!(cc.state, State::CongestionAvoidance);
1179 // simulate packet bursts below app_limit
1180 let mut next_pn = 3;
1181 for packet_burst_size in 1..=BELOW_APP_LIMIT_PKTS {
1182 // always stay below app_limit during sent.
1183 let mut pkts = Vec::new();
1184 for _ in 0..packet_burst_size {
1185 let p = SentPacket::new(
1186 PacketType::Short,
1187 next_pn,
1188 now,
1189 true,
1190 Vec::new(),
1191 cc.max_datagram_size(),
1192 );
1193 next_pn += 1;
1194 cc.on_packet_sent(&p, now);
1195 pkts.push(p);
1196 }
1197 assert_eq!(
1198 cc.bytes_in_flight(),
1199 packet_burst_size * cc.max_datagram_size()
1200 );
1201 now += RTT;
1202 for (i, pkt) in pkts.into_iter().enumerate() {
1203 cc.on_packets_acked(&[pkt], &RttEstimate::default(), now);
1204
1205 assert_eq!(
1206 cc.bytes_in_flight(),
1207 (packet_burst_size - i - 1) * cc.max_datagram_size()
1208 );
1209 cwnd_is_halved(&cc); // CWND doesn't grow because we're app limited
1210 assert_eq!(cc.acked_bytes, 0);
1211 }
1212 }
1213
1214 // Fully utilize the congestion window by sending enough packets to
1215 // have `bytes_in_flight` above the `app_limited` threshold.
1216 let mut pkts = Vec::new();
1217 for _ in 0..ABOVE_APP_LIMIT_PKTS {
1218 let p = SentPacket::new(
1219 PacketType::Short,
1220 next_pn,
1221 now,
1222 true,
1223 Vec::new(),
1224 cc.max_datagram_size(),
1225 );
1226 next_pn += 1;
1227 cc.on_packet_sent(&p, now);
1228 pkts.push(p);
1229 }
1230 assert_eq!(
1231 cc.bytes_in_flight(),
1232 ABOVE_APP_LIMIT_PKTS * cc.max_datagram_size()
1233 );
1234 now += RTT;
1235 let mut last_acked_bytes = 0;
1236 // Check if congestion window gets increased for all packets currently in flight
1237 for (i, pkt) in pkts.into_iter().enumerate() {
1238 cc.on_packets_acked(&[pkt], &RttEstimate::default(), now);
1239
1240 assert_eq!(
1241 cc.bytes_in_flight(),
1242 (ABOVE_APP_LIMIT_PKTS - i - 1) * cc.max_datagram_size()
1243 );
1244 // The cwnd doesn't increase, but the acked_bytes do, which will eventually lead to an
1245 // increase, once the number of bytes reaches the necessary level
1246 cwnd_is_halved(&cc);
1247 // increase acked_bytes with each packet
1248 assert_ne!(cc.acked_bytes, last_acked_bytes);
1249 last_acked_bytes = cc.acked_bytes;
1250 }
1251 }
1252
1253 #[test]
1254 fn ecn_ce() {
1255 let now = now();
1256 let mut cc = ClassicCongestionControl::new(NewReno::default(), Pmtud::new(IP_ADDR, MTU));
1257 let p_ce = SentPacket::new(
1258 PacketType::Short,
1259 1,
1260 now,
1261 true,
1262 Vec::new(),
1263 cc.max_datagram_size(),
1264 );
1265 cc.on_packet_sent(&p_ce, now);
1266 cwnd_is_default(&cc);
1267 assert_eq!(cc.state, State::SlowStart);
1268
1269 // Signal congestion (ECN CE) and thus change state to recovery start.
1270 cc.on_ecn_ce_received(&p_ce, now);
1271 cwnd_is_halved(&cc);
1272 assert_eq!(cc.state, State::RecoveryStart);
1273 }
1274 }