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;
34use 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
53const INITIAL_TIME_THRESHOLD: f64 = 9.0 / 8.0;
54
55const GRANULARITY: Duration = Duration::from_millis(1);
56
57const MAX_PTO_PROBES_COUNT: usize = 2;
58
59const MINIMUM_WINDOW_PACKETS: usize = 2;
60
61const LOSS_REDUCTION_FACTOR: f64 = 0.5;
62
63// How many non ACK eliciting packets we send before including a PING to solicit
64// an ACK.
65pub(super) const MAX_OUTSTANDING_NON_ACK_ELICITING: usize = 24;
66
67#[derive(Default)]
68struct LossDetectionTimer {
69    time: Option<Instant>,
70}
71
72impl LossDetectionTimer {
73    fn update(&mut self, timeout: Instant) {
74        self.time = Some(timeout);
75    }
76
77    fn clear(&mut self) {
78        self.time = None;
79    }
80}
81
82impl std::fmt::Debug for LossDetectionTimer {
83    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
84        match self.time {
85            Some(v) => {
86                let now = Instant::now();
87                if v > now {
88                    let d = v.duration_since(now);
89                    write!(f, "{d:?}")
90                } else {
91                    write!(f, "exp")
92                }
93            },
94            None => write!(f, "none"),
95        }
96    }
97}
98
99#[derive(Clone, Copy, PartialEq)]
100pub struct RecoveryConfig {
101    pub initial_rtt: Duration,
102    pub max_send_udp_payload_size: usize,
103    pub max_ack_delay: Duration,
104    pub cc_algorithm: CongestionControlAlgorithm,
105    pub custom_bbr_params: Option<BbrParams>,
106    pub hystart: bool,
107    pub pacing: bool,
108    pub max_pacing_rate: Option<u64>,
109    pub initial_congestion_window_packets: usize,
110}
111
112impl RecoveryConfig {
113    pub fn from_config(config: &Config) -> Self {
114        Self {
115            initial_rtt: config.initial_rtt,
116            max_send_udp_payload_size: config.max_send_udp_payload_size,
117            max_ack_delay: Duration::ZERO,
118            cc_algorithm: config.cc_algorithm,
119            custom_bbr_params: config.custom_bbr_params,
120            hystart: config.hystart,
121            pacing: config.pacing,
122            max_pacing_rate: config.max_pacing_rate,
123            initial_congestion_window_packets: config
124                .initial_congestion_window_packets,
125        }
126    }
127}
128
129#[enum_dispatch::enum_dispatch(RecoveryOps)]
130#[allow(clippy::large_enum_variant)]
131#[derive(Debug)]
132pub(crate) enum Recovery {
133    Legacy(LegacyRecovery),
134    GCongestion(GRecovery),
135}
136
137#[derive(Debug, Default, PartialEq)]
138pub struct OnAckReceivedOutcome {
139    pub lost_packets: usize,
140    pub lost_bytes: usize,
141    pub acked_bytes: usize,
142    pub spurious_losses: usize,
143}
144
145#[derive(Debug, Default)]
146pub struct OnLossDetectionTimeoutOutcome {
147    pub lost_packets: usize,
148    pub lost_bytes: usize,
149}
150
151#[enum_dispatch::enum_dispatch]
152/// Api for the Recovery implementation
153pub trait RecoveryOps {
154    fn lost_count(&self) -> usize;
155    fn bytes_lost(&self) -> u64;
156
157    /// Returns whether or not we should elicit an ACK even if we wouldn't
158    /// otherwise have constructed an ACK eliciting packet.
159    fn should_elicit_ack(&self, epoch: packet::Epoch) -> bool;
160
161    fn get_acked_frames(&mut self, epoch: packet::Epoch) -> Vec<frame::Frame>;
162
163    fn get_lost_frames(&mut self, epoch: packet::Epoch) -> Vec<frame::Frame>;
164
165    fn get_largest_acked_on_epoch(&self, epoch: packet::Epoch) -> Option<u64>;
166    fn has_lost_frames(&self, epoch: packet::Epoch) -> bool;
167    fn loss_probes(&self, epoch: packet::Epoch) -> usize;
168    #[cfg(test)]
169    fn inc_loss_probes(&mut self, epoch: packet::Epoch);
170
171    fn ping_sent(&mut self, epoch: packet::Epoch);
172
173    fn on_packet_sent(
174        &mut self, pkt: Sent, epoch: packet::Epoch,
175        handshake_status: HandshakeStatus, now: Instant, trace_id: &str,
176    );
177    fn get_packet_send_time(&self, now: Instant) -> Instant;
178
179    #[allow(clippy::too_many_arguments)]
180    fn on_ack_received(
181        &mut self, ranges: &RangeSet, ack_delay: u64, epoch: packet::Epoch,
182        handshake_status: HandshakeStatus, now: Instant, skip_pn: Option<u64>,
183        trace_id: &str,
184    ) -> Result<OnAckReceivedOutcome>;
185
186    fn on_loss_detection_timeout(
187        &mut self, handshake_status: HandshakeStatus, now: Instant,
188        trace_id: &str,
189    ) -> OnLossDetectionTimeoutOutcome;
190    fn on_pkt_num_space_discarded(
191        &mut self, epoch: packet::Epoch, handshake_status: HandshakeStatus,
192        now: Instant,
193    );
194    fn on_path_change(
195        &mut self, epoch: packet::Epoch, now: Instant, _trace_id: &str,
196    ) -> (usize, usize);
197    fn loss_detection_timer(&self) -> Option<Instant>;
198    fn cwnd(&self) -> usize;
199    fn cwnd_available(&self) -> usize;
200    fn rtt(&self) -> Duration;
201
202    fn min_rtt(&self) -> Option<Duration>;
203
204    fn max_rtt(&self) -> Option<Duration>;
205
206    fn rttvar(&self) -> Duration;
207
208    fn pto(&self) -> Duration;
209
210    /// The most recent data delivery rate estimate.
211    fn delivery_rate(&self) -> Bandwidth;
212
213    /// Statistics from when a CCA first exited the startup phase.
214    fn startup_exit(&self) -> Option<StartupExit>;
215
216    fn max_datagram_size(&self) -> usize;
217
218    fn pmtud_update_max_datagram_size(&mut self, new_max_datagram_size: usize);
219
220    fn update_max_datagram_size(&mut self, new_max_datagram_size: usize);
221
222    fn on_app_limited(&mut self);
223
224    // Since a recovery module is path specific, this tracks the largest packet
225    // sent per path.
226    #[cfg(test)]
227    fn largest_sent_pkt_num_on_path(&self, epoch: packet::Epoch) -> Option<u64>;
228
229    #[cfg(test)]
230    fn app_limited(&self) -> bool;
231
232    #[cfg(test)]
233    fn sent_packets_len(&self, epoch: packet::Epoch) -> usize;
234
235    #[cfg(test)]
236    fn bytes_in_flight(&self) -> usize;
237
238    fn bytes_in_flight_duration(&self) -> Duration;
239
240    #[cfg(test)]
241    fn in_flight_count(&self, epoch: packet::Epoch) -> usize;
242
243    #[cfg(test)]
244    fn pacing_rate(&self) -> u64;
245
246    #[cfg(test)]
247    fn pto_count(&self) -> u32;
248
249    #[cfg(test)]
250    fn pkt_thresh(&self) -> u64;
251
252    #[cfg(test)]
253    fn lost_spurious_count(&self) -> usize;
254
255    #[cfg(test)]
256    fn detect_lost_packets_for_test(
257        &mut self, epoch: packet::Epoch, now: Instant,
258    ) -> (usize, usize);
259
260    fn update_app_limited(&mut self, v: bool);
261
262    fn delivery_rate_update_app_limited(&mut self, v: bool);
263
264    fn update_max_ack_delay(&mut self, max_ack_delay: Duration);
265
266    #[cfg(feature = "qlog")]
267    fn state_str(&self, now: Instant) -> &'static str;
268
269    #[cfg(feature = "qlog")]
270    fn get_updated_qlog_event_data(&mut self) -> Option<EventData>;
271
272    #[cfg(feature = "qlog")]
273    fn get_updated_qlog_cc_state(&mut self, now: Instant)
274        -> Option<&'static str>;
275
276    fn send_quantum(&self) -> usize;
277
278    fn get_next_release_time(&self) -> ReleaseDecision;
279
280    fn gcongestion_enabled(&self) -> bool;
281}
282
283impl Recovery {
284    pub fn new_with_config(recovery_config: &RecoveryConfig) -> Self {
285        let grecovery = GRecovery::new(recovery_config);
286        if let Some(grecovery) = grecovery {
287            Recovery::from(grecovery)
288        } else {
289            Recovery::from(LegacyRecovery::new_with_config(recovery_config))
290        }
291    }
292
293    #[cfg(feature = "qlog")]
294    pub fn maybe_qlog(
295        &mut self, qlog: &mut qlog::streamer::QlogStreamer, now: Instant,
296    ) {
297        if let Some(ev_data) = self.get_updated_qlog_event_data() {
298            qlog.add_event_data_with_instant(ev_data, now).ok();
299        }
300
301        if let Some(cc_state) = self.get_updated_qlog_cc_state(now) {
302            let ev_data = EventData::CongestionStateUpdated(
303                qlog::events::quic::CongestionStateUpdated {
304                    old: None,
305                    new: cc_state.to_string(),
306                    trigger: None,
307                },
308            );
309
310            qlog.add_event_data_with_instant(ev_data, now).ok();
311        }
312    }
313
314    #[cfg(test)]
315    pub fn new(config: &Config) -> Self {
316        Self::new_with_config(&RecoveryConfig::from_config(config))
317    }
318}
319
320/// Available congestion control algorithms.
321///
322/// This enum provides currently available list of congestion control
323/// algorithms.
324#[derive(Debug, Copy, Clone, PartialEq, Eq)]
325#[repr(C)]
326pub enum CongestionControlAlgorithm {
327    /// Reno congestion control algorithm. `reno` in a string form.
328    Reno            = 0,
329    /// CUBIC congestion control algorithm (default). `cubic` in a string form.
330    CUBIC           = 1,
331    /// BBR congestion control algorithm. `bbr` in a string form.
332    BBR             = 2,
333    /// BBRv2 congestion control algorithm. `bbr2` in a string form.
334    BBR2            = 3,
335    /// BBRv2 congestion control algorithm implementation from gcongestion
336    /// branch. `bbr2_gcongestion` in a string form.
337    Bbr2Gcongestion = 4,
338}
339
340impl FromStr for CongestionControlAlgorithm {
341    type Err = crate::Error;
342
343    /// Converts a string to `CongestionControlAlgorithm`.
344    ///
345    /// If `name` is not valid, `Error::CongestionControl` is returned.
346    fn from_str(name: &str) -> std::result::Result<Self, Self::Err> {
347        match name {
348            "reno" => Ok(CongestionControlAlgorithm::Reno),
349            "cubic" => Ok(CongestionControlAlgorithm::CUBIC),
350            "bbr" => Ok(CongestionControlAlgorithm::BBR),
351            #[cfg(not(feature = "gcongestion"))]
352            "bbr2" => Ok(CongestionControlAlgorithm::BBR2),
353            #[cfg(feature = "gcongestion")]
354            "bbr2" => Ok(CongestionControlAlgorithm::Bbr2Gcongestion),
355            "bbr2_gcongestion" => Ok(CongestionControlAlgorithm::Bbr2Gcongestion),
356            _ => Err(crate::Error::CongestionControl),
357        }
358    }
359}
360
361#[derive(Clone)]
362pub struct Sent {
363    pub pkt_num: u64,
364
365    pub frames: SmallVec<[frame::Frame; 1]>,
366
367    pub time_sent: Instant,
368
369    pub time_acked: Option<Instant>,
370
371    pub time_lost: Option<Instant>,
372
373    pub size: usize,
374
375    pub ack_eliciting: bool,
376
377    pub in_flight: bool,
378
379    pub delivered: usize,
380
381    pub delivered_time: Instant,
382
383    pub first_sent_time: Instant,
384
385    pub is_app_limited: bool,
386
387    pub tx_in_flight: usize,
388
389    pub lost: u64,
390
391    pub has_data: bool,
392
393    pub is_pmtud_probe: bool,
394}
395
396impl std::fmt::Debug for Sent {
397    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
398        write!(f, "pkt_num={:?} ", self.pkt_num)?;
399        write!(f, "pkt_sent_time={:?} ", self.time_sent)?;
400        write!(f, "pkt_size={:?} ", self.size)?;
401        write!(f, "delivered={:?} ", self.delivered)?;
402        write!(f, "delivered_time={:?} ", self.delivered_time)?;
403        write!(f, "first_sent_time={:?} ", self.first_sent_time)?;
404        write!(f, "is_app_limited={} ", self.is_app_limited)?;
405        write!(f, "tx_in_flight={} ", self.tx_in_flight)?;
406        write!(f, "lost={} ", self.lost)?;
407        write!(f, "has_data={} ", self.has_data)?;
408        write!(f, "is_pmtud_probe={}", self.is_pmtud_probe)?;
409
410        Ok(())
411    }
412}
413
414#[derive(Clone, Copy, Debug)]
415pub struct HandshakeStatus {
416    pub has_handshake_keys: bool,
417
418    pub peer_verified_address: bool,
419
420    pub completed: bool,
421}
422
423#[cfg(test)]
424impl Default for HandshakeStatus {
425    fn default() -> HandshakeStatus {
426        HandshakeStatus {
427            has_handshake_keys: true,
428
429            peer_verified_address: true,
430
431            completed: true,
432        }
433    }
434}
435
436// We don't need to log all qlog metrics every time there is a recovery event.
437// Instead, we can log only the MetricsUpdated event data fields that we care
438// about, only when they change. To support this, the QLogMetrics structure
439// keeps a running picture of the fields.
440#[derive(Default)]
441#[cfg(feature = "qlog")]
442struct QlogMetrics {
443    min_rtt: Duration,
444    smoothed_rtt: Duration,
445    latest_rtt: Duration,
446    rttvar: Duration,
447    cwnd: u64,
448    bytes_in_flight: u64,
449    ssthresh: Option<u64>,
450    pacing_rate: u64,
451}
452
453#[cfg(feature = "qlog")]
454impl QlogMetrics {
455    // Make a qlog event if the latest instance of QlogMetrics is different.
456    //
457    // This function diffs each of the fields. A qlog MetricsUpdated event is
458    // only generated if at least one field is different. Where fields are
459    // different, the qlog event contains the latest value.
460    fn maybe_update(&mut self, latest: Self) -> Option<EventData> {
461        let mut emit_event = false;
462
463        let new_min_rtt = if self.min_rtt != latest.min_rtt {
464            self.min_rtt = latest.min_rtt;
465            emit_event = true;
466            Some(latest.min_rtt.as_secs_f32() * 1000.0)
467        } else {
468            None
469        };
470
471        let new_smoothed_rtt = if self.smoothed_rtt != latest.smoothed_rtt {
472            self.smoothed_rtt = latest.smoothed_rtt;
473            emit_event = true;
474            Some(latest.smoothed_rtt.as_secs_f32() * 1000.0)
475        } else {
476            None
477        };
478
479        let new_latest_rtt = if self.latest_rtt != latest.latest_rtt {
480            self.latest_rtt = latest.latest_rtt;
481            emit_event = true;
482            Some(latest.latest_rtt.as_secs_f32() * 1000.0)
483        } else {
484            None
485        };
486
487        let new_rttvar = if self.rttvar != latest.rttvar {
488            self.rttvar = latest.rttvar;
489            emit_event = true;
490            Some(latest.rttvar.as_secs_f32() * 1000.0)
491        } else {
492            None
493        };
494
495        let new_cwnd = if self.cwnd != latest.cwnd {
496            self.cwnd = latest.cwnd;
497            emit_event = true;
498            Some(latest.cwnd)
499        } else {
500            None
501        };
502
503        let new_bytes_in_flight =
504            if self.bytes_in_flight != latest.bytes_in_flight {
505                self.bytes_in_flight = latest.bytes_in_flight;
506                emit_event = true;
507                Some(latest.bytes_in_flight)
508            } else {
509                None
510            };
511
512        let new_ssthresh = if self.ssthresh != latest.ssthresh {
513            self.ssthresh = latest.ssthresh;
514            emit_event = true;
515            latest.ssthresh
516        } else {
517            None
518        };
519
520        let new_pacing_rate = if self.pacing_rate != latest.pacing_rate {
521            self.pacing_rate = latest.pacing_rate;
522            emit_event = true;
523            Some(latest.pacing_rate)
524        } else {
525            None
526        };
527
528        if emit_event {
529            // QVis can't use all these fields and they can be large.
530            return Some(EventData::MetricsUpdated(
531                qlog::events::quic::MetricsUpdated {
532                    min_rtt: new_min_rtt,
533                    smoothed_rtt: new_smoothed_rtt,
534                    latest_rtt: new_latest_rtt,
535                    rtt_variance: new_rttvar,
536                    congestion_window: new_cwnd,
537                    bytes_in_flight: new_bytes_in_flight,
538                    ssthresh: new_ssthresh,
539                    pacing_rate: new_pacing_rate,
540                    ..Default::default()
541                },
542            ));
543        }
544
545        None
546    }
547}
548
549/// When the pacer thinks is a good time to release the next packet
550#[derive(Debug, Clone, Copy, PartialEq, Eq)]
551pub enum ReleaseTime {
552    Immediate,
553    At(Instant),
554}
555
556/// When the next packet should be release and if it can be part of a burst
557#[derive(Clone, Copy, Debug, PartialEq, Eq)]
558pub struct ReleaseDecision {
559    time: ReleaseTime,
560    allow_burst: bool,
561}
562
563impl ReleaseTime {
564    /// Add the specific delay to the current time
565    #[allow(dead_code)]
566    fn inc(&mut self, delay: Duration) {
567        match self {
568            ReleaseTime::Immediate => {},
569            ReleaseTime::At(time) => *time += delay,
570        }
571    }
572
573    /// Set the time to the later of two times
574    #[allow(dead_code)]
575    fn set_max(&mut self, other: Instant) {
576        match self {
577            ReleaseTime::Immediate => *self = ReleaseTime::At(other),
578            ReleaseTime::At(time) => *self = ReleaseTime::At(other.max(*time)),
579        }
580    }
581}
582
583impl ReleaseDecision {
584    pub(crate) const EQUAL_THRESHOLD: Duration = Duration::from_micros(50);
585
586    /// Get the [`Instant`] the next packet should be released. It will never be
587    /// in the past.
588    #[allow(dead_code)]
589    #[inline]
590    pub fn time(&self, now: Instant) -> Option<Instant> {
591        match self.time {
592            ReleaseTime::Immediate => None,
593            ReleaseTime::At(other) => other.gt(&now).then_some(other),
594        }
595    }
596
597    /// Can this packet be appended to a previous burst
598    #[allow(dead_code)]
599    #[inline]
600    pub fn can_burst(&self) -> bool {
601        self.allow_burst
602    }
603
604    /// Check if the two packets can be released at the same time
605    #[allow(dead_code)]
606    #[inline]
607    pub fn time_eq(&self, other: &Self, now: Instant) -> bool {
608        let delta = match (self.time(now), other.time(now)) {
609            (None, None) => Duration::ZERO,
610            (Some(t), None) | (None, Some(t)) => t.duration_since(now),
611            (Some(t1), Some(t2)) if t1 < t2 => t2.duration_since(t1),
612            (Some(t1), Some(t2)) => t1.duration_since(t2),
613        };
614
615        delta <= Self::EQUAL_THRESHOLD
616    }
617}
618
619/// Recovery statistics
620#[derive(Default, Debug)]
621pub struct RecoveryStats {
622    startup_exit: Option<StartupExit>,
623}
624
625impl RecoveryStats {
626    // Record statistics when a CCA first exits startup.
627    pub fn set_startup_exit(&mut self, startup_exit: StartupExit) {
628        if self.startup_exit.is_none() {
629            self.startup_exit = Some(startup_exit);
630        }
631    }
632}
633
634/// Statistics from when a CCA first exited the startup phase.
635#[derive(Debug, Clone, Copy, PartialEq)]
636pub struct StartupExit {
637    /// The congestion_window recorded at Startup exit.
638    pub cwnd: usize,
639
640    /// The reason a CCA exited the startup phase.
641    pub reason: StartupExitReason,
642}
643
644impl StartupExit {
645    fn new(cwnd: usize, reason: StartupExitReason) -> Self {
646        Self { cwnd, reason }
647    }
648}
649
650/// The reason a CCA exited the startup phase.
651#[derive(Debug, Clone, Copy, PartialEq)]
652pub enum StartupExitReason {
653    /// Exit startup due to excessive loss
654    Loss,
655
656    /// Exit startup due to bandwidth plateau.
657    BandwidthPlateau,
658
659    /// Exit startup due to persistent queue.
660    PersistentQueue,
661}
662
663#[cfg(test)]
664mod tests {
665    use super::*;
666    use crate::packet;
667    use crate::recovery::congestion::PACING_MULTIPLIER;
668    use crate::test_utils;
669    use crate::CongestionControlAlgorithm;
670    use rstest::rstest;
671    use smallvec::smallvec;
672    use std::str::FromStr;
673
674    fn recovery_for_alg(algo: CongestionControlAlgorithm) -> Recovery {
675        let mut cfg = Config::new(crate::PROTOCOL_VERSION).unwrap();
676        cfg.set_cc_algorithm(algo);
677        Recovery::new(&cfg)
678    }
679
680    #[test]
681    fn lookup_cc_algo_ok() {
682        let algo = CongestionControlAlgorithm::from_str("reno").unwrap();
683        assert_eq!(algo, CongestionControlAlgorithm::Reno);
684        assert!(!recovery_for_alg(algo).gcongestion_enabled());
685
686        let algo = CongestionControlAlgorithm::from_str("cubic").unwrap();
687        assert_eq!(algo, CongestionControlAlgorithm::CUBIC);
688        assert!(!recovery_for_alg(algo).gcongestion_enabled());
689
690        let algo = CongestionControlAlgorithm::from_str("bbr").unwrap();
691        assert_eq!(algo, CongestionControlAlgorithm::BBR);
692        assert!(!recovery_for_alg(algo).gcongestion_enabled());
693
694        let algo = CongestionControlAlgorithm::from_str("bbr2").unwrap();
695        #[cfg(not(feature = "gcongestion"))]
696        {
697            assert_eq!(algo, CongestionControlAlgorithm::BBR2);
698            assert!(!recovery_for_alg(algo).gcongestion_enabled());
699        }
700        #[cfg(feature = "gcongestion")]
701        {
702            assert_eq!(algo, CongestionControlAlgorithm::Bbr2Gcongestion);
703            assert!(recovery_for_alg(algo).gcongestion_enabled());
704        }
705
706        let algo =
707            CongestionControlAlgorithm::from_str("bbr2_gcongestion").unwrap();
708        assert_eq!(algo, CongestionControlAlgorithm::Bbr2Gcongestion);
709        assert!(recovery_for_alg(algo).gcongestion_enabled());
710    }
711
712    #[test]
713    fn lookup_cc_algo_bad() {
714        assert_eq!(
715            CongestionControlAlgorithm::from_str("???"),
716            Err(crate::Error::CongestionControl)
717        );
718    }
719
720    #[rstest]
721    fn loss_on_pto(
722        #[values("reno", "cubic", "bbr", "bbr2", "bbr2_gcongestion")]
723        cc_algorithm_name: &str,
724    ) {
725        let mut cfg = Config::new(crate::PROTOCOL_VERSION).unwrap();
726        assert_eq!(cfg.set_cc_algorithm_name(cc_algorithm_name), Ok(()));
727
728        let mut r = Recovery::new(&cfg);
729
730        let mut now = Instant::now();
731
732        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 0);
733
734        // Start by sending a few packets.
735        let p = Sent {
736            pkt_num: 0,
737            frames: smallvec![],
738            time_sent: now,
739            time_acked: None,
740            time_lost: None,
741            size: 1000,
742            ack_eliciting: true,
743            in_flight: true,
744            delivered: 0,
745            delivered_time: now,
746            first_sent_time: now,
747            is_app_limited: false,
748            tx_in_flight: 0,
749            lost: 0,
750            has_data: false,
751            is_pmtud_probe: false,
752        };
753
754        r.on_packet_sent(
755            p,
756            packet::Epoch::Application,
757            HandshakeStatus::default(),
758            now,
759            "",
760        );
761
762        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 1);
763        assert_eq!(r.bytes_in_flight(), 1000);
764        assert_eq!(r.bytes_in_flight_duration(), Duration::ZERO);
765
766        let p = Sent {
767            pkt_num: 1,
768            frames: smallvec![],
769            time_sent: now,
770            time_acked: None,
771            time_lost: None,
772            size: 1000,
773            ack_eliciting: true,
774            in_flight: true,
775            delivered: 0,
776            delivered_time: now,
777            first_sent_time: now,
778            is_app_limited: false,
779            tx_in_flight: 0,
780            lost: 0,
781            has_data: false,
782            is_pmtud_probe: false,
783        };
784
785        r.on_packet_sent(
786            p,
787            packet::Epoch::Application,
788            HandshakeStatus::default(),
789            now,
790            "",
791        );
792
793        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 2);
794        assert_eq!(r.bytes_in_flight(), 2000);
795        assert_eq!(r.bytes_in_flight_duration(), Duration::ZERO);
796
797        let p = Sent {
798            pkt_num: 2,
799            frames: smallvec![],
800            time_sent: now,
801            time_acked: None,
802            time_lost: None,
803            size: 1000,
804            ack_eliciting: true,
805            in_flight: true,
806            delivered: 0,
807            delivered_time: now,
808            first_sent_time: now,
809            is_app_limited: false,
810            tx_in_flight: 0,
811            lost: 0,
812            has_data: false,
813            is_pmtud_probe: false,
814        };
815
816        r.on_packet_sent(
817            p,
818            packet::Epoch::Application,
819            HandshakeStatus::default(),
820            now,
821            "",
822        );
823        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 3);
824        assert_eq!(r.bytes_in_flight(), 3000);
825        assert_eq!(r.bytes_in_flight_duration(), Duration::ZERO);
826
827        let p = Sent {
828            pkt_num: 3,
829            frames: smallvec![],
830            time_sent: now,
831            time_acked: None,
832            time_lost: None,
833            size: 1000,
834            ack_eliciting: true,
835            in_flight: true,
836            delivered: 0,
837            delivered_time: now,
838            first_sent_time: now,
839            is_app_limited: false,
840            tx_in_flight: 0,
841            lost: 0,
842            has_data: false,
843            is_pmtud_probe: false,
844        };
845
846        r.on_packet_sent(
847            p,
848            packet::Epoch::Application,
849            HandshakeStatus::default(),
850            now,
851            "",
852        );
853        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 4);
854        assert_eq!(r.bytes_in_flight(), 4000);
855        assert_eq!(r.bytes_in_flight_duration(), Duration::ZERO);
856
857        // Wait for 10ms.
858        now += Duration::from_millis(10);
859
860        // Only the first 2 packets are acked.
861        let mut acked = RangeSet::default();
862        acked.insert(0..2);
863
864        assert_eq!(
865            r.on_ack_received(
866                &acked,
867                25,
868                packet::Epoch::Application,
869                HandshakeStatus::default(),
870                now,
871                None,
872                "",
873            )
874            .unwrap(),
875            OnAckReceivedOutcome {
876                lost_packets: 0,
877                lost_bytes: 0,
878                acked_bytes: 2 * 1000,
879                spurious_losses: 0,
880            }
881        );
882
883        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 2);
884        assert_eq!(r.bytes_in_flight(), 2000);
885        assert_eq!(r.bytes_in_flight_duration(), Duration::from_millis(10));
886        assert_eq!(r.lost_count(), 0);
887
888        // Wait until loss detection timer expires.
889        now = r.loss_detection_timer().unwrap();
890
891        // PTO.
892        r.on_loss_detection_timeout(HandshakeStatus::default(), now, "");
893        assert_eq!(r.loss_probes(packet::Epoch::Application), 1);
894        assert_eq!(r.lost_count(), 0);
895        assert_eq!(r.pto_count(), 1);
896
897        let p = Sent {
898            pkt_num: 4,
899            frames: smallvec![],
900            time_sent: now,
901            time_acked: None,
902            time_lost: None,
903            size: 1000,
904            ack_eliciting: true,
905            in_flight: true,
906            delivered: 0,
907            delivered_time: now,
908            first_sent_time: now,
909            is_app_limited: false,
910            tx_in_flight: 0,
911            lost: 0,
912            has_data: false,
913            is_pmtud_probe: false,
914        };
915
916        r.on_packet_sent(
917            p,
918            packet::Epoch::Application,
919            HandshakeStatus::default(),
920            now,
921            "",
922        );
923        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 3);
924        assert_eq!(r.bytes_in_flight(), 3000);
925        assert_eq!(r.bytes_in_flight_duration(), Duration::from_millis(30));
926
927        let p = Sent {
928            pkt_num: 5,
929            frames: smallvec![],
930            time_sent: now,
931            time_acked: None,
932            time_lost: None,
933            size: 1000,
934            ack_eliciting: true,
935            in_flight: true,
936            delivered: 0,
937            delivered_time: now,
938            first_sent_time: now,
939            is_app_limited: false,
940            tx_in_flight: 0,
941            lost: 0,
942            has_data: false,
943            is_pmtud_probe: false,
944        };
945
946        r.on_packet_sent(
947            p,
948            packet::Epoch::Application,
949            HandshakeStatus::default(),
950            now,
951            "",
952        );
953        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 4);
954        assert_eq!(r.bytes_in_flight(), 4000);
955        assert_eq!(r.bytes_in_flight_duration(), Duration::from_millis(30));
956        assert_eq!(r.lost_count(), 0);
957
958        // Wait for 10ms.
959        now += Duration::from_millis(10);
960
961        // PTO packets are acked.
962        let mut acked = RangeSet::default();
963        acked.insert(4..6);
964
965        assert_eq!(
966            r.on_ack_received(
967                &acked,
968                25,
969                packet::Epoch::Application,
970                HandshakeStatus::default(),
971                now,
972                None,
973                "",
974            )
975            .unwrap(),
976            OnAckReceivedOutcome {
977                lost_packets: 2,
978                lost_bytes: 2000,
979                acked_bytes: 2 * 1000,
980                spurious_losses: 0,
981            }
982        );
983
984        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 4);
985        assert_eq!(r.bytes_in_flight(), 0);
986        assert_eq!(r.bytes_in_flight_duration(), Duration::from_millis(40));
987
988        assert_eq!(r.lost_count(), 2);
989
990        // Wait 1 RTT.
991        now += r.rtt();
992
993        assert_eq!(
994            r.detect_lost_packets_for_test(packet::Epoch::Application, now),
995            (0, 0)
996        );
997
998        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 0);
999        if cc_algorithm_name == "reno" || cc_algorithm_name == "cubic" {
1000            assert!(r.startup_exit().is_some());
1001            assert_eq!(r.startup_exit().unwrap().reason, StartupExitReason::Loss);
1002        } else {
1003            assert_eq!(r.startup_exit(), None);
1004        }
1005    }
1006
1007    #[rstest]
1008    fn loss_on_timer(
1009        #[values("reno", "cubic", "bbr", "bbr2", "bbr2_gcongestion")]
1010        cc_algorithm_name: &str,
1011    ) {
1012        let mut cfg = Config::new(crate::PROTOCOL_VERSION).unwrap();
1013        assert_eq!(cfg.set_cc_algorithm_name(cc_algorithm_name), Ok(()));
1014
1015        let mut r = Recovery::new(&cfg);
1016
1017        let mut now = Instant::now();
1018
1019        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 0);
1020
1021        // Start by sending a few packets.
1022        let p = Sent {
1023            pkt_num: 0,
1024            frames: smallvec![],
1025            time_sent: now,
1026            time_acked: None,
1027            time_lost: None,
1028            size: 1000,
1029            ack_eliciting: true,
1030            in_flight: true,
1031            delivered: 0,
1032            delivered_time: now,
1033            first_sent_time: now,
1034            is_app_limited: false,
1035            tx_in_flight: 0,
1036            lost: 0,
1037            has_data: false,
1038            is_pmtud_probe: false,
1039        };
1040
1041        r.on_packet_sent(
1042            p,
1043            packet::Epoch::Application,
1044            HandshakeStatus::default(),
1045            now,
1046            "",
1047        );
1048        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 1);
1049        assert_eq!(r.bytes_in_flight(), 1000);
1050        assert_eq!(r.bytes_in_flight_duration(), Duration::ZERO);
1051
1052        let p = Sent {
1053            pkt_num: 1,
1054            frames: smallvec![],
1055            time_sent: now,
1056            time_acked: None,
1057            time_lost: None,
1058            size: 1000,
1059            ack_eliciting: true,
1060            in_flight: true,
1061            delivered: 0,
1062            delivered_time: now,
1063            first_sent_time: now,
1064            is_app_limited: false,
1065            tx_in_flight: 0,
1066            lost: 0,
1067            has_data: false,
1068            is_pmtud_probe: false,
1069        };
1070
1071        r.on_packet_sent(
1072            p,
1073            packet::Epoch::Application,
1074            HandshakeStatus::default(),
1075            now,
1076            "",
1077        );
1078        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 2);
1079        assert_eq!(r.bytes_in_flight(), 2000);
1080        assert_eq!(r.bytes_in_flight_duration(), Duration::ZERO);
1081
1082        let p = Sent {
1083            pkt_num: 2,
1084            frames: smallvec![],
1085            time_sent: now,
1086            time_acked: None,
1087            time_lost: None,
1088            size: 1000,
1089            ack_eliciting: true,
1090            in_flight: true,
1091            delivered: 0,
1092            delivered_time: now,
1093            first_sent_time: now,
1094            is_app_limited: false,
1095            tx_in_flight: 0,
1096            lost: 0,
1097            has_data: false,
1098            is_pmtud_probe: false,
1099        };
1100
1101        r.on_packet_sent(
1102            p,
1103            packet::Epoch::Application,
1104            HandshakeStatus::default(),
1105            now,
1106            "",
1107        );
1108        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 3);
1109        assert_eq!(r.bytes_in_flight(), 3000);
1110        assert_eq!(r.bytes_in_flight_duration(), Duration::ZERO);
1111
1112        let p = Sent {
1113            pkt_num: 3,
1114            frames: smallvec![],
1115            time_sent: now,
1116            time_acked: None,
1117            time_lost: None,
1118            size: 1000,
1119            ack_eliciting: true,
1120            in_flight: true,
1121            delivered: 0,
1122            delivered_time: now,
1123            first_sent_time: now,
1124            is_app_limited: false,
1125            tx_in_flight: 0,
1126            lost: 0,
1127            has_data: false,
1128            is_pmtud_probe: false,
1129        };
1130
1131        r.on_packet_sent(
1132            p,
1133            packet::Epoch::Application,
1134            HandshakeStatus::default(),
1135            now,
1136            "",
1137        );
1138        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 4);
1139        assert_eq!(r.bytes_in_flight(), 4000);
1140        assert_eq!(r.bytes_in_flight_duration(), Duration::ZERO);
1141
1142        // Wait for 10ms.
1143        now += Duration::from_millis(10);
1144
1145        // Only the first 2 packets and the last one are acked.
1146        let mut acked = RangeSet::default();
1147        acked.insert(0..2);
1148        acked.insert(3..4);
1149
1150        assert_eq!(
1151            r.on_ack_received(
1152                &acked,
1153                25,
1154                packet::Epoch::Application,
1155                HandshakeStatus::default(),
1156                now,
1157                None,
1158                "",
1159            )
1160            .unwrap(),
1161            OnAckReceivedOutcome {
1162                lost_packets: 0,
1163                lost_bytes: 0,
1164                acked_bytes: 3 * 1000,
1165                spurious_losses: 0,
1166            }
1167        );
1168
1169        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 2);
1170        assert_eq!(r.bytes_in_flight(), 1000);
1171        assert_eq!(r.bytes_in_flight_duration(), Duration::from_millis(10));
1172        assert_eq!(r.lost_count(), 0);
1173
1174        // Wait until loss detection timer expires.
1175        now = r.loss_detection_timer().unwrap();
1176
1177        // Packet is declared lost.
1178        r.on_loss_detection_timeout(HandshakeStatus::default(), now, "");
1179        assert_eq!(r.loss_probes(packet::Epoch::Application), 0);
1180
1181        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 2);
1182        assert_eq!(r.bytes_in_flight(), 0);
1183        assert_eq!(r.bytes_in_flight_duration(), Duration::from_micros(11250));
1184
1185        assert_eq!(r.lost_count(), 1);
1186
1187        // Wait 1 RTT.
1188        now += r.rtt();
1189
1190        assert_eq!(
1191            r.detect_lost_packets_for_test(packet::Epoch::Application, now),
1192            (0, 0)
1193        );
1194
1195        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 0);
1196        if cc_algorithm_name == "reno" || cc_algorithm_name == "cubic" {
1197            assert!(r.startup_exit().is_some());
1198            assert_eq!(r.startup_exit().unwrap().reason, StartupExitReason::Loss);
1199        } else {
1200            assert_eq!(r.startup_exit(), None);
1201        }
1202    }
1203
1204    #[rstest]
1205    fn loss_on_reordering(
1206        #[values("reno", "cubic", "bbr", "bbr2", "bbr2_gcongestion")]
1207        cc_algorithm_name: &str,
1208    ) {
1209        let mut cfg = Config::new(crate::PROTOCOL_VERSION).unwrap();
1210        assert_eq!(cfg.set_cc_algorithm_name(cc_algorithm_name), Ok(()));
1211
1212        let mut r = Recovery::new(&cfg);
1213
1214        let mut now = Instant::now();
1215
1216        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 0);
1217
1218        // Start by sending a few packets.
1219        let p = Sent {
1220            pkt_num: 0,
1221            frames: smallvec![],
1222            time_sent: now,
1223            time_acked: None,
1224            time_lost: None,
1225            size: 1000,
1226            ack_eliciting: true,
1227            in_flight: true,
1228            delivered: 0,
1229            delivered_time: now,
1230            first_sent_time: now,
1231            is_app_limited: false,
1232            tx_in_flight: 0,
1233            lost: 0,
1234            has_data: false,
1235            is_pmtud_probe: false,
1236        };
1237
1238        r.on_packet_sent(
1239            p,
1240            packet::Epoch::Application,
1241            HandshakeStatus::default(),
1242            now,
1243            "",
1244        );
1245        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 1);
1246        assert_eq!(r.bytes_in_flight(), 1000);
1247        assert_eq!(r.bytes_in_flight_duration(), Duration::ZERO);
1248
1249        let p = Sent {
1250            pkt_num: 1,
1251            frames: smallvec![],
1252            time_sent: now,
1253            time_acked: None,
1254            time_lost: None,
1255            size: 1000,
1256            ack_eliciting: true,
1257            in_flight: true,
1258            delivered: 0,
1259            delivered_time: now,
1260            first_sent_time: now,
1261            is_app_limited: false,
1262            tx_in_flight: 0,
1263            lost: 0,
1264            has_data: false,
1265            is_pmtud_probe: false,
1266        };
1267
1268        r.on_packet_sent(
1269            p,
1270            packet::Epoch::Application,
1271            HandshakeStatus::default(),
1272            now,
1273            "",
1274        );
1275        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 2);
1276        assert_eq!(r.bytes_in_flight(), 2000);
1277        assert_eq!(r.bytes_in_flight_duration(), Duration::ZERO);
1278
1279        let p = Sent {
1280            pkt_num: 2,
1281            frames: smallvec![],
1282            time_sent: now,
1283            time_acked: None,
1284            time_lost: None,
1285            size: 1000,
1286            ack_eliciting: true,
1287            in_flight: true,
1288            delivered: 0,
1289            delivered_time: now,
1290            first_sent_time: now,
1291            is_app_limited: false,
1292            tx_in_flight: 0,
1293            lost: 0,
1294            has_data: false,
1295            is_pmtud_probe: false,
1296        };
1297
1298        r.on_packet_sent(
1299            p,
1300            packet::Epoch::Application,
1301            HandshakeStatus::default(),
1302            now,
1303            "",
1304        );
1305        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 3);
1306        assert_eq!(r.bytes_in_flight(), 3000);
1307        assert_eq!(r.bytes_in_flight_duration(), Duration::ZERO);
1308
1309        let p = Sent {
1310            pkt_num: 3,
1311            frames: smallvec![],
1312            time_sent: now,
1313            time_acked: None,
1314            time_lost: None,
1315            size: 1000,
1316            ack_eliciting: true,
1317            in_flight: true,
1318            delivered: 0,
1319            delivered_time: now,
1320            first_sent_time: now,
1321            is_app_limited: false,
1322            tx_in_flight: 0,
1323            lost: 0,
1324            has_data: false,
1325            is_pmtud_probe: false,
1326        };
1327
1328        r.on_packet_sent(
1329            p,
1330            packet::Epoch::Application,
1331            HandshakeStatus::default(),
1332            now,
1333            "",
1334        );
1335        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 4);
1336        assert_eq!(r.bytes_in_flight(), 4000);
1337        assert_eq!(r.bytes_in_flight_duration(), Duration::ZERO);
1338
1339        // Wait for 10ms.
1340        now += Duration::from_millis(10);
1341
1342        // ACKs are reordered.
1343        let mut acked = RangeSet::default();
1344        acked.insert(2..4);
1345
1346        assert_eq!(
1347            r.on_ack_received(
1348                &acked,
1349                25,
1350                packet::Epoch::Application,
1351                HandshakeStatus::default(),
1352                now,
1353                None,
1354                "",
1355            )
1356            .unwrap(),
1357            OnAckReceivedOutcome {
1358                lost_packets: 1,
1359                lost_bytes: 1000,
1360                acked_bytes: 1000 * 2,
1361                spurious_losses: 0,
1362            }
1363        );
1364
1365        now += Duration::from_millis(10);
1366
1367        let mut acked = RangeSet::default();
1368        acked.insert(0..2);
1369
1370        assert_eq!(r.pkt_thresh(), INITIAL_PACKET_THRESHOLD);
1371
1372        assert_eq!(
1373            r.on_ack_received(
1374                &acked,
1375                25,
1376                packet::Epoch::Application,
1377                HandshakeStatus::default(),
1378                now,
1379                None,
1380                "",
1381            )
1382            .unwrap(),
1383            OnAckReceivedOutcome {
1384                lost_packets: 0,
1385                lost_bytes: 0,
1386                acked_bytes: 1000,
1387                spurious_losses: 1,
1388            }
1389        );
1390
1391        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 0);
1392        assert_eq!(r.bytes_in_flight(), 0);
1393        assert_eq!(r.bytes_in_flight_duration(), Duration::from_millis(20));
1394
1395        // Spurious loss.
1396        assert_eq!(r.lost_count(), 1);
1397        assert_eq!(r.lost_spurious_count(), 1);
1398
1399        // Packet threshold was increased.
1400        assert_eq!(r.pkt_thresh(), 4);
1401
1402        // Wait 1 RTT.
1403        now += r.rtt();
1404
1405        assert_eq!(
1406            r.detect_lost_packets_for_test(packet::Epoch::Application, now),
1407            (0, 0)
1408        );
1409
1410        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 0);
1411        if cc_algorithm_name == "reno" || cc_algorithm_name == "cubic" {
1412            assert!(r.startup_exit().is_some());
1413            assert_eq!(r.startup_exit().unwrap().reason, StartupExitReason::Loss);
1414        } else {
1415            assert_eq!(r.startup_exit(), None);
1416        }
1417    }
1418
1419    #[rstest]
1420    fn pacing(
1421        #[values("reno", "cubic", "bbr", "bbr2", "bbr2_gcongestion")]
1422        cc_algorithm_name: &str,
1423    ) {
1424        let mut cfg = Config::new(crate::PROTOCOL_VERSION).unwrap();
1425        assert_eq!(cfg.set_cc_algorithm_name(cc_algorithm_name), Ok(()));
1426
1427        let mut r = Recovery::new(&cfg);
1428
1429        let mut now = Instant::now();
1430
1431        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 0);
1432
1433        // send out first packet burst (a full initcwnd).
1434        for i in 0..10 {
1435            let p = Sent {
1436                pkt_num: i,
1437                frames: smallvec![],
1438                time_sent: now,
1439                time_acked: None,
1440                time_lost: None,
1441                size: 1200,
1442                ack_eliciting: true,
1443                in_flight: true,
1444                delivered: 0,
1445                delivered_time: now,
1446                first_sent_time: now,
1447                is_app_limited: false,
1448                tx_in_flight: 0,
1449                lost: 0,
1450                has_data: true,
1451                is_pmtud_probe: false,
1452            };
1453
1454            r.on_packet_sent(
1455                p,
1456                packet::Epoch::Application,
1457                HandshakeStatus::default(),
1458                now,
1459                "",
1460            );
1461        }
1462
1463        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 10);
1464        assert_eq!(r.bytes_in_flight(), 12000);
1465        assert_eq!(r.bytes_in_flight_duration(), Duration::ZERO);
1466
1467        // Next packet will be sent out immediately.
1468        if cc_algorithm_name != "bbr2_gcongestion" {
1469            assert_eq!(r.pacing_rate(), 0);
1470        } else {
1471            assert_eq!(r.pacing_rate(), 103963);
1472        }
1473        assert_eq!(r.get_packet_send_time(now), now);
1474
1475        assert_eq!(r.cwnd(), 12000);
1476        assert_eq!(r.cwnd_available(), 0);
1477
1478        // Wait 50ms for ACK.
1479        now += Duration::from_millis(50);
1480
1481        let mut acked = RangeSet::default();
1482        acked.insert(0..10);
1483
1484        assert_eq!(
1485            r.on_ack_received(
1486                &acked,
1487                10,
1488                packet::Epoch::Application,
1489                HandshakeStatus::default(),
1490                now,
1491                None,
1492                "",
1493            )
1494            .unwrap(),
1495            OnAckReceivedOutcome {
1496                lost_packets: 0,
1497                lost_bytes: 0,
1498                acked_bytes: 12000,
1499                spurious_losses: 0,
1500            }
1501        );
1502
1503        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 0);
1504        assert_eq!(r.bytes_in_flight(), 0);
1505        assert_eq!(r.bytes_in_flight_duration(), Duration::from_millis(50));
1506        assert_eq!(r.rtt(), Duration::from_millis(50));
1507
1508        // 10 MSS increased due to acks.
1509        assert_eq!(r.cwnd(), 12000 + 1200 * 10);
1510
1511        // Send the second packet burst.
1512        let p = Sent {
1513            pkt_num: 10,
1514            frames: smallvec![],
1515            time_sent: now,
1516            time_acked: None,
1517            time_lost: None,
1518            size: 6000,
1519            ack_eliciting: true,
1520            in_flight: true,
1521            delivered: 0,
1522            delivered_time: now,
1523            first_sent_time: now,
1524            is_app_limited: false,
1525            tx_in_flight: 0,
1526            lost: 0,
1527            has_data: true,
1528            is_pmtud_probe: false,
1529        };
1530
1531        r.on_packet_sent(
1532            p,
1533            packet::Epoch::Application,
1534            HandshakeStatus::default(),
1535            now,
1536            "",
1537        );
1538
1539        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 1);
1540        assert_eq!(r.bytes_in_flight(), 6000);
1541        assert_eq!(r.bytes_in_flight_duration(), Duration::from_millis(50));
1542
1543        if cc_algorithm_name != "bbr2_gcongestion" {
1544            // Pacing is not done during initial phase of connection.
1545            assert_eq!(r.get_packet_send_time(now), now);
1546        } else {
1547            // Pacing is done from the beginning.
1548            assert_ne!(r.get_packet_send_time(now), now);
1549        }
1550
1551        // Send the third packet burst.
1552        let p = Sent {
1553            pkt_num: 11,
1554            frames: smallvec![],
1555            time_sent: now,
1556            time_acked: None,
1557            time_lost: None,
1558            size: 6000,
1559            ack_eliciting: true,
1560            in_flight: true,
1561            delivered: 0,
1562            delivered_time: now,
1563            first_sent_time: now,
1564            is_app_limited: false,
1565            tx_in_flight: 0,
1566            lost: 0,
1567            has_data: true,
1568            is_pmtud_probe: false,
1569        };
1570
1571        r.on_packet_sent(
1572            p,
1573            packet::Epoch::Application,
1574            HandshakeStatus::default(),
1575            now,
1576            "",
1577        );
1578
1579        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 2);
1580        assert_eq!(r.bytes_in_flight(), 12000);
1581        assert_eq!(r.bytes_in_flight_duration(), Duration::from_millis(50));
1582
1583        // Send the fourth packet burst.
1584        let p = Sent {
1585            pkt_num: 12,
1586            frames: smallvec![],
1587            time_sent: now,
1588            time_acked: None,
1589            time_lost: None,
1590            size: 1000,
1591            ack_eliciting: true,
1592            in_flight: true,
1593            delivered: 0,
1594            delivered_time: now,
1595            first_sent_time: now,
1596            is_app_limited: false,
1597            tx_in_flight: 0,
1598            lost: 0,
1599            has_data: true,
1600            is_pmtud_probe: false,
1601        };
1602
1603        r.on_packet_sent(
1604            p,
1605            packet::Epoch::Application,
1606            HandshakeStatus::default(),
1607            now,
1608            "",
1609        );
1610
1611        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 3);
1612        assert_eq!(r.bytes_in_flight(), 13000);
1613        assert_eq!(r.bytes_in_flight_duration(), Duration::from_millis(50));
1614
1615        // We pace this outgoing packet. as all conditions for pacing
1616        // are passed.
1617        let pacing_rate = match cc_algorithm_name {
1618            "bbr" => {
1619                // Constants from congestion/bbr/mod.rs
1620                let cwnd_gain = 2.0;
1621                let startup_pacing_gain = 2.89;
1622                // Adjust for cwnd_gain.  BW estimate was made before the CWND
1623                // increase.
1624                let bw = r.cwnd() as f64 /
1625                    cwnd_gain /
1626                    Duration::from_millis(50).as_secs_f64();
1627                (bw * startup_pacing_gain) as u64
1628            },
1629            "bbr2_gcongestion" => {
1630                let cwnd_gain: f64 = 2.0;
1631                // Adjust for cwnd_gain.  BW estimate was made before the CWND
1632                // increase.
1633                let bw = r.cwnd() as f64 /
1634                    cwnd_gain /
1635                    Duration::from_millis(50).as_secs_f64();
1636                bw as u64
1637            },
1638            "bbr2" => {
1639                // Constants from congestion/bbr2/mod.rs
1640                let cwnd_gain = 2.0;
1641                let startup_pacing_gain = 2.77;
1642                let pacing_margin_percent = 0.01;
1643                // Adjust for cwnd_gain.  BW estimate was made before the CWND
1644                // increase.
1645                let bw = r.cwnd() as f64 /
1646                    cwnd_gain /
1647                    Duration::from_millis(50).as_secs_f64();
1648                (bw * startup_pacing_gain * (1.0 - pacing_margin_percent)) as u64
1649            },
1650            _ => {
1651                let bw =
1652                    r.cwnd() as f64 / Duration::from_millis(50).as_secs_f64();
1653                (bw * PACING_MULTIPLIER) as u64
1654            },
1655        };
1656        assert_eq!(r.pacing_rate(), pacing_rate);
1657
1658        let scale_factor = if cc_algorithm_name == "bbr2_gcongestion" {
1659            // For bbr2_gcongestion, send time is almost 13000 / pacing_rate.
1660            // Don't know where 13000 comes from.
1661            1.08333332
1662        } else {
1663            1.0
1664        };
1665        assert_eq!(
1666            r.get_packet_send_time(now) - now,
1667            Duration::from_secs_f64(scale_factor * 12000.0 / pacing_rate as f64)
1668        );
1669        assert_eq!(r.startup_exit(), None);
1670    }
1671
1672    #[rstest]
1673    fn validate_ack_range_on_ack_received(
1674        #[values("cubic", "bbr2", "bbr2_gcongestion")] cc_algorithm_name: &str,
1675    ) {
1676        let mut cfg = Config::new(crate::PROTOCOL_VERSION).unwrap();
1677        cfg.set_cc_algorithm_name(cc_algorithm_name).unwrap();
1678
1679        let epoch = packet::Epoch::Application;
1680        let mut r = Recovery::new(&cfg);
1681        let mut now = Instant::now();
1682        assert_eq!(r.sent_packets_len(epoch), 0);
1683
1684        // Send 4 packets
1685        let pkt_size = 1000;
1686        let pkt_count = 4;
1687        for pkt_num in 0..pkt_count {
1688            let sent = test_utils::helper_packet_sent(pkt_num, now, pkt_size);
1689            r.on_packet_sent(sent, epoch, HandshakeStatus::default(), now, "");
1690        }
1691        assert_eq!(r.sent_packets_len(epoch), pkt_count as usize);
1692        assert_eq!(r.bytes_in_flight(), pkt_count as usize * pkt_size);
1693        assert!(r.get_largest_acked_on_epoch(epoch).is_none());
1694        assert_eq!(r.largest_sent_pkt_num_on_path(epoch).unwrap(), 3);
1695
1696        // Wait for 10ms.
1697        now += Duration::from_millis(10);
1698
1699        // ACK 2 packets
1700        let mut acked = RangeSet::default();
1701        acked.insert(0..2);
1702
1703        assert_eq!(
1704            r.on_ack_received(
1705                &acked,
1706                25,
1707                epoch,
1708                HandshakeStatus::default(),
1709                now,
1710                None,
1711                "",
1712            )
1713            .unwrap(),
1714            OnAckReceivedOutcome {
1715                lost_packets: 0,
1716                lost_bytes: 0,
1717                acked_bytes: 2 * 1000,
1718                spurious_losses: 0,
1719            }
1720        );
1721
1722        assert_eq!(r.sent_packets_len(epoch), 2);
1723        assert_eq!(r.bytes_in_flight(), 2 * 1000);
1724
1725        assert_eq!(r.get_largest_acked_on_epoch(epoch).unwrap(), 1);
1726        assert_eq!(r.largest_sent_pkt_num_on_path(epoch).unwrap(), 3);
1727
1728        // ACK large range
1729        let mut acked = RangeSet::default();
1730        acked.insert(0..10);
1731        assert_eq!(
1732            r.on_ack_received(
1733                &acked,
1734                25,
1735                epoch,
1736                HandshakeStatus::default(),
1737                now,
1738                None,
1739                "",
1740            )
1741            .unwrap(),
1742            OnAckReceivedOutcome {
1743                lost_packets: 0,
1744                lost_bytes: 0,
1745                acked_bytes: 2 * 1000,
1746                spurious_losses: 0,
1747            }
1748        );
1749        assert_eq!(r.sent_packets_len(epoch), 0);
1750        assert_eq!(r.bytes_in_flight(), 0);
1751
1752        assert_eq!(r.get_largest_acked_on_epoch(epoch).unwrap(), 3);
1753        assert_eq!(r.largest_sent_pkt_num_on_path(epoch).unwrap(), 3);
1754    }
1755
1756    #[rstest]
1757    fn pmtud_loss_on_timer(
1758        #[values("reno", "cubic", "bbr", "bbr2", "bbr2_gcongestion")]
1759        cc_algorithm_name: &str,
1760    ) {
1761        let mut cfg = Config::new(crate::PROTOCOL_VERSION).unwrap();
1762        assert_eq!(cfg.set_cc_algorithm_name(cc_algorithm_name), Ok(()));
1763
1764        let mut r = Recovery::new(&cfg);
1765        assert_eq!(r.cwnd(), 12000);
1766
1767        let mut now = Instant::now();
1768
1769        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 0);
1770
1771        // Start by sending a few packets.
1772        let p = Sent {
1773            pkt_num: 0,
1774            frames: smallvec![],
1775            time_sent: now,
1776            time_acked: None,
1777            time_lost: None,
1778            size: 1000,
1779            ack_eliciting: true,
1780            in_flight: true,
1781            delivered: 0,
1782            delivered_time: now,
1783            first_sent_time: now,
1784            is_app_limited: false,
1785            tx_in_flight: 0,
1786            lost: 0,
1787            has_data: false,
1788            is_pmtud_probe: false,
1789        };
1790
1791        r.on_packet_sent(
1792            p,
1793            packet::Epoch::Application,
1794            HandshakeStatus::default(),
1795            now,
1796            "",
1797        );
1798
1799        assert_eq!(r.in_flight_count(packet::Epoch::Application), 1);
1800        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 1);
1801        assert_eq!(r.bytes_in_flight(), 1000);
1802        assert_eq!(r.bytes_in_flight_duration(), Duration::ZERO);
1803
1804        let p = Sent {
1805            pkt_num: 1,
1806            frames: smallvec![],
1807            time_sent: now,
1808            time_acked: None,
1809            time_lost: None,
1810            size: 1000,
1811            ack_eliciting: true,
1812            in_flight: true,
1813            delivered: 0,
1814            delivered_time: now,
1815            first_sent_time: now,
1816            is_app_limited: false,
1817            tx_in_flight: 0,
1818            lost: 0,
1819            has_data: false,
1820            is_pmtud_probe: true,
1821        };
1822
1823        r.on_packet_sent(
1824            p,
1825            packet::Epoch::Application,
1826            HandshakeStatus::default(),
1827            now,
1828            "",
1829        );
1830
1831        assert_eq!(r.in_flight_count(packet::Epoch::Application), 2);
1832
1833        let p = Sent {
1834            pkt_num: 2,
1835            frames: smallvec![],
1836            time_sent: now,
1837            time_acked: None,
1838            time_lost: None,
1839            size: 1000,
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: false,
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.in_flight_count(packet::Epoch::Application), 3);
1861
1862        // Wait for 10ms.
1863        now += Duration::from_millis(10);
1864
1865        // Only the first  packets and the last one are acked.
1866        let mut acked = RangeSet::default();
1867        acked.insert(0..1);
1868        acked.insert(2..3);
1869
1870        assert_eq!(
1871            r.on_ack_received(
1872                &acked,
1873                25,
1874                packet::Epoch::Application,
1875                HandshakeStatus::default(),
1876                now,
1877                None,
1878                "",
1879            )
1880            .unwrap(),
1881            OnAckReceivedOutcome {
1882                lost_packets: 0,
1883                lost_bytes: 0,
1884                acked_bytes: 2 * 1000,
1885                spurious_losses: 0,
1886            }
1887        );
1888
1889        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 2);
1890        assert_eq!(r.bytes_in_flight(), 1000);
1891        assert_eq!(r.bytes_in_flight_duration(), Duration::from_millis(10));
1892        assert_eq!(r.lost_count(), 0);
1893
1894        // Wait until loss detection timer expires.
1895        now = r.loss_detection_timer().unwrap();
1896
1897        // Packet is declared lost.
1898        r.on_loss_detection_timeout(HandshakeStatus::default(), now, "");
1899        assert_eq!(r.loss_probes(packet::Epoch::Application), 0);
1900
1901        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 2);
1902        assert_eq!(r.in_flight_count(packet::Epoch::Application), 0);
1903        assert_eq!(r.bytes_in_flight(), 0);
1904        assert_eq!(r.bytes_in_flight_duration(), Duration::from_micros(11250));
1905        assert_eq!(r.cwnd(), match cc_algorithm_name {
1906            "bbr" => 14000,
1907            "bbr2" => 14000,
1908            _ => 12000,
1909        });
1910
1911        assert_eq!(r.lost_count(), 0);
1912
1913        // Wait 1 RTT.
1914        now += r.rtt();
1915
1916        assert_eq!(
1917            r.detect_lost_packets_for_test(packet::Epoch::Application, now),
1918            (0, 0)
1919        );
1920
1921        assert_eq!(r.sent_packets_len(packet::Epoch::Application), 0);
1922        assert_eq!(r.in_flight_count(packet::Epoch::Application), 0);
1923        assert_eq!(r.bytes_in_flight(), 0);
1924        assert_eq!(r.bytes_in_flight_duration(), Duration::from_micros(11250));
1925        assert_eq!(r.lost_count(), 0);
1926        assert_eq!(r.startup_exit(), None);
1927    }
1928
1929    // Modeling delivery_rate for gcongestion is non-trivial so we only test the
1930    // congestion specific algorithms.
1931    #[rstest]
1932    fn congestion_delivery_rate(
1933        #[values("reno", "cubic", "bbr", "bbr2")] cc_algorithm_name: &str,
1934    ) {
1935        let mut cfg = Config::new(crate::PROTOCOL_VERSION).unwrap();
1936        assert_eq!(cfg.set_cc_algorithm_name(cc_algorithm_name), Ok(()));
1937
1938        let mut r = Recovery::new(&cfg);
1939        assert_eq!(r.cwnd(), 12000);
1940
1941        let now = Instant::now();
1942
1943        let mut total_bytes_sent = 0;
1944        for pn in 0..10 {
1945            // Start by sending a few packets.
1946            let bytes = 1000;
1947            let sent = test_utils::helper_packet_sent(pn, now, bytes);
1948            r.on_packet_sent(
1949                sent,
1950                packet::Epoch::Application,
1951                HandshakeStatus::default(),
1952                now,
1953                "",
1954            );
1955
1956            total_bytes_sent += bytes;
1957        }
1958
1959        // Ack
1960        let interval = Duration::from_secs(10);
1961        let mut acked = RangeSet::default();
1962        acked.insert(0..10);
1963        assert_eq!(
1964            r.on_ack_received(
1965                &acked,
1966                25,
1967                packet::Epoch::Application,
1968                HandshakeStatus::default(),
1969                now + interval,
1970                None,
1971                "",
1972            )
1973            .unwrap(),
1974            OnAckReceivedOutcome {
1975                lost_packets: 0,
1976                lost_bytes: 0,
1977                acked_bytes: total_bytes_sent,
1978                spurious_losses: 0,
1979            }
1980        );
1981        assert_eq!(r.delivery_rate().to_bytes_per_second(), 1000);
1982        assert_eq!(r.min_rtt().unwrap(), interval);
1983        // delivery rate should be in units bytes/sec
1984        assert_eq!(
1985            total_bytes_sent as u64 / interval.as_secs(),
1986            r.delivery_rate().to_bytes_per_second()
1987        );
1988        assert_eq!(r.startup_exit(), None);
1989    }
1990}
1991
1992mod bandwidth;
1993mod bytes_in_flight;
1994mod congestion;
1995mod gcongestion;
1996mod rtt;