| // Copyright (C) 2020, Cloudflare, Inc. |
| // All rights reserved. |
| // |
| // Redistribution and use in source and binary forms, with or without |
| // modification, are permitted provided that the following conditions are |
| // met: |
| // |
| // * Redistributions of source code must retain the above copyright notice, |
| // this list of conditions and the following disclaimer. |
| // |
| // * Redistributions in binary form must reproduce the above copyright |
| // notice, this list of conditions and the following disclaimer in the |
| // documentation and/or other materials provided with the distribution. |
| // |
| // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS |
| // IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, |
| // THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
| // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR |
| // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
| // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
| // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF |
| // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING |
| // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
| // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| |
| //! HyStart++ |
| //! |
| //! This implementation is based on the following I-D: |
| //! |
| //! <https://tools.ietf.org/html/draft-balasubramanian-tcpm-hystartplusplus-03> |
| |
| use std::cmp; |
| use std::time::Duration; |
| use std::time::Instant; |
| |
| use crate::packet; |
| use crate::recovery; |
| |
| /// Constants from I-D. |
| const LOW_CWND: usize = 16; |
| |
| const MIN_RTT_THRESH: Duration = Duration::from_millis(4); |
| |
| const MAX_RTT_THRESH: Duration = Duration::from_millis(16); |
| |
| pub const LSS_DIVISOR: f64 = 0.25; |
| |
| pub const N_RTT_SAMPLE: usize = 8; |
| |
| #[derive(Default)] |
| pub struct Hystart { |
| enabled: bool, |
| |
| window_end: Option<u64>, |
| |
| last_round_min_rtt: Option<Duration>, |
| |
| current_round_min_rtt: Option<Duration>, |
| |
| rtt_sample_count: usize, |
| |
| lss_start_time: Option<Instant>, |
| } |
| |
| impl std::fmt::Debug for Hystart { |
| fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result { |
| write!(f, "window_end={:?} ", self.window_end)?; |
| write!(f, "last_round_min_rtt={:?} ", self.last_round_min_rtt)?; |
| write!(f, "current_round_min_rtt={:?} ", self.current_round_min_rtt)?; |
| write!(f, "rtt_sample_count={:?} ", self.rtt_sample_count)?; |
| write!(f, "lss_start_time={:?} ", self.lss_start_time)?; |
| |
| Ok(()) |
| } |
| } |
| |
| impl Hystart { |
| pub fn new(enabled: bool) -> Self { |
| Self { |
| enabled, |
| |
| ..Default::default() |
| } |
| } |
| |
| pub fn enabled(&self) -> bool { |
| self.enabled |
| } |
| |
| pub fn lss_start_time(&self) -> Option<Instant> { |
| self.lss_start_time |
| } |
| |
| pub fn in_lss(&self, epoch: packet::Epoch) -> bool { |
| self.enabled && |
| epoch == packet::EPOCH_APPLICATION && |
| self.lss_start_time().is_some() |
| } |
| |
| pub fn start_round(&mut self, pkt_num: u64) { |
| if self.window_end.is_none() { |
| *self = Hystart { |
| enabled: self.enabled, |
| |
| window_end: Some(pkt_num), |
| |
| last_round_min_rtt: self.current_round_min_rtt, |
| |
| current_round_min_rtt: None, |
| |
| rtt_sample_count: 0, |
| |
| lss_start_time: None, |
| }; |
| } |
| } |
| |
| // Returns true if LSS started. |
| pub fn try_enter_lss( |
| &mut self, packet: &recovery::Acked, rtt: Duration, cwnd: usize, |
| now: Instant, max_datagram_size: usize, |
| ) -> bool { |
| if self.lss_start_time().is_none() { |
| if let Some(current_round_min_rtt) = self.current_round_min_rtt { |
| self.current_round_min_rtt = |
| Some(cmp::min(current_round_min_rtt, rtt)); |
| } else { |
| self.current_round_min_rtt = Some(rtt); |
| } |
| |
| self.rtt_sample_count += 1; |
| |
| if cwnd >= (LOW_CWND * max_datagram_size) && |
| self.rtt_sample_count >= N_RTT_SAMPLE && |
| self.current_round_min_rtt.is_some() && |
| self.last_round_min_rtt.is_some() |
| { |
| // clamp(min_rtt_thresh, last_round_min_rtt/8, |
| // max_rtt_thresh) |
| let rtt_thresh = cmp::max( |
| self.last_round_min_rtt.unwrap() / 8, |
| MIN_RTT_THRESH, |
| ); |
| let rtt_thresh = cmp::min(rtt_thresh, MAX_RTT_THRESH); |
| |
| // Check if we can exit to LSS. |
| if self.current_round_min_rtt.unwrap() >= |
| (self.last_round_min_rtt.unwrap() + rtt_thresh) |
| { |
| self.lss_start_time = Some(now); |
| } |
| } |
| |
| // Check if we reached the end of the round. |
| if let Some(end_pkt_num) = self.window_end { |
| if packet.pkt_num >= end_pkt_num { |
| // Start of a new round. |
| self.window_end = None; |
| } |
| } |
| } |
| |
| self.lss_start_time.is_some() |
| } |
| |
| // Return a cwnd increment during LSS (Limited Slow Start). |
| pub fn lss_cwnd_inc( |
| &self, pkt_size: usize, cwnd: usize, ssthresh: usize, |
| ) -> usize { |
| pkt_size / (cwnd as f64 / (LSS_DIVISOR * ssthresh as f64)) as usize |
| } |
| |
| // Exit HyStart++ when entering congestion avoidance. |
| pub fn congestion_event(&mut self) { |
| self.window_end = None; |
| self.lss_start_time = None; |
| } |
| } |
| |
| #[cfg(test)] |
| mod tests { |
| use super::*; |
| |
| #[test] |
| fn start_round() { |
| let mut hspp = Hystart::default(); |
| let pkt_num = 100; |
| |
| hspp.start_round(pkt_num); |
| |
| assert_eq!(hspp.window_end, Some(pkt_num)); |
| assert_eq!(hspp.current_round_min_rtt, None); |
| } |
| |
| #[test] |
| fn lss_cwnd_inc() { |
| let hspp = Hystart::default(); |
| |
| let datagram_size = 1200; |
| let cwnd = 24000; |
| let ssthresh = 24000; |
| |
| let lss_cwnd_inc = hspp.lss_cwnd_inc(datagram_size, cwnd, ssthresh); |
| |
| assert_eq!((datagram_size as f64 * LSS_DIVISOR) as usize, lss_cwnd_inc); |
| } |
| |
| #[test] |
| fn congestion_event() { |
| let mut hspp = Hystart::default(); |
| let pkt_num = 100; |
| |
| hspp.start_round(pkt_num); |
| |
| assert_eq!(hspp.window_end, Some(pkt_num)); |
| |
| // When moving into CA mode, window_end should be cleared. |
| hspp.congestion_event(); |
| |
| assert_eq!(hspp.window_end, None); |
| } |
| } |