quiche/recovery/congestion/
hystart.rs

1// Copyright (C) 2020, 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
27//! HyStart++
28//!
29//! This implementation is based on the following I-D:
30//!
31//! <https://datatracker.ietf.org/doc/html/draft-ietf-tcpm-hystartplusplus-04>
32
33use std::cmp;
34use std::time::Duration;
35use std::time::Instant;
36
37use super::Acked;
38
39/// Constants from I-D.
40const MIN_RTT_THRESH: Duration = Duration::from_millis(4);
41
42const MAX_RTT_THRESH: Duration = Duration::from_millis(16);
43
44pub const N_RTT_SAMPLE: usize = 8;
45
46pub const CSS_GROWTH_DIVISOR: usize = 4;
47
48pub const CSS_ROUNDS: usize = 5;
49
50#[derive(Default)]
51pub struct Hystart {
52    enabled: bool,
53
54    window_end: Option<u64>,
55
56    last_round_min_rtt: Duration,
57
58    current_round_min_rtt: Duration,
59
60    css_baseline_min_rtt: Duration,
61
62    rtt_sample_count: usize,
63
64    css_start_time: Option<Instant>,
65
66    css_round_count: usize,
67}
68
69impl std::fmt::Debug for Hystart {
70    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
71        write!(f, "window_end={:?} ", self.window_end)?;
72        write!(f, "last_round_min_rtt={:?} ", self.last_round_min_rtt)?;
73        write!(f, "current_round_min_rtt={:?} ", self.current_round_min_rtt)?;
74        write!(f, "css_baseline_min_rtt={:?} ", self.css_baseline_min_rtt)?;
75        write!(f, "rtt_sample_count={:?} ", self.rtt_sample_count)?;
76        write!(f, "css_start_time={:?} ", self.css_start_time)?;
77        write!(f, "css_round_count={:?}", self.css_round_count)?;
78
79        Ok(())
80    }
81}
82
83impl Hystart {
84    pub fn new(enabled: bool) -> Self {
85        Self {
86            enabled,
87
88            last_round_min_rtt: Duration::MAX,
89
90            current_round_min_rtt: Duration::MAX,
91
92            css_baseline_min_rtt: Duration::MAX,
93
94            ..Default::default()
95        }
96    }
97
98    pub fn enabled(&self) -> bool {
99        self.enabled
100    }
101
102    pub fn css_start_time(&self) -> Option<Instant> {
103        self.css_start_time
104    }
105
106    pub fn in_css(&self) -> bool {
107        self.enabled && self.css_start_time().is_some()
108    }
109
110    pub fn start_round(&mut self, pkt_num: u64) {
111        if self.window_end.is_none() {
112            self.window_end = Some(pkt_num);
113
114            self.last_round_min_rtt = self.current_round_min_rtt;
115
116            self.current_round_min_rtt = Duration::MAX;
117
118            self.rtt_sample_count = 0;
119        }
120    }
121
122    // On receiving ACK. Returns true if need to enter Congestion Avoidance.
123    pub fn on_packet_acked(
124        &mut self, packet: &Acked, rtt: Duration, now: Instant,
125    ) -> bool {
126        if !self.enabled {
127            return false;
128        }
129
130        self.current_round_min_rtt = cmp::min(self.current_round_min_rtt, rtt);
131
132        self.rtt_sample_count += 1;
133
134        // Slow Start.
135        if self.css_start_time().is_none() {
136            if self.rtt_sample_count >= N_RTT_SAMPLE &&
137                self.current_round_min_rtt != Duration::MAX &&
138                self.last_round_min_rtt != Duration::MAX
139            {
140                // clamp(min_rtt_thresh, last_round_min_rtt/8,
141                // max_rtt_thresh)
142                let rtt_thresh =
143                    cmp::max(self.last_round_min_rtt / 8, MIN_RTT_THRESH);
144                let rtt_thresh = cmp::min(rtt_thresh, MAX_RTT_THRESH);
145
146                // Check if we can exit to CSS.
147                if self.current_round_min_rtt >=
148                    self.last_round_min_rtt.saturating_add(rtt_thresh)
149                {
150                    self.css_baseline_min_rtt = self.current_round_min_rtt;
151                    self.css_start_time = Some(now);
152                }
153            }
154        } else {
155            // Conservative Slow Start.
156            if self.rtt_sample_count >= N_RTT_SAMPLE {
157                self.rtt_sample_count = 0;
158
159                if self.current_round_min_rtt < self.css_baseline_min_rtt {
160                    self.css_baseline_min_rtt = Duration::MAX;
161
162                    // Back to Slow Start.
163                    self.css_start_time = None;
164                    self.css_round_count = 0;
165                }
166            }
167        }
168
169        // Check if we reached the end of the round.
170        if let Some(end_pkt_num) = self.window_end {
171            if packet.pkt_num >= end_pkt_num {
172                // Start of a new round.
173                self.window_end = None;
174
175                if self.css_start_time().is_some() {
176                    self.css_round_count += 1;
177
178                    // End of CSS - exit to congestion avoidance.
179                    if self.css_round_count >= CSS_ROUNDS {
180                        self.css_round_count = 0;
181                        return true;
182                    }
183                }
184            }
185        }
186
187        false
188    }
189
190    // Return a cwnd increment during CSS (Conservative Slow Start).
191    pub fn css_cwnd_inc(&self, pkt_size: usize) -> usize {
192        pkt_size / CSS_GROWTH_DIVISOR
193    }
194
195    // Exit HyStart++ when entering congestion avoidance.
196    pub fn congestion_event(&mut self) {
197        self.window_end = None;
198        self.css_start_time = None;
199    }
200}
201
202#[cfg(test)]
203mod tests {
204    use super::*;
205
206    #[test]
207    fn start_round() {
208        let mut hspp = Hystart::default();
209        let pkt_num = 100;
210
211        hspp.start_round(pkt_num);
212
213        assert_eq!(hspp.window_end, Some(pkt_num));
214        assert_eq!(hspp.current_round_min_rtt, Duration::MAX);
215    }
216
217    #[test]
218    fn css_cwnd_inc() {
219        let hspp = Hystart::default();
220        let datagram_size = 1200;
221
222        let css_cwnd_inc = hspp.css_cwnd_inc(datagram_size);
223
224        assert_eq!(datagram_size / CSS_GROWTH_DIVISOR, css_cwnd_inc);
225    }
226
227    #[test]
228    fn congestion_event() {
229        let mut hspp = Hystart::default();
230        let pkt_num = 100;
231
232        hspp.start_round(pkt_num);
233
234        assert_eq!(hspp.window_end, Some(pkt_num));
235
236        // When moving into CA mode, window_end should be cleared.
237        hspp.congestion_event();
238
239        assert_eq!(hspp.window_end, None);
240    }
241}
quiche/recovery/congestion/hystart.rs

quiche/recovery/congestion/
hystart.rs
