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