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