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

quiche/recovery/
mod.rs
