cc: BBR congestion control
Adding a new congestion control module `bbr`, implementing
BBR Congestion Control algorithm as specified in
draft-cardwell-iccrg-bbr-congestion-control-00 (bbr version 1).
Added files:
- `bbr/mod.rs`: congestion control modules hooks.
- `bbr/init.rs`: initialization functions.
- `bbr/pacing.rs`: pacing functions.
- `bbr/per_ack.rs`: ACK processing functions.
- `bbr/per_transmit.rs`: per-transmit functions.
Notable changes:
- In `on_packets_acked()` hook, run `bbr_update_model_and_state()`
per ACK'ed packets for most of state changes and run
`bbr_update_control_parameters()` at the end for updating control
parameters (e.g. pacing rate, cwnd) for ACK received.
- `has_custom_pacing()` now returns true: pacing rate will be
updated during ACK processing.
- No Hystart/PRR will be used even enabled.
diff --git a/quiche/include/quiche.h b/quiche/include/quiche.h
index 25318f9..9dedd03 100644
--- a/quiche/include/quiche.h
+++ b/quiche/include/quiche.h
@@ -203,6 +203,7 @@
enum quiche_cc_algorithm {
QUICHE_CC_RENO = 0,
QUICHE_CC_CUBIC = 1,
+ QUICHE_CC_BBR = 2,
};
// Sets the congestion control algorithm used.
diff --git a/quiche/src/minmax.rs b/quiche/src/minmax.rs
index 8d81c28..274d138 100644
--- a/quiche/src/minmax.rs
+++ b/quiche/src/minmax.rs
@@ -108,7 +108,7 @@
}
/// Updates the max estimate based on the given measurement, and returns it.
- pub fn _running_max(&mut self, win: Duration, time: Instant, meas: T) -> T {
+ pub fn running_max(&mut self, win: Duration, time: Instant, meas: T) -> T {
let val = MinmaxSample { time, value: meas };
let delta_time = time.duration_since(self.estimate[2].time);
@@ -269,13 +269,13 @@
assert_eq!(rtt_max, rtt_24);
time += Duration::from_millis(250);
- rtt_max = f._running_max(win, time, rtt_25);
+ rtt_max = f.running_max(win, time, rtt_25);
assert_eq!(rtt_max, rtt_25);
assert_eq!(f.estimate[1].value, rtt_25);
assert_eq!(f.estimate[2].value, rtt_25);
time += Duration::from_millis(600);
- rtt_max = f._running_max(win, time, rtt_24);
+ rtt_max = f.running_max(win, time, rtt_24);
assert_eq!(rtt_max, rtt_24);
assert_eq!(f.estimate[1].value, rtt_24);
assert_eq!(f.estimate[2].value, rtt_24);
@@ -293,13 +293,13 @@
assert_eq!(bw_max, bw_200);
time += Duration::from_millis(5000);
- bw_max = f._running_max(win, time, bw_500);
+ bw_max = f.running_max(win, time, bw_500);
assert_eq!(bw_max, bw_500);
assert_eq!(f.estimate[1].value, bw_500);
assert_eq!(f.estimate[2].value, bw_500);
time += Duration::from_millis(600);
- bw_max = f._running_max(win, time, bw_200);
+ bw_max = f.running_max(win, time, bw_200);
assert_eq!(bw_max, bw_200);
assert_eq!(f.estimate[1].value, bw_200);
assert_eq!(f.estimate[2].value, bw_200);
@@ -383,19 +383,19 @@
assert_eq!(rtt_max, rtt_25);
time += Duration::from_millis(300);
- rtt_max = f._running_max(win, time, rtt_24);
+ rtt_max = f.running_max(win, time, rtt_24);
assert_eq!(rtt_max, rtt_25);
assert_eq!(f.estimate[1].value, rtt_24);
assert_eq!(f.estimate[2].value, rtt_24);
time += Duration::from_millis(300);
- rtt_max = f._running_max(win, time, rtt_23);
+ rtt_max = f.running_max(win, time, rtt_23);
assert_eq!(rtt_max, rtt_25);
assert_eq!(f.estimate[1].value, rtt_24);
assert_eq!(f.estimate[2].value, rtt_23);
time += Duration::from_millis(300);
- rtt_max = f._running_max(win, time, rtt_26);
+ rtt_max = f.running_max(win, time, rtt_26);
assert_eq!(rtt_max, rtt_26);
assert_eq!(f.estimate[1].value, rtt_26);
assert_eq!(f.estimate[2].value, rtt_26);
@@ -415,19 +415,19 @@
assert_eq!(bw_max, bw_500);
time += Duration::from_millis(300);
- bw_max = f._running_max(win, time, bw_400);
+ bw_max = f.running_max(win, time, bw_400);
assert_eq!(bw_max, bw_500);
assert_eq!(f.estimate[1].value, bw_400);
assert_eq!(f.estimate[2].value, bw_400);
time += Duration::from_millis(300);
- bw_max = f._running_max(win, time, bw_300);
+ bw_max = f.running_max(win, time, bw_300);
assert_eq!(bw_max, bw_500);
assert_eq!(f.estimate[1].value, bw_400);
assert_eq!(f.estimate[2].value, bw_300);
time += Duration::from_millis(300);
- bw_max = f._running_max(win, time, bw_600);
+ bw_max = f.running_max(win, time, bw_600);
assert_eq!(bw_max, bw_600);
assert_eq!(f.estimate[1].value, bw_600);
assert_eq!(f.estimate[2].value, bw_600);
diff --git a/quiche/src/recovery/bbr/init.rs b/quiche/src/recovery/bbr/init.rs
new file mode 100644
index 0000000..6a3f7ba
--- /dev/null
+++ b/quiche/src/recovery/bbr/init.rs
@@ -0,0 +1,93 @@
+// Copyright (C) 2022, 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.
+
+use super::*;
+use crate::recovery::Recovery;
+
+use std::time::Duration;
+use std::time::Instant;
+
+// BBR Functions at Initialization.
+//
+
+// 4.3.1. Initialization Steps
+pub fn bbr_init(r: &mut Recovery) {
+ let rtt = r.rtt();
+ let bbr = &mut r.bbr_state;
+
+ bbr.rtprop = rtt;
+ bbr.rtprop_stamp = Instant::now();
+ bbr.next_round_delivered = r.delivery_rate.delivered();
+
+ r.send_quantum = r.max_datagram_size;
+
+ bbr_init_round_counting(r);
+ bbr_init_full_pipe(r);
+ bbr_init_pacing_rate(r);
+ bbr_enter_startup(r);
+}
+
+// 4.1.1.3. Tracking Time for the BBR.BtlBw Max Filter
+fn bbr_init_round_counting(r: &mut Recovery) {
+ let bbr = &mut r.bbr_state;
+
+ bbr.next_round_delivered = 0;
+ bbr.round_start = false;
+ bbr.round_count = 0;
+}
+
+// 4.2.1. Pacing Rate
+fn bbr_init_pacing_rate(r: &mut Recovery) {
+ let bbr = &mut r.bbr_state;
+
+ let srtt = r
+ .smoothed_rtt
+ .unwrap_or_else(|| Duration::from_millis(1))
+ .as_secs_f64();
+
+ // At init, cwnd is initcwnd.
+ let nominal_bandwidth = r.congestion_window as f64 / srtt;
+
+ bbr.pacing_rate = (bbr.pacing_gain * nominal_bandwidth) as u64;
+}
+
+// 4.3.2.1. Startup Dynamics
+pub fn bbr_enter_startup(r: &mut Recovery) {
+ let bbr = &mut r.bbr_state;
+
+ bbr.state = BBRStateMachine::Startup;
+ bbr.pacing_gain = BBR_HIGH_GAIN;
+ bbr.cwnd_gain = BBR_HIGH_GAIN;
+}
+
+// 4.3.2.2. Estimating When Startup has Filled the Pipe
+fn bbr_init_full_pipe(r: &mut Recovery) {
+ let bbr = &mut r.bbr_state;
+
+ bbr.filled_pipe = false;
+ bbr.full_bw = 0;
+ bbr.full_bw_count = 0;
+}
diff --git a/quiche/src/recovery/bbr/mod.rs b/quiche/src/recovery/bbr/mod.rs
new file mode 100644
index 0000000..2168086
--- /dev/null
+++ b/quiche/src/recovery/bbr/mod.rs
@@ -0,0 +1,830 @@
+// Copyright (C) 2022, 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.
+
+//! BBR Congestion Control
+//!
+//! This implementation is based on the following draft:
+//! <https://tools.ietf.org/html/draft-cardwell-iccrg-bbr-congestion-control-00>
+
+use crate::minmax::Minmax;
+use crate::packet;
+use crate::recovery::*;
+
+use std::time::Duration;
+use std::time::Instant;
+
+pub static BBR: CongestionControlOps = CongestionControlOps {
+ on_init,
+ on_packet_sent,
+ on_packets_acked,
+ congestion_event,
+ collapse_cwnd,
+ checkpoint,
+ rollback,
+ has_custom_pacing,
+ debug_fmt,
+};
+
+/// A constant specifying the length of the BBR.BtlBw max filter window for
+/// BBR.BtlBwFilter, BtlBwFilterLen is 10 packet-timed round trips.
+const BTLBW_FILTER_LEN: Duration = Duration::from_secs(10);
+
+/// A constant specifying the minimum time interval between ProbeRTT states: 10
+/// secs.
+const PROBE_RTT_INTERVAL: Duration = Duration::from_secs(10);
+
+/// A constant specifying the length of the RTProp min filter window.
+const RTPROP_FILTER_LEN: Duration = PROBE_RTT_INTERVAL;
+
+/// A constant specifying the minimum gain value that will allow the sending
+/// rate to double each round (2/ln(2) ~= 2.89), used in Startup mode for both
+/// BBR.pacing_gain and BBR.cwnd_gain.
+const BBR_HIGH_GAIN: f64 = 2.89;
+
+/// The minimal cwnd value BBR tries to target using: 4 packets, or 4 * SMSS
+const BBR_MIN_PIPE_CWND_PKTS: usize = 4;
+
+/// The number of phases in the BBR ProbeBW gain cycle: 8.
+const BBR_GAIN_CYCLE_LEN: usize = 8;
+
+/// A constant specifying the minimum duration for which ProbeRTT state holds
+/// inflight to BBRMinPipeCwnd or fewer packets: 200 ms.
+const PROBE_RTT_DURATION: Duration = Duration::from_millis(200);
+
+/// Pacing Gain Cycle.
+const PACING_GAIN_CYCLE: [f64; BBR_GAIN_CYCLE_LEN] =
+ [5.0 / 4.0, 3.0 / 4.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0];
+
+/// A constant to check BBR.BtlBW is still growing.
+const BTLBW_GROWTH_TARGET: f64 = 1.25;
+
+/// BBR Internal State Machine.
+#[derive(Debug, PartialEq, Eq)]
+enum BBRStateMachine {
+ Startup,
+ Drain,
+ ProbeBW,
+ ProbeRTT,
+}
+
+/// BBR Specific State Variables.
+pub struct State {
+ // The current state of a BBR flow in the BBR state machine.
+ state: BBRStateMachine,
+
+ // The current pacing rate for a BBR flow, which controls inter-packet
+ // spacing.
+ pacing_rate: u64,
+
+ // BBR's estimated bottleneck bandwidth available to the transport flow,
+ // estimated from the maximum delivery rate sample in a sliding window.
+ btlbw: u64,
+
+ // The max filter used to estimate BBR.BtlBw.
+ btlbwfilter: Minmax<u64>,
+
+ // BBR's estimated two-way round-trip propagation delay of the path,
+ // estimated from the windowed minimum recent round-trip delay sample.
+ rtprop: Duration,
+
+ // The wall clock time at which the current BBR.RTProp sample was obtained.
+ rtprop_stamp: Instant,
+
+ // A boolean recording whether the BBR.RTprop has expired and is due for a
+ // refresh with an application idle period or a transition into ProbeRTT
+ // state.
+ rtprop_expired: bool,
+
+ // The dynamic gain factor used to scale BBR.BtlBw to produce
+ // BBR.pacing_rate.
+ pacing_gain: f64,
+
+ // The dynamic gain factor used to scale the estimated BDP to produce a
+ // congestion window (cwnd).
+ cwnd_gain: f64,
+
+ // A boolean that records whether BBR estimates that it has ever fully
+ // utilized its available bandwidth ("filled the pipe").
+ filled_pipe: bool,
+
+ // Count of packet-timed round trips elapsed so far.
+ round_count: u64,
+
+ // A boolean that BBR sets to true once per packet-timed round trip,
+ // on ACKs that advance BBR.round_count.
+ round_start: bool,
+
+ // packet.delivered value denoting the end of a packet-timed round trip.
+ next_round_delivered: usize,
+
+ // Timestamp when ProbeRTT state ends.
+ probe_rtt_done_stamp: Option<Instant>,
+
+ // Checking if a roundtrip in ProbeRTT state ends.
+ probe_rtt_round_done: bool,
+
+ // Checking if in the packet conservation mode during recovery.
+ packet_conservation: bool,
+
+ // Saved cwnd before loss recovery.
+ prior_cwnd: usize,
+
+ // Checking if restarting from idle.
+ idle_restart: bool,
+
+ // Baseline level delivery rate for full pipe estimator.
+ full_bw: u64,
+
+ // The number of round for full pipe estimator without much growth.
+ full_bw_count: usize,
+
+ // Last time cycle_index is updated.
+ cycle_stamp: Instant,
+
+ // Current index of pacing_gain_cycle[].
+ cycle_index: usize,
+
+ // The upper bound on the volume of data BBR allows in flight.
+ target_cwnd: usize,
+
+ // Whether in the recovery episode.
+ in_recovery: bool,
+
+ // Start time of the connection.
+ start_time: Instant,
+
+ // Newly marked lost data size in bytes.
+ newly_lost_bytes: usize,
+
+ // Newly acked data size in bytes.
+ newly_acked_bytes: usize,
+
+ // bytes_in_flight before processing this ACK.
+ prior_bytes_in_flight: usize,
+}
+
+impl State {
+ pub fn new() -> Self {
+ let now = Instant::now();
+
+ State {
+ state: BBRStateMachine::Startup,
+
+ pacing_rate: 0,
+
+ btlbw: 0,
+
+ btlbwfilter: Minmax::new(0),
+
+ rtprop: Duration::ZERO,
+
+ rtprop_stamp: now,
+
+ rtprop_expired: false,
+
+ pacing_gain: 0.0,
+
+ cwnd_gain: 0.0,
+
+ filled_pipe: false,
+
+ round_count: 0,
+
+ round_start: false,
+
+ next_round_delivered: 0,
+
+ probe_rtt_done_stamp: None,
+
+ probe_rtt_round_done: false,
+
+ packet_conservation: false,
+
+ prior_cwnd: 0,
+
+ idle_restart: false,
+
+ full_bw: 0,
+
+ full_bw_count: 0,
+
+ cycle_stamp: now,
+
+ cycle_index: 0,
+
+ target_cwnd: 0,
+
+ in_recovery: false,
+
+ start_time: now,
+
+ newly_lost_bytes: 0,
+
+ newly_acked_bytes: 0,
+
+ prior_bytes_in_flight: 0,
+ }
+ }
+}
+
+// When entering the recovery episode.
+fn bbr_enter_recovery(r: &mut Recovery, now: Instant) {
+ r.bbr_state.prior_cwnd = per_ack::bbr_save_cwnd(r);
+
+ r.congestion_window = r.bytes_in_flight +
+ r.bbr_state.newly_acked_bytes.max(r.max_datagram_size);
+ r.congestion_recovery_start_time = Some(now);
+
+ r.bbr_state.packet_conservation = true;
+ r.bbr_state.in_recovery = true;
+
+ // Start round now.
+ r.bbr_state.next_round_delivered = r.delivery_rate.delivered();
+}
+
+// When exiting the recovery episode.
+fn bbr_exit_recovery(r: &mut Recovery) {
+ r.congestion_recovery_start_time = None;
+
+ r.bbr_state.packet_conservation = false;
+ r.bbr_state.in_recovery = false;
+
+ per_ack::bbr_restore_cwnd(r);
+}
+
+// Congestion Control Hooks.
+//
+fn on_init(r: &mut Recovery) {
+ init::bbr_init(r);
+}
+
+fn on_packet_sent(r: &mut Recovery, sent_bytes: usize, _now: Instant) {
+ r.bytes_in_flight += sent_bytes;
+
+ per_transmit::bbr_on_transmit(r);
+}
+
+fn on_packets_acked(
+ r: &mut Recovery, packets: &[Acked], _epoch: packet::Epoch, now: Instant,
+) {
+ r.bbr_state.newly_acked_bytes = packets.iter().fold(0, |acked_bytes, p| {
+ r.bbr_state.prior_bytes_in_flight = r.bytes_in_flight;
+
+ per_ack::bbr_update_model_and_state(r, p, now);
+
+ r.bytes_in_flight = r.bytes_in_flight.saturating_sub(p.size);
+
+ acked_bytes + p.size
+ });
+
+ if let Some(pkt) = packets.last() {
+ if !r.in_congestion_recovery(pkt.time_sent) {
+ // Upon exiting loss recovery.
+ bbr_exit_recovery(r);
+ }
+ }
+
+ per_ack::bbr_update_control_parameters(r, now);
+
+ r.bbr_state.newly_lost_bytes = 0;
+}
+
+fn congestion_event(
+ r: &mut Recovery, lost_bytes: usize, time_sent: Instant,
+ _epoch: packet::Epoch, now: Instant,
+) {
+ r.bbr_state.newly_lost_bytes = lost_bytes;
+
+ // Upon entering Fast Recovery.
+ if !r.in_congestion_recovery(time_sent) {
+ // Upon entering Fast Recovery.
+ bbr_enter_recovery(r, now);
+ }
+}
+
+fn collapse_cwnd(r: &mut Recovery) {
+ r.bbr_state.prior_cwnd = per_ack::bbr_save_cwnd(r);
+
+ reno::collapse_cwnd(r);
+}
+
+fn checkpoint(_r: &mut Recovery) {}
+
+fn rollback(_r: &mut Recovery) -> bool {
+ false
+}
+
+fn has_custom_pacing() -> bool {
+ true
+}
+
+fn debug_fmt(r: &Recovery, f: &mut std::fmt::Formatter) -> std::fmt::Result {
+ let bbr = &r.bbr_state;
+
+ write!(
+ f,
+ "bbr={{ state={:?} btlbw={} rtprop={:?} pacing_rate={} pacing_gain={} cwnd_gain={} target_cwnd={} send_quantum={} filled_pipe={} round_count={} }}",
+ bbr.state, bbr.btlbw, bbr.rtprop, bbr.pacing_rate, bbr.pacing_gain, bbr.cwnd_gain, bbr.target_cwnd, r.send_quantum(), bbr.filled_pipe, bbr.round_count
+ )
+}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+
+ use crate::recovery;
+
+ #[test]
+ fn bbr_init() {
+ let mut cfg = crate::Config::new(crate::PROTOCOL_VERSION).unwrap();
+ cfg.set_cc_algorithm(recovery::CongestionControlAlgorithm::BBR);
+
+ let mut r = Recovery::new(&cfg);
+
+ // on_init() is called in Connection::new(), so it need to be
+ // called manually here.
+ r.on_init();
+
+ assert_eq!(r.cwnd(), r.max_datagram_size * INITIAL_WINDOW_PACKETS);
+ assert_eq!(r.bytes_in_flight, 0);
+
+ assert_eq!(r.bbr_state.state, BBRStateMachine::Startup);
+ }
+
+ #[test]
+ fn bbr_send() {
+ let mut cfg = crate::Config::new(crate::PROTOCOL_VERSION).unwrap();
+ cfg.set_cc_algorithm(recovery::CongestionControlAlgorithm::BBR);
+
+ let mut r = Recovery::new(&cfg);
+ let now = Instant::now();
+
+ r.on_init();
+ r.on_packet_sent_cc(1000, now);
+
+ assert_eq!(r.bytes_in_flight, 1000);
+ }
+
+ #[test]
+ fn bbr_startup() {
+ let mut cfg = crate::Config::new(crate::PROTOCOL_VERSION).unwrap();
+ cfg.set_cc_algorithm(recovery::CongestionControlAlgorithm::BBR);
+
+ let mut r = Recovery::new(&cfg);
+ let now = Instant::now();
+ let mss = r.max_datagram_size;
+
+ r.on_init();
+
+ // Send 5 packets.
+ for pn in 0..5 {
+ let pkt = Sent {
+ pkt_num: pn,
+ frames: vec![],
+ time_sent: now,
+ time_acked: None,
+ time_lost: None,
+ size: mss,
+ ack_eliciting: true,
+ in_flight: true,
+ delivered: 0,
+ delivered_time: now,
+ first_sent_time: now,
+ is_app_limited: false,
+ has_data: false,
+ };
+
+ r.on_packet_sent(
+ pkt,
+ packet::EPOCH_APPLICATION,
+ HandshakeStatus::default(),
+ now,
+ "",
+ );
+ }
+
+ let rtt = Duration::from_millis(50);
+ let now = now + rtt;
+ let cwnd_prev = r.cwnd();
+
+ let mut acked = ranges::RangeSet::default();
+ acked.insert(0..5);
+
+ assert_eq!(
+ r.on_ack_received(
+ &acked,
+ 25,
+ packet::EPOCH_APPLICATION,
+ HandshakeStatus::default(),
+ now,
+ "",
+ ),
+ Ok(()),
+ );
+
+ assert_eq!(r.bbr_state.state, BBRStateMachine::Startup);
+ assert_eq!(r.cwnd(), cwnd_prev + mss * 5);
+ assert_eq!(r.bytes_in_flight, 0);
+ assert_eq!(
+ r.delivery_rate(),
+ ((mss * 5) as f64 / rtt.as_secs_f64()) as u64
+ );
+ assert_eq!(r.bbr_state.btlbw, r.delivery_rate());
+ }
+
+ #[test]
+ fn bbr_congestion_event() {
+ let mut cfg = crate::Config::new(crate::PROTOCOL_VERSION).unwrap();
+ cfg.set_cc_algorithm(recovery::CongestionControlAlgorithm::BBR);
+
+ let mut r = Recovery::new(&cfg);
+ let now = Instant::now();
+ let mss = r.max_datagram_size;
+
+ r.on_init();
+
+ // Send 5 packets.
+ for pn in 0..5 {
+ let pkt = Sent {
+ pkt_num: pn,
+ frames: vec![],
+ time_sent: now,
+ time_acked: None,
+ time_lost: None,
+ size: mss,
+ ack_eliciting: true,
+ in_flight: true,
+ delivered: 0,
+ delivered_time: now,
+ first_sent_time: now,
+ is_app_limited: false,
+ has_data: false,
+ };
+
+ r.on_packet_sent(
+ pkt,
+ packet::EPOCH_APPLICATION,
+ HandshakeStatus::default(),
+ now,
+ "",
+ );
+ }
+
+ let rtt = Duration::from_millis(50);
+ let now = now + rtt;
+
+ // Make a packet loss to trigger a congestion event.
+ let mut acked = ranges::RangeSet::default();
+ acked.insert(4..5);
+
+ assert_eq!(
+ r.on_ack_received(
+ &acked,
+ 25,
+ packet::EPOCH_APPLICATION,
+ HandshakeStatus::default(),
+ now,
+ "",
+ ),
+ Ok(()),
+ );
+
+ // Sent: 0, 1, 2, 3, 4, Acked 4
+ assert_eq!(r.cwnd(), mss * 4);
+ // Lost: 0, 1, Stil in flight: 2, 3
+ assert_eq!(r.bytes_in_flight, mss * 2);
+ }
+
+ #[test]
+ fn bbr_drain() {
+ let mut cfg = crate::Config::new(crate::PROTOCOL_VERSION).unwrap();
+ cfg.set_cc_algorithm(recovery::CongestionControlAlgorithm::BBR);
+
+ let mut r = Recovery::new(&cfg);
+ let now = Instant::now();
+ let mss = r.max_datagram_size;
+
+ r.on_init();
+
+ let mut pn = 0;
+
+ // Stop right before filled_pipe=true.
+ for _ in 0..3 {
+ let pkt = Sent {
+ pkt_num: pn,
+ frames: vec![],
+ time_sent: now,
+ time_acked: None,
+ time_lost: None,
+ size: mss,
+ ack_eliciting: true,
+ in_flight: true,
+ delivered: r.delivery_rate.delivered(),
+ delivered_time: now,
+ first_sent_time: now,
+ is_app_limited: false,
+ has_data: false,
+ };
+
+ r.on_packet_sent(
+ pkt,
+ packet::EPOCH_APPLICATION,
+ HandshakeStatus::default(),
+ now,
+ "",
+ );
+
+ pn += 1;
+
+ let rtt = Duration::from_millis(50);
+
+ let now = now + rtt;
+
+ let mut acked = ranges::RangeSet::default();
+ acked.insert(0..pn);
+
+ assert_eq!(
+ r.on_ack_received(
+ &acked,
+ 25,
+ packet::EPOCH_APPLICATION,
+ HandshakeStatus::default(),
+ now,
+ "",
+ ),
+ Ok(()),
+ );
+ }
+
+ // Stop at right before filled_pipe=true.
+ for _ in 0..5 {
+ let pkt = Sent {
+ pkt_num: pn,
+ frames: vec![],
+ time_sent: now,
+ time_acked: None,
+ time_lost: None,
+ size: mss,
+ ack_eliciting: true,
+ in_flight: true,
+ delivered: r.delivery_rate.delivered(),
+ delivered_time: now,
+ first_sent_time: now,
+ is_app_limited: false,
+ has_data: false,
+ };
+
+ r.on_packet_sent(
+ pkt,
+ packet::EPOCH_APPLICATION,
+ HandshakeStatus::default(),
+ now,
+ "",
+ );
+
+ pn += 1;
+ }
+
+ let rtt = Duration::from_millis(50);
+ let now = now + rtt;
+
+ let mut acked = ranges::RangeSet::default();
+
+ // We sent 5 packets, but ack only one, to stay
+ // in Drain state.
+ acked.insert(0..pn - 4);
+
+ assert_eq!(
+ r.on_ack_received(
+ &acked,
+ 25,
+ packet::EPOCH_APPLICATION,
+ HandshakeStatus::default(),
+ now,
+ "",
+ ),
+ Ok(()),
+ );
+
+ // Now we are in Drain state.
+ assert_eq!(r.bbr_state.filled_pipe, true);
+ assert_eq!(r.bbr_state.state, BBRStateMachine::Drain);
+ assert!(r.bbr_state.pacing_gain < 1.0);
+ }
+
+ #[test]
+ fn bbr_probe_bw() {
+ let mut cfg = crate::Config::new(crate::PROTOCOL_VERSION).unwrap();
+ cfg.set_cc_algorithm(recovery::CongestionControlAlgorithm::BBR);
+
+ let mut r = Recovery::new(&cfg);
+ let now = Instant::now();
+ let mss = r.max_datagram_size;
+
+ r.on_init();
+
+ let mut pn = 0;
+
+ // At 4th roundtrip, filled_pipe=true and switch to Drain,
+ // but move to ProbeBW immediately because bytes_in_flight is
+ // smaller than BBRInFlight(1).
+ for _ in 0..4 {
+ let pkt = Sent {
+ pkt_num: pn,
+ frames: vec![],
+ time_sent: now,
+ time_acked: None,
+ time_lost: None,
+ size: mss,
+ ack_eliciting: true,
+ in_flight: true,
+ delivered: r.delivery_rate.delivered(),
+ delivered_time: now,
+ first_sent_time: now,
+ is_app_limited: false,
+ has_data: false,
+ };
+
+ r.on_packet_sent(
+ pkt,
+ packet::EPOCH_APPLICATION,
+ HandshakeStatus::default(),
+ now,
+ "",
+ );
+
+ pn += 1;
+
+ let rtt = Duration::from_millis(50);
+ let now = now + rtt;
+
+ let mut acked = ranges::RangeSet::default();
+ acked.insert(0..pn);
+
+ assert_eq!(
+ r.on_ack_received(
+ &acked,
+ 25,
+ packet::EPOCH_APPLICATION,
+ HandshakeStatus::default(),
+ now,
+ "",
+ ),
+ Ok(()),
+ );
+ }
+
+ // Now we are in ProbeBW state.
+ assert_eq!(r.bbr_state.filled_pipe, true);
+ assert_eq!(r.bbr_state.state, BBRStateMachine::ProbeBW);
+
+ // In the first ProbeBW cycle, pacing_gain should be >= 1.0.
+ assert!(r.bbr_state.pacing_gain >= 1.0);
+ }
+
+ #[test]
+ fn bbr_probe_rtt() {
+ let mut cfg = crate::Config::new(crate::PROTOCOL_VERSION).unwrap();
+ cfg.set_cc_algorithm(recovery::CongestionControlAlgorithm::BBR);
+
+ let mut r = Recovery::new(&cfg);
+ let now = Instant::now();
+ let mss = r.max_datagram_size;
+
+ r.on_init();
+
+ let mut pn = 0;
+
+ // At 4th roundtrip, filled_pipe=true and switch to Drain,
+ // but move to ProbeBW immediately because bytes_in_flight is
+ // smaller than BBRInFlight(1).
+ for _ in 0..4 {
+ let pkt = Sent {
+ pkt_num: pn,
+ frames: vec![],
+ time_sent: now,
+ time_acked: None,
+ time_lost: None,
+ size: mss,
+ ack_eliciting: true,
+ in_flight: true,
+ delivered: r.delivery_rate.delivered(),
+ delivered_time: now,
+ first_sent_time: now,
+ is_app_limited: false,
+ has_data: false,
+ };
+
+ r.on_packet_sent(
+ pkt,
+ packet::EPOCH_APPLICATION,
+ HandshakeStatus::default(),
+ now,
+ "",
+ );
+
+ pn += 1;
+
+ let rtt = Duration::from_millis(50);
+ let now = now + rtt;
+
+ let mut acked = ranges::RangeSet::default();
+ acked.insert(0..pn);
+
+ assert_eq!(
+ r.on_ack_received(
+ &acked,
+ 25,
+ packet::EPOCH_APPLICATION,
+ HandshakeStatus::default(),
+ now,
+ "",
+ ),
+ Ok(()),
+ );
+ }
+
+ // Now we are in ProbeBW state.
+ assert_eq!(r.bbr_state.state, BBRStateMachine::ProbeBW);
+
+ // After RTPROP_FILTER_LEN (10s), switch to ProbeRTT.
+ let now = now + RTPROP_FILTER_LEN;
+
+ let pkt = Sent {
+ pkt_num: pn,
+ frames: vec![],
+ time_sent: now,
+ time_acked: None,
+ time_lost: None,
+ size: mss,
+ ack_eliciting: true,
+ in_flight: true,
+ delivered: r.delivery_rate.delivered(),
+ delivered_time: now,
+ first_sent_time: now,
+ is_app_limited: false,
+ has_data: false,
+ };
+
+ r.on_packet_sent(
+ pkt,
+ packet::EPOCH_APPLICATION,
+ HandshakeStatus::default(),
+ now,
+ "",
+ );
+
+ pn += 1;
+
+ // Don't update rtprop by giving larger rtt than before.
+ // If rtprop is updated, rtprop expiry check is reset.
+ let rtt = Duration::from_millis(100);
+ let now = now + rtt;
+
+ let mut acked = ranges::RangeSet::default();
+ acked.insert(0..pn);
+
+ assert_eq!(
+ r.on_ack_received(
+ &acked,
+ 25,
+ packet::EPOCH_APPLICATION,
+ HandshakeStatus::default(),
+ now,
+ "",
+ ),
+ Ok(()),
+ );
+
+ assert_eq!(r.bbr_state.state, BBRStateMachine::ProbeRTT);
+ assert_eq!(r.bbr_state.pacing_gain, 1.0);
+ }
+}
+
+mod init;
+mod pacing;
+mod per_ack;
+mod per_transmit;
diff --git a/quiche/src/recovery/bbr/pacing.rs b/quiche/src/recovery/bbr/pacing.rs
new file mode 100644
index 0000000..e5e21dd
--- /dev/null
+++ b/quiche/src/recovery/bbr/pacing.rs
@@ -0,0 +1,43 @@
+// Copyright (C) 2022, 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.
+
+use crate::recovery::Recovery;
+
+// BBR Transmit Packet Pacing Functions
+//
+
+// 4.2.1. Pacing Rate
+pub fn bbr_set_pacing_rate_with_gain(r: &mut Recovery, pacing_gain: f64) {
+ let rate = (pacing_gain * r.bbr_state.btlbw as f64) as u64;
+
+ if r.bbr_state.filled_pipe || rate > r.bbr_state.pacing_rate {
+ r.bbr_state.pacing_rate = rate;
+ }
+}
+
+pub fn bbr_set_pacing_rate(r: &mut Recovery) {
+ bbr_set_pacing_rate_with_gain(r, r.bbr_state.pacing_gain);
+}
diff --git a/quiche/src/recovery/bbr/per_ack.rs b/quiche/src/recovery/bbr/per_ack.rs
new file mode 100644
index 0000000..6fe5651
--- /dev/null
+++ b/quiche/src/recovery/bbr/per_ack.rs
@@ -0,0 +1,380 @@
+// Copyright (C) 2022, 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.
+
+use super::*;
+use crate::rand;
+use crate::recovery;
+
+use std::cmp;
+use std::time::Instant;
+
+/// 1.2Mbps in bytes/sec
+const PACING_RATE_1_2MBPS: u64 = 1200 * 1000 / 8;
+
+/// 24Mbps in bytes/sec
+const PACING_RATE_24MBPS: u64 = 24 * 1000 * 1000 / 8;
+
+/// The minimal cwnd value BBR tries to target, in bytes
+#[inline]
+fn bbr_min_pipe_cwnd(r: &mut Recovery) -> usize {
+ BBR_MIN_PIPE_CWND_PKTS * r.max_datagram_size
+}
+
+// BBR Functions when ACK is received.
+//
+pub fn bbr_update_model_and_state(
+ r: &mut Recovery, packet: &Acked, now: Instant,
+) {
+ bbr_update_btlbw(r, packet);
+ bbr_check_cycle_phase(r, now);
+ bbr_check_full_pipe(r);
+ bbr_check_drain(r, now);
+ bbr_update_rtprop(r, now);
+ bbr_check_probe_rtt(r, now);
+}
+
+pub fn bbr_update_control_parameters(r: &mut Recovery, now: Instant) {
+ pacing::bbr_set_pacing_rate(r);
+ bbr_set_send_quantum(r);
+
+ // Set outgoing packet pacing rate
+ // It is called here because send_quantum may be updated too.
+ r.set_pacing_rate(r.bbr_state.pacing_rate, now);
+
+ bbr_set_cwnd(r);
+}
+
+// BBR Functions while processing ACKs.
+//
+
+// 4.1.1.5. Updating the BBR.BtlBw Max Filter
+fn bbr_update_btlbw(r: &mut Recovery, packet: &Acked) {
+ bbr_update_round(r, packet);
+
+ if r.delivery_rate() >= r.bbr_state.btlbw ||
+ !r.delivery_rate.sample_is_app_limited()
+ {
+ // Since minmax filter is based on time,
+ // start_time + (round_count as seconds) is used instead.
+ r.bbr_state.btlbw = r.bbr_state.btlbwfilter.running_max(
+ BTLBW_FILTER_LEN,
+ r.bbr_state.start_time + Duration::from_secs(r.bbr_state.round_count),
+ r.delivery_rate(),
+ );
+ }
+}
+
+// 4.1.1.3 Tracking Time for the BBR.BtlBw Max Filter
+fn bbr_update_round(r: &mut Recovery, packet: &Acked) {
+ let bbr = &mut r.bbr_state;
+
+ if packet.delivered >= bbr.next_round_delivered {
+ bbr.next_round_delivered = r.delivery_rate.delivered();
+ bbr.round_count += 1;
+ bbr.round_start = true;
+ bbr.packet_conservation = false;
+ } else {
+ bbr.round_start = false;
+ }
+}
+
+// 4.1.2.3. Updating the BBR.RTprop Min Filter
+fn bbr_update_rtprop(r: &mut Recovery, now: Instant) {
+ let bbr = &mut r.bbr_state;
+ let rs_rtt = r.delivery_rate.sample_rtt();
+
+ bbr.rtprop_expired = now > bbr.rtprop_stamp + RTPROP_FILTER_LEN;
+
+ if !rs_rtt.is_zero() && (rs_rtt <= bbr.rtprop || bbr.rtprop_expired) {
+ bbr.rtprop = rs_rtt;
+ bbr.rtprop_stamp = now;
+ }
+}
+
+// 4.2.2 Send Quantum
+fn bbr_set_send_quantum(r: &mut Recovery) {
+ let rate = r.bbr_state.pacing_rate;
+
+ r.send_quantum = match rate {
+ rate if rate < PACING_RATE_1_2MBPS => r.max_datagram_size,
+
+ rate if rate < PACING_RATE_24MBPS => 2 * r.max_datagram_size,
+
+ _ => cmp::min((rate / 1000_u64) as usize, 64 * 1024),
+ }
+}
+
+// 4.2.3.2 Target cwnd
+fn bbr_inflight(r: &mut Recovery, gain: f64) -> usize {
+ let bbr = &mut r.bbr_state;
+
+ if bbr.rtprop == Duration::MAX {
+ return r.max_datagram_size * INITIAL_WINDOW_PACKETS;
+ }
+
+ let quanta = 3 * r.send_quantum;
+ let estimated_bdp = bbr.btlbw as f64 * bbr.rtprop.as_secs_f64();
+
+ (gain * estimated_bdp) as usize + quanta
+}
+
+fn bbr_update_target_cwnd(r: &mut Recovery) {
+ r.bbr_state.target_cwnd = bbr_inflight(r, r.bbr_state.cwnd_gain);
+}
+
+// 4.2.3.4 Modulating cwnd in Loss Recovery
+pub fn bbr_save_cwnd(r: &mut Recovery) -> usize {
+ if !r.bbr_state.in_recovery && r.bbr_state.state != BBRStateMachine::ProbeRTT
+ {
+ r.congestion_window
+ } else {
+ r.congestion_window.max(r.bbr_state.prior_cwnd)
+ }
+}
+
+pub fn bbr_restore_cwnd(r: &mut Recovery) {
+ r.congestion_window = r.congestion_window.max(r.bbr_state.prior_cwnd);
+}
+
+fn bbr_modulate_cwnd_for_recovery(r: &mut Recovery) {
+ let acked_bytes = r.bbr_state.newly_acked_bytes;
+ let lost_bytes = r.bbr_state.newly_lost_bytes;
+
+ if lost_bytes > 0 {
+ // QUIC mininum cwnd is 2 x MSS.
+ r.congestion_window = r
+ .congestion_window
+ .saturating_sub(lost_bytes)
+ .max(r.max_datagram_size * recovery::MINIMUM_WINDOW_PACKETS);
+ }
+
+ if r.bbr_state.packet_conservation {
+ r.congestion_window =
+ r.congestion_window.max(r.bytes_in_flight + acked_bytes);
+ }
+}
+
+// 4.2.3.5 Modulating cwnd in ProbeRTT
+fn bbr_modulate_cwnd_for_probe_rtt(r: &mut Recovery) {
+ if r.bbr_state.state == BBRStateMachine::ProbeRTT {
+ r.congestion_window = r.congestion_window.min(bbr_min_pipe_cwnd(r))
+ }
+}
+
+// 4.2.3.6 Core cwnd Adjustment Mechanism
+fn bbr_set_cwnd(r: &mut Recovery) {
+ let acked_bytes = r.bbr_state.newly_acked_bytes;
+
+ bbr_update_target_cwnd(r);
+ bbr_modulate_cwnd_for_recovery(r);
+
+ if !r.bbr_state.packet_conservation {
+ if r.bbr_state.filled_pipe {
+ r.congestion_window = cmp::min(
+ r.congestion_window + acked_bytes,
+ r.bbr_state.target_cwnd,
+ )
+ } else if r.congestion_window < r.bbr_state.target_cwnd ||
+ r.delivery_rate.delivered() <
+ r.max_datagram_size * INITIAL_WINDOW_PACKETS
+ {
+ r.congestion_window += acked_bytes;
+ }
+
+ r.congestion_window = r.congestion_window.max(bbr_min_pipe_cwnd(r))
+ }
+
+ bbr_modulate_cwnd_for_probe_rtt(r);
+}
+
+// 4.3.2.2. Estimating When Startup has Filled the Pipe
+fn bbr_check_full_pipe(r: &mut Recovery) {
+ // No need to check for a full pipe now.
+ if r.bbr_state.filled_pipe ||
+ !r.bbr_state.round_start ||
+ r.delivery_rate.sample_is_app_limited()
+ {
+ return;
+ }
+
+ // BBR.BtlBw still growing?
+ if r.bbr_state.btlbw >=
+ (r.bbr_state.full_bw as f64 * BTLBW_GROWTH_TARGET) as u64
+ {
+ // record new baseline level
+ r.bbr_state.full_bw = r.bbr_state.btlbw;
+ r.bbr_state.full_bw_count = 0;
+ return;
+ }
+
+ // another round w/o much growth
+ r.bbr_state.full_bw_count += 1;
+
+ if r.bbr_state.full_bw_count >= 3 {
+ r.bbr_state.filled_pipe = true;
+ }
+}
+
+// 4.3.3. Drain
+fn bbr_enter_drain(r: &mut Recovery) {
+ let bbr = &mut r.bbr_state;
+
+ bbr.state = BBRStateMachine::Drain;
+
+ // pace slowly
+ bbr.pacing_gain = 1.0 / BBR_HIGH_GAIN;
+
+ // maintain cwnd
+ bbr.cwnd_gain = BBR_HIGH_GAIN;
+}
+
+fn bbr_check_drain(r: &mut Recovery, now: Instant) {
+ if r.bbr_state.state == BBRStateMachine::Startup && r.bbr_state.filled_pipe {
+ bbr_enter_drain(r);
+ }
+
+ if r.bbr_state.state == BBRStateMachine::Drain &&
+ r.bytes_in_flight <= bbr_inflight(r, 1.0)
+ {
+ // we estimate queue is drained
+ bbr_enter_probe_bw(r, now);
+ }
+}
+
+// 4.3.4.3. Gain Cycling Algorithm
+fn bbr_enter_probe_bw(r: &mut Recovery, now: Instant) {
+ let bbr = &mut r.bbr_state;
+
+ bbr.state = BBRStateMachine::ProbeBW;
+ bbr.pacing_gain = 1.0;
+ bbr.cwnd_gain = 2.0;
+
+ // cycle_index will be one of (1, 2, 3, 4, 5, 6, 7). Since
+ // bbr_advance_cycle_phase() is called right next and it will
+ // increase cycle_index by 1, the actual cycle_index in the
+ // beginning of ProbeBW will be one of (2, 3, 4, 5, 6, 7, 0)
+ // to avoid index 1 (pacing_gain=3/4). See 4.3.4.2 for details.
+ bbr.cycle_index = BBR_GAIN_CYCLE_LEN -
+ 1 -
+ (rand::rand_u64_uniform(BBR_GAIN_CYCLE_LEN as u64 - 1) as usize);
+
+ bbr_advance_cycle_phase(r, now);
+}
+
+fn bbr_check_cycle_phase(r: &mut Recovery, now: Instant) {
+ let bbr = &mut r.bbr_state;
+
+ if bbr.state == BBRStateMachine::ProbeBW && bbr_is_next_cycle_phase(r, now) {
+ bbr_advance_cycle_phase(r, now);
+ }
+}
+
+fn bbr_advance_cycle_phase(r: &mut Recovery, now: Instant) {
+ let bbr = &mut r.bbr_state;
+
+ bbr.cycle_stamp = now;
+ bbr.cycle_index = (bbr.cycle_index + 1) % BBR_GAIN_CYCLE_LEN;
+ bbr.pacing_gain = PACING_GAIN_CYCLE[bbr.cycle_index];
+}
+
+fn bbr_is_next_cycle_phase(r: &mut Recovery, now: Instant) -> bool {
+ let bbr = &mut r.bbr_state;
+ let lost_bytes = bbr.newly_lost_bytes;
+ let pacing_gain = bbr.pacing_gain;
+ let prior_in_flight = bbr.prior_bytes_in_flight;
+
+ let is_full_length = (now - bbr.cycle_stamp) > bbr.rtprop;
+
+ // pacing_gain == 1.0
+ if (pacing_gain - 1.0).abs() < f64::EPSILON {
+ return is_full_length;
+ }
+
+ if pacing_gain > 1.0 {
+ return is_full_length &&
+ (lost_bytes > 0 ||
+ prior_in_flight >= bbr_inflight(r, pacing_gain));
+ }
+
+ is_full_length || prior_in_flight <= bbr_inflight(r, 1.0)
+}
+
+// 4.3.5. ProbeRTT
+fn bbr_check_probe_rtt(r: &mut Recovery, now: Instant) {
+ if r.bbr_state.state != BBRStateMachine::ProbeRTT &&
+ r.bbr_state.rtprop_expired &&
+ !r.bbr_state.idle_restart
+ {
+ bbr_enter_probe_rtt(r);
+
+ r.bbr_state.prior_cwnd = bbr_save_cwnd(r);
+ r.bbr_state.probe_rtt_done_stamp = None;
+ }
+
+ if r.bbr_state.state == BBRStateMachine::ProbeRTT {
+ bbr_handle_probe_rtt(r, now);
+ }
+
+ r.bbr_state.idle_restart = false;
+}
+
+fn bbr_enter_probe_rtt(r: &mut Recovery) {
+ let bbr = &mut r.bbr_state;
+
+ bbr.state = BBRStateMachine::ProbeRTT;
+ bbr.pacing_gain = 1.0;
+ bbr.cwnd_gain = 1.0;
+}
+
+fn bbr_handle_probe_rtt(r: &mut Recovery, now: Instant) {
+ // Ignore low rate samples during ProbeRTT.
+ r.delivery_rate.update_app_limited(true);
+
+ if let Some(probe_rtt_done_stamp) = r.bbr_state.probe_rtt_done_stamp {
+ if r.bbr_state.round_start {
+ r.bbr_state.probe_rtt_round_done = true;
+ }
+
+ if r.bbr_state.probe_rtt_round_done && now > probe_rtt_done_stamp {
+ r.bbr_state.rtprop_stamp = now;
+
+ bbr_restore_cwnd(r);
+ bbr_exit_probe_rtt(r, now);
+ }
+ } else if r.bytes_in_flight <= bbr_min_pipe_cwnd(r) {
+ r.bbr_state.probe_rtt_done_stamp = Some(now + PROBE_RTT_DURATION);
+ r.bbr_state.probe_rtt_round_done = false;
+ r.bbr_state.next_round_delivered = r.delivery_rate.delivered();
+ }
+}
+
+fn bbr_exit_probe_rtt(r: &mut Recovery, now: Instant) {
+ if r.bbr_state.filled_pipe {
+ bbr_enter_probe_bw(r, now);
+ } else {
+ init::bbr_enter_startup(r);
+ }
+}
diff --git a/quiche/src/recovery/bbr/per_transmit.rs b/quiche/src/recovery/bbr/per_transmit.rs
new file mode 100644
index 0000000..f454387
--- /dev/null
+++ b/quiche/src/recovery/bbr/per_transmit.rs
@@ -0,0 +1,46 @@
+// Copyright (C) 2022, 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.
+
+use super::*;
+
+use crate::recovery::Recovery;
+
+// BBR Functions when trasmitting packets.
+//
+pub fn bbr_on_transmit(r: &mut Recovery) {
+ bbr_handle_restart_from_idle(r);
+}
+
+// 4.3.4.4. Restarting From Idle
+fn bbr_handle_restart_from_idle(r: &mut Recovery) {
+ if r.bytes_in_flight == 0 && r.delivery_rate.app_limited() {
+ r.bbr_state.idle_restart = true;
+
+ if r.bbr_state.state == BBRStateMachine::ProbeBW {
+ pacing::bbr_set_pacing_rate_with_gain(r, 1.0);
+ }
+ }
+}
diff --git a/quiche/src/recovery/delivery_rate.rs b/quiche/src/recovery/delivery_rate.rs
index dcc3e48..37c2aaf 100644
--- a/quiche/src/recovery/delivery_rate.rs
+++ b/quiche/src/recovery/delivery_rate.rs
@@ -162,7 +162,7 @@
self.end_of_app_limited != 0
}
- pub fn _delivered(&self) -> usize {
+ pub fn delivered(&self) -> usize {
self.delivered
}
@@ -170,11 +170,11 @@
self.rate_sample.delivery_rate
}
- pub fn _sample_rtt(&self) -> Duration {
+ pub fn sample_rtt(&self) -> Duration {
self.rate_sample.rtt
}
- pub fn _sample_is_app_limited(&self) -> bool {
+ pub fn sample_is_app_limited(&self) -> bool {
self.rate_sample.is_app_limited
}
}
@@ -264,7 +264,7 @@
r.delivery_rate.generate_rate_sample(rtt);
// Bytes acked so far.
- assert_eq!(r.delivery_rate._delivered(), 2400);
+ assert_eq!(r.delivery_rate.delivered(), 2400);
// Estimated delivery rate = (1200 x 2) / 0.05s = 48000.
assert_eq!(r.delivery_rate(), 48000);
@@ -306,7 +306,7 @@
}
assert_eq!(r.app_limited(), false);
- assert_eq!(r.delivery_rate._sample_is_app_limited(), false);
+ assert_eq!(r.delivery_rate.sample_is_app_limited(), false);
}
#[test]
@@ -363,9 +363,8 @@
);
assert_eq!(r.app_limited(), true);
-
// Rate sample is not app limited (all acked).
- assert_eq!(r.delivery_rate._sample_is_app_limited(), false);
- assert_eq!(r.delivery_rate._sample_rtt(), rtt);
+ assert_eq!(r.delivery_rate.sample_is_app_limited(), false);
+ assert_eq!(r.delivery_rate.sample_rtt(), rtt);
}
}
diff --git a/quiche/src/recovery/mod.rs b/quiche/src/recovery/mod.rs
index a753422..4011fe3 100644
--- a/quiche/src/recovery/mod.rs
+++ b/quiche/src/recovery/mod.rs
@@ -156,6 +156,9 @@
// The maximum size of a data aggregate scheduled and
// transmitted together.
send_quantum: usize,
+
+ // BBR state.
+ bbr_state: bbr::State,
}
impl Recovery {
@@ -249,6 +252,8 @@
#[cfg(feature = "qlog")]
qlog_metrics: QlogMetrics::default(),
+
+ bbr_state: bbr::State::new(),
}
}
@@ -977,6 +982,8 @@
Reno = 0,
/// CUBIC congestion control algorithm (default). `cubic` in a string form.
CUBIC = 1,
+ /// BBR congestion control algorithm. `bbr` in a string form.
+ BBR = 2,
}
impl FromStr for CongestionControlAlgorithm {
@@ -989,6 +996,7 @@
match name {
"reno" => Ok(CongestionControlAlgorithm::Reno),
"cubic" => Ok(CongestionControlAlgorithm::CUBIC),
+ "bbr" => Ok(CongestionControlAlgorithm::BBR),
_ => Err(crate::Error::CongestionControl),
}
@@ -1032,6 +1040,7 @@
match algo {
CongestionControlAlgorithm::Reno => &reno::RENO,
CongestionControlAlgorithm::CUBIC => &cubic::CUBIC,
+ CongestionControlAlgorithm::BBR => &bbr::BBR,
}
}
}
@@ -2045,6 +2054,7 @@
}
}
+mod bbr;
mod cubic;
mod delivery_rate;
mod hystart;
