quiche/recovery/congestion/
mod.rs

1// Copyright (C) 2024, 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::Instant;
29
30use super::rtt::RttStats;
31use super::Acked;
32use super::RecoveryConfig;
33use super::Sent;
34
35pub const PACING_MULTIPLIER: f64 = 1.25;
36pub struct Congestion {
37    // Congestion control.
38    pub(crate) cc_ops: &'static CongestionControlOps,
39
40    cubic_state: cubic::State,
41
42    // HyStart++.
43    pub(crate) hystart: hystart::Hystart,
44
45    // Pacing.
46    pub(crate) pacer: pacer::Pacer,
47
48    // RFC6937 PRR.
49    pub(crate) prr: prr::PRR,
50
51    // The maximum size of a data aggregate scheduled and
52    // transmitted together.
53    send_quantum: usize,
54
55    // BBR state.
56    bbr_state: bbr::State,
57
58    // BBRv2 state.
59    bbr2_state: bbr2::State,
60
61    pub(crate) congestion_window: usize,
62
63    pub(crate) ssthresh: usize,
64
65    bytes_acked_sl: usize,
66
67    bytes_acked_ca: usize,
68
69    pub(crate) congestion_recovery_start_time: Option<Instant>,
70
71    pub(crate) app_limited: bool,
72
73    pub(crate) delivery_rate: delivery_rate::Rate,
74
75    /// Initial congestion window size in terms of packet count.
76    pub(crate) initial_congestion_window_packets: usize,
77
78    max_datagram_size: usize,
79
80    pub(crate) lost_count: usize,
81}
82
83impl Congestion {
84    pub(crate) fn from_config(recovery_config: &RecoveryConfig) -> Self {
85        let initial_congestion_window = recovery_config.max_send_udp_payload_size *
86            recovery_config.initial_congestion_window_packets;
87
88        let mut cc = Congestion {
89            congestion_window: initial_congestion_window,
90
91            ssthresh: usize::MAX,
92
93            bytes_acked_sl: 0,
94
95            bytes_acked_ca: 0,
96
97            congestion_recovery_start_time: None,
98
99            cc_ops: recovery_config.cc_algorithm.into(),
100
101            cubic_state: cubic::State::default(),
102
103            app_limited: false,
104
105            lost_count: 0,
106
107            initial_congestion_window_packets: recovery_config
108                .initial_congestion_window_packets,
109
110            max_datagram_size: recovery_config.max_send_udp_payload_size,
111
112            send_quantum: initial_congestion_window,
113
114            delivery_rate: delivery_rate::Rate::default(),
115
116            hystart: hystart::Hystart::new(recovery_config.hystart),
117
118            pacer: pacer::Pacer::new(
119                recovery_config.pacing,
120                initial_congestion_window,
121                0,
122                recovery_config.max_send_udp_payload_size,
123                recovery_config.max_pacing_rate,
124            ),
125
126            prr: prr::PRR::default(),
127
128            bbr_state: bbr::State::new(),
129
130            bbr2_state: bbr2::State::new(),
131        };
132
133        (cc.cc_ops.on_init)(&mut cc);
134
135        cc
136    }
137
138    pub(crate) fn in_congestion_recovery(&self, sent_time: Instant) -> bool {
139        match self.congestion_recovery_start_time {
140            Some(congestion_recovery_start_time) =>
141                sent_time <= congestion_recovery_start_time,
142
143            None => false,
144        }
145    }
146
147    pub(crate) fn delivery_rate(&self) -> u64 {
148        self.delivery_rate.sample_delivery_rate()
149    }
150
151    pub(crate) fn send_quantum(&self) -> usize {
152        self.send_quantum
153    }
154
155    pub(crate) fn set_pacing_rate(&mut self, rate: u64, now: Instant) {
156        self.pacer.update(self.send_quantum, rate, now);
157    }
158
159    pub(crate) fn congestion_window(&self) -> usize {
160        self.congestion_window
161    }
162
163    fn update_app_limited(&mut self, v: bool) {
164        self.app_limited = v;
165    }
166
167    #[allow(clippy::too_many_arguments)]
168    pub(crate) fn on_packet_sent(
169        &mut self, bytes_in_flight: usize, sent_bytes: usize, now: Instant,
170        pkt: &mut Sent, rtt_stats: &RttStats, bytes_lost: u64, in_flight: bool,
171    ) {
172        if in_flight {
173            self.update_app_limited(
174                (bytes_in_flight + sent_bytes) < self.congestion_window,
175            );
176
177            (self.cc_ops.on_packet_sent)(self, sent_bytes, bytes_in_flight, now);
178
179            self.prr.on_packet_sent(sent_bytes);
180
181            // HyStart++: Start of the round in a slow start.
182            if self.hystart.enabled() && self.congestion_window < self.ssthresh {
183                self.hystart.start_round(pkt.pkt_num);
184            }
185        }
186
187        // Pacing: Set the pacing rate if CC doesn't do its own.
188        if !(self.cc_ops.has_custom_pacing)() &&
189            rtt_stats.first_rtt_sample.is_some()
190        {
191            let rate = PACING_MULTIPLIER * self.congestion_window as f64 /
192                rtt_stats.smoothed_rtt.as_secs_f64();
193            self.set_pacing_rate(rate as u64, now);
194        }
195
196        self.schedule_next_packet(now, sent_bytes);
197
198        pkt.time_sent = self.get_packet_send_time();
199
200        // bytes_in_flight is already updated. Use previous value.
201        self.delivery_rate
202            .on_packet_sent(pkt, bytes_in_flight, bytes_lost);
203    }
204
205    pub(crate) fn on_packets_acked(
206        &mut self, bytes_in_flight: usize, acked: &mut Vec<Acked>,
207        rtt_stats: &RttStats, now: Instant,
208    ) {
209        // Update delivery rate sample per acked packet.
210        for pkt in acked.iter() {
211            self.delivery_rate.update_rate_sample(pkt, now);
212        }
213
214        // Fill in a rate sample.
215        self.delivery_rate.generate_rate_sample(*rtt_stats.min_rtt);
216
217        // Call congestion control hooks.
218        (self.cc_ops.on_packets_acked)(
219            self,
220            bytes_in_flight,
221            acked,
222            now,
223            rtt_stats,
224        );
225    }
226
227    fn schedule_next_packet(&mut self, now: Instant, packet_size: usize) {
228        // Don't pace in any of these cases:
229        //   * Packet contains no data.
230        //   * The congestion window is within initcwnd.
231
232        let in_initcwnd = self.congestion_window <
233            self.max_datagram_size * self.initial_congestion_window_packets;
234
235        let sent_bytes = if !self.pacer.enabled() || in_initcwnd {
236            0
237        } else {
238            packet_size
239        };
240
241        self.pacer.send(sent_bytes, now);
242    }
243
244    pub(crate) fn get_packet_send_time(&self) -> Instant {
245        self.pacer.next_time()
246    }
247}
248
249/// Available congestion control algorithms.
250///
251/// This enum provides currently available list of congestion control
252/// algorithms.
253#[derive(Debug, Copy, Clone, PartialEq, Eq)]
254#[repr(C)]
255pub enum CongestionControlAlgorithm {
256    /// Reno congestion control algorithm. `reno` in a string form.
257    Reno  = 0,
258    /// CUBIC congestion control algorithm (default). `cubic` in a string form.
259    CUBIC = 1,
260    /// BBR congestion control algorithm. `bbr` in a string form.
261    BBR   = 2,
262    /// BBRv2 congestion control algorithm. `bbr2` in a string form.
263    BBR2  = 3,
264}
265
266impl FromStr for CongestionControlAlgorithm {
267    type Err = crate::Error;
268
269    /// Converts a string to `CongestionControlAlgorithm`.
270    ///
271    /// If `name` is not valid, `Error::CongestionControl` is returned.
272    fn from_str(name: &str) -> std::result::Result<Self, Self::Err> {
273        match name {
274            "reno" => Ok(CongestionControlAlgorithm::Reno),
275            "cubic" => Ok(CongestionControlAlgorithm::CUBIC),
276            "bbr" => Ok(CongestionControlAlgorithm::BBR),
277            "bbr2" => Ok(CongestionControlAlgorithm::BBR2),
278
279            _ => Err(crate::Error::CongestionControl),
280        }
281    }
282}
283
284pub(crate) struct CongestionControlOps {
285    pub on_init: fn(r: &mut Congestion),
286
287    pub on_packet_sent: fn(
288        r: &mut Congestion,
289        sent_bytes: usize,
290        bytes_in_flight: usize,
291        now: Instant,
292    ),
293
294    pub on_packets_acked: fn(
295        r: &mut Congestion,
296        bytes_in_flight: usize,
297        packets: &mut Vec<Acked>,
298        now: Instant,
299        rtt_stats: &RttStats,
300    ),
301
302    pub congestion_event: fn(
303        r: &mut Congestion,
304        bytes_in_flight: usize,
305        lost_bytes: usize,
306        largest_lost_packet: &Sent,
307        now: Instant,
308    ),
309
310    pub checkpoint: fn(r: &mut Congestion),
311
312    pub rollback: fn(r: &mut Congestion) -> bool,
313
314    pub has_custom_pacing: fn() -> bool,
315
316    pub debug_fmt: fn(
317        r: &Congestion,
318        formatter: &mut std::fmt::Formatter,
319    ) -> std::fmt::Result,
320}
321
322impl From<CongestionControlAlgorithm> for &'static CongestionControlOps {
323    fn from(algo: CongestionControlAlgorithm) -> Self {
324        match algo {
325            CongestionControlAlgorithm::Reno => &reno::RENO,
326            CongestionControlAlgorithm::CUBIC => &cubic::CUBIC,
327            CongestionControlAlgorithm::BBR => &bbr::BBR,
328            CongestionControlAlgorithm::BBR2 => &bbr2::BBR2,
329        }
330    }
331}
332
333mod bbr;
334mod bbr2;
335mod cubic;
336mod delivery_rate;
337mod hystart;
338pub(crate) mod pacer;
339mod prr;
340mod reno;
341
342#[cfg(test)]
343mod test_sender;
quiche/recovery/congestion/mod.rs

quiche/recovery/congestion/
mod.rs
