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

quiche/recovery/congestion/
mod.rs
