lsquic_bbr.c revision 9fc12041
17d09751dSDmitri Tikhonov/* Copyright (c) 2017 - 2020 LiteSpeed Technologies Inc.  See LICENSE. */
25392f7a3SLiteSpeed Tech// Copyright 2016 The Chromium Authors. All rights reserved.
35392f7a3SLiteSpeed Tech// Use of this source code is governed by a BSD-style license that can be
45392f7a3SLiteSpeed Tech// found in the LICENSE.chrome file.
55392f7a3SLiteSpeed Tech
65392f7a3SLiteSpeed Tech#include <assert.h>
75392f7a3SLiteSpeed Tech#include <inttypes.h>
85392f7a3SLiteSpeed Tech#include <stdint.h>
95392f7a3SLiteSpeed Tech#include <stdlib.h>
105392f7a3SLiteSpeed Tech#include <string.h>
115392f7a3SLiteSpeed Tech#include <sys/queue.h>
125392f7a3SLiteSpeed Tech
135392f7a3SLiteSpeed Tech#include "lsquic.h"
145392f7a3SLiteSpeed Tech#include "lsquic_int_types.h"
155392f7a3SLiteSpeed Tech#include "lsquic_cong_ctl.h"
165392f7a3SLiteSpeed Tech#include "lsquic_minmax.h"
175392f7a3SLiteSpeed Tech#include "lsquic_packet_common.h"
185392f7a3SLiteSpeed Tech#include "lsquic_packet_out.h"
195392f7a3SLiteSpeed Tech#include "lsquic_bw_sampler.h"
205392f7a3SLiteSpeed Tech#include "lsquic_bbr.h"
215392f7a3SLiteSpeed Tech#include "lsquic_hash.h"
225392f7a3SLiteSpeed Tech#include "lsquic_conn.h"
235392f7a3SLiteSpeed Tech#include "lsquic_sfcw.h"
245392f7a3SLiteSpeed Tech#include "lsquic_conn_flow.h"
255392f7a3SLiteSpeed Tech#include "lsquic_varint.h"
265392f7a3SLiteSpeed Tech#include "lsquic_hq.h"
275392f7a3SLiteSpeed Tech#include "lsquic_stream.h"
285392f7a3SLiteSpeed Tech#include "lsquic_rtt.h"
295392f7a3SLiteSpeed Tech#include "lsquic_conn_public.h"
305392f7a3SLiteSpeed Tech#include "lsquic_util.h"
315392f7a3SLiteSpeed Tech#include "lsquic_malo.h"
3210c41073SDmitri Tikhonov#include "lsquic_crand.h"
3310c41073SDmitri Tikhonov#include "lsquic_mm.h"
3410c41073SDmitri Tikhonov#include "lsquic_engine_public.h"
355392f7a3SLiteSpeed Tech
365392f7a3SLiteSpeed Tech#define LSQUIC_LOGGER_MODULE LSQLM_BBR
3710c41073SDmitri Tikhonov#define LSQUIC_LOG_CONN_ID lsquic_conn_log_cid(bbr->bbr_conn_pub->lconn)
385392f7a3SLiteSpeed Tech#include "lsquic_logger.h"
395392f7a3SLiteSpeed Tech
405392f7a3SLiteSpeed Tech#define MIN(a, b) ((a) < (b) ? (a) : (b))
415392f7a3SLiteSpeed Tech#define MAX(a, b) ((a) > (b) ? (a) : (b))
425392f7a3SLiteSpeed Tech
435392f7a3SLiteSpeed Tech#define ms(val_) ((val_) * 1000)
445392f7a3SLiteSpeed Tech#define sec(val_) ((val_) * 1000 * 1000)
455392f7a3SLiteSpeed Tech
465392f7a3SLiteSpeed Tech// Default maximum packet size used in the Linux TCP implementation.
475392f7a3SLiteSpeed Tech// Used in QUIC for congestion window computations in bytes.
485392f7a3SLiteSpeed Tech#define kDefaultTCPMSS 1460
495392f7a3SLiteSpeed Tech#define kMaxSegmentSize kDefaultTCPMSS
505392f7a3SLiteSpeed Tech
515392f7a3SLiteSpeed Tech// Constants based on TCP defaults.
525392f7a3SLiteSpeed Tech// The minimum CWND to ensure delayed acks don't reduce bandwidth measurements.
535392f7a3SLiteSpeed Tech// Does not inflate the pacing rate.
545392f7a3SLiteSpeed Tech#define kDefaultMinimumCongestionWindow  (4 * kDefaultTCPMSS)
555392f7a3SLiteSpeed Tech
565392f7a3SLiteSpeed Tech// The gain used for the STARTUP, equal to 2/ln(2).
575392f7a3SLiteSpeed Tech#define kDefaultHighGain 2.885f
585392f7a3SLiteSpeed Tech
595392f7a3SLiteSpeed Tech// The newly derived gain for STARTUP, equal to 4 * ln(2)
605392f7a3SLiteSpeed Tech#define kDerivedHighGain 2.773f
615392f7a3SLiteSpeed Tech
625392f7a3SLiteSpeed Tech// The newly derived CWND gain for STARTUP, 2.
635392f7a3SLiteSpeed Tech#define kDerivedHighCWNDGain 2.0f
645392f7a3SLiteSpeed Tech
655392f7a3SLiteSpeed Tech// The gain used in STARTUP after loss has been detected.
665392f7a3SLiteSpeed Tech// 1.5 is enough to allow for 25% exogenous loss and still observe a 25% growth
675392f7a3SLiteSpeed Tech// in measured bandwidth.
685392f7a3SLiteSpeed Tech#define kStartupAfterLossGain 1.5f
695392f7a3SLiteSpeed Tech
705392f7a3SLiteSpeed Tech// We match SPDY's use of 32 (since we'd compete with SPDY).
715392f7a3SLiteSpeed Tech#define kInitialCongestionWindow 32
725392f7a3SLiteSpeed Tech
735392f7a3SLiteSpeed Tech/* Taken from send_algorithm_interface.h */
745392f7a3SLiteSpeed Tech#define kDefaultMaxCongestionWindowPackets 2000
755392f7a3SLiteSpeed Tech
765392f7a3SLiteSpeed Tech// The time after which the current min_rtt value expires.
775392f7a3SLiteSpeed Tech#define kMinRttExpiry sec(10)
785392f7a3SLiteSpeed Tech
795392f7a3SLiteSpeed Tech// Coefficient to determine if a new RTT is sufficiently similar to min_rtt that
805392f7a3SLiteSpeed Tech// we don't need to enter PROBE_RTT.
815392f7a3SLiteSpeed Tech#define kSimilarMinRttThreshold 1.125f
825392f7a3SLiteSpeed Tech
835392f7a3SLiteSpeed Tech// If the bandwidth does not increase by the factor of |kStartupGrowthTarget|
845392f7a3SLiteSpeed Tech// within |kRoundTripsWithoutGrowthBeforeExitingStartup| rounds, the connection
855392f7a3SLiteSpeed Tech// will exit the STARTUP mode.
865392f7a3SLiteSpeed Tech#define kStartupGrowthTarget 1.25
875392f7a3SLiteSpeed Tech
885392f7a3SLiteSpeed Tech#define kRoundTripsWithoutGrowthBeforeExitingStartup 3
895392f7a3SLiteSpeed Tech
905392f7a3SLiteSpeed Tech#define startup_rate_reduction_multiplier_ 0
915392f7a3SLiteSpeed Tech
925392f7a3SLiteSpeed Tech// The cycle of gains used during the PROBE_BW stage.
935392f7a3SLiteSpeed Techstatic const float kPacingGain[] = {1.25, 0.75, 1, 1, 1, 1, 1, 1};
945392f7a3SLiteSpeed Tech
955392f7a3SLiteSpeed Tech// The length of the gain cycle.
965392f7a3SLiteSpeed Techstatic const size_t kGainCycleLength = sizeof(kPacingGain)
975392f7a3SLiteSpeed Tech                                                    / sizeof(kPacingGain[0]);
985392f7a3SLiteSpeed Tech
995392f7a3SLiteSpeed Tech// Coefficient of target congestion window to use when basing PROBE_RTT on BDP.
1005392f7a3SLiteSpeed Tech#define kModerateProbeRttMultiplier 0.75
1015392f7a3SLiteSpeed Tech
1025392f7a3SLiteSpeed Tech// The maximum packet size of any QUIC packet over IPv6, based on ethernet's max
1035392f7a3SLiteSpeed Tech// size, minus the IP and UDP headers. IPv6 has a 40 byte header, UDP adds an
1045392f7a3SLiteSpeed Tech// additional 8 bytes.  This is a total overhead of 48 bytes.  Ethernet's
1055392f7a3SLiteSpeed Tech// max packet size is 1500 bytes,  1500 - 48 = 1452.
1065392f7a3SLiteSpeed Tech#define kMaxV6PacketSize 1452
1075392f7a3SLiteSpeed Tech// The maximum packet size of any QUIC packet over IPv4.
1085392f7a3SLiteSpeed Tech// 1500(Ethernet) - 20(IPv4 header) - 8(UDP header) = 1472.
1095392f7a3SLiteSpeed Tech#define kMaxV4PacketSize 1472
1105392f7a3SLiteSpeed Tech// The maximum incoming packet size allowed.
1115392f7a3SLiteSpeed Tech#define kMaxIncomingPacketSize kMaxV4PacketSize
1125392f7a3SLiteSpeed Tech// The maximum outgoing packet size allowed.
1135392f7a3SLiteSpeed Tech#define kMaxOutgoingPacketSize kMaxV6PacketSize
1145392f7a3SLiteSpeed Tech
1155392f7a3SLiteSpeed Tech// The minimum time the connection can spend in PROBE_RTT mode.
1165392f7a3SLiteSpeed Tech#define kProbeRttTime ms(200)
1175392f7a3SLiteSpeed Tech
1185392f7a3SLiteSpeed Tech/* FLAG* are from net/quic/quic_flags_list.h */
1195392f7a3SLiteSpeed Tech
1205392f7a3SLiteSpeed Tech// When in STARTUP and recovery, do not add bytes_acked to QUIC BBR's CWND in
1215392f7a3SLiteSpeed Tech// CalculateCongestionWindow()
1225392f7a3SLiteSpeed Tech#define FLAGS_quic_bbr_no_bytes_acked_in_startup_recovery 0
1235392f7a3SLiteSpeed Tech
1245392f7a3SLiteSpeed Tech// When true, ensure BBR allows at least one MSS to be sent in response to an
1255392f7a3SLiteSpeed Tech// ACK in packet conservation.
1265392f7a3SLiteSpeed Tech#define FLAG_quic_bbr_one_mss_conservation 0
1275392f7a3SLiteSpeed Tech
1285392f7a3SLiteSpeed Tech/* From net/quic/quic_flags_list.h */
1295392f7a3SLiteSpeed Tech#define kCwndGain 2.0
1305392f7a3SLiteSpeed Tech
1315392f7a3SLiteSpeed Tech
1325392f7a3SLiteSpeed Techstatic uint64_t lsquic_bbr_get_cwnd (void *);
1335392f7a3SLiteSpeed Tech
1345392f7a3SLiteSpeed Tech
1355392f7a3SLiteSpeed Techstatic const char *const mode2str[] =
1365392f7a3SLiteSpeed Tech{
1375392f7a3SLiteSpeed Tech    [BBR_MODE_STARTUP]   = "STARTUP",
1385392f7a3SLiteSpeed Tech    [BBR_MODE_DRAIN]     = "DRAIN",
1395392f7a3SLiteSpeed Tech    [BBR_MODE_PROBE_BW]  = "PROBE_BW",
1405392f7a3SLiteSpeed Tech    [BBR_MODE_PROBE_RTT] = "PROBE_RTT",
1415392f7a3SLiteSpeed Tech};
1425392f7a3SLiteSpeed Tech
1435392f7a3SLiteSpeed Tech
1445392f7a3SLiteSpeed Techstatic void
1455392f7a3SLiteSpeed Techset_mode (struct lsquic_bbr *bbr, enum bbr_mode mode)
1465392f7a3SLiteSpeed Tech{
1475392f7a3SLiteSpeed Tech    if (bbr->bbr_mode != mode)
1485392f7a3SLiteSpeed Tech    {
1495392f7a3SLiteSpeed Tech        LSQ_DEBUG("mode change %s -> %s", mode2str[bbr->bbr_mode],
1505392f7a3SLiteSpeed Tech                                                        mode2str[mode]);
1515392f7a3SLiteSpeed Tech        bbr->bbr_mode = mode;
1525392f7a3SLiteSpeed Tech    }
1535392f7a3SLiteSpeed Tech    else
1545392f7a3SLiteSpeed Tech        LSQ_DEBUG("mode remains %s", mode2str[mode]);
1555392f7a3SLiteSpeed Tech}
1565392f7a3SLiteSpeed Tech
1575392f7a3SLiteSpeed Tech
1585392f7a3SLiteSpeed Techstatic void
1595392f7a3SLiteSpeed Techset_startup_values (struct lsquic_bbr *bbr)
1605392f7a3SLiteSpeed Tech{
1615392f7a3SLiteSpeed Tech    bbr->bbr_pacing_gain = bbr->bbr_high_gain;
1625392f7a3SLiteSpeed Tech    bbr->bbr_cwnd_gain = bbr->bbr_high_cwnd_gain;
1635392f7a3SLiteSpeed Tech}
1645392f7a3SLiteSpeed Tech
1655392f7a3SLiteSpeed Tech
1665392f7a3SLiteSpeed Techstatic void
1679fc12041SDmitri Tikhonovinit_bbr (struct lsquic_bbr *bbr)
1685392f7a3SLiteSpeed Tech{
1695392f7a3SLiteSpeed Tech    bbr->bbr_mode = BBR_MODE_STARTUP;
1705392f7a3SLiteSpeed Tech    bbr->bbr_round_count = 0;
1715392f7a3SLiteSpeed Tech    minmax_init(&bbr->bbr_max_bandwidth, 10);
1725392f7a3SLiteSpeed Tech    minmax_init(&bbr->bbr_max_ack_height, 10);
1735392f7a3SLiteSpeed Tech    bbr->bbr_aggregation_epoch_bytes = 0;
1745392f7a3SLiteSpeed Tech    bbr->bbr_aggregation_epoch_start_time = 0;
1755392f7a3SLiteSpeed Tech    bbr->bbr_min_rtt = 0;
1765392f7a3SLiteSpeed Tech    bbr->bbr_min_rtt_timestamp = 0;
1775392f7a3SLiteSpeed Tech    bbr->bbr_init_cwnd = kInitialCongestionWindow * kDefaultTCPMSS;
1785392f7a3SLiteSpeed Tech    bbr->bbr_cwnd = kInitialCongestionWindow * kDefaultTCPMSS;
1795392f7a3SLiteSpeed Tech    bbr->bbr_max_cwnd = kDefaultMaxCongestionWindowPackets * kDefaultTCPMSS;
1805392f7a3SLiteSpeed Tech    bbr->bbr_min_cwnd = kDefaultMinimumCongestionWindow;
1815392f7a3SLiteSpeed Tech    bbr->bbr_high_gain = kDefaultHighGain;
1825392f7a3SLiteSpeed Tech    bbr->bbr_high_cwnd_gain = kDefaultHighGain;
1835392f7a3SLiteSpeed Tech    bbr->bbr_drain_gain = 1.0 / kDefaultHighGain;
1845392f7a3SLiteSpeed Tech    bbr->bbr_pacing_rate = BW_ZERO();
1855392f7a3SLiteSpeed Tech    bbr->bbr_pacing_gain = 1.0;
1865392f7a3SLiteSpeed Tech    bbr->bbr_cwnd_gain = 1.0;
1875392f7a3SLiteSpeed Tech    bbr->bbr_num_startup_rtts = kRoundTripsWithoutGrowthBeforeExitingStartup;
1885392f7a3SLiteSpeed Tech    bbr->bbr_flags &= ~BBR_FLAG_EXIT_STARTUP_ON_LOSS;
1895392f7a3SLiteSpeed Tech    bbr->bbr_cycle_current_offset = 0;
1905392f7a3SLiteSpeed Tech    bbr->bbr_last_cycle_start = 0;
1915392f7a3SLiteSpeed Tech    bbr->bbr_flags &= ~BBR_FLAG_IS_AT_FULL_BANDWIDTH;
1925392f7a3SLiteSpeed Tech    bbr->bbr_round_wo_bw_gain = 0;
1935392f7a3SLiteSpeed Tech    bbr->bbr_bw_at_last_round = BW_ZERO();
1945392f7a3SLiteSpeed Tech    bbr->bbr_flags &= ~BBR_FLAG_EXITING_QUIESCENCE;
1955392f7a3SLiteSpeed Tech    bbr->bbr_exit_probe_rtt_at = 0;
1965392f7a3SLiteSpeed Tech    bbr->bbr_flags &= ~BBR_FLAG_PROBE_RTT_ROUND_PASSED;
1975392f7a3SLiteSpeed Tech    bbr->bbr_flags &= ~BBR_FLAG_LAST_SAMPLE_APP_LIMITED;
1985392f7a3SLiteSpeed Tech    bbr->bbr_flags &= ~BBR_FLAG_HAS_NON_APP_LIMITED;
1995392f7a3SLiteSpeed Tech    bbr->bbr_flags &= ~BBR_FLAG_FLEXIBLE_APP_LIMITED;
2005392f7a3SLiteSpeed Tech    set_startup_values(bbr);
2019fc12041SDmitri Tikhonov}
2029fc12041SDmitri Tikhonov
2039fc12041SDmitri Tikhonov
2049fc12041SDmitri Tikhonovstatic void
2059fc12041SDmitri Tikhonovlsquic_bbr_init (void *cong_ctl, const struct lsquic_conn_public *conn_pub,
2069fc12041SDmitri Tikhonov                                                enum quic_ft_bit retx_frames)
2079fc12041SDmitri Tikhonov{
2089fc12041SDmitri Tikhonov    struct lsquic_bbr *const bbr = cong_ctl;
2099fc12041SDmitri Tikhonov    bbr->bbr_conn_pub = conn_pub;
2109fc12041SDmitri Tikhonov    lsquic_bw_sampler_init(&bbr->bbr_bw_sampler, conn_pub->lconn, retx_frames);
2119fc12041SDmitri Tikhonov    bbr->bbr_rtt_stats = &conn_pub->rtt_stats;
2129fc12041SDmitri Tikhonov
2139fc12041SDmitri Tikhonov    init_bbr(bbr);
2145392f7a3SLiteSpeed Tech
2155392f7a3SLiteSpeed Tech    LSQ_DEBUG("initialized");
2165392f7a3SLiteSpeed Tech}
2175392f7a3SLiteSpeed Tech
2185392f7a3SLiteSpeed Tech
2199fc12041SDmitri Tikhonovstatic void
2209fc12041SDmitri Tikhonovlsquic_bbr_reinit (void *cong_ctl)
2219fc12041SDmitri Tikhonov{
2229fc12041SDmitri Tikhonov    struct lsquic_bbr *const bbr = cong_ctl;
2239fc12041SDmitri Tikhonov
2249fc12041SDmitri Tikhonov    init_bbr(bbr);
2259fc12041SDmitri Tikhonov
2269fc12041SDmitri Tikhonov    LSQ_DEBUG("re-initialized");
2279fc12041SDmitri Tikhonov}
2289fc12041SDmitri Tikhonov
2299fc12041SDmitri Tikhonov
2305392f7a3SLiteSpeed Techstatic lsquic_time_t
2315392f7a3SLiteSpeed Techget_min_rtt (const struct lsquic_bbr *bbr)
2325392f7a3SLiteSpeed Tech{
2335392f7a3SLiteSpeed Tech    lsquic_time_t min_rtt;
2345392f7a3SLiteSpeed Tech
2355392f7a3SLiteSpeed Tech    if (bbr->bbr_min_rtt)
2365392f7a3SLiteSpeed Tech        return bbr->bbr_min_rtt;
2375392f7a3SLiteSpeed Tech    else
2385392f7a3SLiteSpeed Tech    {
2395392f7a3SLiteSpeed Tech        min_rtt = lsquic_rtt_stats_get_min_rtt(bbr->bbr_rtt_stats);
2405392f7a3SLiteSpeed Tech        if (min_rtt == 0)
2415392f7a3SLiteSpeed Tech            min_rtt = 25000;
2425392f7a3SLiteSpeed Tech        return min_rtt;
2435392f7a3SLiteSpeed Tech    }
2445392f7a3SLiteSpeed Tech}
2455392f7a3SLiteSpeed Tech
2465392f7a3SLiteSpeed Tech
2475392f7a3SLiteSpeed Techstatic uint64_t
2485392f7a3SLiteSpeed Techlsquic_bbr_pacing_rate (void *cong_ctl, int in_recovery)
2495392f7a3SLiteSpeed Tech{
2505392f7a3SLiteSpeed Tech    struct lsquic_bbr *const bbr = cong_ctl;
2515392f7a3SLiteSpeed Tech    lsquic_time_t min_rtt;
2525392f7a3SLiteSpeed Tech    struct bandwidth bw;
2535392f7a3SLiteSpeed Tech
2545392f7a3SLiteSpeed Tech    if (!BW_IS_ZERO(&bbr->bbr_pacing_rate))
2555392f7a3SLiteSpeed Tech        bw = bbr->bbr_pacing_rate;
2565392f7a3SLiteSpeed Tech    else
2575392f7a3SLiteSpeed Tech    {
2585392f7a3SLiteSpeed Tech        min_rtt = get_min_rtt(bbr);
2595392f7a3SLiteSpeed Tech        bw = BW_FROM_BYTES_AND_DELTA(bbr->bbr_init_cwnd, min_rtt);
2605392f7a3SLiteSpeed Tech        bw = BW_TIMES(&bw, bbr->bbr_high_cwnd_gain);
2615392f7a3SLiteSpeed Tech    }
2625392f7a3SLiteSpeed Tech
2635392f7a3SLiteSpeed Tech    return BW_TO_BYTES_PER_SEC(&bw);
2645392f7a3SLiteSpeed Tech}
2655392f7a3SLiteSpeed Tech
2665392f7a3SLiteSpeed Tech
2675392f7a3SLiteSpeed Tech/* BbrSender::GetTargetCongestionWindow */
2685392f7a3SLiteSpeed Techstatic uint64_t
2695392f7a3SLiteSpeed Techget_target_cwnd (const struct lsquic_bbr *bbr, float gain)
2705392f7a3SLiteSpeed Tech{
2715392f7a3SLiteSpeed Tech    struct bandwidth bw;
2725392f7a3SLiteSpeed Tech    uint64_t bdp, cwnd;
2735392f7a3SLiteSpeed Tech
2745392f7a3SLiteSpeed Tech    bw = BW(minmax_get(&bbr->bbr_max_bandwidth));
2755392f7a3SLiteSpeed Tech    bdp = get_min_rtt(bbr) * BW_TO_BYTES_PER_SEC(&bw) / 1000000;
2765392f7a3SLiteSpeed Tech    cwnd = gain * bdp;
2775392f7a3SLiteSpeed Tech
2785392f7a3SLiteSpeed Tech    // BDP estimate will be zero if no bandwidth samples are available yet.
2795392f7a3SLiteSpeed Tech    if (cwnd == 0)
2805392f7a3SLiteSpeed Tech        cwnd = gain * bbr->bbr_init_cwnd;
2815392f7a3SLiteSpeed Tech
2825392f7a3SLiteSpeed Tech    return MAX(cwnd, bbr->bbr_min_cwnd);
2835392f7a3SLiteSpeed Tech}
2845392f7a3SLiteSpeed Tech
2855392f7a3SLiteSpeed Tech
2865392f7a3SLiteSpeed Tech/* See BbrSender::IsPipeSufficientlyFull */
2875392f7a3SLiteSpeed Techstatic int
2885392f7a3SLiteSpeed Techis_pipe_sufficiently_full (struct lsquic_bbr *bbr, uint64_t bytes_in_flight)
2895392f7a3SLiteSpeed Tech{
2905392f7a3SLiteSpeed Tech    // See if we need more bytes in flight to see more bandwidth.
2915392f7a3SLiteSpeed Tech    if (bbr->bbr_mode == BBR_MODE_STARTUP)
2925392f7a3SLiteSpeed Tech        // STARTUP exits if it doesn't observe a 25% bandwidth increase, so
2935392f7a3SLiteSpeed Tech        // the CWND must be more than 25% above the target.
2945392f7a3SLiteSpeed Tech        return bytes_in_flight >= get_target_cwnd(bbr, 1.5);
2955392f7a3SLiteSpeed Tech    else if (bbr->bbr_pacing_gain > 1)
2965392f7a3SLiteSpeed Tech        // Super-unity PROBE_BW doesn't exit until 1.25 * BDP is achieved.
2975392f7a3SLiteSpeed Tech        return bytes_in_flight >= get_target_cwnd(bbr, bbr->bbr_pacing_gain);
2985392f7a3SLiteSpeed Tech    else
2995392f7a3SLiteSpeed Tech        // If bytes_in_flight are above the target congestion window, it should
3005392f7a3SLiteSpeed Tech        // be possible to observe the same or more bandwidth if it's available.
3015392f7a3SLiteSpeed Tech        return bytes_in_flight >= get_target_cwnd(bbr, 1.1);
3025392f7a3SLiteSpeed Tech}
3035392f7a3SLiteSpeed Tech
3045392f7a3SLiteSpeed Tech
3055392f7a3SLiteSpeed Techstatic void
306cca25415SDmitri Tikhonovlsquic_bbr_was_quiet (void *cong_ctl, lsquic_time_t now, uint64_t in_flight)
3075392f7a3SLiteSpeed Tech{
3085392f7a3SLiteSpeed Tech    struct lsquic_bbr *const bbr = cong_ctl;
309cca25415SDmitri Tikhonov    LSQ_DEBUG("was quiet");         /* Do nothing */
310cca25415SDmitri Tikhonov}
311cca25415SDmitri Tikhonov
312cca25415SDmitri Tikhonov
313cca25415SDmitri Tikhonov/* See BbrSender::OnApplicationLimited */
314cca25415SDmitri Tikhonovstatic void
315cca25415SDmitri Tikhonovbbr_app_limited (struct lsquic_bbr *bbr, uint64_t bytes_in_flight)
316cca25415SDmitri Tikhonov{
3175392f7a3SLiteSpeed Tech    uint64_t cwnd;
3185392f7a3SLiteSpeed Tech
319cca25415SDmitri Tikhonov    cwnd = lsquic_bbr_get_cwnd(bbr);
3205392f7a3SLiteSpeed Tech    if (bytes_in_flight >= cwnd)
3215392f7a3SLiteSpeed Tech        return;
3225392f7a3SLiteSpeed Tech    if ((bbr->bbr_flags & BBR_FLAG_FLEXIBLE_APP_LIMITED)
3235392f7a3SLiteSpeed Tech                            && is_pipe_sufficiently_full(bbr, bytes_in_flight))
3245392f7a3SLiteSpeed Tech        return;
3255392f7a3SLiteSpeed Tech
3265392f7a3SLiteSpeed Tech    bbr->bbr_flags |= BBR_FLAG_APP_LIMITED_SINCE_LAST_PROBE_RTT;
3275392f7a3SLiteSpeed Tech    lsquic_bw_sampler_app_limited(&bbr->bbr_bw_sampler);
3285392f7a3SLiteSpeed Tech    LSQ_DEBUG("becoming application-limited.  Last sent packet: %"PRIu64"; "
3295392f7a3SLiteSpeed Tech                            "CWND: %"PRIu64, bbr->bbr_last_sent_packno, cwnd);
3305392f7a3SLiteSpeed Tech}
3315392f7a3SLiteSpeed Tech
3325392f7a3SLiteSpeed Tech
3335392f7a3SLiteSpeed Techstatic void
3345392f7a3SLiteSpeed Techlsquic_bbr_ack (void *cong_ctl, struct lsquic_packet_out *packet_out,
3355392f7a3SLiteSpeed Tech                  unsigned packet_sz, lsquic_time_t now_time, int app_limited)
3365392f7a3SLiteSpeed Tech{
3375392f7a3SLiteSpeed Tech    struct lsquic_bbr *const bbr = cong_ctl;
3385392f7a3SLiteSpeed Tech    struct bw_sample *sample;
3395392f7a3SLiteSpeed Tech
3405392f7a3SLiteSpeed Tech    assert(bbr->bbr_flags & BBR_FLAG_IN_ACK);
3415392f7a3SLiteSpeed Tech
3425392f7a3SLiteSpeed Tech    sample = lsquic_bw_sampler_packet_acked(&bbr->bbr_bw_sampler, packet_out,
3435392f7a3SLiteSpeed Tech                                                bbr->bbr_ack_state.ack_time);
3445392f7a3SLiteSpeed Tech    if (sample)
3455392f7a3SLiteSpeed Tech        TAILQ_INSERT_TAIL(&bbr->bbr_ack_state.samples, sample, next);
3465392f7a3SLiteSpeed Tech
3475392f7a3SLiteSpeed Tech    if (is_valid_packno(bbr->bbr_ack_state.max_packno))
3485392f7a3SLiteSpeed Tech        /* We assume packet numbers are ordered */
3495392f7a3SLiteSpeed Tech        assert(packet_out->po_packno > bbr->bbr_ack_state.max_packno);
3505392f7a3SLiteSpeed Tech    bbr->bbr_ack_state.max_packno = packet_out->po_packno;
3515392f7a3SLiteSpeed Tech    bbr->bbr_ack_state.acked_bytes += packet_sz;
3525392f7a3SLiteSpeed Tech}
3535392f7a3SLiteSpeed Tech
3545392f7a3SLiteSpeed Tech
3555392f7a3SLiteSpeed Techstatic void
3565392f7a3SLiteSpeed Techlsquic_bbr_sent (void *cong_ctl, struct lsquic_packet_out *packet_out,
357cca25415SDmitri Tikhonov                                        uint64_t in_flight, int app_limited)
3585392f7a3SLiteSpeed Tech{
3595392f7a3SLiteSpeed Tech    struct lsquic_bbr *const bbr = cong_ctl;
3605392f7a3SLiteSpeed Tech
3615392f7a3SLiteSpeed Tech    if (!(packet_out->po_flags & PO_MINI))
3625392f7a3SLiteSpeed Tech        lsquic_bw_sampler_packet_sent(&bbr->bbr_bw_sampler, packet_out,
3635392f7a3SLiteSpeed Tech                                                                in_flight);
3645392f7a3SLiteSpeed Tech
3655392f7a3SLiteSpeed Tech    /* Obviously we make an assumption that sent packet number are always
3665392f7a3SLiteSpeed Tech     * increasing.
3675392f7a3SLiteSpeed Tech     */
3685392f7a3SLiteSpeed Tech    bbr->bbr_last_sent_packno = packet_out->po_packno;
369cca25415SDmitri Tikhonov
370cca25415SDmitri Tikhonov    if (app_limited)
371cca25415SDmitri Tikhonov        bbr_app_limited(bbr, in_flight);
3725392f7a3SLiteSpeed Tech}
3735392f7a3SLiteSpeed Tech
3745392f7a3SLiteSpeed Tech
3755392f7a3SLiteSpeed Techstatic void
3765392f7a3SLiteSpeed Techlsquic_bbr_lost (void *cong_ctl, struct lsquic_packet_out *packet_out,
3775392f7a3SLiteSpeed Tech                                                        unsigned packet_sz)
3785392f7a3SLiteSpeed Tech{
3795392f7a3SLiteSpeed Tech    struct lsquic_bbr *const bbr = cong_ctl;
3805392f7a3SLiteSpeed Tech
3815392f7a3SLiteSpeed Tech    lsquic_bw_sampler_packet_lost(&bbr->bbr_bw_sampler, packet_out);
3825392f7a3SLiteSpeed Tech    bbr->bbr_ack_state.has_losses = 1;
3835392f7a3SLiteSpeed Tech    bbr->bbr_ack_state.lost_bytes += packet_sz;
3845392f7a3SLiteSpeed Tech}
3855392f7a3SLiteSpeed Tech
3865392f7a3SLiteSpeed Tech
3875392f7a3SLiteSpeed Techstatic void
3885392f7a3SLiteSpeed Techlsquic_bbr_begin_ack (void *cong_ctl, lsquic_time_t ack_time, uint64_t in_flight)
3895392f7a3SLiteSpeed Tech{
3905392f7a3SLiteSpeed Tech    struct lsquic_bbr *const bbr = cong_ctl;
3915392f7a3SLiteSpeed Tech
3925392f7a3SLiteSpeed Tech    assert(!(bbr->bbr_flags & BBR_FLAG_IN_ACK));
3935392f7a3SLiteSpeed Tech    bbr->bbr_flags |= BBR_FLAG_IN_ACK;
3945392f7a3SLiteSpeed Tech    memset(&bbr->bbr_ack_state, 0, sizeof(bbr->bbr_ack_state));
3955392f7a3SLiteSpeed Tech    TAILQ_INIT(&bbr->bbr_ack_state.samples);
3965392f7a3SLiteSpeed Tech    bbr->bbr_ack_state.ack_time = ack_time;
3975392f7a3SLiteSpeed Tech    bbr->bbr_ack_state.max_packno = UINT64_MAX;
3985392f7a3SLiteSpeed Tech    bbr->bbr_ack_state.in_flight = in_flight;
3995392f7a3SLiteSpeed Tech    bbr->bbr_ack_state.total_bytes_acked_before
4005392f7a3SLiteSpeed Tech                        = lsquic_bw_sampler_total_acked(&bbr->bbr_bw_sampler);
4015392f7a3SLiteSpeed Tech}
4025392f7a3SLiteSpeed Tech
4035392f7a3SLiteSpeed Tech
4045392f7a3SLiteSpeed Tech/* Based on BbrSender::ShouldExtendMinRttExpiry() */
4055392f7a3SLiteSpeed Techstatic int
4065392f7a3SLiteSpeed Techshould_extend_min_rtt_expiry (const struct lsquic_bbr *bbr)
4075392f7a3SLiteSpeed Tech{
4085392f7a3SLiteSpeed Tech    int increased_since_last_probe;
4095392f7a3SLiteSpeed Tech
4105392f7a3SLiteSpeed Tech    if ((bbr->bbr_flags & (BBR_FLAG_APP_LIMITED_SINCE_LAST_PROBE_RTT
4115392f7a3SLiteSpeed Tech                          |BBR_FLAG_PROBE_RTT_DISABLED_IF_APP_LIMITED))
4125392f7a3SLiteSpeed Tech            == (BBR_FLAG_APP_LIMITED_SINCE_LAST_PROBE_RTT
4135392f7a3SLiteSpeed Tech               |BBR_FLAG_PROBE_RTT_DISABLED_IF_APP_LIMITED))
4145392f7a3SLiteSpeed Tech        // Extend the current min_rtt if we've been app limited recently.
4155392f7a3SLiteSpeed Tech        return 1;
4165392f7a3SLiteSpeed Tech
4175392f7a3SLiteSpeed Tech    increased_since_last_probe = bbr->bbr_min_rtt_since_last_probe
4185392f7a3SLiteSpeed Tech                                > bbr->bbr_min_rtt * kSimilarMinRttThreshold;
4195392f7a3SLiteSpeed Tech    if ((bbr->bbr_flags & (BBR_FLAG_APP_LIMITED_SINCE_LAST_PROBE_RTT
4205392f7a3SLiteSpeed Tech                          |BBR_FLAG_PROBE_RTT_SKIPPED_IF_SIMILAR_RTT))
4215392f7a3SLiteSpeed Tech            == (BBR_FLAG_APP_LIMITED_SINCE_LAST_PROBE_RTT
4225392f7a3SLiteSpeed Tech               |BBR_FLAG_PROBE_RTT_SKIPPED_IF_SIMILAR_RTT)
4235392f7a3SLiteSpeed Tech            && !increased_since_last_probe)
4245392f7a3SLiteSpeed Tech        // Extend the current min_rtt if we've been app limited recently and an
4255392f7a3SLiteSpeed Tech        // rtt has been measured in that time that's less than 12.5% more than
4265392f7a3SLiteSpeed Tech        // the current min_rtt.
4275392f7a3SLiteSpeed Tech        return 1;
4285392f7a3SLiteSpeed Tech
4295392f7a3SLiteSpeed Tech    return 0;
4305392f7a3SLiteSpeed Tech}
4315392f7a3SLiteSpeed Tech
4325392f7a3SLiteSpeed Tech
4335392f7a3SLiteSpeed Tech/* Based on BbrSender::UpdateBandwidthAndMinRtt */
4345392f7a3SLiteSpeed Tech/* Returns true if min RTT expired, false otherwise */
4355392f7a3SLiteSpeed Techstatic int
4365392f7a3SLiteSpeed Techupdate_bandwidth_and_min_rtt (struct lsquic_bbr *bbr)
4375392f7a3SLiteSpeed Tech{
4385392f7a3SLiteSpeed Tech    struct bw_sample *sample, *next_sample;
4395392f7a3SLiteSpeed Tech    uint64_t sample_min_rtt;
4405392f7a3SLiteSpeed Tech    int min_rtt_expired;
4415392f7a3SLiteSpeed Tech
4425392f7a3SLiteSpeed Tech    sample_min_rtt = UINT64_MAX;
4435392f7a3SLiteSpeed Tech    for (sample = TAILQ_FIRST(&bbr->bbr_ack_state.samples); sample;
4445392f7a3SLiteSpeed Tech                                                        sample = next_sample)
4455392f7a3SLiteSpeed Tech    {
4465392f7a3SLiteSpeed Tech        next_sample = TAILQ_NEXT(sample, next);
4475392f7a3SLiteSpeed Tech
4485392f7a3SLiteSpeed Tech        if (sample->is_app_limited)
4495392f7a3SLiteSpeed Tech            bbr->bbr_flags |= BBR_FLAG_LAST_SAMPLE_APP_LIMITED;
4505392f7a3SLiteSpeed Tech        else
4515392f7a3SLiteSpeed Tech        {
4525392f7a3SLiteSpeed Tech            bbr->bbr_flags &= ~BBR_FLAG_LAST_SAMPLE_APP_LIMITED;
4535392f7a3SLiteSpeed Tech            bbr->bbr_flags |=  BBR_FLAG_HAS_NON_APP_LIMITED;
4545392f7a3SLiteSpeed Tech        }
4555392f7a3SLiteSpeed Tech
4565392f7a3SLiteSpeed Tech        if (sample_min_rtt == UINT64_MAX || sample->rtt < sample_min_rtt)
4575392f7a3SLiteSpeed Tech            sample_min_rtt = sample->rtt;
4585392f7a3SLiteSpeed Tech
4595392f7a3SLiteSpeed Tech        if (!sample->is_app_limited
4605392f7a3SLiteSpeed Tech                    || BW_VALUE(&sample->bandwidth)
4615392f7a3SLiteSpeed Tech                                    > minmax_get(&bbr->bbr_max_bandwidth))
4625392f7a3SLiteSpeed Tech            minmax_upmax(&bbr->bbr_max_bandwidth, bbr->bbr_round_count,
4635392f7a3SLiteSpeed Tech                                                BW_VALUE(&sample->bandwidth));
4645392f7a3SLiteSpeed Tech
4655392f7a3SLiteSpeed Tech        lsquic_malo_put(sample);
4665392f7a3SLiteSpeed Tech    }
4675392f7a3SLiteSpeed Tech
4685392f7a3SLiteSpeed Tech    if (sample_min_rtt == UINT64_MAX)
4695392f7a3SLiteSpeed Tech        return 0;
4705392f7a3SLiteSpeed Tech
4715392f7a3SLiteSpeed Tech    bbr->bbr_min_rtt_since_last_probe
4725392f7a3SLiteSpeed Tech                    = MIN(bbr->bbr_min_rtt_since_last_probe, sample_min_rtt);
4735392f7a3SLiteSpeed Tech
4745392f7a3SLiteSpeed Tech    min_rtt_expired = bbr->bbr_min_rtt != 0 && (bbr->bbr_ack_state.ack_time
4755392f7a3SLiteSpeed Tech                                > bbr->bbr_min_rtt_timestamp + kMinRttExpiry);
4765392f7a3SLiteSpeed Tech    if (min_rtt_expired || sample_min_rtt < bbr->bbr_min_rtt
4775392f7a3SLiteSpeed Tech                                                    || 0 == bbr->bbr_min_rtt)
4785392f7a3SLiteSpeed Tech    {
4795392f7a3SLiteSpeed Tech        if (min_rtt_expired && should_extend_min_rtt_expiry(bbr))
4805392f7a3SLiteSpeed Tech        {
4815392f7a3SLiteSpeed Tech            LSQ_DEBUG("min rtt expiration extended, stay at: %"PRIu64,
4825392f7a3SLiteSpeed Tech                bbr->bbr_min_rtt);
4835392f7a3SLiteSpeed Tech            min_rtt_expired = 0;
4845392f7a3SLiteSpeed Tech        }
4855392f7a3SLiteSpeed Tech        else
4865392f7a3SLiteSpeed Tech        {
4875392f7a3SLiteSpeed Tech            LSQ_DEBUG("min rtt updated: %"PRIu64" -> %"PRIu64,
4885392f7a3SLiteSpeed Tech                bbr->bbr_min_rtt, sample_min_rtt);
4895392f7a3SLiteSpeed Tech            bbr->bbr_min_rtt = sample_min_rtt;
4905392f7a3SLiteSpeed Tech        }
4915392f7a3SLiteSpeed Tech        bbr->bbr_min_rtt_timestamp = bbr->bbr_ack_state.ack_time;
4925392f7a3SLiteSpeed Tech        bbr->bbr_min_rtt_since_last_probe = UINT64_MAX;
4935392f7a3SLiteSpeed Tech        bbr->bbr_flags &= ~BBR_FLAG_APP_LIMITED_SINCE_LAST_PROBE_RTT;
4945392f7a3SLiteSpeed Tech    }
4955392f7a3SLiteSpeed Tech
4965392f7a3SLiteSpeed Tech    return min_rtt_expired;
4975392f7a3SLiteSpeed Tech}
4985392f7a3SLiteSpeed Tech
4995392f7a3SLiteSpeed Tech
5005392f7a3SLiteSpeed Tech/* Based on BbrSender::UpdateRecoveryState() */
5015392f7a3SLiteSpeed Techstatic void
5025392f7a3SLiteSpeed Techupdate_recovery_state (struct lsquic_bbr *bbr, int is_round_start)
5035392f7a3SLiteSpeed Tech{
5045392f7a3SLiteSpeed Tech    // Exit recovery when there are no losses for a round.
5055392f7a3SLiteSpeed Tech    if (bbr->bbr_ack_state.has_losses)
5065392f7a3SLiteSpeed Tech        bbr->bbr_end_recovery_at = bbr->bbr_last_sent_packno;
5075392f7a3SLiteSpeed Tech
5085392f7a3SLiteSpeed Tech    switch (bbr->bbr_recovery_state)
5095392f7a3SLiteSpeed Tech    {
5105392f7a3SLiteSpeed Tech    case BBR_RS_NOT_IN_RECOVERY:
5115392f7a3SLiteSpeed Tech        // Enter conservation on the first loss.
5125392f7a3SLiteSpeed Tech        if (bbr->bbr_ack_state.has_losses)
5135392f7a3SLiteSpeed Tech        {
5145392f7a3SLiteSpeed Tech            bbr->bbr_recovery_state = BBR_RS_CONSERVATION;
5155392f7a3SLiteSpeed Tech            // This will cause the |bbr_recovery_window| to be set to the
5165392f7a3SLiteSpeed Tech            // correct value in CalculateRecoveryWindow().
5175392f7a3SLiteSpeed Tech            bbr->bbr_recovery_window = 0;
5185392f7a3SLiteSpeed Tech            // Since the conservation phase is meant to be lasting for a whole
5195392f7a3SLiteSpeed Tech            // round, extend the current round as if it were started right now.
5205392f7a3SLiteSpeed Tech            bbr->bbr_current_round_trip_end = bbr->bbr_last_sent_packno;
5215392f7a3SLiteSpeed Tech        }
5225392f7a3SLiteSpeed Tech        break;
5235392f7a3SLiteSpeed Tech    case BBR_RS_CONSERVATION:
5245392f7a3SLiteSpeed Tech        if (is_round_start)
5255392f7a3SLiteSpeed Tech            bbr->bbr_recovery_state = BBR_RS_GROWTH;
5265392f7a3SLiteSpeed Tech        /* Fall-through */
5275392f7a3SLiteSpeed Tech    case BBR_RS_GROWTH:
5285392f7a3SLiteSpeed Tech        // Exit recovery if appropriate.
5295392f7a3SLiteSpeed Tech        if (!bbr->bbr_ack_state.has_losses
5305392f7a3SLiteSpeed Tech                && bbr->bbr_ack_state.max_packno > bbr->bbr_end_recovery_at)
5315392f7a3SLiteSpeed Tech            bbr->bbr_recovery_state = BBR_RS_NOT_IN_RECOVERY;
5325392f7a3SLiteSpeed Tech        break;
5335392f7a3SLiteSpeed Tech    }
5345392f7a3SLiteSpeed Tech}
5355392f7a3SLiteSpeed Tech
5365392f7a3SLiteSpeed Tech
5375392f7a3SLiteSpeed Techstatic uint64_t
5385392f7a3SLiteSpeed Techupdate_ack_aggregation_bytes (struct lsquic_bbr *bbr,
5395392f7a3SLiteSpeed Tech                                                uint64_t newly_acked_bytes)
5405392f7a3SLiteSpeed Tech{
5415392f7a3SLiteSpeed Tech    const lsquic_time_t ack_time = bbr->bbr_ack_state.ack_time;
5425392f7a3SLiteSpeed Tech    uint64_t expected_bytes_acked, diff;
5435392f7a3SLiteSpeed Tech
5445392f7a3SLiteSpeed Tech    // Compute how many bytes are expected to be delivered, assuming max
5455392f7a3SLiteSpeed Tech    // bandwidth is correct.
5465392f7a3SLiteSpeed Tech    expected_bytes_acked = minmax_get(&bbr->bbr_max_bandwidth)
5475392f7a3SLiteSpeed Tech                        * (ack_time - bbr->bbr_aggregation_epoch_start_time);
5485392f7a3SLiteSpeed Tech
5495392f7a3SLiteSpeed Tech    // Reset the current aggregation epoch as soon as the ack arrival rate is
5505392f7a3SLiteSpeed Tech    // less than or equal to the max bandwidth.
5515392f7a3SLiteSpeed Tech    if (bbr->bbr_aggregation_epoch_bytes <= expected_bytes_acked)
5525392f7a3SLiteSpeed Tech    {
5535392f7a3SLiteSpeed Tech        // Reset to start measuring a new aggregation epoch.
5545392f7a3SLiteSpeed Tech        bbr->bbr_aggregation_epoch_bytes = newly_acked_bytes;
5555392f7a3SLiteSpeed Tech        bbr->bbr_aggregation_epoch_start_time = ack_time;
5565392f7a3SLiteSpeed Tech        return 0;
5575392f7a3SLiteSpeed Tech    }
5585392f7a3SLiteSpeed Tech
5595392f7a3SLiteSpeed Tech    // Compute how many extra bytes were delivered vs max bandwidth.
5605392f7a3SLiteSpeed Tech    // Include the bytes most recently acknowledged to account for stretch acks.
5615392f7a3SLiteSpeed Tech    bbr->bbr_aggregation_epoch_bytes += newly_acked_bytes;
5625392f7a3SLiteSpeed Tech    diff = bbr->bbr_aggregation_epoch_bytes - expected_bytes_acked;
5635392f7a3SLiteSpeed Tech    minmax_upmax(&bbr->bbr_max_ack_height, bbr->bbr_round_count, diff);
5645392f7a3SLiteSpeed Tech    return diff;
5655392f7a3SLiteSpeed Tech}
5665392f7a3SLiteSpeed Tech
5675392f7a3SLiteSpeed Tech
5685392f7a3SLiteSpeed Tech/* See BbrSender::UpdateGainCyclePhase() */
5695392f7a3SLiteSpeed Techstatic void
5705392f7a3SLiteSpeed Techupdate_gain_cycle_phase (struct lsquic_bbr *bbr, uint64_t bytes_in_flight)
5715392f7a3SLiteSpeed Tech{
5725392f7a3SLiteSpeed Tech    const uint64_t prior_in_flight = bbr->bbr_ack_state.in_flight;
5735392f7a3SLiteSpeed Tech    const lsquic_time_t now = bbr->bbr_ack_state.ack_time;
5745392f7a3SLiteSpeed Tech    // In most cases, the cycle is advanced after an RTT passes.
5755392f7a3SLiteSpeed Tech    int should_advance_gain_cycling
5765392f7a3SLiteSpeed Tech        = now - bbr->bbr_last_cycle_start > get_min_rtt(bbr);
5775392f7a3SLiteSpeed Tech
5785392f7a3SLiteSpeed Tech    // If the pacing gain is above 1.0, the connection is trying to probe the
5795392f7a3SLiteSpeed Tech    // bandwidth by increasing the number of bytes in flight to at least
5805392f7a3SLiteSpeed Tech    // pacing_gain * BDP.  Make sure that it actually reaches the target, as
5815392f7a3SLiteSpeed Tech    // long as there are no losses suggesting that the buffers are not able to
5825392f7a3SLiteSpeed Tech    // hold that much.
5835392f7a3SLiteSpeed Tech    if (bbr->bbr_pacing_gain > 1.0
5845392f7a3SLiteSpeed Tech            && !bbr->bbr_ack_state.has_losses
5855392f7a3SLiteSpeed Tech            && prior_in_flight < get_target_cwnd(bbr, bbr->bbr_pacing_gain))
5865392f7a3SLiteSpeed Tech        should_advance_gain_cycling = 0;
5875392f7a3SLiteSpeed Tech
5885392f7a3SLiteSpeed Tech    /* Several optimizations are possible here: "else if" instead of "if", as
5895392f7a3SLiteSpeed Tech     * well as not calling get_target_cwnd() if `should_advance_gain_cycling'
5905392f7a3SLiteSpeed Tech     * is already set to the target value.
5915392f7a3SLiteSpeed Tech     */
5925392f7a3SLiteSpeed Tech
5935392f7a3SLiteSpeed Tech    // If pacing gain is below 1.0, the connection is trying to drain the extra
5945392f7a3SLiteSpeed Tech    // queue which could have been incurred by probing prior to it.  If the
5955392f7a3SLiteSpeed Tech    // number of bytes in flight falls down to the estimated BDP value earlier,
5965392f7a3SLiteSpeed Tech    // conclude that the queue has been successfully drained and exit this cycle
5975392f7a3SLiteSpeed Tech    // early.
5985392f7a3SLiteSpeed Tech    if (bbr->bbr_pacing_gain < 1.0
5995392f7a3SLiteSpeed Tech                                && bytes_in_flight <= get_target_cwnd(bbr, 1))
6005392f7a3SLiteSpeed Tech        should_advance_gain_cycling = 1;
6015392f7a3SLiteSpeed Tech
6025392f7a3SLiteSpeed Tech    if (should_advance_gain_cycling)
6035392f7a3SLiteSpeed Tech    {
6045392f7a3SLiteSpeed Tech        bbr->bbr_cycle_current_offset =
6055392f7a3SLiteSpeed Tech                        (bbr->bbr_cycle_current_offset + 1) % kGainCycleLength;
6065392f7a3SLiteSpeed Tech        bbr->bbr_last_cycle_start = now;
6075392f7a3SLiteSpeed Tech        // Stay in low gain mode until the target BDP is hit.  Low gain mode
6085392f7a3SLiteSpeed Tech        // will be exited immediately when the target BDP is achieved.
6095392f7a3SLiteSpeed Tech        if ((bbr->bbr_flags & BBR_FLAG_DRAIN_TO_TARGET)
6105392f7a3SLiteSpeed Tech                && bbr->bbr_pacing_gain < 1
6115392f7a3SLiteSpeed Tech                && kPacingGain[bbr->bbr_cycle_current_offset] == 1
6125392f7a3SLiteSpeed Tech                && bytes_in_flight > get_target_cwnd(bbr, 1))
6135392f7a3SLiteSpeed Tech              return;
6145392f7a3SLiteSpeed Tech        bbr->bbr_pacing_gain = kPacingGain[bbr->bbr_cycle_current_offset];
6155392f7a3SLiteSpeed Tech        LSQ_DEBUG("advanced gain cycle, pacing gain set to %.2f",
6165392f7a3SLiteSpeed Tech                                                        bbr->bbr_pacing_gain);
6175392f7a3SLiteSpeed Tech    }
6185392f7a3SLiteSpeed Tech}
6195392f7a3SLiteSpeed Tech
6205392f7a3SLiteSpeed Tech
6215392f7a3SLiteSpeed Tech/* BbrSender::InRecovery() */
6225392f7a3SLiteSpeed Techstatic int
6235392f7a3SLiteSpeed Techin_recovery (const struct lsquic_bbr *bbr)
6245392f7a3SLiteSpeed Tech{
6255392f7a3SLiteSpeed Tech    return bbr->bbr_recovery_state != BBR_RS_NOT_IN_RECOVERY;
6265392f7a3SLiteSpeed Tech}
6275392f7a3SLiteSpeed Tech
6285392f7a3SLiteSpeed Tech
6295392f7a3SLiteSpeed Tech/* See BbrSender::CheckIfFullBandwidthReached() */
6305392f7a3SLiteSpeed Techstatic void
6315392f7a3SLiteSpeed Techcheck_if_full_bw_reached (struct lsquic_bbr *bbr)
6325392f7a3SLiteSpeed Tech{
6335392f7a3SLiteSpeed Tech    struct bandwidth target, bw;
6345392f7a3SLiteSpeed Tech
6355392f7a3SLiteSpeed Tech    if (bbr->bbr_flags & BBR_FLAG_LAST_SAMPLE_APP_LIMITED)
6365392f7a3SLiteSpeed Tech    {
6375392f7a3SLiteSpeed Tech        LSQ_DEBUG("last sample app limited: full BW not reached");
6385392f7a3SLiteSpeed Tech        return;
6395392f7a3SLiteSpeed Tech    }
6405392f7a3SLiteSpeed Tech
6415392f7a3SLiteSpeed Tech    target = BW_TIMES(&bbr->bbr_bw_at_last_round, kStartupGrowthTarget);
6425392f7a3SLiteSpeed Tech    bw = BW(minmax_get(&bbr->bbr_max_bandwidth));
6435392f7a3SLiteSpeed Tech    if (BW_VALUE(&bw) >= BW_VALUE(&target))
6445392f7a3SLiteSpeed Tech    {
6455392f7a3SLiteSpeed Tech        bbr->bbr_bw_at_last_round = bw;
6465392f7a3SLiteSpeed Tech        bbr->bbr_round_wo_bw_gain = 0;
6475392f7a3SLiteSpeed Tech        if (bbr->bbr_flags & BBR_FLAG_EXPIRE_ACK_AGG_IN_STARTUP)
6485392f7a3SLiteSpeed Tech            // Expire old excess delivery measurements now that bandwidth
6495392f7a3SLiteSpeed Tech            // increased.
6505392f7a3SLiteSpeed Tech            minmax_reset(&bbr->bbr_max_ack_height,
6515392f7a3SLiteSpeed Tech                        ((struct minmax_sample) { bbr->bbr_round_count, 0, }));
6525392f7a3SLiteSpeed Tech        LSQ_DEBUG("BW estimate %"PRIu64"bps greater than or equal to target "
6535392f7a3SLiteSpeed Tech            "%"PRIu64"bps: full BW not reached",
6545392f7a3SLiteSpeed Tech            BW_VALUE(&bw), BW_VALUE(&target));
6555392f7a3SLiteSpeed Tech        return;
6565392f7a3SLiteSpeed Tech    }
6575392f7a3SLiteSpeed Tech
6585392f7a3SLiteSpeed Tech    ++bbr->bbr_round_wo_bw_gain;
6595392f7a3SLiteSpeed Tech    if ((bbr->bbr_round_wo_bw_gain >= bbr->bbr_num_startup_rtts)
6605392f7a3SLiteSpeed Tech            || ((bbr->bbr_flags & BBR_FLAG_EXIT_STARTUP_ON_LOSS)
6615392f7a3SLiteSpeed Tech                                                    && in_recovery(bbr)))
6625392f7a3SLiteSpeed Tech    {
6635392f7a3SLiteSpeed Tech        assert(bbr->bbr_flags & BBR_FLAG_HAS_NON_APP_LIMITED);  /* DCHECK */
6645392f7a3SLiteSpeed Tech        bbr->bbr_flags |= BBR_FLAG_IS_AT_FULL_BANDWIDTH;
6655392f7a3SLiteSpeed Tech        LSQ_DEBUG("reached full BW");
6665392f7a3SLiteSpeed Tech    }
6675392f7a3SLiteSpeed Tech    else
6685392f7a3SLiteSpeed Tech        LSQ_DEBUG("rounds w/o gain: %u, full BW not reached",
6695392f7a3SLiteSpeed Tech                                                bbr->bbr_round_wo_bw_gain);
6705392f7a3SLiteSpeed Tech}
6715392f7a3SLiteSpeed Tech
6725392f7a3SLiteSpeed Tech
6735392f7a3SLiteSpeed Tech/* See BbrSender::OnExitStartup */
6745392f7a3SLiteSpeed Techstatic void
6755392f7a3SLiteSpeed Techon_exit_startup (struct lsquic_bbr *bbr, lsquic_time_t now)
6765392f7a3SLiteSpeed Tech{
6775392f7a3SLiteSpeed Tech    assert(bbr->bbr_mode == BBR_MODE_STARTUP);
6785392f7a3SLiteSpeed Tech    /* Apparently this method is just to update stats, something that we
6795392f7a3SLiteSpeed Tech     * don't do yet.
6805392f7a3SLiteSpeed Tech     */
6815392f7a3SLiteSpeed Tech}
6825392f7a3SLiteSpeed Tech
6835392f7a3SLiteSpeed Tech
6845392f7a3SLiteSpeed Tech/* See BbrSender::EnterProbeBandwidthMode */
6855392f7a3SLiteSpeed Techstatic void
6865392f7a3SLiteSpeed Techenter_probe_bw_mode (struct lsquic_bbr *bbr, lsquic_time_t now)
6875392f7a3SLiteSpeed Tech{
68810c41073SDmitri Tikhonov    uint8_t rand;
68910c41073SDmitri Tikhonov
6905392f7a3SLiteSpeed Tech    set_mode(bbr, BBR_MODE_PROBE_BW);
6915392f7a3SLiteSpeed Tech    bbr->bbr_cwnd_gain = kCwndGain;
6925392f7a3SLiteSpeed Tech
6935392f7a3SLiteSpeed Tech    // Pick a random offset for the gain cycle out of {0, 2..7} range. 1 is
6945392f7a3SLiteSpeed Tech    // excluded because in that case increased gain and decreased gain would not
6955392f7a3SLiteSpeed Tech    // follow each other.
69610c41073SDmitri Tikhonov    rand = lsquic_crand_get_byte(bbr->bbr_conn_pub->enpub->enp_crand);
69710c41073SDmitri Tikhonov    bbr->bbr_cycle_current_offset = rand % (kGainCycleLength - 1);
6985392f7a3SLiteSpeed Tech    if (bbr->bbr_cycle_current_offset >= 1)
6995392f7a3SLiteSpeed Tech        ++bbr->bbr_cycle_current_offset;
7005392f7a3SLiteSpeed Tech
7015392f7a3SLiteSpeed Tech    bbr->bbr_last_cycle_start = now;
7025392f7a3SLiteSpeed Tech    bbr->bbr_pacing_gain = kPacingGain[bbr->bbr_cycle_current_offset];
7035392f7a3SLiteSpeed Tech}
7045392f7a3SLiteSpeed Tech
7055392f7a3SLiteSpeed Tech
7065392f7a3SLiteSpeed Tech/* See BbrSender::EnterStartupMode */
7075392f7a3SLiteSpeed Techstatic void
7085392f7a3SLiteSpeed Techenter_startup_mode (struct lsquic_bbr *bbr, lsquic_time_t now)
7095392f7a3SLiteSpeed Tech{
7105392f7a3SLiteSpeed Tech    set_mode(bbr, BBR_MODE_STARTUP);
7115392f7a3SLiteSpeed Tech    set_startup_values(bbr);
7125392f7a3SLiteSpeed Tech}
7135392f7a3SLiteSpeed Tech
7145392f7a3SLiteSpeed Tech
7155392f7a3SLiteSpeed Tech/* See  BbrSender::MaybeExitStartupOrDrain() */
7165392f7a3SLiteSpeed Techstatic void
7175392f7a3SLiteSpeed Techmaybe_exit_startup_or_drain (struct lsquic_bbr *bbr, lsquic_time_t now,
7185392f7a3SLiteSpeed Tech                                                    uint64_t bytes_in_flight)
7195392f7a3SLiteSpeed Tech{
7205392f7a3SLiteSpeed Tech    uint64_t target_cwnd;
7215392f7a3SLiteSpeed Tech
7225392f7a3SLiteSpeed Tech    if (bbr->bbr_mode == BBR_MODE_STARTUP
7235392f7a3SLiteSpeed Tech                        && (bbr->bbr_flags & BBR_FLAG_IS_AT_FULL_BANDWIDTH))
7245392f7a3SLiteSpeed Tech    {
7255392f7a3SLiteSpeed Tech        on_exit_startup(bbr, now);
7265392f7a3SLiteSpeed Tech        set_mode(bbr, BBR_MODE_DRAIN);
7275392f7a3SLiteSpeed Tech        bbr->bbr_pacing_gain = bbr->bbr_drain_gain;
7285392f7a3SLiteSpeed Tech        bbr->bbr_cwnd_gain = bbr->bbr_high_cwnd_gain;
7295392f7a3SLiteSpeed Tech    }
7305392f7a3SLiteSpeed Tech
7315392f7a3SLiteSpeed Tech    if (bbr->bbr_mode == BBR_MODE_DRAIN)
7325392f7a3SLiteSpeed Tech    {
7335392f7a3SLiteSpeed Tech        target_cwnd = get_target_cwnd(bbr, 1);
7345392f7a3SLiteSpeed Tech        LSQ_DEBUG("%s: bytes in flight: %"PRIu64"; target cwnd: %"PRIu64,
7355392f7a3SLiteSpeed Tech                                    __func__, bytes_in_flight, target_cwnd);
7365392f7a3SLiteSpeed Tech        if (bytes_in_flight <= target_cwnd)
7375392f7a3SLiteSpeed Tech            enter_probe_bw_mode(bbr, now);
7385392f7a3SLiteSpeed Tech    }
7395392f7a3SLiteSpeed Tech}
7405392f7a3SLiteSpeed Tech
7415392f7a3SLiteSpeed Tech
7425392f7a3SLiteSpeed Techstatic int
7435392f7a3SLiteSpeed Techin_slow_start (const struct lsquic_bbr *bbr)
7445392f7a3SLiteSpeed Tech{
7455392f7a3SLiteSpeed Tech    return bbr->bbr_mode == BBR_MODE_STARTUP;
7465392f7a3SLiteSpeed Tech}
7475392f7a3SLiteSpeed Tech
7485392f7a3SLiteSpeed Tech
7495392f7a3SLiteSpeed Tech/* See QuicByteCount BbrSender::ProbeRttCongestionWindow() */
7505392f7a3SLiteSpeed Techstatic uint64_t
7515392f7a3SLiteSpeed Techget_probe_rtt_cwnd (const struct lsquic_bbr *bbr)
7525392f7a3SLiteSpeed Tech{
7535392f7a3SLiteSpeed Tech    if (bbr->bbr_flags & BBR_FLAG_PROBE_RTT_BASED_ON_BDP)
7545392f7a3SLiteSpeed Tech        return get_target_cwnd(bbr, kModerateProbeRttMultiplier);
7555392f7a3SLiteSpeed Tech    else
7565392f7a3SLiteSpeed Tech        return bbr->bbr_min_cwnd;
7575392f7a3SLiteSpeed Tech}
7585392f7a3SLiteSpeed Tech
7595392f7a3SLiteSpeed Tech
7605392f7a3SLiteSpeed Techstatic uint64_t
7615392f7a3SLiteSpeed Techlsquic_bbr_get_cwnd (void *cong_ctl)
7625392f7a3SLiteSpeed Tech{
7635392f7a3SLiteSpeed Tech    struct lsquic_bbr *const bbr = cong_ctl;
7645392f7a3SLiteSpeed Tech    uint64_t cwnd;
7655392f7a3SLiteSpeed Tech
7665392f7a3SLiteSpeed Tech    if (bbr->bbr_mode == BBR_MODE_PROBE_RTT)
7675392f7a3SLiteSpeed Tech        cwnd = get_probe_rtt_cwnd(bbr);
7685392f7a3SLiteSpeed Tech    else if (in_recovery(bbr) &&
7695392f7a3SLiteSpeed Tech                !((bbr->bbr_flags & BBR_FLAG_RATE_BASED_STARTUP)
7705392f7a3SLiteSpeed Tech                                    && bbr->bbr_mode == BBR_MODE_STARTUP))
7715392f7a3SLiteSpeed Tech        cwnd = MIN(bbr->bbr_cwnd, bbr->bbr_recovery_window);
7725392f7a3SLiteSpeed Tech    else
7735392f7a3SLiteSpeed Tech        cwnd = bbr->bbr_cwnd;
7745392f7a3SLiteSpeed Tech
7755392f7a3SLiteSpeed Tech    return cwnd;
7765392f7a3SLiteSpeed Tech}
7775392f7a3SLiteSpeed Tech
7785392f7a3SLiteSpeed Tech
7795392f7a3SLiteSpeed Tech/* See BbrSender::MaybeEnterOrExitProbeRtt */
7805392f7a3SLiteSpeed Techstatic void
7815392f7a3SLiteSpeed Techmaybe_enter_or_exit_probe_rtt (struct lsquic_bbr *bbr, lsquic_time_t now,
7825392f7a3SLiteSpeed Tech            int is_round_start, int min_rtt_expired, uint64_t bytes_in_flight)
7835392f7a3SLiteSpeed Tech{
7845392f7a3SLiteSpeed Tech    if (min_rtt_expired
7855392f7a3SLiteSpeed Tech            && !(bbr->bbr_flags & BBR_FLAG_EXITING_QUIESCENCE)
7865392f7a3SLiteSpeed Tech                && bbr->bbr_mode != BBR_MODE_PROBE_RTT)
7875392f7a3SLiteSpeed Tech    {
7885392f7a3SLiteSpeed Tech        if (in_slow_start(bbr))
7895392f7a3SLiteSpeed Tech            on_exit_startup(bbr, now);
7905392f7a3SLiteSpeed Tech        set_mode(bbr, BBR_MODE_PROBE_RTT);
7915392f7a3SLiteSpeed Tech        bbr->bbr_pacing_gain = 1;
7925392f7a3SLiteSpeed Tech        // Do not decide on the time to exit PROBE_RTT until the
7935392f7a3SLiteSpeed Tech        // |bytes_in_flight| is at the target small value.
7945392f7a3SLiteSpeed Tech        bbr->bbr_exit_probe_rtt_at = 0;
7955392f7a3SLiteSpeed Tech    }
7965392f7a3SLiteSpeed Tech
7975392f7a3SLiteSpeed Tech    if (bbr->bbr_mode == BBR_MODE_PROBE_RTT)
7985392f7a3SLiteSpeed Tech    {
7995392f7a3SLiteSpeed Tech        lsquic_bw_sampler_app_limited(&bbr->bbr_bw_sampler);
8005392f7a3SLiteSpeed Tech        LSQ_DEBUG("%s: exit probe at: %"PRIu64"; now: %"PRIu64
8015392f7a3SLiteSpeed Tech            "; round start: %d; round passed: %d; rtt: %"PRIu64" usec",
8025392f7a3SLiteSpeed Tech            __func__, bbr->bbr_exit_probe_rtt_at, now, is_round_start,
8035392f7a3SLiteSpeed Tech            !!(bbr->bbr_flags & BBR_FLAG_PROBE_RTT_ROUND_PASSED),
8045392f7a3SLiteSpeed Tech            lsquic_rtt_stats_get_min_rtt(bbr->bbr_rtt_stats));
8055392f7a3SLiteSpeed Tech        if (bbr->bbr_exit_probe_rtt_at == 0)
8065392f7a3SLiteSpeed Tech        {
8075392f7a3SLiteSpeed Tech            // If the window has reached the appropriate size, schedule exiting
8085392f7a3SLiteSpeed Tech            // PROBE_RTT.  The CWND during PROBE_RTT is
8095392f7a3SLiteSpeed Tech            // kMinimumCongestionWindow, but we allow an extra packet since QUIC
8105392f7a3SLiteSpeed Tech            // checks CWND before sending a packet.
8115392f7a3SLiteSpeed Tech            if (bytes_in_flight
8125392f7a3SLiteSpeed Tech                        < get_probe_rtt_cwnd(bbr) + kMaxOutgoingPacketSize)
8135392f7a3SLiteSpeed Tech            {
8145392f7a3SLiteSpeed Tech                bbr->bbr_exit_probe_rtt_at = now + kProbeRttTime;
8155392f7a3SLiteSpeed Tech                bbr->bbr_flags &= ~BBR_FLAG_PROBE_RTT_ROUND_PASSED;
8165392f7a3SLiteSpeed Tech            }
8175392f7a3SLiteSpeed Tech        }
8185392f7a3SLiteSpeed Tech        else
8195392f7a3SLiteSpeed Tech        {
8205392f7a3SLiteSpeed Tech            if (is_round_start)
8215392f7a3SLiteSpeed Tech                bbr->bbr_flags |= BBR_FLAG_PROBE_RTT_ROUND_PASSED;
8225392f7a3SLiteSpeed Tech            if (now >= bbr->bbr_exit_probe_rtt_at
8235392f7a3SLiteSpeed Tech                        && (bbr->bbr_flags & BBR_FLAG_PROBE_RTT_ROUND_PASSED))
8245392f7a3SLiteSpeed Tech            {
8255392f7a3SLiteSpeed Tech                bbr->bbr_min_rtt_timestamp = now;
8265392f7a3SLiteSpeed Tech                if (!(bbr->bbr_flags & BBR_FLAG_IS_AT_FULL_BANDWIDTH))
8275392f7a3SLiteSpeed Tech                    enter_startup_mode(bbr, now);
8285392f7a3SLiteSpeed Tech                else
8295392f7a3SLiteSpeed Tech                    enter_probe_bw_mode(bbr, now);
8305392f7a3SLiteSpeed Tech            }
8315392f7a3SLiteSpeed Tech        }
8325392f7a3SLiteSpeed Tech    }
8335392f7a3SLiteSpeed Tech
8345392f7a3SLiteSpeed Tech    bbr->bbr_flags &= ~BBR_FLAG_EXITING_QUIESCENCE;
8355392f7a3SLiteSpeed Tech}
8365392f7a3SLiteSpeed Tech
8375392f7a3SLiteSpeed Tech
8385392f7a3SLiteSpeed Tech/* See BbrSender::CalculatePacingRate */
8395392f7a3SLiteSpeed Techstatic void
8405392f7a3SLiteSpeed Techcalculate_pacing_rate (struct lsquic_bbr *bbr)
8415392f7a3SLiteSpeed Tech{
8425392f7a3SLiteSpeed Tech    struct bandwidth bw, target_rate;
8435392f7a3SLiteSpeed Tech
8445392f7a3SLiteSpeed Tech    bw = BW(minmax_get(&bbr->bbr_max_bandwidth));
8455392f7a3SLiteSpeed Tech    if (BW_IS_ZERO(&bw))
8465392f7a3SLiteSpeed Tech        return;
8475392f7a3SLiteSpeed Tech
8485392f7a3SLiteSpeed Tech    LSQ_DEBUG("BW estimate: %"PRIu64, BW_VALUE(&bw));
8495392f7a3SLiteSpeed Tech
8505392f7a3SLiteSpeed Tech    target_rate = BW_TIMES(&bw, bbr->bbr_pacing_gain);
8515392f7a3SLiteSpeed Tech    if (bbr->bbr_flags & BBR_FLAG_IS_AT_FULL_BANDWIDTH)
8525392f7a3SLiteSpeed Tech    {
8535392f7a3SLiteSpeed Tech        bbr->bbr_pacing_rate = target_rate;
8545392f7a3SLiteSpeed Tech        return;
8555392f7a3SLiteSpeed Tech    }
8565392f7a3SLiteSpeed Tech
8575392f7a3SLiteSpeed Tech    // Pace at the rate of initial_window / RTT as soon as RTT measurements are
8585392f7a3SLiteSpeed Tech    // available.
8595392f7a3SLiteSpeed Tech    if (BW_IS_ZERO(&bbr->bbr_pacing_rate)
8605392f7a3SLiteSpeed Tech            && 0 != lsquic_rtt_stats_get_min_rtt(bbr->bbr_rtt_stats))
8615392f7a3SLiteSpeed Tech    {
8625392f7a3SLiteSpeed Tech        bbr->bbr_pacing_rate = BW_FROM_BYTES_AND_DELTA(
8635392f7a3SLiteSpeed Tech            bbr->bbr_init_cwnd,
8645392f7a3SLiteSpeed Tech            lsquic_rtt_stats_get_min_rtt(bbr->bbr_rtt_stats));
8655392f7a3SLiteSpeed Tech        return;
8665392f7a3SLiteSpeed Tech    }
8675392f7a3SLiteSpeed Tech
8685392f7a3SLiteSpeed Tech    // Slow the pacing rate in STARTUP once loss has ever been detected.
8695392f7a3SLiteSpeed Tech    const int has_ever_detected_loss = bbr->bbr_end_recovery_at != 0;
8705392f7a3SLiteSpeed Tech    if (has_ever_detected_loss
8715392f7a3SLiteSpeed Tech            && (bbr->bbr_flags & (BBR_FLAG_SLOWER_STARTUP
8725392f7a3SLiteSpeed Tech                                  |BBR_FLAG_HAS_NON_APP_LIMITED))
8735392f7a3SLiteSpeed Tech                == (BBR_FLAG_SLOWER_STARTUP|BBR_FLAG_HAS_NON_APP_LIMITED))
8745392f7a3SLiteSpeed Tech    {
8755392f7a3SLiteSpeed Tech        bbr->bbr_pacing_rate = BW_TIMES(&bw, kStartupAfterLossGain);
8765392f7a3SLiteSpeed Tech        return;
8775392f7a3SLiteSpeed Tech    }
8785392f7a3SLiteSpeed Tech
8795392f7a3SLiteSpeed Tech    // Slow the pacing rate in STARTUP by the bytes_lost / CWND.
8805392f7a3SLiteSpeed Tech    if (startup_rate_reduction_multiplier_ != 0
8815392f7a3SLiteSpeed Tech            && has_ever_detected_loss
8825392f7a3SLiteSpeed Tech                && (bbr->bbr_flags & BBR_FLAG_HAS_NON_APP_LIMITED))
8835392f7a3SLiteSpeed Tech    {
8845392f7a3SLiteSpeed Tech        bbr->bbr_pacing_rate = BW_TIMES(&target_rate,
8855392f7a3SLiteSpeed Tech            (1 - (bbr->bbr_startup_bytes_lost
8865392f7a3SLiteSpeed Tech                    * startup_rate_reduction_multiplier_ * 1.0f
8875392f7a3SLiteSpeed Tech                        / bbr->bbr_cwnd_gain)));
8885392f7a3SLiteSpeed Tech        // Ensure the pacing rate doesn't drop below the startup growth target
8895392f7a3SLiteSpeed Tech        // times  the bandwidth estimate.
8905392f7a3SLiteSpeed Tech        if (BW_VALUE(&bbr->bbr_pacing_rate)
8915392f7a3SLiteSpeed Tech                                        < BW_VALUE(&bw) * kStartupGrowthTarget)
8925392f7a3SLiteSpeed Tech            bbr->bbr_pacing_rate = BW_TIMES(&bw, kStartupGrowthTarget);
8935392f7a3SLiteSpeed Tech        return;
8945392f7a3SLiteSpeed Tech    }
8955392f7a3SLiteSpeed Tech
8965392f7a3SLiteSpeed Tech    // Do not decrease the pacing rate during startup.
8975392f7a3SLiteSpeed Tech    if (BW_VALUE(&bbr->bbr_pacing_rate) < BW_VALUE(&target_rate))
8985392f7a3SLiteSpeed Tech        bbr->bbr_pacing_rate = target_rate;
8995392f7a3SLiteSpeed Tech}
9005392f7a3SLiteSpeed Tech
9015392f7a3SLiteSpeed Tech
9025392f7a3SLiteSpeed Tech/* See BbrSender::CalculateCongestionWindow */
9035392f7a3SLiteSpeed Techstatic void
9045392f7a3SLiteSpeed Techcalculate_cwnd (struct lsquic_bbr *bbr, uint64_t bytes_acked,
9055392f7a3SLiteSpeed Tech                                                  uint64_t excess_acked)
9065392f7a3SLiteSpeed Tech{
9075392f7a3SLiteSpeed Tech    if (bbr->bbr_mode == BBR_MODE_PROBE_RTT)
9085392f7a3SLiteSpeed Tech        return;
9095392f7a3SLiteSpeed Tech
9105392f7a3SLiteSpeed Tech    uint64_t target_window = get_target_cwnd(bbr, bbr->bbr_cwnd_gain);
9115392f7a3SLiteSpeed Tech    if (bbr->bbr_flags & BBR_FLAG_IS_AT_FULL_BANDWIDTH)
9125392f7a3SLiteSpeed Tech        // Add the max recently measured ack aggregation to CWND.
9135392f7a3SLiteSpeed Tech        target_window += minmax_get(&bbr->bbr_max_ack_height);
9145392f7a3SLiteSpeed Tech    else if (bbr->bbr_flags & BBR_FLAG_ENABLE_ACK_AGG_IN_STARTUP)
9155392f7a3SLiteSpeed Tech        // Add the most recent excess acked.  Because CWND never decreases in
9165392f7a3SLiteSpeed Tech        // STARTUP, this will automatically create a very localized max filter.
9175392f7a3SLiteSpeed Tech        target_window += excess_acked;
9185392f7a3SLiteSpeed Tech
9195392f7a3SLiteSpeed Tech    // Instead of immediately setting the target CWND as the new one, BBR grows
9205392f7a3SLiteSpeed Tech    // the CWND towards |target_window| by only increasing it |bytes_acked| at a
9215392f7a3SLiteSpeed Tech    // time.
9225392f7a3SLiteSpeed Tech    const int add_bytes_acked =
9235392f7a3SLiteSpeed Tech	!FLAGS_quic_bbr_no_bytes_acked_in_startup_recovery || !in_recovery(bbr);
9245392f7a3SLiteSpeed Tech    if (bbr->bbr_flags & BBR_FLAG_IS_AT_FULL_BANDWIDTH)
9255392f7a3SLiteSpeed Tech        bbr->bbr_cwnd = MIN(target_window, bbr->bbr_cwnd + bytes_acked);
9265392f7a3SLiteSpeed Tech    else if (add_bytes_acked &&
9275392f7a3SLiteSpeed Tech             (bbr->bbr_cwnd_gain < target_window ||
9285392f7a3SLiteSpeed Tech              lsquic_bw_sampler_total_acked(&bbr->bbr_bw_sampler)
9295392f7a3SLiteSpeed Tech                                                        < bbr->bbr_init_cwnd))
9305392f7a3SLiteSpeed Tech        // If the connection is not yet out of startup phase, do not decrease
9315392f7a3SLiteSpeed Tech        // the window.
9325392f7a3SLiteSpeed Tech        bbr->bbr_cwnd += bytes_acked;
9335392f7a3SLiteSpeed Tech
9345392f7a3SLiteSpeed Tech    // Enforce the limits on the congestion window.
9355392f7a3SLiteSpeed Tech    if (bbr->bbr_cwnd < bbr->bbr_min_cwnd)
9365392f7a3SLiteSpeed Tech        bbr->bbr_cwnd = bbr->bbr_min_cwnd;
9375392f7a3SLiteSpeed Tech    else if (bbr->bbr_cwnd > bbr->bbr_max_cwnd)
9385392f7a3SLiteSpeed Tech    {
9395392f7a3SLiteSpeed Tech        LSQ_DEBUG("exceed max cwnd");
9405392f7a3SLiteSpeed Tech        bbr->bbr_cwnd = bbr->bbr_max_cwnd;
9415392f7a3SLiteSpeed Tech    }
9425392f7a3SLiteSpeed Tech}
9435392f7a3SLiteSpeed Tech
9445392f7a3SLiteSpeed Tech
9455392f7a3SLiteSpeed Tech/* See BbrSender::CalculateRecoveryWindow */
9465392f7a3SLiteSpeed Techstatic void
9475392f7a3SLiteSpeed Techcalculate_recovery_window (struct lsquic_bbr *bbr, uint64_t bytes_acked,
9485392f7a3SLiteSpeed Tech                                uint64_t bytes_lost, uint64_t bytes_in_flight)
9495392f7a3SLiteSpeed Tech{
9505392f7a3SLiteSpeed Tech    if ((bbr->bbr_flags & BBR_FLAG_RATE_BASED_STARTUP)
9515392f7a3SLiteSpeed Tech                                        && bbr->bbr_mode == BBR_MODE_STARTUP)
9525392f7a3SLiteSpeed Tech        return;
9535392f7a3SLiteSpeed Tech
9545392f7a3SLiteSpeed Tech    if (bbr->bbr_recovery_state == BBR_RS_NOT_IN_RECOVERY)
9555392f7a3SLiteSpeed Tech        return;
9565392f7a3SLiteSpeed Tech
9575392f7a3SLiteSpeed Tech    // Set up the initial recovery window.
9585392f7a3SLiteSpeed Tech    if (bbr->bbr_recovery_window == 0)
9595392f7a3SLiteSpeed Tech    {
9605392f7a3SLiteSpeed Tech        bbr->bbr_recovery_window = bytes_in_flight + bytes_acked;
9615392f7a3SLiteSpeed Tech        bbr->bbr_recovery_window = MAX(bbr->bbr_min_cwnd,
9625392f7a3SLiteSpeed Tech                                                    bbr->bbr_recovery_window);
9635392f7a3SLiteSpeed Tech        return;
9645392f7a3SLiteSpeed Tech    }
9655392f7a3SLiteSpeed Tech
9665392f7a3SLiteSpeed Tech    // Remove losses from the recovery window, while accounting for a potential
9675392f7a3SLiteSpeed Tech    // integer underflow.
9685392f7a3SLiteSpeed Tech    if (bbr->bbr_recovery_window >= bytes_lost)
9695392f7a3SLiteSpeed Tech        bbr->bbr_recovery_window -= bytes_lost;
9705392f7a3SLiteSpeed Tech    else
9715392f7a3SLiteSpeed Tech        bbr->bbr_recovery_window = kMaxSegmentSize;
9725392f7a3SLiteSpeed Tech
9735392f7a3SLiteSpeed Tech    // In CONSERVATION mode, just subtracting losses is sufficient.  In GROWTH,
9745392f7a3SLiteSpeed Tech    // release additional |bytes_acked| to achieve a slow-start-like behavior.
9755392f7a3SLiteSpeed Tech    if (bbr->bbr_recovery_state == BBR_RS_GROWTH)
9765392f7a3SLiteSpeed Tech        bbr->bbr_recovery_window += bytes_acked;
9775392f7a3SLiteSpeed Tech
9785392f7a3SLiteSpeed Tech    // Sanity checks.  Ensure that we always allow to send at least an MSS or
9795392f7a3SLiteSpeed Tech    // |bytes_acked| in response, whichever is larger.
9805392f7a3SLiteSpeed Tech    bbr->bbr_recovery_window = MAX(bbr->bbr_recovery_window,
9815392f7a3SLiteSpeed Tech                                            bytes_in_flight + bytes_acked);
9825392f7a3SLiteSpeed Tech    if (FLAG_quic_bbr_one_mss_conservation)
9835392f7a3SLiteSpeed Tech        bbr->bbr_recovery_window = MAX(bbr->bbr_recovery_window,
9845392f7a3SLiteSpeed Tech                                            bytes_in_flight + kMaxSegmentSize);
9855392f7a3SLiteSpeed Tech    bbr->bbr_recovery_window = MAX(bbr->bbr_recovery_window, bbr->bbr_min_cwnd);
9865392f7a3SLiteSpeed Tech}
9875392f7a3SLiteSpeed Tech
9885392f7a3SLiteSpeed Tech
9895392f7a3SLiteSpeed Techstatic void
9905392f7a3SLiteSpeed Techlsquic_bbr_end_ack (void *cong_ctl, uint64_t in_flight)
9915392f7a3SLiteSpeed Tech{
9925392f7a3SLiteSpeed Tech    struct lsquic_bbr *const bbr = cong_ctl;
9935392f7a3SLiteSpeed Tech    int is_round_start, min_rtt_expired;
9945392f7a3SLiteSpeed Tech    uint64_t bytes_acked, excess_acked, bytes_lost;
9955392f7a3SLiteSpeed Tech
9965392f7a3SLiteSpeed Tech    assert(bbr->bbr_flags & BBR_FLAG_IN_ACK);
9975392f7a3SLiteSpeed Tech    bbr->bbr_flags &= ~BBR_FLAG_IN_ACK;
9985392f7a3SLiteSpeed Tech
9995392f7a3SLiteSpeed Tech    LSQ_DEBUG("end_ack; mode: %s; in_flight: %"PRIu64, mode2str[bbr->bbr_mode],
10005392f7a3SLiteSpeed Tech                                                                    in_flight);
10015392f7a3SLiteSpeed Tech
10025392f7a3SLiteSpeed Tech    bytes_acked = lsquic_bw_sampler_total_acked(&bbr->bbr_bw_sampler)
10035392f7a3SLiteSpeed Tech                            - bbr->bbr_ack_state.total_bytes_acked_before;
10045392f7a3SLiteSpeed Tech    if (bbr->bbr_ack_state.acked_bytes)
10055392f7a3SLiteSpeed Tech    {
10065392f7a3SLiteSpeed Tech        is_round_start = bbr->bbr_ack_state.max_packno
10075392f7a3SLiteSpeed Tech                                    > bbr->bbr_current_round_trip_end
10085392f7a3SLiteSpeed Tech                    || !is_valid_packno(bbr->bbr_current_round_trip_end);
10095392f7a3SLiteSpeed Tech        if (is_round_start)
10105392f7a3SLiteSpeed Tech        {
10115392f7a3SLiteSpeed Tech            ++bbr->bbr_round_count;
10125392f7a3SLiteSpeed Tech            bbr->bbr_current_round_trip_end = bbr->bbr_last_sent_packno;
10135392f7a3SLiteSpeed Tech            LSQ_DEBUG("up round count to %"PRIu64"; new rt end: %"PRIu64,
10145392f7a3SLiteSpeed Tech                        bbr->bbr_round_count, bbr->bbr_current_round_trip_end);
10155392f7a3SLiteSpeed Tech        }
10165392f7a3SLiteSpeed Tech        min_rtt_expired = update_bandwidth_and_min_rtt(bbr);
10175392f7a3SLiteSpeed Tech        update_recovery_state(bbr, is_round_start);
10185392f7a3SLiteSpeed Tech        excess_acked = update_ack_aggregation_bytes(bbr, bytes_acked);
10195392f7a3SLiteSpeed Tech    }
10205392f7a3SLiteSpeed Tech    else
10215392f7a3SLiteSpeed Tech    {
10225392f7a3SLiteSpeed Tech        is_round_start = 0;
10235392f7a3SLiteSpeed Tech        min_rtt_expired = 0;
10245392f7a3SLiteSpeed Tech        excess_acked = 0;
10255392f7a3SLiteSpeed Tech    }
10265392f7a3SLiteSpeed Tech
10275392f7a3SLiteSpeed Tech    if (bbr->bbr_mode == BBR_MODE_PROBE_BW)
10285392f7a3SLiteSpeed Tech        update_gain_cycle_phase(bbr, in_flight);
10295392f7a3SLiteSpeed Tech
10305392f7a3SLiteSpeed Tech    if (is_round_start && !(bbr->bbr_flags & BBR_FLAG_IS_AT_FULL_BANDWIDTH))
10315392f7a3SLiteSpeed Tech        check_if_full_bw_reached(bbr);
10325392f7a3SLiteSpeed Tech
10335392f7a3SLiteSpeed Tech    maybe_exit_startup_or_drain(bbr, bbr->bbr_ack_state.ack_time, in_flight);
10345392f7a3SLiteSpeed Tech
10355392f7a3SLiteSpeed Tech    maybe_enter_or_exit_probe_rtt(bbr, bbr->bbr_ack_state.ack_time,
10365392f7a3SLiteSpeed Tech                                is_round_start, min_rtt_expired, in_flight);
10375392f7a3SLiteSpeed Tech
10385392f7a3SLiteSpeed Tech    // Calculate number of packets acked and lost.
10395392f7a3SLiteSpeed Tech    bytes_lost = bbr->bbr_ack_state.lost_bytes;
10405392f7a3SLiteSpeed Tech
10415392f7a3SLiteSpeed Tech    // After the model is updated, recalculate the pacing rate and congestion
10425392f7a3SLiteSpeed Tech    // window.
10435392f7a3SLiteSpeed Tech    calculate_pacing_rate(bbr);
10445392f7a3SLiteSpeed Tech    calculate_cwnd(bbr, bytes_acked, excess_acked);
10455392f7a3SLiteSpeed Tech    calculate_recovery_window(bbr, bytes_acked, bytes_lost, in_flight);
10465392f7a3SLiteSpeed Tech
10475392f7a3SLiteSpeed Tech    /* We don't need to clean up BW sampler */
10485392f7a3SLiteSpeed Tech}
10495392f7a3SLiteSpeed Tech
10505392f7a3SLiteSpeed Tech
10515392f7a3SLiteSpeed Techstatic void
10525392f7a3SLiteSpeed Techlsquic_bbr_cleanup (void *cong_ctl)
10535392f7a3SLiteSpeed Tech{
10545392f7a3SLiteSpeed Tech    struct lsquic_bbr *const bbr = cong_ctl;
10555392f7a3SLiteSpeed Tech
1056a6cdaedbSDmitri Tikhonov    lsquic_bw_sampler_cleanup(&bbr->bbr_bw_sampler);
10575392f7a3SLiteSpeed Tech    LSQ_DEBUG("cleanup");
10585392f7a3SLiteSpeed Tech}
10595392f7a3SLiteSpeed Tech
10605392f7a3SLiteSpeed Tech
10615392f7a3SLiteSpeed Techstatic void
10625392f7a3SLiteSpeed Techlsquic_bbr_loss (void *cong_ctl) {   /* Noop */   }
10635392f7a3SLiteSpeed Tech
10645392f7a3SLiteSpeed Tech
10655392f7a3SLiteSpeed Techstatic void
10665392f7a3SLiteSpeed Techlsquic_bbr_timeout (void *cong_ctl) {   /* Noop */   }
10675392f7a3SLiteSpeed Tech
10685392f7a3SLiteSpeed Tech
10695392f7a3SLiteSpeed Techconst struct cong_ctl_if lsquic_cong_bbr_if =
10705392f7a3SLiteSpeed Tech{
10715392f7a3SLiteSpeed Tech    .cci_ack           = lsquic_bbr_ack,
10725392f7a3SLiteSpeed Tech    .cci_begin_ack     = lsquic_bbr_begin_ack,
10735392f7a3SLiteSpeed Tech    .cci_end_ack       = lsquic_bbr_end_ack,
10745392f7a3SLiteSpeed Tech    .cci_cleanup       = lsquic_bbr_cleanup,
10755392f7a3SLiteSpeed Tech    .cci_get_cwnd      = lsquic_bbr_get_cwnd,
10765392f7a3SLiteSpeed Tech    .cci_init          = lsquic_bbr_init,
10775392f7a3SLiteSpeed Tech    .cci_pacing_rate   = lsquic_bbr_pacing_rate,
10785392f7a3SLiteSpeed Tech    .cci_loss          = lsquic_bbr_loss,
10795392f7a3SLiteSpeed Tech    .cci_lost          = lsquic_bbr_lost,
10809fc12041SDmitri Tikhonov    .cci_reinit        = lsquic_bbr_reinit,
10815392f7a3SLiteSpeed Tech    .cci_timeout       = lsquic_bbr_timeout,
10825392f7a3SLiteSpeed Tech    .cci_sent          = lsquic_bbr_sent,
10835392f7a3SLiteSpeed Tech    .cci_was_quiet     = lsquic_bbr_was_quiet,
10845392f7a3SLiteSpeed Tech};
1085