quiche/recovery/
mod.rs

1// Copyright (C) 2018-2019, Cloudflare, Inc.
2// All rights reserved.
3//
4// Redistribution and use in source and binary forms, with or without
5// modification, are permitted provided that the following conditions are
6// met:
7//
8//     * Redistributions of source code must retain the above copyright notice,
9//       this list of conditions and the following disclaimer.
10//
11//     * Redistributions in binary form must reproduce the above copyright
12//       notice, this list of conditions and the following disclaimer in the
13//       documentation and/or other materials provided with the distribution.
14//
15// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
16// IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
17// THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
18// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
19// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
20// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
21// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
22// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
23// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
24// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26
27use std::str::FromStr;
28use std::time::Duration;
29use std::time::Instant;
30
31use crate::frame;
32use crate::packet;
33use crate::ranges::RangeSet;
34pub(crate) use crate::recovery::bandwidth::Bandwidth;
35use crate::Config;
36use crate::Result;
37
38#[cfg(feature = "qlog")]
39use qlog::events::EventData;
40
41use smallvec::SmallVec;
42
43use self::congestion::recovery::LegacyRecovery;
44use self::gcongestion::GRecovery;
45pub use gcongestion::BbrBwLoReductionStrategy;
46pub use gcongestion::BbrParams;
47
48// Loss Recovery
49const INITIAL_PACKET_THRESHOLD: u64 = 3;
50
51const MAX_PACKET_THRESHOLD: u64 = 20;
52
53// Time threshold used to calculate the loss time.
54//
55// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.1.2
56const INITIAL_TIME_THRESHOLD: f64 = 9.0 / 8.0;
57
58// Reduce the sensitivity to packet reordering after the first reordering event.
59//
60// Packet reorder is not a real loss event so quickly reduce the sensitivity to
61// avoid penializing subsequent packet reordering.
62//
63// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.1.2
64//
65// Implementations MAY experiment with absolute thresholds, thresholds from
66// previous connections, adaptive thresholds, or the including of RTT variation.
67// Smaller thresholds reduce reordering resilience and increase spurious
68// retransmissions, and larger thresholds increase loss detection delay.
69const PACKET_REORDER_TIME_THRESHOLD: f64 = 5.0 / 4.0;
70
71// # Experiment: enable_relaxed_loss_threshold
72//
73// Time threshold overhead used to calculate the loss time.
74//
75// The actual threshold is calcualted as 1 + INITIAL_TIME_THRESHOLD_OVERHEAD and
76// equivalent to INITIAL_TIME_THRESHOLD.
77const INITIAL_TIME_THRESHOLD_OVERHEAD: f64 = 1.0 / 8.0;
78// # Experiment: enable_relaxed_loss_threshold
79//
80// The factor by which to increase the time threshold on spurious loss.
81const TIME_THRESHOLD_OVERHEAD_MULTIPLIER: f64 = 2.0;
82
83const GRANULARITY: Duration = Duration::from_millis(1);
84
85const MAX_PTO_PROBES_COUNT: usize = 2;
86
87const MINIMUM_WINDOW_PACKETS: usize = 2;
88
89const LOSS_REDUCTION_FACTOR: f64 = 0.5;
90
91// How many non ACK eliciting packets we send before including a PING to solicit
92// an ACK.
93pub(super) const MAX_OUTSTANDING_NON_ACK_ELICITING: usize = 24;
94
95#[derive(Default)]
96struct LossDetectionTimer {
97    time: Option<Instant>,
98}
99
100impl LossDetectionTimer {
101    fn update(&mut self, timeout: Instant) {
102        self.time = Some(timeout);
103    }
104
105    fn clear(&mut self) {
106        self.time = None;
107    }
108}
109
110impl std::fmt::Debug for LossDetectionTimer {
111    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
112        match self.time {
113            Some(v) => {
114                let now = Instant::now();
115                if v > now {
116                    let d = v.duration_since(now);
117                    write!(f, "{d:?}")
118                } else {
119                    write!(f, "exp")
120                }
121            },
122            None => write!(f, "none"),
123        }
124    }
125}
126
127#[derive(Clone, Copy, PartialEq)]
128pub struct RecoveryConfig {
129    pub initial_rtt: Duration,
130    pub max_send_udp_payload_size: usize,
131    pub max_ack_delay: Duration,
132    pub cc_algorithm: CongestionControlAlgorithm,
133    pub custom_bbr_params: Option<BbrParams>,
134    pub hystart: bool,
135    pub pacing: bool,
136    pub max_pacing_rate: Option<u64>,
137    pub initial_congestion_window_packets: usize,
138    pub enable_relaxed_loss_threshold: bool,
139}
140
141impl RecoveryConfig {
142    pub fn from_config(config: &Config) -> Self {
143        Self {
144            initial_rtt: config.initial_rtt,
145            max_send_udp_payload_size: config.max_send_udp_payload_size,
146            max_ack_delay: Duration::ZERO,
147            cc_algorithm: config.cc_algorithm,
148            custom_bbr_params: config.custom_bbr_params,
149            hystart: config.hystart,
150            pacing: config.pacing,
151            max_pacing_rate: config.max_pacing_rate,
152            initial_congestion_window_packets: config
153                .initial_congestion_window_packets,
154            enable_relaxed_loss_threshold: config.enable_relaxed_loss_threshold,
155        }
156    }
157}
158
159#[enum_dispatch::enum_dispatch(RecoveryOps)]
160#[allow(clippy::large_enum_variant)]
161#[derive(Debug)]
162pub(crate) enum Recovery {
163    Legacy(LegacyRecovery),
164    GCongestion(GRecovery),
165}
166
167#[derive(Debug, Default, PartialEq)]
168pub struct OnAckReceivedOutcome {
169    pub lost_packets: usize,
170    pub lost_bytes: usize,
171    pub acked_bytes: usize,
172    pub spurious_losses: usize,
173}
174
175#[derive(Debug, Default)]
176pub struct OnLossDetectionTimeoutOutcome {
177    pub lost_packets: usize,
178    pub lost_bytes: usize,
179}
180
181#[enum_dispatch::enum_dispatch]
182/// Api for the Recovery implementation
183pub trait RecoveryOps {
184    fn lost_count(&self) -> usize;
185    fn bytes_lost(&self) -> u64;
186
187    /// Returns whether or not we should elicit an ACK even if we wouldn't
188    /// otherwise have constructed an ACK eliciting packet.
189    fn should_elicit_ack(&self, epoch: packet::Epoch) -> bool;
190
191    fn get_acked_frames(&mut self, epoch: packet::Epoch) -> Vec<frame::Frame>;
192
193    fn get_lost_frames(&mut self, epoch: packet::Epoch) -> Vec<frame::Frame>;
194
195    fn get_largest_acked_on_epoch(&self, epoch: packet::Epoch) -> Option<u64>;
196    fn has_lost_frames(&self, epoch: packet::Epoch) -> bool;
197    fn loss_probes(&self, epoch: packet::Epoch) -> usize;
198    #[cfg(test)]
199    fn inc_loss_probes(&mut self, epoch: packet::Epoch);
200
201    fn ping_sent(&mut self, epoch: packet::Epoch);
202
203    fn on_packet_sent(
204        &mut self, pkt: Sent, epoch: packet::Epoch,
205        handshake_status: HandshakeStatus, now: Instant, trace_id: &str,
206    );
207    fn get_packet_send_time(&self, now: Instant) -> Instant;
208
209    #[allow(clippy::too_many_arguments)]
210    fn on_ack_received(
211        &mut self, ranges: &RangeSet, ack_delay: u64, epoch: packet::Epoch,
212        handshake_status: HandshakeStatus, now: Instant, skip_pn: Option<u64>,
213        trace_id: &str,
214    ) -> Result<OnAckReceivedOutcome>;
215
216    fn on_loss_detection_timeout(
217        &mut self, handshake_status: HandshakeStatus, now: Instant,
218        trace_id: &str,
219    ) -> OnLossDetectionTimeoutOutcome;
220    fn on_pkt_num_space_discarded(
221        &mut self, epoch: packet::Epoch, handshake_status: HandshakeStatus,
222        now: Instant,
223    );
224    fn on_path_change(
225        &mut self, epoch: packet::Epoch, now: Instant, _trace_id: &str,
226    ) -> (usize, usize);
227    fn loss_detection_timer(&self) -> Option<Instant>;
228    fn cwnd(&self) -> usize;
229    fn cwnd_available(&self) -> usize;
230    fn rtt(&self) -> Duration;
231
232    fn min_rtt(&self) -> Option<Duration>;
233
234    fn max_rtt(&self) -> Option<Duration>;
235
236    fn rttvar(&self) -> Duration;
237
238    fn pto(&self) -> Duration;
239
240    /// The most recent data delivery rate estimate.
241    fn delivery_rate(&self) -> Bandwidth;
242
243    /// Maximum bandwidth estimate, if one is available.
244    fn max_bandwidth(&self) -> Option<Bandwidth>;
245
246    /// Statistics from when a CCA first exited the startup phase.
247    fn startup_exit(&self) -> Option<StartupExit>;
248
249    fn max_datagram_size(&self) -> usize;
250
251    fn pmtud_update_max_datagram_size(&mut self, new_max_datagram_size: usize);
252
253    fn update_max_datagram_size(&mut self, new_max_datagram_size: usize);
254
255    fn on_app_limited(&mut self);
256
257    // Since a recovery module is path specific, this tracks the largest packet
258    // sent per path.
259    #[cfg(test)]
260    fn largest_sent_pkt_num_on_path(&self, epoch: packet::Epoch) -> Option<u64>;
261
262    #[cfg(test)]
263    fn app_limited(&self) -> bool;
264
265    #[cfg(test)]
266    fn sent_packets_len(&self, epoch: packet::Epoch) -> usize;
267
268    #[cfg(test)]
269    fn bytes_in_flight(&self) -> usize;
270
271    fn bytes_in_flight_duration(&self) -> Duration;
272
273    #[cfg(test)]
274    fn in_flight_count(&self, epoch: packet::Epoch) -> usize;
275
276    #[cfg(test)]
277    fn pacing_rate(&self) -> u64;
278
279    #[cfg(test)]
280    fn pto_count(&self) -> u32;
281
282    // This value might be `None` when experiment `enable_relaxed_loss_threshold`
283    // is enabled for gcongestion
284    #[cfg(test)]
285    fn pkt_thresh(&self) -> Option<u64>;
286
287    #[cfg(test)]
288    fn time_thresh(&self) -> f64;
289
290    #[cfg(test)]
291    fn lost_spurious_count(&self) -> usize;
292
293    #[cfg(test)]
294    fn detect_lost_packets_for_test(
295        &mut self, epoch: packet::Epoch, now: Instant,
296    ) -> (usize, usize);
297
298    fn update_app_limited(&mut self, v: bool);
299
300    fn delivery_rate_update_app_limited(&mut self, v: bool);
301
302    fn update_max_ack_delay(&mut self, max_ack_delay: Duration);
303
304    #[cfg(feature = "qlog")]
305    fn state_str(&self, now: Instant) -> &'static str;
306
307    #[cfg(feature = "qlog")]
308    fn get_updated_qlog_event_data(&mut self) -> Option<EventData>;
309
310    #[cfg(feature = "qlog")]
311    fn get_updated_qlog_cc_state(&mut self, now: Instant)
312        -> Option<&'static str>;
313
314    fn send_quantum(&self) -> usize;
315
316    fn get_next_release_time(&self) -> ReleaseDecision;
317
318    fn gcongestion_enabled(&self) -> bool;
319}
320
321impl Recovery {
322    pub fn new_with_config(recovery_config: &RecoveryConfig) -> Self {
323        let grecovery = GRecovery::new(recovery_config);
324        if let Some(grecovery) = grecovery {
325            Recovery::from(grecovery)
326        } else {
327            Recovery::from(LegacyRecovery::new_with_config(recovery_config))
328        }
329    }
330
331    #[cfg(feature = "qlog")]
332    pub fn maybe_qlog(
333        &mut self, qlog: &mut qlog::streamer::QlogStreamer, now: Instant,
334    ) {
335        if let Some(ev_data) = self.get_updated_qlog_event_data() {
336            qlog.add_event_data_with_instant(ev_data, now).ok();
337        }
338
339        if let Some(cc_state) = self.get_updated_qlog_cc_state(now) {
340            let ev_data = EventData::CongestionStateUpdated(
341                qlog::events::quic::CongestionStateUpdated {
342                    old: None,
343                    new: cc_state.to_string(),
344                    trigger: None,
345                },
346            );
347
348            qlog.add_event_data_with_instant(ev_data, now).ok();
349        }
350    }
351
352    #[cfg(test)]
353    pub fn new(config: &Config) -> Self {
354        Self::new_with_config(&RecoveryConfig::from_config(config))
355    }
356}
357
358/// Available congestion control algorithms.
359///
360/// This enum provides currently available list of congestion control
361/// algorithms.
362#[derive(Debug, Copy, Clone, PartialEq, Eq)]
363#[repr(C)]
364pub enum CongestionControlAlgorithm {
365    /// Reno congestion control algorithm. `reno` in a string form.
366    Reno            = 0,
367    /// CUBIC congestion control algorithm (default). `cubic` in a string form.
368    CUBIC           = 1,
369    /// BBR congestion control algorithm. `bbr` in a string form.
370    BBR             = 2,
371    /// BBRv2 congestion control algorithm. `bbr2` in a string form.
372    BBR2            = 3,
373    /// BBRv2 congestion control algorithm implementation from gcongestion
374    /// branch. `bbr2_gcongestion` in a string form.
375    Bbr2Gcongestion = 4,
376}
377
378impl FromStr for CongestionControlAlgorithm {
379    type Err = crate::Error;
380
381    /// Converts a string to `CongestionControlAlgorithm`.
382    ///
383    /// If `name` is not valid, `Error::CongestionControl` is returned.
384    fn from_str(name: &str) -> std::result::Result<Self, Self::Err> {
385        match name {
386            "reno" => Ok(CongestionControlAlgorithm::Reno),
387            "cubic" => Ok(CongestionControlAlgorithm::CUBIC),
388            "bbr" => Ok(CongestionControlAlgorithm::BBR),
389            #[cfg(not(feature = "gcongestion"))]
390            "bbr2" => Ok(CongestionControlAlgorithm::BBR2),
391            #[cfg(feature = "gcongestion")]
392            "bbr2" => Ok(CongestionControlAlgorithm::Bbr2Gcongestion),
393            "bbr2_gcongestion" => Ok(CongestionControlAlgorithm::Bbr2Gcongestion),
394            _ => Err(crate::Error::CongestionControl),
395        }
396    }
397}
398
399#[derive(Clone)]
400pub struct Sent {
401    pub pkt_num: u64,
402
403    pub frames: SmallVec<[frame::Frame; 1]>,
404
405    pub time_sent: Instant,
406
407    pub time_acked: Option<Instant>,
408
409    pub time_lost: Option<Instant>,
410
411    pub size: usize,
412
413    pub ack_eliciting: bool,
414
415    pub in_flight: bool,
416
417    pub delivered: usize,
418
419    pub delivered_time: Instant,
420
421    pub first_sent_time: Instant,
422
423    pub is_app_limited: bool,
424
425    pub tx_in_flight: usize,
426
427    pub lost: u64,
428
429    pub has_data: bool,
430
431    pub is_pmtud_probe: bool,
432}
433
434impl std::fmt::Debug for Sent {
435    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
436        write!(f, "pkt_num={:?} ", self.pkt_num)?;
437        write!(f, "pkt_sent_time={:?} ", self.time_sent)?;
438        write!(f, "pkt_size={:?} ", self.size)?;
439        write!(f, "delivered={:?} ", self.delivered)?;
440        write!(f, "delivered_time={:?} ", self.delivered_time)?;
441        write!(f, "first_sent_time={:?} ", self.first_sent_time)?;
442        write!(f, "is_app_limited={} ", self.is_app_limited)?;
443        write!(f, "tx_in_flight={} ", self.tx_in_flight)?;
444        write!(f, "lost={} ", self.lost)?;
445        write!(f, "has_data={} ", self.has_data)?;
446        write!(f, "is_pmtud_probe={}", self.is_pmtud_probe)?;
447
448        Ok(())
449    }
450}
451
452#[derive(Clone, Copy, Debug)]
453pub struct HandshakeStatus {
454    pub has_handshake_keys: bool,
455
456    pub peer_verified_address: bool,
457
458    pub completed: bool,
459}
460
461#[cfg(test)]
462impl Default for HandshakeStatus {
463    fn default() -> HandshakeStatus {
464        HandshakeStatus {
465            has_handshake_keys: true,
466
467            peer_verified_address: true,
468
469            completed: true,
470        }
471    }
472}
473
474// We don't need to log all qlog metrics every time there is a recovery event.
475// Instead, we can log only the MetricsUpdated event data fields that we care
476// about, only when they change. To support this, the QLogMetrics structure
477// keeps a running picture of the fields.
478#[derive(Default)]
479#[cfg(feature = "qlog")]
480struct QlogMetrics {
481    min_rtt: Duration,
482    smoothed_rtt: Duration,
483    latest_rtt: Duration,
484    rttvar: Duration,
485    cwnd: u64,
486    bytes_in_flight: u64,
487    ssthresh: Option<u64>,
488    pacing_rate: u64,
489}
490
491#[cfg(feature = "qlog")]
492impl QlogMetrics {
493    // Make a qlog event if the latest instance of QlogMetrics is different.
494    //
495    // This function diffs each of the fields. A qlog MetricsUpdated event is
496    // only generated if at least one field is different. Where fields are
497    // different, the qlog event contains the latest value.
498    fn maybe_update(&mut self, latest: Self) -> Option<EventData> {
499        let mut emit_event = false;
500
501        let new_min_rtt = if self.min_rtt != latest.min_rtt {
502            self.min_rtt = latest.min_rtt;
503            emit_event = true;
504            Some(latest.min_rtt.as_secs_f32() * 1000.0)
505        } else {
506            None
507        };
508
509        let new_smoothed_rtt = if self.smoothed_rtt != latest.smoothed_rtt {
510            self.smoothed_rtt = latest.smoothed_rtt;
511            emit_event = true;
512            Some(latest.smoothed_rtt.as_secs_f32() * 1000.0)
513        } else {
514            None
515        };
516
517        let new_latest_rtt = if self.latest_rtt != latest.latest_rtt {
518            self.latest_rtt = latest.latest_rtt;
519            emit_event = true;
520            Some(latest.latest_rtt.as_secs_f32() * 1000.0)
521        } else {
522            None
523        };
524
525        let new_rttvar = if self.rttvar != latest.rttvar {
526            self.rttvar = latest.rttvar;
527            emit_event = true;
528            Some(latest.rttvar.as_secs_f32() * 1000.0)
529        } else {
530            None
531        };
532
533        let new_cwnd = if self.cwnd != latest.cwnd {
534            self.cwnd = latest.cwnd;
535            emit_event = true;
536            Some(latest.cwnd)
537        } else {
538            None
539        };
540
541        let new_bytes_in_flight =
542            if self.bytes_in_flight != latest.bytes_in_flight {
543                self.bytes_in_flight = latest.bytes_in_flight;
544                emit_event = true;
545                Some(latest.bytes_in_flight)
546            } else {
547                None
548            };
549
550        let new_ssthresh = if self.ssthresh != latest.ssthresh {
551            self.ssthresh = latest.ssthresh;
552            emit_event = true;
553            latest.ssthresh
554        } else {
555            None
556        };
557
558        let new_pacing_rate = if self.pacing_rate != latest.pacing_rate {
559            self.pacing_rate = latest.pacing_rate;
560            emit_event = true;
561            Some(latest.pacing_rate)
562        } else {
563            None
564        };
565
566        if emit_event {
567            // QVis can't use all these fields and they can be large.
568            return Some(EventData::MetricsUpdated(
569                qlog::events::quic::MetricsUpdated {
570                    min_rtt: new_min_rtt,
571                    smoothed_rtt: new_smoothed_rtt,
572                    latest_rtt: new_latest_rtt,
573                    rtt_variance: new_rttvar,
574                    congestion_window: new_cwnd,
575                    bytes_in_flight: new_bytes_in_flight,
576                    ssthresh: new_ssthresh,
577                    pacing_rate: new_pacing_rate,
578                    ..Default::default()
579                },
580            ));
581        }
582
583        None
584    }
585}
586
587/// When the pacer thinks is a good time to release the next packet
588#[derive(Debug, Clone, Copy, PartialEq, Eq)]
589pub enum ReleaseTime {
590    Immediate,
591    At(Instant),
592}
593
594/// When the next packet should be release and if it can be part of a burst
595#[derive(Clone, Copy, Debug, PartialEq, Eq)]
596pub struct ReleaseDecision {
597    time: ReleaseTime,
598    allow_burst: bool,
599}
600
601impl ReleaseTime {
602    /// Add the specific delay to the current time
603    #[allow(dead_code)]
604    fn inc(&mut self, delay: Duration) {
605        match self {
606            ReleaseTime::Immediate => {},
607            ReleaseTime::At(time) => *time += delay,
608        }
609    }
610
611    /// Set the time to the later of two times
612    #[allow(dead_code)]
613    fn set_max(&mut self, other: Instant) {
614        match self {
615            ReleaseTime::Immediate => *self = ReleaseTime::At(other),
616            ReleaseTime::At(time) => *self = ReleaseTime::At(other.max(*time)),
617        }
618    }
619}
620
621impl ReleaseDecision {
622    pub(crate) const EQUAL_THRESHOLD: Duration = Duration::from_micros(50);
623
624    /// Get the [`Instant`] the next packet should be released. It will never be
625    /// in the past.
626    #[allow(dead_code)]
627    #[inline]
628    pub fn time(&self, now: Instant) -> Option<Instant> {
629        match self.time {
630            ReleaseTime::Immediate => None,
631            ReleaseTime::At(other) => other.gt(&now).then_some(other),
632        }
633    }
634
635    /// Can this packet be appended to a previous burst
636    #[allow(dead_code)]
637    #[inline]
638    pub fn can_burst(&self) -> bool {
639        self.allow_burst
640    }
641
642    /// Check if the two packets can be released at the same time
643    #[allow(dead_code)]
644    #[inline]
645    pub fn time_eq(&self, other: &Self, now: Instant) -> bool {
646        let delta = match (self.time(now), other.time(now)) {
647            (None, None) => Duration::ZERO,
648            (Some(t), None) | (None, Some(t)) => t.duration_since(now),
649            (Some(t1), Some(t2)) if t1 < t2 => t2.duration_since(t1),
650            (Some(t1), Some(t2)) => t1.duration_since(t2),
651        };
652
653        delta <= Self::EQUAL_THRESHOLD
654    }
655}
656
657/// Recovery statistics
658#[derive(Default, Debug)]
659pub struct RecoveryStats {
660    startup_exit: Option<StartupExit>,
661}
662
663impl RecoveryStats {
664    // Record statistics when a CCA first exits startup.
665    pub fn set_startup_exit(&mut self, startup_exit: StartupExit) {
666        if self.startup_exit.is_none() {
667            self.startup_exit = Some(startup_exit);
668        }
669    }
670}
671
672/// Statistics from when a CCA first exited the startup phase.
673#[derive(Debug, Clone, Copy, PartialEq)]
674pub struct StartupExit {
675    /// The congestion_window recorded at Startup exit.
676    pub cwnd: usize,
677
678    /// The bandwidth estimate recorded at Startup exit.
679    pub bandwidth: Option<u64>,
680
681    /// The reason a CCA exited the startup phase.
682    pub reason: StartupExitReason,
683}
684
685impl StartupExit {
686    fn new(
687        cwnd: usize, bandwidth: Option<Bandwidth>, reason: StartupExitReason,
688    ) -> Self {
689        let bandwidth = bandwidth.map(Bandwidth::to_bytes_per_second);
690        Self {
691            cwnd,
692            bandwidth,
693            reason,
694        }
695    }
696}
697
698/// The reason a CCA exited the startup phase.
699#[derive(Debug, Clone, Copy, PartialEq)]
700pub enum StartupExitReason {
701    /// Exit startup due to excessive loss
702    Loss,
703
704    /// Exit startup due to bandwidth plateau.
705    BandwidthPlateau,
706
707    /// Exit startup due to persistent queue.
708    PersistentQueue,
709}
710
711#[cfg(test)]
712mod tests {
713    use super::*;
714    use crate::packet;
715    use crate::recovery::congestion::PACING_MULTIPLIER;
716    use crate::test_utils;
717    use crate::CongestionControlAlgorithm;
718    use crate::DEFAULT_INITIAL_RTT;
719    use rstest::rstest;
720    use smallvec::smallvec;
721    use std::str::FromStr;
722
723    fn recovery_for_alg(algo: CongestionControlAlgorithm) -> Recovery {
724        let mut cfg = Config::new(crate::PROTOCOL_VERSION).unwrap();
725        cfg.set_cc_algorithm(algo);
726        Recovery::new(&cfg)
727    }
728
729    #[test]
730    fn lookup_cc_algo_ok() {
731        let algo = CongestionControlAlgorithm::from_str("reno").unwrap();
732        assert_eq!(algo, CongestionControlAlgorithm::Reno);
733        assert!(!recovery_for_alg(algo).gcongestion_enabled());
734
735        let algo = CongestionControlAlgorithm::from_str("cubic").unwrap();
736        assert_eq!(algo, CongestionControlAlgorithm::CUBIC);
737        assert!(!recovery_for_alg(algo).gcongestion_enabled());
738
739        let algo = CongestionControlAlgorithm::from_str("bbr").unwrap();
740        assert_eq!(algo, CongestionControlAlgorithm::BBR);
741        assert!(!recovery_for_alg(algo).gcongestion_enabled());
742
743        let algo = CongestionControlAlgorithm::from_str("bbr2").unwrap();
744        #[cfg(not(feature = "gcongestion"))]
745        {
746            assert_eq!(algo, CongestionControlAlgorithm::BBR2);
747            assert!(!recovery_for_alg(algo).gcongestion_enabled());
748        }
749        #[cfg(feature = "gcongestion")]
750        {
751            assert_eq!(algo, CongestionControlAlgorithm::Bbr2Gcongestion);
752            assert!(recovery_for_alg(algo).gcongestion_enabled());
753        }
754
755        let algo =
756            CongestionControlAlgorithm::from_str("bbr2_gcongestion").unwrap();
757        assert_eq!(algo, CongestionControlAlgorithm::Bbr2Gcongestion);
758        assert!(recovery_for_alg(algo).gcongestion_enabled());
759    }
760
761    #[test]
762    fn lookup_cc_algo_bad() {
763        assert_eq!(
764            CongestionControlAlgorithm::from_str("???"),
765            Err(crate::Error::CongestionControl)
766        );
767    }
768
769    #[rstest]
770    fn loss_on_pto(
771        #[values("reno", "cubic", "bbr", "bbr2", "bbr2_gcongestion")]
772        cc_algorithm_name: &str,
773    ) {
774        let mut cfg = Config::new(crate::PROTOCOL_VERSION).unwrap();
775        assert_eq!(cfg.set_cc_algorithm_name(cc_algorithm_name), Ok(()));
776
777        let mut r = Recovery::new(&cfg);
778
779        let mut now = Instant::now();
780
781        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 0);
782
783        // Start by sending a few packets.
784        let p = Sent {
785            pkt_num: 0,
786            frames: smallvec![],
787            time_sent: now,
788            time_acked: None,
789            time_lost: None,
790            size: 1000,
791            ack_eliciting: true,
792            in_flight: true,
793            delivered: 0,
794            delivered_time: now,
795            first_sent_time: now,
796            is_app_limited: false,
797            tx_in_flight: 0,
798            lost: 0,
799            has_data: false,
800            is_pmtud_probe: false,
801        };
802
803        r.on_packet_sent(
804            p,
805            packet::Epoch::Application,
806            HandshakeStatus::default(),
807            now,
808            "",
809        );
810
811        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 1);
812        assert_eq!(r.bytes_in_flight(), 1000);
813        assert_eq!(r.bytes_in_flight_duration(), Duration::ZERO);
814
815        let p = Sent {
816            pkt_num: 1,
817            frames: smallvec![],
818            time_sent: now,
819            time_acked: None,
820            time_lost: None,
821            size: 1000,
822            ack_eliciting: true,
823            in_flight: true,
824            delivered: 0,
825            delivered_time: now,
826            first_sent_time: now,
827            is_app_limited: false,
828            tx_in_flight: 0,
829            lost: 0,
830            has_data: false,
831            is_pmtud_probe: false,
832        };
833
834        r.on_packet_sent(
835            p,
836            packet::Epoch::Application,
837            HandshakeStatus::default(),
838            now,
839            "",
840        );
841
842        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 2);
843        assert_eq!(r.bytes_in_flight(), 2000);
844        assert_eq!(r.bytes_in_flight_duration(), Duration::ZERO);
845
846        let p = Sent {
847            pkt_num: 2,
848            frames: smallvec![],
849            time_sent: now,
850            time_acked: None,
851            time_lost: None,
852            size: 1000,
853            ack_eliciting: true,
854            in_flight: true,
855            delivered: 0,
856            delivered_time: now,
857            first_sent_time: now,
858            is_app_limited: false,
859            tx_in_flight: 0,
860            lost: 0,
861            has_data: false,
862            is_pmtud_probe: false,
863        };
864
865        r.on_packet_sent(
866            p,
867            packet::Epoch::Application,
868            HandshakeStatus::default(),
869            now,
870            "",
871        );
872        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 3);
873        assert_eq!(r.bytes_in_flight(), 3000);
874        assert_eq!(r.bytes_in_flight_duration(), Duration::ZERO);
875
876        let p = Sent {
877            pkt_num: 3,
878            frames: smallvec![],
879            time_sent: now,
880            time_acked: None,
881            time_lost: None,
882            size: 1000,
883            ack_eliciting: true,
884            in_flight: true,
885            delivered: 0,
886            delivered_time: now,
887            first_sent_time: now,
888            is_app_limited: false,
889            tx_in_flight: 0,
890            lost: 0,
891            has_data: false,
892            is_pmtud_probe: false,
893        };
894
895        r.on_packet_sent(
896            p,
897            packet::Epoch::Application,
898            HandshakeStatus::default(),
899            now,
900            "",
901        );
902        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 4);
903        assert_eq!(r.bytes_in_flight(), 4000);
904        assert_eq!(r.bytes_in_flight_duration(), Duration::ZERO);
905
906        // Wait for 10ms.
907        now += Duration::from_millis(10);
908
909        // Only the first 2 packets are acked.
910        let mut acked = RangeSet::default();
911        acked.insert(0..2);
912
913        assert_eq!(
914            r.on_ack_received(
915                &acked,
916                25,
917                packet::Epoch::Application,
918                HandshakeStatus::default(),
919                now,
920                None,
921                "",
922            )
923            .unwrap(),
924            OnAckReceivedOutcome {
925                lost_packets: 0,
926                lost_bytes: 0,
927                acked_bytes: 2 * 1000,
928                spurious_losses: 0,
929            }
930        );
931
932        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 2);
933        assert_eq!(r.bytes_in_flight(), 2000);
934        assert_eq!(r.bytes_in_flight_duration(), Duration::from_millis(10));
935        assert_eq!(r.lost_count(), 0);
936
937        // Wait until loss detection timer expires.
938        now = r.loss_detection_timer().unwrap();
939
940        // PTO.
941        r.on_loss_detection_timeout(HandshakeStatus::default(), now, "");
942        assert_eq!(r.loss_probes(packet::Epoch::Application), 1);
943        assert_eq!(r.lost_count(), 0);
944        assert_eq!(r.pto_count(), 1);
945
946        let p = Sent {
947            pkt_num: 4,
948            frames: smallvec![],
949            time_sent: now,
950            time_acked: None,
951            time_lost: None,
952            size: 1000,
953            ack_eliciting: true,
954            in_flight: true,
955            delivered: 0,
956            delivered_time: now,
957            first_sent_time: now,
958            is_app_limited: false,
959            tx_in_flight: 0,
960            lost: 0,
961            has_data: false,
962            is_pmtud_probe: false,
963        };
964
965        r.on_packet_sent(
966            p,
967            packet::Epoch::Application,
968            HandshakeStatus::default(),
969            now,
970            "",
971        );
972        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 3);
973        assert_eq!(r.bytes_in_flight(), 3000);
974        assert_eq!(r.bytes_in_flight_duration(), Duration::from_millis(30));
975
976        let p = Sent {
977            pkt_num: 5,
978            frames: smallvec![],
979            time_sent: now,
980            time_acked: None,
981            time_lost: None,
982            size: 1000,
983            ack_eliciting: true,
984            in_flight: true,
985            delivered: 0,
986            delivered_time: now,
987            first_sent_time: now,
988            is_app_limited: false,
989            tx_in_flight: 0,
990            lost: 0,
991            has_data: false,
992            is_pmtud_probe: false,
993        };
994
995        r.on_packet_sent(
996            p,
997            packet::Epoch::Application,
998            HandshakeStatus::default(),
999            now,
1000            "",
1001        );
1002        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 4);
1003        assert_eq!(r.bytes_in_flight(), 4000);
1004        assert_eq!(r.bytes_in_flight_duration(), Duration::from_millis(30));
1005        assert_eq!(r.lost_count(), 0);
1006
1007        // Wait for 10ms.
1008        now += Duration::from_millis(10);
1009
1010        // PTO packets are acked.
1011        let mut acked = RangeSet::default();
1012        acked.insert(4..6);
1013
1014        assert_eq!(
1015            r.on_ack_received(
1016                &acked,
1017                25,
1018                packet::Epoch::Application,
1019                HandshakeStatus::default(),
1020                now,
1021                None,
1022                "",
1023            )
1024            .unwrap(),
1025            OnAckReceivedOutcome {
1026                lost_packets: 2,
1027                lost_bytes: 2000,
1028                acked_bytes: 2 * 1000,
1029                spurious_losses: 0,
1030            }
1031        );
1032
1033        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 4);
1034        assert_eq!(r.bytes_in_flight(), 0);
1035        assert_eq!(r.bytes_in_flight_duration(), Duration::from_millis(40));
1036
1037        assert_eq!(r.lost_count(), 2);
1038
1039        // Wait 1 RTT.
1040        now += r.rtt();
1041
1042        assert_eq!(
1043            r.detect_lost_packets_for_test(packet::Epoch::Application, now),
1044            (0, 0)
1045        );
1046
1047        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 0);
1048        if cc_algorithm_name == "reno" || cc_algorithm_name == "cubic" {
1049            assert!(r.startup_exit().is_some());
1050            assert_eq!(r.startup_exit().unwrap().reason, StartupExitReason::Loss);
1051        } else {
1052            assert_eq!(r.startup_exit(), None);
1053        }
1054    }
1055
1056    #[rstest]
1057    fn loss_on_timer(
1058        #[values("reno", "cubic", "bbr", "bbr2", "bbr2_gcongestion")]
1059        cc_algorithm_name: &str,
1060    ) {
1061        let mut cfg = Config::new(crate::PROTOCOL_VERSION).unwrap();
1062        assert_eq!(cfg.set_cc_algorithm_name(cc_algorithm_name), Ok(()));
1063
1064        let mut r = Recovery::new(&cfg);
1065
1066        let mut now = Instant::now();
1067
1068        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 0);
1069
1070        // Start by sending a few packets.
1071        let p = Sent {
1072            pkt_num: 0,
1073            frames: smallvec![],
1074            time_sent: now,
1075            time_acked: None,
1076            time_lost: None,
1077            size: 1000,
1078            ack_eliciting: true,
1079            in_flight: true,
1080            delivered: 0,
1081            delivered_time: now,
1082            first_sent_time: now,
1083            is_app_limited: false,
1084            tx_in_flight: 0,
1085            lost: 0,
1086            has_data: false,
1087            is_pmtud_probe: false,
1088        };
1089
1090        r.on_packet_sent(
1091            p,
1092            packet::Epoch::Application,
1093            HandshakeStatus::default(),
1094            now,
1095            "",
1096        );
1097        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 1);
1098        assert_eq!(r.bytes_in_flight(), 1000);
1099        assert_eq!(r.bytes_in_flight_duration(), Duration::ZERO);
1100
1101        let p = Sent {
1102            pkt_num: 1,
1103            frames: smallvec![],
1104            time_sent: now,
1105            time_acked: None,
1106            time_lost: None,
1107            size: 1000,
1108            ack_eliciting: true,
1109            in_flight: true,
1110            delivered: 0,
1111            delivered_time: now,
1112            first_sent_time: now,
1113            is_app_limited: false,
1114            tx_in_flight: 0,
1115            lost: 0,
1116            has_data: false,
1117            is_pmtud_probe: false,
1118        };
1119
1120        r.on_packet_sent(
1121            p,
1122            packet::Epoch::Application,
1123            HandshakeStatus::default(),
1124            now,
1125            "",
1126        );
1127        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 2);
1128        assert_eq!(r.bytes_in_flight(), 2000);
1129        assert_eq!(r.bytes_in_flight_duration(), Duration::ZERO);
1130
1131        let p = Sent {
1132            pkt_num: 2,
1133            frames: smallvec![],
1134            time_sent: now,
1135            time_acked: None,
1136            time_lost: None,
1137            size: 1000,
1138            ack_eliciting: true,
1139            in_flight: true,
1140            delivered: 0,
1141            delivered_time: now,
1142            first_sent_time: now,
1143            is_app_limited: false,
1144            tx_in_flight: 0,
1145            lost: 0,
1146            has_data: false,
1147            is_pmtud_probe: false,
1148        };
1149
1150        r.on_packet_sent(
1151            p,
1152            packet::Epoch::Application,
1153            HandshakeStatus::default(),
1154            now,
1155            "",
1156        );
1157        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 3);
1158        assert_eq!(r.bytes_in_flight(), 3000);
1159        assert_eq!(r.bytes_in_flight_duration(), Duration::ZERO);
1160
1161        let p = Sent {
1162            pkt_num: 3,
1163            frames: smallvec![],
1164            time_sent: now,
1165            time_acked: None,
1166            time_lost: None,
1167            size: 1000,
1168            ack_eliciting: true,
1169            in_flight: true,
1170            delivered: 0,
1171            delivered_time: now,
1172            first_sent_time: now,
1173            is_app_limited: false,
1174            tx_in_flight: 0,
1175            lost: 0,
1176            has_data: false,
1177            is_pmtud_probe: false,
1178        };
1179
1180        r.on_packet_sent(
1181            p,
1182            packet::Epoch::Application,
1183            HandshakeStatus::default(),
1184            now,
1185            "",
1186        );
1187        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 4);
1188        assert_eq!(r.bytes_in_flight(), 4000);
1189        assert_eq!(r.bytes_in_flight_duration(), Duration::ZERO);
1190
1191        // Wait for 10ms.
1192        now += Duration::from_millis(10);
1193
1194        // Only the first 2 packets and the last one are acked.
1195        let mut acked = RangeSet::default();
1196        acked.insert(0..2);
1197        acked.insert(3..4);
1198
1199        assert_eq!(
1200            r.on_ack_received(
1201                &acked,
1202                25,
1203                packet::Epoch::Application,
1204                HandshakeStatus::default(),
1205                now,
1206                None,
1207                "",
1208            )
1209            .unwrap(),
1210            OnAckReceivedOutcome {
1211                lost_packets: 0,
1212                lost_bytes: 0,
1213                acked_bytes: 3 * 1000,
1214                spurious_losses: 0,
1215            }
1216        );
1217
1218        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 2);
1219        assert_eq!(r.bytes_in_flight(), 1000);
1220        assert_eq!(r.bytes_in_flight_duration(), Duration::from_millis(10));
1221        assert_eq!(r.lost_count(), 0);
1222
1223        // Wait until loss detection timer expires.
1224        now = r.loss_detection_timer().unwrap();
1225
1226        // Packet is declared lost.
1227        r.on_loss_detection_timeout(HandshakeStatus::default(), now, "");
1228        assert_eq!(r.loss_probes(packet::Epoch::Application), 0);
1229
1230        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 2);
1231        assert_eq!(r.bytes_in_flight(), 0);
1232        assert_eq!(r.bytes_in_flight_duration(), Duration::from_micros(11250));
1233
1234        assert_eq!(r.lost_count(), 1);
1235
1236        // Wait 1 RTT.
1237        now += r.rtt();
1238
1239        assert_eq!(
1240            r.detect_lost_packets_for_test(packet::Epoch::Application, now),
1241            (0, 0)
1242        );
1243
1244        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 0);
1245        if cc_algorithm_name == "reno" || cc_algorithm_name == "cubic" {
1246            assert!(r.startup_exit().is_some());
1247            assert_eq!(r.startup_exit().unwrap().reason, StartupExitReason::Loss);
1248        } else {
1249            assert_eq!(r.startup_exit(), None);
1250        }
1251    }
1252
1253    #[rstest]
1254    fn loss_on_reordering(
1255        #[values("reno", "cubic", "bbr", "bbr2", "bbr2_gcongestion")]
1256        cc_algorithm_name: &str,
1257    ) {
1258        let mut cfg = Config::new(crate::PROTOCOL_VERSION).unwrap();
1259        assert_eq!(cfg.set_cc_algorithm_name(cc_algorithm_name), Ok(()));
1260
1261        let mut r = Recovery::new(&cfg);
1262
1263        let mut now = Instant::now();
1264
1265        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 0);
1266
1267        // Start by sending a few packets.
1268        //
1269        // pkt number: [0, 1, 2, 3]
1270        for i in 0..4 {
1271            let p = test_utils::helper_packet_sent(i, now, 1000);
1272            r.on_packet_sent(
1273                p,
1274                packet::Epoch::Application,
1275                HandshakeStatus::default(),
1276                now,
1277                "",
1278            );
1279
1280            let pkt_count = (i + 1) as usize;
1281            assert_eq!(r.sent_packets_len(packet::Epoch::Application), pkt_count);
1282            assert_eq!(r.bytes_in_flight(), pkt_count * 1000);
1283            assert_eq!(r.bytes_in_flight_duration(), Duration::ZERO);
1284        }
1285
1286        // Wait for 10ms after sending.
1287        now += Duration::from_millis(10);
1288
1289        // Recieve reordered ACKs, i.e. pkt_num [2, 3]
1290        let mut acked = RangeSet::default();
1291        acked.insert(2..4);
1292        assert_eq!(
1293            r.on_ack_received(
1294                &acked,
1295                25,
1296                packet::Epoch::Application,
1297                HandshakeStatus::default(),
1298                now,
1299                None,
1300                "",
1301            )
1302            .unwrap(),
1303            OnAckReceivedOutcome {
1304                lost_packets: 1,
1305                lost_bytes: 1000,
1306                acked_bytes: 1000 * 2,
1307                spurious_losses: 0,
1308            }
1309        );
1310        // Since we only remove packets from the back to avoid compaction, the
1311        // send length remains the same after receiving reordered ACKs
1312        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 4);
1313        assert_eq!(r.pkt_thresh().unwrap(), INITIAL_PACKET_THRESHOLD);
1314        assert_eq!(r.time_thresh(), INITIAL_TIME_THRESHOLD);
1315
1316        // Wait for 10ms after receiving first set of ACKs.
1317        now += Duration::from_millis(10);
1318
1319        // Recieve remaining ACKs, i.e. pkt_num [0, 1]
1320        let mut acked = RangeSet::default();
1321        acked.insert(0..2);
1322        assert_eq!(
1323            r.on_ack_received(
1324                &acked,
1325                25,
1326                packet::Epoch::Application,
1327                HandshakeStatus::default(),
1328                now,
1329                None,
1330                "",
1331            )
1332            .unwrap(),
1333            OnAckReceivedOutcome {
1334                lost_packets: 0,
1335                lost_bytes: 0,
1336                acked_bytes: 1000,
1337                spurious_losses: 1,
1338            }
1339        );
1340        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 0);
1341        assert_eq!(r.bytes_in_flight(), 0);
1342        assert_eq!(r.bytes_in_flight_duration(), Duration::from_millis(20));
1343
1344        // Spurious loss.
1345        assert_eq!(r.lost_count(), 1);
1346        assert_eq!(r.lost_spurious_count(), 1);
1347
1348        // Packet threshold was increased.
1349        assert_eq!(r.pkt_thresh().unwrap(), 4);
1350        assert_eq!(r.time_thresh(), PACKET_REORDER_TIME_THRESHOLD);
1351
1352        // Wait 1 RTT.
1353        now += r.rtt();
1354
1355        // All packets have been ACKed so dont expect additional lost packets
1356        assert_eq!(
1357            r.detect_lost_packets_for_test(packet::Epoch::Application, now),
1358            (0, 0)
1359        );
1360        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 0);
1361
1362        if cc_algorithm_name == "reno" || cc_algorithm_name == "cubic" {
1363            assert!(r.startup_exit().is_some());
1364            assert_eq!(r.startup_exit().unwrap().reason, StartupExitReason::Loss);
1365        } else {
1366            assert_eq!(r.startup_exit(), None);
1367        }
1368    }
1369
1370    // TODO: This should run agains both `congestion` and `gcongestion`.
1371    // `congestion` and `gcongestion` behave differently. That might be ok
1372    // given the different algorithms but it would be ideal to merge and share
1373    // the logic.
1374    #[rstest]
1375    fn time_thresholds_on_reordering(
1376        #[values("bbr2_gcongestion")] cc_algorithm_name: &str,
1377    ) {
1378        let mut cfg = Config::new(crate::PROTOCOL_VERSION).unwrap();
1379        assert_eq!(cfg.set_cc_algorithm_name(cc_algorithm_name), Ok(()));
1380
1381        let mut now = Instant::now();
1382        let mut r = Recovery::new(&cfg);
1383        assert_eq!(r.rtt(), DEFAULT_INITIAL_RTT);
1384
1385        // Pick time between and above thresholds for testing threshold increase.
1386        //
1387        //```
1388        //              between_thresh_ms
1389        //                         |
1390        //    initial_thresh_ms    |     spurious_thresh_ms
1391        //      v                  v             v
1392        // --------------------------------------------------
1393        //      | ................ | ..................... |
1394        //            THRESH_GAP         THRESH_GAP
1395        // ```
1396        // 
1397        // Threshold gap time.
1398        const THRESH_GAP: Duration = Duration::from_millis(30);
1399        // Initial time theshold based on inital RTT.
1400        let initial_thresh_ms =
1401            DEFAULT_INITIAL_RTT.mul_f64(INITIAL_TIME_THRESHOLD);
1402        // The time threshold after spurious loss.
1403        let spurious_thresh_ms: Duration =
1404            DEFAULT_INITIAL_RTT.mul_f64(PACKET_REORDER_TIME_THRESHOLD);
1405        // Time between the two thresholds
1406        let between_thresh_ms = initial_thresh_ms + THRESH_GAP;
1407        assert!(between_thresh_ms > initial_thresh_ms);
1408        assert!(between_thresh_ms < spurious_thresh_ms);
1409        assert!(between_thresh_ms + THRESH_GAP > spurious_thresh_ms);
1410
1411        for i in 0..6 {
1412            let send_time = now + i * between_thresh_ms;
1413
1414            let p = test_utils::helper_packet_sent(i.into(), send_time, 1000);
1415            r.on_packet_sent(
1416                p,
1417                packet::Epoch::Application,
1418                HandshakeStatus::default(),
1419                send_time,
1420                "",
1421            );
1422        }
1423
1424        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 6);
1425        assert_eq!(r.bytes_in_flight(), 6 * 1000);
1426        assert_eq!(r.pkt_thresh().unwrap(), INITIAL_PACKET_THRESHOLD);
1427        assert_eq!(r.time_thresh(), INITIAL_TIME_THRESHOLD);
1428
1429        // Wait for `between_thresh_ms` after sending to trigger loss based on
1430        // loss threshold.
1431        now += between_thresh_ms;
1432
1433        // Ack packet: 1
1434        //
1435        // [0, 1, 2, 3, 4, 5]
1436        //     ^
1437        let mut acked = RangeSet::default();
1438        acked.insert(1..2);
1439        assert_eq!(
1440            r.on_ack_received(
1441                &acked,
1442                25,
1443                packet::Epoch::Application,
1444                HandshakeStatus::default(),
1445                now,
1446                None,
1447                "",
1448            )
1449            .unwrap(),
1450            OnAckReceivedOutcome {
1451                lost_packets: 1,
1452                lost_bytes: 1000,
1453                acked_bytes: 1000,
1454                spurious_losses: 0,
1455            }
1456        );
1457        assert_eq!(r.pkt_thresh().unwrap(), INITIAL_PACKET_THRESHOLD);
1458        assert_eq!(r.time_thresh(), INITIAL_TIME_THRESHOLD);
1459
1460        // Ack packet: 0
1461        //
1462        // [0, 1, 2, 3, 4, 5]
1463        //  ^  x
1464        let mut acked = RangeSet::default();
1465        acked.insert(0..1);
1466        assert_eq!(
1467            r.on_ack_received(
1468                &acked,
1469                25,
1470                packet::Epoch::Application,
1471                HandshakeStatus::default(),
1472                now,
1473                None,
1474                "",
1475            )
1476            .unwrap(),
1477            OnAckReceivedOutcome {
1478                lost_packets: 0,
1479                lost_bytes: 0,
1480                acked_bytes: 0,
1481                spurious_losses: 1,
1482            }
1483        );
1484        // The time_thresh after spurious loss
1485        assert_eq!(r.time_thresh(), PACKET_REORDER_TIME_THRESHOLD);
1486
1487        // Wait for `between_thresh_ms` after sending. However, since the
1488        // threshold has increased, we do not expect loss.
1489        now += between_thresh_ms;
1490
1491        // Ack packet: 3
1492        //
1493        // [2, 3, 4, 5]
1494        //     ^
1495        let mut acked = RangeSet::default();
1496        acked.insert(3..4);
1497        assert_eq!(
1498            r.on_ack_received(
1499                &acked,
1500                25,
1501                packet::Epoch::Application,
1502                HandshakeStatus::default(),
1503                now,
1504                None,
1505                "",
1506            )
1507            .unwrap(),
1508            OnAckReceivedOutcome {
1509                lost_packets: 0,
1510                lost_bytes: 0,
1511                acked_bytes: 1000,
1512                spurious_losses: 0,
1513            }
1514        );
1515
1516        // Wait for and additional `plus_overhead` to trigger loss based on the
1517        // new time threshold.
1518        now += THRESH_GAP;
1519
1520        // Ack packet: 4
1521        //
1522        // [2, 3, 4, 5]
1523        //     x  ^
1524        let mut acked = RangeSet::default();
1525        acked.insert(4..5);
1526        assert_eq!(
1527            r.on_ack_received(
1528                &acked,
1529                25,
1530                packet::Epoch::Application,
1531                HandshakeStatus::default(),
1532                now,
1533                None,
1534                "",
1535            )
1536            .unwrap(),
1537            OnAckReceivedOutcome {
1538                lost_packets: 1,
1539                lost_bytes: 1000,
1540                acked_bytes: 1000,
1541                spurious_losses: 0,
1542            }
1543        );
1544    }
1545
1546    // TODO: Implement enable_relaxed_loss_threshold and enable this test for the
1547    // congestion module.
1548    #[rstest]
1549    fn relaxed_thresholds_on_reordering(
1550        #[values("bbr2_gcongestion")] cc_algorithm_name: &str,
1551    ) {
1552        let mut cfg = Config::new(crate::PROTOCOL_VERSION).unwrap();
1553        cfg.enable_relaxed_loss_threshold = true;
1554        assert_eq!(cfg.set_cc_algorithm_name(cc_algorithm_name), Ok(()));
1555
1556        let mut now = Instant::now();
1557        let mut r = Recovery::new(&cfg);
1558        assert_eq!(r.rtt(), DEFAULT_INITIAL_RTT);
1559
1560        // Pick time between and above thresholds for testing threshold increase.
1561        //
1562        //```
1563        //              between_thresh_ms
1564        //                         |
1565        //    initial_thresh_ms    |     spurious_thresh_ms
1566        //      v                  v             v
1567        // --------------------------------------------------
1568        //      | ................ | ..................... |
1569        //            THRESH_GAP         THRESH_GAP
1570        // ```
1571        // Threshold gap time.
1572        const THRESH_GAP: Duration = Duration::from_millis(30);
1573        // Initial time theshold based on inital RTT.
1574        let initial_thresh_ms =
1575            DEFAULT_INITIAL_RTT.mul_f64(INITIAL_TIME_THRESHOLD);
1576        // The time threshold after spurious loss.
1577        let spurious_thresh_ms: Duration =
1578            DEFAULT_INITIAL_RTT.mul_f64(PACKET_REORDER_TIME_THRESHOLD);
1579        // Time between the two thresholds
1580        let between_thresh_ms = initial_thresh_ms + THRESH_GAP;
1581        assert!(between_thresh_ms > initial_thresh_ms);
1582        assert!(between_thresh_ms < spurious_thresh_ms);
1583        assert!(between_thresh_ms + THRESH_GAP > spurious_thresh_ms);
1584
1585        for i in 0..6 {
1586            let send_time = now + i * between_thresh_ms;
1587
1588            let p = test_utils::helper_packet_sent(i.into(), send_time, 1000);
1589            r.on_packet_sent(
1590                p,
1591                packet::Epoch::Application,
1592                HandshakeStatus::default(),
1593                send_time,
1594                "",
1595            );
1596        }
1597
1598        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 6);
1599        assert_eq!(r.bytes_in_flight(), 6 * 1000);
1600        // Intitial thresholds
1601        assert_eq!(r.pkt_thresh().unwrap(), INITIAL_PACKET_THRESHOLD);
1602        assert_eq!(r.time_thresh(), INITIAL_TIME_THRESHOLD);
1603
1604        // Wait for `between_thresh_ms` after sending to trigger loss based on
1605        // loss threshold.
1606        now += between_thresh_ms;
1607
1608        // Ack packet: 1
1609        //
1610        // [0, 1, 2, 3, 4, 5]
1611        //     ^
1612        let mut acked = RangeSet::default();
1613        acked.insert(1..2);
1614        assert_eq!(
1615            r.on_ack_received(
1616                &acked,
1617                25,
1618                packet::Epoch::Application,
1619                HandshakeStatus::default(),
1620                now,
1621                None,
1622                "",
1623            )
1624            .unwrap(),
1625            OnAckReceivedOutcome {
1626                lost_packets: 1,
1627                lost_bytes: 1000,
1628                acked_bytes: 1000,
1629                spurious_losses: 0,
1630            }
1631        );
1632        // Thresholds after 1st loss
1633        assert_eq!(r.pkt_thresh().unwrap(), INITIAL_PACKET_THRESHOLD);
1634        assert_eq!(r.time_thresh(), INITIAL_TIME_THRESHOLD);
1635
1636        // Ack packet: 0
1637        //
1638        // [0, 1, 2, 3, 4, 5]
1639        //  ^  x
1640        let mut acked = RangeSet::default();
1641        acked.insert(0..1);
1642        assert_eq!(
1643            r.on_ack_received(
1644                &acked,
1645                25,
1646                packet::Epoch::Application,
1647                HandshakeStatus::default(),
1648                now,
1649                None,
1650                "",
1651            )
1652            .unwrap(),
1653            OnAckReceivedOutcome {
1654                lost_packets: 0,
1655                lost_bytes: 0,
1656                acked_bytes: 0,
1657                spurious_losses: 1,
1658            }
1659        );
1660        // Thresholds after 1st spurious loss
1661        //
1662        // Packet threshold should be disabled. Time threshold overhead should
1663        // stay the same.
1664        assert_eq!(r.pkt_thresh(), None);
1665        assert_eq!(r.time_thresh(), INITIAL_TIME_THRESHOLD);
1666
1667        // Set now to send time of packet 2 so we can trigger spurious loss for
1668        // packet 2.
1669        now += between_thresh_ms;
1670        // Then wait for `between_thresh_ms` after sending packet 2 to trigger
1671        // loss. Since the time threshold has NOT increased, expect a
1672        // loss.
1673        now += between_thresh_ms;
1674
1675        // Ack packet: 3
1676        //
1677        // [2, 3, 4, 5]
1678        //     ^
1679        let mut acked = RangeSet::default();
1680        acked.insert(3..4);
1681        assert_eq!(
1682            r.on_ack_received(
1683                &acked,
1684                25,
1685                packet::Epoch::Application,
1686                HandshakeStatus::default(),
1687                now,
1688                None,
1689                "",
1690            )
1691            .unwrap(),
1692            OnAckReceivedOutcome {
1693                lost_packets: 1,
1694                lost_bytes: 1000,
1695                acked_bytes: 1000,
1696                spurious_losses: 0,
1697            }
1698        );
1699        // Thresholds after 2nd loss.
1700        assert_eq!(r.pkt_thresh(), None);
1701        assert_eq!(r.time_thresh(), INITIAL_TIME_THRESHOLD);
1702
1703        // Wait for and additional `plus_overhead` to trigger loss based on the
1704        // new time threshold.
1705        // now += THRESH_GAP;
1706
1707        // Ack packet: 2
1708        //
1709        // [2, 3, 4, 5]
1710        //  ^  x
1711        let mut acked = RangeSet::default();
1712        acked.insert(2..3);
1713        assert_eq!(
1714            r.on_ack_received(
1715                &acked,
1716                25,
1717                packet::Epoch::Application,
1718                HandshakeStatus::default(),
1719                now,
1720                None,
1721                "",
1722            )
1723            .unwrap(),
1724            OnAckReceivedOutcome {
1725                lost_packets: 0,
1726                lost_bytes: 0,
1727                acked_bytes: 0,
1728                spurious_losses: 1,
1729            }
1730        );
1731        // Thresholds after 2nd spurious loss.
1732        //
1733        // Time threshold overhead should double.
1734        assert_eq!(r.pkt_thresh(), None);
1735        let double_time_thresh_overhead =
1736            1.0 + 2.0 * INITIAL_TIME_THRESHOLD_OVERHEAD;
1737        assert_eq!(r.time_thresh(), double_time_thresh_overhead);
1738    }
1739
1740    #[rstest]
1741    fn pacing(
1742        #[values("reno", "cubic", "bbr", "bbr2", "bbr2_gcongestion")]
1743        cc_algorithm_name: &str,
1744    ) {
1745        let mut cfg = Config::new(crate::PROTOCOL_VERSION).unwrap();
1746        assert_eq!(cfg.set_cc_algorithm_name(cc_algorithm_name), Ok(()));
1747
1748        let mut r = Recovery::new(&cfg);
1749
1750        let mut now = Instant::now();
1751
1752        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 0);
1753
1754        // send out first packet burst (a full initcwnd).
1755        for i in 0..10 {
1756            let p = Sent {
1757                pkt_num: i,
1758                frames: smallvec![],
1759                time_sent: now,
1760                time_acked: None,
1761                time_lost: None,
1762                size: 1200,
1763                ack_eliciting: true,
1764                in_flight: true,
1765                delivered: 0,
1766                delivered_time: now,
1767                first_sent_time: now,
1768                is_app_limited: false,
1769                tx_in_flight: 0,
1770                lost: 0,
1771                has_data: true,
1772                is_pmtud_probe: false,
1773            };
1774
1775            r.on_packet_sent(
1776                p,
1777                packet::Epoch::Application,
1778                HandshakeStatus::default(),
1779                now,
1780                "",
1781            );
1782        }
1783
1784        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 10);
1785        assert_eq!(r.bytes_in_flight(), 12000);
1786        assert_eq!(r.bytes_in_flight_duration(), Duration::ZERO);
1787
1788        // Next packet will be sent out immediately.
1789        if cc_algorithm_name != "bbr2_gcongestion" {
1790            assert_eq!(r.pacing_rate(), 0);
1791        } else {
1792            assert_eq!(r.pacing_rate(), 103963);
1793        }
1794        assert_eq!(r.get_packet_send_time(now), now);
1795
1796        assert_eq!(r.cwnd(), 12000);
1797        assert_eq!(r.cwnd_available(), 0);
1798
1799        // Wait 50ms for ACK.
1800        now += Duration::from_millis(50);
1801
1802        let mut acked = RangeSet::default();
1803        acked.insert(0..10);
1804
1805        assert_eq!(
1806            r.on_ack_received(
1807                &acked,
1808                10,
1809                packet::Epoch::Application,
1810                HandshakeStatus::default(),
1811                now,
1812                None,
1813                "",
1814            )
1815            .unwrap(),
1816            OnAckReceivedOutcome {
1817                lost_packets: 0,
1818                lost_bytes: 0,
1819                acked_bytes: 12000,
1820                spurious_losses: 0,
1821            }
1822        );
1823
1824        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 0);
1825        assert_eq!(r.bytes_in_flight(), 0);
1826        assert_eq!(r.bytes_in_flight_duration(), Duration::from_millis(50));
1827        assert_eq!(r.rtt(), Duration::from_millis(50));
1828
1829        // 10 MSS increased due to acks.
1830        assert_eq!(r.cwnd(), 12000 + 1200 * 10);
1831
1832        // Send the second packet burst.
1833        let p = Sent {
1834            pkt_num: 10,
1835            frames: smallvec![],
1836            time_sent: now,
1837            time_acked: None,
1838            time_lost: None,
1839            size: 6000,
1840            ack_eliciting: true,
1841            in_flight: true,
1842            delivered: 0,
1843            delivered_time: now,
1844            first_sent_time: now,
1845            is_app_limited: false,
1846            tx_in_flight: 0,
1847            lost: 0,
1848            has_data: true,
1849            is_pmtud_probe: false,
1850        };
1851
1852        r.on_packet_sent(
1853            p,
1854            packet::Epoch::Application,
1855            HandshakeStatus::default(),
1856            now,
1857            "",
1858        );
1859
1860        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 1);
1861        assert_eq!(r.bytes_in_flight(), 6000);
1862        assert_eq!(r.bytes_in_flight_duration(), Duration::from_millis(50));
1863
1864        if cc_algorithm_name != "bbr2_gcongestion" {
1865            // Pacing is not done during initial phase of connection.
1866            assert_eq!(r.get_packet_send_time(now), now);
1867        } else {
1868            // Pacing is done from the beginning.
1869            assert_ne!(r.get_packet_send_time(now), now);
1870        }
1871
1872        // Send the third packet burst.
1873        let p = Sent {
1874            pkt_num: 11,
1875            frames: smallvec![],
1876            time_sent: now,
1877            time_acked: None,
1878            time_lost: None,
1879            size: 6000,
1880            ack_eliciting: true,
1881            in_flight: true,
1882            delivered: 0,
1883            delivered_time: now,
1884            first_sent_time: now,
1885            is_app_limited: false,
1886            tx_in_flight: 0,
1887            lost: 0,
1888            has_data: true,
1889            is_pmtud_probe: false,
1890        };
1891
1892        r.on_packet_sent(
1893            p,
1894            packet::Epoch::Application,
1895            HandshakeStatus::default(),
1896            now,
1897            "",
1898        );
1899
1900        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 2);
1901        assert_eq!(r.bytes_in_flight(), 12000);
1902        assert_eq!(r.bytes_in_flight_duration(), Duration::from_millis(50));
1903
1904        // Send the fourth packet burst.
1905        let p = Sent {
1906            pkt_num: 12,
1907            frames: smallvec![],
1908            time_sent: now,
1909            time_acked: None,
1910            time_lost: None,
1911            size: 1000,
1912            ack_eliciting: true,
1913            in_flight: true,
1914            delivered: 0,
1915            delivered_time: now,
1916            first_sent_time: now,
1917            is_app_limited: false,
1918            tx_in_flight: 0,
1919            lost: 0,
1920            has_data: true,
1921            is_pmtud_probe: false,
1922        };
1923
1924        r.on_packet_sent(
1925            p,
1926            packet::Epoch::Application,
1927            HandshakeStatus::default(),
1928            now,
1929            "",
1930        );
1931
1932        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 3);
1933        assert_eq!(r.bytes_in_flight(), 13000);
1934        assert_eq!(r.bytes_in_flight_duration(), Duration::from_millis(50));
1935
1936        // We pace this outgoing packet. as all conditions for pacing
1937        // are passed.
1938        let pacing_rate = match cc_algorithm_name {
1939            "bbr" => {
1940                // Constants from congestion/bbr/mod.rs
1941                let cwnd_gain = 2.0;
1942                let startup_pacing_gain = 2.89;
1943                // Adjust for cwnd_gain.  BW estimate was made before the CWND
1944                // increase.
1945                let bw = r.cwnd() as f64 /
1946                    cwnd_gain /
1947                    Duration::from_millis(50).as_secs_f64();
1948                (bw * startup_pacing_gain) as u64
1949            },
1950            "bbr2_gcongestion" => {
1951                let cwnd_gain: f64 = 2.0;
1952                // Adjust for cwnd_gain.  BW estimate was made before the CWND
1953                // increase.
1954                let bw = r.cwnd() as f64 /
1955                    cwnd_gain /
1956                    Duration::from_millis(50).as_secs_f64();
1957                bw as u64
1958            },
1959            "bbr2" => {
1960                // Constants from congestion/bbr2/mod.rs
1961                let cwnd_gain = 2.0;
1962                let startup_pacing_gain = 2.77;
1963                let pacing_margin_percent = 0.01;
1964                // Adjust for cwnd_gain.  BW estimate was made before the CWND
1965                // increase.
1966                let bw = r.cwnd() as f64 /
1967                    cwnd_gain /
1968                    Duration::from_millis(50).as_secs_f64();
1969                (bw * startup_pacing_gain * (1.0 - pacing_margin_percent)) as u64
1970            },
1971            _ => {
1972                let bw =
1973                    r.cwnd() as f64 / Duration::from_millis(50).as_secs_f64();
1974                (bw * PACING_MULTIPLIER) as u64
1975            },
1976        };
1977        assert_eq!(r.pacing_rate(), pacing_rate);
1978
1979        let scale_factor = if cc_algorithm_name == "bbr2_gcongestion" {
1980            // For bbr2_gcongestion, send time is almost 13000 / pacing_rate.
1981            // Don't know where 13000 comes from.
1982            1.08333332
1983        } else {
1984            1.0
1985        };
1986        assert_eq!(
1987            r.get_packet_send_time(now) - now,
1988            Duration::from_secs_f64(scale_factor * 12000.0 / pacing_rate as f64)
1989        );
1990        assert_eq!(r.startup_exit(), None);
1991    }
1992
1993    #[rstest]
1994    // initial_cwnd / first_rtt == initial_pacing_rate.  Pacing is 1.0 * bw before
1995    // and after.
1996    #[case::bw_estimate_equal_after_first_rtt(1.0, 1.0)]
1997    // initial_cwnd / first_rtt < initial_pacing_rate.  Pacing decreases from 2 *
1998    // bw to 1.0 * bw.
1999    #[case::bw_estimate_decrease_after_first_rtt(2.0, 1.0)]
2000    // initial_cwnd / first_rtt > initial_pacing_rate from 0.5 * bw to 1.0 * bw.
2001    // Initial pacing remains 0.5 * bw because the initial_pacing_rate parameter
2002    // is used an upper bound for the pacing rate after the first RTT.
2003    // Pacing rate after the first ACK should be:
2004    // min(initial_pacing_rate_bytes_per_second, init_cwnd / first_rtt)
2005    #[case::bw_estimate_increase_after_first_rtt(0.5, 0.5)]
2006    #[cfg(feature = "internal")]
2007    fn initial_pacing_rate_override(
2008        #[case] initial_multipler: f64, #[case] expected_multiplier: f64,
2009    ) {
2010        let rtt = Duration::from_millis(50);
2011        let bw = Bandwidth::from_bytes_and_time_delta(12000, rtt);
2012        let initial_pacing_rate_hint = bw * initial_multipler;
2013        let expected_pacing_with_rtt_measurement = bw * expected_multiplier;
2014
2015        let cc_algorithm_name = "bbr2_gcongestion";
2016        let mut cfg = Config::new(crate::PROTOCOL_VERSION).unwrap();
2017        assert_eq!(cfg.set_cc_algorithm_name(cc_algorithm_name), Ok(()));
2018        cfg.set_custom_bbr_params(BbrParams {
2019            initial_pacing_rate_bytes_per_second: Some(
2020                initial_pacing_rate_hint.to_bytes_per_second(),
2021            ),
2022            ..Default::default()
2023        });
2024
2025        let mut r = Recovery::new(&cfg);
2026
2027        let mut now = Instant::now();
2028
2029        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 0);
2030
2031        // send some packets.
2032        for i in 0..2 {
2033            let p = test_utils::helper_packet_sent(i, now, 1200);
2034            r.on_packet_sent(
2035                p,
2036                packet::Epoch::Application,
2037                HandshakeStatus::default(),
2038                now,
2039                "",
2040            );
2041        }
2042
2043        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 2);
2044        assert_eq!(r.bytes_in_flight(), 2400);
2045        assert_eq!(r.bytes_in_flight_duration(), Duration::ZERO);
2046
2047        // Initial pacing rate matches the override value.
2048        assert_eq!(
2049            r.pacing_rate(),
2050            initial_pacing_rate_hint.to_bytes_per_second()
2051        );
2052        assert_eq!(r.get_packet_send_time(now), now);
2053
2054        assert_eq!(r.cwnd(), 12000);
2055        assert_eq!(r.cwnd_available(), 9600);
2056
2057        // Wait 1 rtt for ACK.
2058        now += rtt;
2059
2060        let mut acked = RangeSet::default();
2061        acked.insert(0..2);
2062
2063        assert_eq!(
2064            r.on_ack_received(
2065                &acked,
2066                10,
2067                packet::Epoch::Application,
2068                HandshakeStatus::default(),
2069                now,
2070                None,
2071                "",
2072            )
2073            .unwrap(),
2074            OnAckReceivedOutcome {
2075                lost_packets: 0,
2076                lost_bytes: 0,
2077                acked_bytes: 2400,
2078                spurious_losses: 0,
2079            }
2080        );
2081
2082        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 0);
2083        assert_eq!(r.bytes_in_flight(), 0);
2084        assert_eq!(r.bytes_in_flight_duration(), rtt);
2085        assert_eq!(r.rtt(), rtt);
2086
2087        // Pacing rate is recalculated based on initial cwnd when the
2088        // first RTT estimate is available.
2089        assert_eq!(
2090            r.pacing_rate(),
2091            expected_pacing_with_rtt_measurement.to_bytes_per_second()
2092        );
2093    }
2094
2095    #[rstest]
2096    fn validate_ack_range_on_ack_received(
2097        #[values("cubic", "bbr2", "bbr2_gcongestion")] cc_algorithm_name: &str,
2098    ) {
2099        let mut cfg = Config::new(crate::PROTOCOL_VERSION).unwrap();
2100        cfg.set_cc_algorithm_name(cc_algorithm_name).unwrap();
2101
2102        let epoch = packet::Epoch::Application;
2103        let mut r = Recovery::new(&cfg);
2104        let mut now = Instant::now();
2105        assert_eq!(r.sent_packets_len(epoch), 0);
2106
2107        // Send 4 packets
2108        let pkt_size = 1000;
2109        let pkt_count = 4;
2110        for pkt_num in 0..pkt_count {
2111            let sent = test_utils::helper_packet_sent(pkt_num, now, pkt_size);
2112            r.on_packet_sent(sent, epoch, HandshakeStatus::default(), now, "");
2113        }
2114        assert_eq!(r.sent_packets_len(epoch), pkt_count as usize);
2115        assert_eq!(r.bytes_in_flight(), pkt_count as usize * pkt_size);
2116        assert!(r.get_largest_acked_on_epoch(epoch).is_none());
2117        assert_eq!(r.largest_sent_pkt_num_on_path(epoch).unwrap(), 3);
2118
2119        // Wait for 10ms.
2120        now += Duration::from_millis(10);
2121
2122        // ACK 2 packets
2123        let mut acked = RangeSet::default();
2124        acked.insert(0..2);
2125
2126        assert_eq!(
2127            r.on_ack_received(
2128                &acked,
2129                25,
2130                epoch,
2131                HandshakeStatus::default(),
2132                now,
2133                None,
2134                "",
2135            )
2136            .unwrap(),
2137            OnAckReceivedOutcome {
2138                lost_packets: 0,
2139                lost_bytes: 0,
2140                acked_bytes: 2 * 1000,
2141                spurious_losses: 0,
2142            }
2143        );
2144
2145        assert_eq!(r.sent_packets_len(epoch), 2);
2146        assert_eq!(r.bytes_in_flight(), 2 * 1000);
2147
2148        assert_eq!(r.get_largest_acked_on_epoch(epoch).unwrap(), 1);
2149        assert_eq!(r.largest_sent_pkt_num_on_path(epoch).unwrap(), 3);
2150
2151        // ACK large range
2152        let mut acked = RangeSet::default();
2153        acked.insert(0..10);
2154        assert_eq!(
2155            r.on_ack_received(
2156                &acked,
2157                25,
2158                epoch,
2159                HandshakeStatus::default(),
2160                now,
2161                None,
2162                "",
2163            )
2164            .unwrap(),
2165            OnAckReceivedOutcome {
2166                lost_packets: 0,
2167                lost_bytes: 0,
2168                acked_bytes: 2 * 1000,
2169                spurious_losses: 0,
2170            }
2171        );
2172        assert_eq!(r.sent_packets_len(epoch), 0);
2173        assert_eq!(r.bytes_in_flight(), 0);
2174
2175        assert_eq!(r.get_largest_acked_on_epoch(epoch).unwrap(), 3);
2176        assert_eq!(r.largest_sent_pkt_num_on_path(epoch).unwrap(), 3);
2177    }
2178
2179    #[rstest]
2180    fn pmtud_loss_on_timer(
2181        #[values("reno", "cubic", "bbr", "bbr2", "bbr2_gcongestion")]
2182        cc_algorithm_name: &str,
2183    ) {
2184        let mut cfg = Config::new(crate::PROTOCOL_VERSION).unwrap();
2185        assert_eq!(cfg.set_cc_algorithm_name(cc_algorithm_name), Ok(()));
2186
2187        let mut r = Recovery::new(&cfg);
2188        assert_eq!(r.cwnd(), 12000);
2189
2190        let mut now = Instant::now();
2191
2192        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 0);
2193
2194        // Start by sending a few packets.
2195        let p = Sent {
2196            pkt_num: 0,
2197            frames: smallvec![],
2198            time_sent: now,
2199            time_acked: None,
2200            time_lost: None,
2201            size: 1000,
2202            ack_eliciting: true,
2203            in_flight: true,
2204            delivered: 0,
2205            delivered_time: now,
2206            first_sent_time: now,
2207            is_app_limited: false,
2208            tx_in_flight: 0,
2209            lost: 0,
2210            has_data: false,
2211            is_pmtud_probe: false,
2212        };
2213
2214        r.on_packet_sent(
2215            p,
2216            packet::Epoch::Application,
2217            HandshakeStatus::default(),
2218            now,
2219            "",
2220        );
2221
2222        assert_eq!(r.in_flight_count(packet::Epoch::Application), 1);
2223        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 1);
2224        assert_eq!(r.bytes_in_flight(), 1000);
2225        assert_eq!(r.bytes_in_flight_duration(), Duration::ZERO);
2226
2227        let p = Sent {
2228            pkt_num: 1,
2229            frames: smallvec![],
2230            time_sent: now,
2231            time_acked: None,
2232            time_lost: None,
2233            size: 1000,
2234            ack_eliciting: true,
2235            in_flight: true,
2236            delivered: 0,
2237            delivered_time: now,
2238            first_sent_time: now,
2239            is_app_limited: false,
2240            tx_in_flight: 0,
2241            lost: 0,
2242            has_data: false,
2243            is_pmtud_probe: true,
2244        };
2245
2246        r.on_packet_sent(
2247            p,
2248            packet::Epoch::Application,
2249            HandshakeStatus::default(),
2250            now,
2251            "",
2252        );
2253
2254        assert_eq!(r.in_flight_count(packet::Epoch::Application), 2);
2255
2256        let p = Sent {
2257            pkt_num: 2,
2258            frames: smallvec![],
2259            time_sent: now,
2260            time_acked: None,
2261            time_lost: None,
2262            size: 1000,
2263            ack_eliciting: true,
2264            in_flight: true,
2265            delivered: 0,
2266            delivered_time: now,
2267            first_sent_time: now,
2268            is_app_limited: false,
2269            tx_in_flight: 0,
2270            lost: 0,
2271            has_data: false,
2272            is_pmtud_probe: false,
2273        };
2274
2275        r.on_packet_sent(
2276            p,
2277            packet::Epoch::Application,
2278            HandshakeStatus::default(),
2279            now,
2280            "",
2281        );
2282
2283        assert_eq!(r.in_flight_count(packet::Epoch::Application), 3);
2284
2285        // Wait for 10ms.
2286        now += Duration::from_millis(10);
2287
2288        // Only the first  packets and the last one are acked.
2289        let mut acked = RangeSet::default();
2290        acked.insert(0..1);
2291        acked.insert(2..3);
2292
2293        assert_eq!(
2294            r.on_ack_received(
2295                &acked,
2296                25,
2297                packet::Epoch::Application,
2298                HandshakeStatus::default(),
2299                now,
2300                None,
2301                "",
2302            )
2303            .unwrap(),
2304            OnAckReceivedOutcome {
2305                lost_packets: 0,
2306                lost_bytes: 0,
2307                acked_bytes: 2 * 1000,
2308                spurious_losses: 0,
2309            }
2310        );
2311
2312        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 2);
2313        assert_eq!(r.bytes_in_flight(), 1000);
2314        assert_eq!(r.bytes_in_flight_duration(), Duration::from_millis(10));
2315        assert_eq!(r.lost_count(), 0);
2316
2317        // Wait until loss detection timer expires.
2318        now = r.loss_detection_timer().unwrap();
2319
2320        // Packet is declared lost.
2321        r.on_loss_detection_timeout(HandshakeStatus::default(), now, "");
2322        assert_eq!(r.loss_probes(packet::Epoch::Application), 0);
2323
2324        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 2);
2325        assert_eq!(r.in_flight_count(packet::Epoch::Application), 0);
2326        assert_eq!(r.bytes_in_flight(), 0);
2327        assert_eq!(r.bytes_in_flight_duration(), Duration::from_micros(11250));
2328        assert_eq!(r.cwnd(), match cc_algorithm_name {
2329            "bbr" => 14000,
2330            "bbr2" => 14000,
2331            _ => 12000,
2332        });
2333
2334        assert_eq!(r.lost_count(), 0);
2335
2336        // Wait 1 RTT.
2337        now += r.rtt();
2338
2339        assert_eq!(
2340            r.detect_lost_packets_for_test(packet::Epoch::Application, now),
2341            (0, 0)
2342        );
2343
2344        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 0);
2345        assert_eq!(r.in_flight_count(packet::Epoch::Application), 0);
2346        assert_eq!(r.bytes_in_flight(), 0);
2347        assert_eq!(r.bytes_in_flight_duration(), Duration::from_micros(11250));
2348        assert_eq!(r.lost_count(), 0);
2349        assert_eq!(r.startup_exit(), None);
2350    }
2351
2352    // Modeling delivery_rate for gcongestion is non-trivial so we only test the
2353    // congestion specific algorithms.
2354    #[rstest]
2355    fn congestion_delivery_rate(
2356        #[values("reno", "cubic", "bbr", "bbr2")] cc_algorithm_name: &str,
2357    ) {
2358        let mut cfg = Config::new(crate::PROTOCOL_VERSION).unwrap();
2359        assert_eq!(cfg.set_cc_algorithm_name(cc_algorithm_name), Ok(()));
2360
2361        let mut r = Recovery::new(&cfg);
2362        assert_eq!(r.cwnd(), 12000);
2363
2364        let now = Instant::now();
2365
2366        let mut total_bytes_sent = 0;
2367        for pn in 0..10 {
2368            // Start by sending a few packets.
2369            let bytes = 1000;
2370            let sent = test_utils::helper_packet_sent(pn, now, bytes);
2371            r.on_packet_sent(
2372                sent,
2373                packet::Epoch::Application,
2374                HandshakeStatus::default(),
2375                now,
2376                "",
2377            );
2378
2379            total_bytes_sent += bytes;
2380        }
2381
2382        // Ack
2383        let interval = Duration::from_secs(10);
2384        let mut acked = RangeSet::default();
2385        acked.insert(0..10);
2386        assert_eq!(
2387            r.on_ack_received(
2388                &acked,
2389                25,
2390                packet::Epoch::Application,
2391                HandshakeStatus::default(),
2392                now + interval,
2393                None,
2394                "",
2395            )
2396            .unwrap(),
2397            OnAckReceivedOutcome {
2398                lost_packets: 0,
2399                lost_bytes: 0,
2400                acked_bytes: total_bytes_sent,
2401                spurious_losses: 0,
2402            }
2403        );
2404        assert_eq!(r.delivery_rate().to_bytes_per_second(), 1000);
2405        assert_eq!(r.min_rtt().unwrap(), interval);
2406        // delivery rate should be in units bytes/sec
2407        assert_eq!(
2408            total_bytes_sent as u64 / interval.as_secs(),
2409            r.delivery_rate().to_bytes_per_second()
2410        );
2411        assert_eq!(r.startup_exit(), None);
2412    }
2413}
2414
2415mod bandwidth;
2416mod bytes_in_flight;
2417mod congestion;
2418mod gcongestion;
2419mod rtt;