quiche/recovery/congestion/bbr/

per_ack.rs

// 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 std::cmp;

use super::*;
use crate::rand;
use crate::recovery::MINIMUM_WINDOW_PACKETS;

/// 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 Congestion) -> 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 Congestion, packet: &Acked, bytes_in_flight: usize, now: Instant,
) {
    bbr_update_btlbw(r, packet, bytes_in_flight);
    bbr_check_cycle_phase(r, now);
    bbr_check_full_pipe(r);
    bbr_check_drain(r, bytes_in_flight, now);
    bbr_update_rtprop(r, now);
    bbr_check_probe_rtt(r, bytes_in_flight, now);
}

pub fn bbr_update_control_parameters(
    r: &mut Congestion, bytes_in_flight: usize, 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, bytes_in_flight);
}

// BBR Functions while processing ACKs.
//

// 4.1.1.5.  Updating the BBR.BtlBw Max Filter
fn bbr_update_btlbw(r: &mut Congestion, packet: &Acked, _bytes_in_flight: usize) {
    bbr_update_round(r, packet);

    if r.delivery_rate().to_bytes_per_second() >= 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().to_bytes_per_second(),
        );
    }
}

// 4.1.1.3 Tracking Time for the BBR.BtlBw Max Filter
fn bbr_update_round(r: &mut Congestion, 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 Congestion, 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 Congestion) {
    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 Congestion, gain: f64) -> usize {
    let bbr = &mut r.bbr_state;

    if bbr.rtprop == Duration::MAX {
        return r.max_datagram_size * r.initial_congestion_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 Congestion) {
    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 Congestion) -> 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 Congestion) {
    r.congestion_window = r.congestion_window.max(r.bbr_state.prior_cwnd);
}

fn bbr_modulate_cwnd_for_recovery(r: &mut Congestion, bytes_in_flight: usize) {
    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 * MINIMUM_WINDOW_PACKETS);
    }

    if r.bbr_state.packet_conservation {
        r.congestion_window =
            r.congestion_window.max(bytes_in_flight + acked_bytes);
    }
}

// 4.2.3.5 Modulating cwnd in ProbeRTT
fn bbr_modulate_cwnd_for_probe_rtt(r: &mut Congestion) {
    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 Congestion, bytes_in_flight: usize) {
    let acked_bytes = r.bbr_state.newly_acked_bytes;

    bbr_update_target_cwnd(r);
    bbr_modulate_cwnd_for_recovery(r, bytes_in_flight);

    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 * r.initial_congestion_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 Congestion) {
    // 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 Congestion) {
    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 Congestion, bytes_in_flight: usize, 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 &&
        bbr_bytes_in_net(r, bytes_in_flight, now) <= bbr_inflight(r, 1.0)
    {
        // we estimate queue is drained
        bbr_enter_probe_bw(r, now);
    }
}

/// Estimates the number of bytes "in the network" based on pacing.
///
/// When pacing is implemented at lower layers (e.g. when TX_TIME and the sch_fq
/// qdisc are used), the in-flight data can be higher than the amount data
/// actually sent on the network.
///
/// This is largely based on the [`bbr_packets_in_net_at_edt()`] function from
/// Linux' BBR implementation.
///
/// [`bbr_packets_in_net_at_edt()`]: https://elixir.bootlin.com/linux/v6.13.7/source/net/ipv4/tcp_bbr.c#L437
fn bbr_bytes_in_net(r: &Congestion, in_flight: usize, now: Instant) -> usize {
    let edt = r.pacer.next_time().max(now);
    let interval = edt.saturating_duration_since(now);
    let interval_delivered = interval.as_secs_f64() * r.bbr_state.btlbw as f64;

    let mut in_flight_at_edt = in_flight;

    if r.bbr_state.pacing_gain > 1.0 {
        in_flight_at_edt += r.send_quantum;
    }

    in_flight_at_edt.saturating_sub(interval_delivered as usize)
}

// 4.3.4.3.  Gain Cycling Algorithm
fn bbr_enter_probe_bw(r: &mut Congestion, 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 Congestion, 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 Congestion, 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 Congestion, now: Instant) -> bool {
    let bbr = &mut r.bbr_state;
    let lost_bytes = bbr.newly_lost_bytes;
    let pacing_gain = bbr.pacing_gain;

    let is_full_length = (now - bbr.cycle_stamp) > bbr.rtprop;

    let prior_in_flight = bbr.prior_bytes_in_flight;
    let prior_in_flight = bbr_bytes_in_net(r, prior_in_flight, now);

    // 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 Congestion, bytes_in_flight: usize, 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, bytes_in_flight, now);
    }

    r.bbr_state.idle_restart = false;
}

fn bbr_enter_probe_rtt(r: &mut Congestion) {
    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 Congestion, bytes_in_flight: usize, 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 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 Congestion, now: Instant) {
    if r.bbr_state.filled_pipe {
        bbr_enter_probe_bw(r, now);
    } else {
        init::bbr_enter_startup(r);
    }
}