lsquic_bbr.c revision a6cdaedb
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 Techstatic void 286cca25415SDmitri Tikhonovlsquic_bbr_was_quiet (void *cong_ctl, lsquic_time_t now, uint64_t in_flight) 2875392f7a3SLiteSpeed Tech{ 2885392f7a3SLiteSpeed Tech struct lsquic_bbr *const bbr = cong_ctl; 289cca25415SDmitri Tikhonov LSQ_DEBUG("was quiet"); /* Do nothing */ 290cca25415SDmitri Tikhonov} 291cca25415SDmitri Tikhonov 292cca25415SDmitri Tikhonov 293cca25415SDmitri Tikhonov/* See BbrSender::OnApplicationLimited */ 294cca25415SDmitri Tikhonovstatic void 295cca25415SDmitri Tikhonovbbr_app_limited (struct lsquic_bbr *bbr, uint64_t bytes_in_flight) 296cca25415SDmitri Tikhonov{ 2975392f7a3SLiteSpeed Tech uint64_t cwnd; 2985392f7a3SLiteSpeed Tech 299cca25415SDmitri Tikhonov cwnd = lsquic_bbr_get_cwnd(bbr); 3005392f7a3SLiteSpeed Tech if (bytes_in_flight >= cwnd) 3015392f7a3SLiteSpeed Tech return; 3025392f7a3SLiteSpeed Tech if ((bbr->bbr_flags & BBR_FLAG_FLEXIBLE_APP_LIMITED) 3035392f7a3SLiteSpeed Tech && is_pipe_sufficiently_full(bbr, bytes_in_flight)) 3045392f7a3SLiteSpeed Tech return; 3055392f7a3SLiteSpeed Tech 3065392f7a3SLiteSpeed Tech bbr->bbr_flags |= BBR_FLAG_APP_LIMITED_SINCE_LAST_PROBE_RTT; 3075392f7a3SLiteSpeed Tech lsquic_bw_sampler_app_limited(&bbr->bbr_bw_sampler); 3085392f7a3SLiteSpeed Tech LSQ_DEBUG("becoming application-limited. Last sent packet: %"PRIu64"; " 3095392f7a3SLiteSpeed Tech "CWND: %"PRIu64, bbr->bbr_last_sent_packno, cwnd); 3105392f7a3SLiteSpeed Tech} 3115392f7a3SLiteSpeed Tech 3125392f7a3SLiteSpeed Tech 3135392f7a3SLiteSpeed Techstatic void 3145392f7a3SLiteSpeed Techlsquic_bbr_ack (void *cong_ctl, struct lsquic_packet_out *packet_out, 3155392f7a3SLiteSpeed Tech unsigned packet_sz, lsquic_time_t now_time, int app_limited) 3165392f7a3SLiteSpeed Tech{ 3175392f7a3SLiteSpeed Tech struct lsquic_bbr *const bbr = cong_ctl; 3185392f7a3SLiteSpeed Tech struct bw_sample *sample; 3195392f7a3SLiteSpeed Tech 3205392f7a3SLiteSpeed Tech assert(bbr->bbr_flags & BBR_FLAG_IN_ACK); 3215392f7a3SLiteSpeed Tech 3225392f7a3SLiteSpeed Tech sample = lsquic_bw_sampler_packet_acked(&bbr->bbr_bw_sampler, packet_out, 3235392f7a3SLiteSpeed Tech bbr->bbr_ack_state.ack_time); 3245392f7a3SLiteSpeed Tech if (sample) 3255392f7a3SLiteSpeed Tech TAILQ_INSERT_TAIL(&bbr->bbr_ack_state.samples, sample, next); 3265392f7a3SLiteSpeed Tech 3275392f7a3SLiteSpeed Tech if (is_valid_packno(bbr->bbr_ack_state.max_packno)) 3285392f7a3SLiteSpeed Tech /* We assume packet numbers are ordered */ 3295392f7a3SLiteSpeed Tech assert(packet_out->po_packno > bbr->bbr_ack_state.max_packno); 3305392f7a3SLiteSpeed Tech bbr->bbr_ack_state.max_packno = packet_out->po_packno; 3315392f7a3SLiteSpeed Tech bbr->bbr_ack_state.acked_bytes += packet_sz; 3325392f7a3SLiteSpeed Tech} 3335392f7a3SLiteSpeed Tech 3345392f7a3SLiteSpeed Tech 3355392f7a3SLiteSpeed Techstatic void 3365392f7a3SLiteSpeed Techlsquic_bbr_sent (void *cong_ctl, struct lsquic_packet_out *packet_out, 337cca25415SDmitri Tikhonov uint64_t in_flight, int app_limited) 3385392f7a3SLiteSpeed Tech{ 3395392f7a3SLiteSpeed Tech struct lsquic_bbr *const bbr = cong_ctl; 3405392f7a3SLiteSpeed Tech 3415392f7a3SLiteSpeed Tech if (!(packet_out->po_flags & PO_MINI)) 3425392f7a3SLiteSpeed Tech lsquic_bw_sampler_packet_sent(&bbr->bbr_bw_sampler, packet_out, 3435392f7a3SLiteSpeed Tech in_flight); 3445392f7a3SLiteSpeed Tech 3455392f7a3SLiteSpeed Tech /* Obviously we make an assumption that sent packet number are always 3465392f7a3SLiteSpeed Tech * increasing. 3475392f7a3SLiteSpeed Tech */ 3485392f7a3SLiteSpeed Tech bbr->bbr_last_sent_packno = packet_out->po_packno; 349cca25415SDmitri Tikhonov 350cca25415SDmitri Tikhonov if (app_limited) 351cca25415SDmitri Tikhonov bbr_app_limited(bbr, in_flight); 3525392f7a3SLiteSpeed Tech} 3535392f7a3SLiteSpeed Tech 3545392f7a3SLiteSpeed Tech 3555392f7a3SLiteSpeed Techstatic void 3565392f7a3SLiteSpeed Techlsquic_bbr_lost (void *cong_ctl, struct lsquic_packet_out *packet_out, 3575392f7a3SLiteSpeed Tech unsigned packet_sz) 3585392f7a3SLiteSpeed Tech{ 3595392f7a3SLiteSpeed Tech struct lsquic_bbr *const bbr = cong_ctl; 3605392f7a3SLiteSpeed Tech 3615392f7a3SLiteSpeed Tech lsquic_bw_sampler_packet_lost(&bbr->bbr_bw_sampler, packet_out); 3625392f7a3SLiteSpeed Tech bbr->bbr_ack_state.has_losses = 1; 3635392f7a3SLiteSpeed Tech bbr->bbr_ack_state.lost_bytes += packet_sz; 3645392f7a3SLiteSpeed Tech} 3655392f7a3SLiteSpeed Tech 3665392f7a3SLiteSpeed Tech 3675392f7a3SLiteSpeed Techstatic void 3685392f7a3SLiteSpeed Techlsquic_bbr_begin_ack (void *cong_ctl, lsquic_time_t ack_time, uint64_t in_flight) 3695392f7a3SLiteSpeed Tech{ 3705392f7a3SLiteSpeed Tech struct lsquic_bbr *const bbr = cong_ctl; 3715392f7a3SLiteSpeed Tech 3725392f7a3SLiteSpeed Tech assert(!(bbr->bbr_flags & BBR_FLAG_IN_ACK)); 3735392f7a3SLiteSpeed Tech bbr->bbr_flags |= BBR_FLAG_IN_ACK; 3745392f7a3SLiteSpeed Tech memset(&bbr->bbr_ack_state, 0, sizeof(bbr->bbr_ack_state)); 3755392f7a3SLiteSpeed Tech TAILQ_INIT(&bbr->bbr_ack_state.samples); 3765392f7a3SLiteSpeed Tech bbr->bbr_ack_state.ack_time = ack_time; 3775392f7a3SLiteSpeed Tech bbr->bbr_ack_state.max_packno = UINT64_MAX; 3785392f7a3SLiteSpeed Tech bbr->bbr_ack_state.in_flight = in_flight; 3795392f7a3SLiteSpeed Tech bbr->bbr_ack_state.total_bytes_acked_before 3805392f7a3SLiteSpeed Tech = lsquic_bw_sampler_total_acked(&bbr->bbr_bw_sampler); 3815392f7a3SLiteSpeed Tech} 3825392f7a3SLiteSpeed Tech 3835392f7a3SLiteSpeed Tech 3845392f7a3SLiteSpeed Tech/* Based on BbrSender::ShouldExtendMinRttExpiry() */ 3855392f7a3SLiteSpeed Techstatic int 3865392f7a3SLiteSpeed Techshould_extend_min_rtt_expiry (const struct lsquic_bbr *bbr) 3875392f7a3SLiteSpeed Tech{ 3885392f7a3SLiteSpeed Tech int increased_since_last_probe; 3895392f7a3SLiteSpeed Tech 3905392f7a3SLiteSpeed Tech if ((bbr->bbr_flags & (BBR_FLAG_APP_LIMITED_SINCE_LAST_PROBE_RTT 3915392f7a3SLiteSpeed Tech |BBR_FLAG_PROBE_RTT_DISABLED_IF_APP_LIMITED)) 3925392f7a3SLiteSpeed Tech == (BBR_FLAG_APP_LIMITED_SINCE_LAST_PROBE_RTT 3935392f7a3SLiteSpeed Tech |BBR_FLAG_PROBE_RTT_DISABLED_IF_APP_LIMITED)) 3945392f7a3SLiteSpeed Tech // Extend the current min_rtt if we've been app limited recently. 3955392f7a3SLiteSpeed Tech return 1; 3965392f7a3SLiteSpeed Tech 3975392f7a3SLiteSpeed Tech increased_since_last_probe = bbr->bbr_min_rtt_since_last_probe 3985392f7a3SLiteSpeed Tech > bbr->bbr_min_rtt * kSimilarMinRttThreshold; 3995392f7a3SLiteSpeed Tech if ((bbr->bbr_flags & (BBR_FLAG_APP_LIMITED_SINCE_LAST_PROBE_RTT 4005392f7a3SLiteSpeed Tech |BBR_FLAG_PROBE_RTT_SKIPPED_IF_SIMILAR_RTT)) 4015392f7a3SLiteSpeed Tech == (BBR_FLAG_APP_LIMITED_SINCE_LAST_PROBE_RTT 4025392f7a3SLiteSpeed Tech |BBR_FLAG_PROBE_RTT_SKIPPED_IF_SIMILAR_RTT) 4035392f7a3SLiteSpeed Tech && !increased_since_last_probe) 4045392f7a3SLiteSpeed Tech // Extend the current min_rtt if we've been app limited recently and an 4055392f7a3SLiteSpeed Tech // rtt has been measured in that time that's less than 12.5% more than 4065392f7a3SLiteSpeed Tech // the current min_rtt. 4075392f7a3SLiteSpeed Tech return 1; 4085392f7a3SLiteSpeed Tech 4095392f7a3SLiteSpeed Tech return 0; 4105392f7a3SLiteSpeed Tech} 4115392f7a3SLiteSpeed Tech 4125392f7a3SLiteSpeed Tech 4135392f7a3SLiteSpeed Tech/* Based on BbrSender::UpdateBandwidthAndMinRtt */ 4145392f7a3SLiteSpeed Tech/* Returns true if min RTT expired, false otherwise */ 4155392f7a3SLiteSpeed Techstatic int 4165392f7a3SLiteSpeed Techupdate_bandwidth_and_min_rtt (struct lsquic_bbr *bbr) 4175392f7a3SLiteSpeed Tech{ 4185392f7a3SLiteSpeed Tech struct bw_sample *sample, *next_sample; 4195392f7a3SLiteSpeed Tech uint64_t sample_min_rtt; 4205392f7a3SLiteSpeed Tech int min_rtt_expired; 4215392f7a3SLiteSpeed Tech 4225392f7a3SLiteSpeed Tech sample_min_rtt = UINT64_MAX; 4235392f7a3SLiteSpeed Tech for (sample = TAILQ_FIRST(&bbr->bbr_ack_state.samples); sample; 4245392f7a3SLiteSpeed Tech sample = next_sample) 4255392f7a3SLiteSpeed Tech { 4265392f7a3SLiteSpeed Tech next_sample = TAILQ_NEXT(sample, next); 4275392f7a3SLiteSpeed Tech 4285392f7a3SLiteSpeed Tech if (sample->is_app_limited) 4295392f7a3SLiteSpeed Tech bbr->bbr_flags |= BBR_FLAG_LAST_SAMPLE_APP_LIMITED; 4305392f7a3SLiteSpeed Tech else 4315392f7a3SLiteSpeed Tech { 4325392f7a3SLiteSpeed Tech bbr->bbr_flags &= ~BBR_FLAG_LAST_SAMPLE_APP_LIMITED; 4335392f7a3SLiteSpeed Tech bbr->bbr_flags |= BBR_FLAG_HAS_NON_APP_LIMITED; 4345392f7a3SLiteSpeed Tech } 4355392f7a3SLiteSpeed Tech 4365392f7a3SLiteSpeed Tech if (sample_min_rtt == UINT64_MAX || sample->rtt < sample_min_rtt) 4375392f7a3SLiteSpeed Tech sample_min_rtt = sample->rtt; 4385392f7a3SLiteSpeed Tech 4395392f7a3SLiteSpeed Tech if (!sample->is_app_limited 4405392f7a3SLiteSpeed Tech || BW_VALUE(&sample->bandwidth) 4415392f7a3SLiteSpeed Tech > minmax_get(&bbr->bbr_max_bandwidth)) 4425392f7a3SLiteSpeed Tech minmax_upmax(&bbr->bbr_max_bandwidth, bbr->bbr_round_count, 4435392f7a3SLiteSpeed Tech BW_VALUE(&sample->bandwidth)); 4445392f7a3SLiteSpeed Tech 4455392f7a3SLiteSpeed Tech lsquic_malo_put(sample); 4465392f7a3SLiteSpeed Tech } 4475392f7a3SLiteSpeed Tech 4485392f7a3SLiteSpeed Tech if (sample_min_rtt == UINT64_MAX) 4495392f7a3SLiteSpeed Tech return 0; 4505392f7a3SLiteSpeed Tech 4515392f7a3SLiteSpeed Tech bbr->bbr_min_rtt_since_last_probe 4525392f7a3SLiteSpeed Tech = MIN(bbr->bbr_min_rtt_since_last_probe, sample_min_rtt); 4535392f7a3SLiteSpeed Tech 4545392f7a3SLiteSpeed Tech min_rtt_expired = bbr->bbr_min_rtt != 0 && (bbr->bbr_ack_state.ack_time 4555392f7a3SLiteSpeed Tech > bbr->bbr_min_rtt_timestamp + kMinRttExpiry); 4565392f7a3SLiteSpeed Tech if (min_rtt_expired || sample_min_rtt < bbr->bbr_min_rtt 4575392f7a3SLiteSpeed Tech || 0 == bbr->bbr_min_rtt) 4585392f7a3SLiteSpeed Tech { 4595392f7a3SLiteSpeed Tech if (min_rtt_expired && should_extend_min_rtt_expiry(bbr)) 4605392f7a3SLiteSpeed Tech { 4615392f7a3SLiteSpeed Tech LSQ_DEBUG("min rtt expiration extended, stay at: %"PRIu64, 4625392f7a3SLiteSpeed Tech bbr->bbr_min_rtt); 4635392f7a3SLiteSpeed Tech min_rtt_expired = 0; 4645392f7a3SLiteSpeed Tech } 4655392f7a3SLiteSpeed Tech else 4665392f7a3SLiteSpeed Tech { 4675392f7a3SLiteSpeed Tech LSQ_DEBUG("min rtt updated: %"PRIu64" -> %"PRIu64, 4685392f7a3SLiteSpeed Tech bbr->bbr_min_rtt, sample_min_rtt); 4695392f7a3SLiteSpeed Tech bbr->bbr_min_rtt = sample_min_rtt; 4705392f7a3SLiteSpeed Tech } 4715392f7a3SLiteSpeed Tech bbr->bbr_min_rtt_timestamp = bbr->bbr_ack_state.ack_time; 4725392f7a3SLiteSpeed Tech bbr->bbr_min_rtt_since_last_probe = UINT64_MAX; 4735392f7a3SLiteSpeed Tech bbr->bbr_flags &= ~BBR_FLAG_APP_LIMITED_SINCE_LAST_PROBE_RTT; 4745392f7a3SLiteSpeed Tech } 4755392f7a3SLiteSpeed Tech 4765392f7a3SLiteSpeed Tech return min_rtt_expired; 4775392f7a3SLiteSpeed Tech} 4785392f7a3SLiteSpeed Tech 4795392f7a3SLiteSpeed Tech 4805392f7a3SLiteSpeed Tech/* Based on BbrSender::UpdateRecoveryState() */ 4815392f7a3SLiteSpeed Techstatic void 4825392f7a3SLiteSpeed Techupdate_recovery_state (struct lsquic_bbr *bbr, int is_round_start) 4835392f7a3SLiteSpeed Tech{ 4845392f7a3SLiteSpeed Tech // Exit recovery when there are no losses for a round. 4855392f7a3SLiteSpeed Tech if (bbr->bbr_ack_state.has_losses) 4865392f7a3SLiteSpeed Tech bbr->bbr_end_recovery_at = bbr->bbr_last_sent_packno; 4875392f7a3SLiteSpeed Tech 4885392f7a3SLiteSpeed Tech switch (bbr->bbr_recovery_state) 4895392f7a3SLiteSpeed Tech { 4905392f7a3SLiteSpeed Tech case BBR_RS_NOT_IN_RECOVERY: 4915392f7a3SLiteSpeed Tech // Enter conservation on the first loss. 4925392f7a3SLiteSpeed Tech if (bbr->bbr_ack_state.has_losses) 4935392f7a3SLiteSpeed Tech { 4945392f7a3SLiteSpeed Tech bbr->bbr_recovery_state = BBR_RS_CONSERVATION; 4955392f7a3SLiteSpeed Tech // This will cause the |bbr_recovery_window| to be set to the 4965392f7a3SLiteSpeed Tech // correct value in CalculateRecoveryWindow(). 4975392f7a3SLiteSpeed Tech bbr->bbr_recovery_window = 0; 4985392f7a3SLiteSpeed Tech // Since the conservation phase is meant to be lasting for a whole 4995392f7a3SLiteSpeed Tech // round, extend the current round as if it were started right now. 5005392f7a3SLiteSpeed Tech bbr->bbr_current_round_trip_end = bbr->bbr_last_sent_packno; 5015392f7a3SLiteSpeed Tech } 5025392f7a3SLiteSpeed Tech break; 5035392f7a3SLiteSpeed Tech case BBR_RS_CONSERVATION: 5045392f7a3SLiteSpeed Tech if (is_round_start) 5055392f7a3SLiteSpeed Tech bbr->bbr_recovery_state = BBR_RS_GROWTH; 5065392f7a3SLiteSpeed Tech /* Fall-through */ 5075392f7a3SLiteSpeed Tech case BBR_RS_GROWTH: 5085392f7a3SLiteSpeed Tech // Exit recovery if appropriate. 5095392f7a3SLiteSpeed Tech if (!bbr->bbr_ack_state.has_losses 5105392f7a3SLiteSpeed Tech && bbr->bbr_ack_state.max_packno > bbr->bbr_end_recovery_at) 5115392f7a3SLiteSpeed Tech bbr->bbr_recovery_state = BBR_RS_NOT_IN_RECOVERY; 5125392f7a3SLiteSpeed Tech break; 5135392f7a3SLiteSpeed Tech } 5145392f7a3SLiteSpeed Tech} 5155392f7a3SLiteSpeed Tech 5165392f7a3SLiteSpeed Tech 5175392f7a3SLiteSpeed Techstatic uint64_t 5185392f7a3SLiteSpeed Techupdate_ack_aggregation_bytes (struct lsquic_bbr *bbr, 5195392f7a3SLiteSpeed Tech uint64_t newly_acked_bytes) 5205392f7a3SLiteSpeed Tech{ 5215392f7a3SLiteSpeed Tech const lsquic_time_t ack_time = bbr->bbr_ack_state.ack_time; 5225392f7a3SLiteSpeed Tech uint64_t expected_bytes_acked, diff; 5235392f7a3SLiteSpeed Tech 5245392f7a3SLiteSpeed Tech // Compute how many bytes are expected to be delivered, assuming max 5255392f7a3SLiteSpeed Tech // bandwidth is correct. 5265392f7a3SLiteSpeed Tech expected_bytes_acked = minmax_get(&bbr->bbr_max_bandwidth) 5275392f7a3SLiteSpeed Tech * (ack_time - bbr->bbr_aggregation_epoch_start_time); 5285392f7a3SLiteSpeed Tech 5295392f7a3SLiteSpeed Tech // Reset the current aggregation epoch as soon as the ack arrival rate is 5305392f7a3SLiteSpeed Tech // less than or equal to the max bandwidth. 5315392f7a3SLiteSpeed Tech if (bbr->bbr_aggregation_epoch_bytes <= expected_bytes_acked) 5325392f7a3SLiteSpeed Tech { 5335392f7a3SLiteSpeed Tech // Reset to start measuring a new aggregation epoch. 5345392f7a3SLiteSpeed Tech bbr->bbr_aggregation_epoch_bytes = newly_acked_bytes; 5355392f7a3SLiteSpeed Tech bbr->bbr_aggregation_epoch_start_time = ack_time; 5365392f7a3SLiteSpeed Tech return 0; 5375392f7a3SLiteSpeed Tech } 5385392f7a3SLiteSpeed Tech 5395392f7a3SLiteSpeed Tech // Compute how many extra bytes were delivered vs max bandwidth. 5405392f7a3SLiteSpeed Tech // Include the bytes most recently acknowledged to account for stretch acks. 5415392f7a3SLiteSpeed Tech bbr->bbr_aggregation_epoch_bytes += newly_acked_bytes; 5425392f7a3SLiteSpeed Tech diff = bbr->bbr_aggregation_epoch_bytes - expected_bytes_acked; 5435392f7a3SLiteSpeed Tech minmax_upmax(&bbr->bbr_max_ack_height, bbr->bbr_round_count, diff); 5445392f7a3SLiteSpeed Tech return diff; 5455392f7a3SLiteSpeed Tech} 5465392f7a3SLiteSpeed Tech 5475392f7a3SLiteSpeed Tech 5485392f7a3SLiteSpeed Tech/* See BbrSender::UpdateGainCyclePhase() */ 5495392f7a3SLiteSpeed Techstatic void 5505392f7a3SLiteSpeed Techupdate_gain_cycle_phase (struct lsquic_bbr *bbr, uint64_t bytes_in_flight) 5515392f7a3SLiteSpeed Tech{ 5525392f7a3SLiteSpeed Tech const uint64_t prior_in_flight = bbr->bbr_ack_state.in_flight; 5535392f7a3SLiteSpeed Tech const lsquic_time_t now = bbr->bbr_ack_state.ack_time; 5545392f7a3SLiteSpeed Tech // In most cases, the cycle is advanced after an RTT passes. 5555392f7a3SLiteSpeed Tech int should_advance_gain_cycling 5565392f7a3SLiteSpeed Tech = now - bbr->bbr_last_cycle_start > get_min_rtt(bbr); 5575392f7a3SLiteSpeed Tech 5585392f7a3SLiteSpeed Tech // If the pacing gain is above 1.0, the connection is trying to probe the 5595392f7a3SLiteSpeed Tech // bandwidth by increasing the number of bytes in flight to at least 5605392f7a3SLiteSpeed Tech // pacing_gain * BDP. Make sure that it actually reaches the target, as 5615392f7a3SLiteSpeed Tech // long as there are no losses suggesting that the buffers are not able to 5625392f7a3SLiteSpeed Tech // hold that much. 5635392f7a3SLiteSpeed Tech if (bbr->bbr_pacing_gain > 1.0 5645392f7a3SLiteSpeed Tech && !bbr->bbr_ack_state.has_losses 5655392f7a3SLiteSpeed Tech && prior_in_flight < get_target_cwnd(bbr, bbr->bbr_pacing_gain)) 5665392f7a3SLiteSpeed Tech should_advance_gain_cycling = 0; 5675392f7a3SLiteSpeed Tech 5685392f7a3SLiteSpeed Tech /* Several optimizations are possible here: "else if" instead of "if", as 5695392f7a3SLiteSpeed Tech * well as not calling get_target_cwnd() if `should_advance_gain_cycling' 5705392f7a3SLiteSpeed Tech * is already set to the target value. 5715392f7a3SLiteSpeed Tech */ 5725392f7a3SLiteSpeed Tech 5735392f7a3SLiteSpeed Tech // If pacing gain is below 1.0, the connection is trying to drain the extra 5745392f7a3SLiteSpeed Tech // queue which could have been incurred by probing prior to it. If the 5755392f7a3SLiteSpeed Tech // number of bytes in flight falls down to the estimated BDP value earlier, 5765392f7a3SLiteSpeed Tech // conclude that the queue has been successfully drained and exit this cycle 5775392f7a3SLiteSpeed Tech // early. 5785392f7a3SLiteSpeed Tech if (bbr->bbr_pacing_gain < 1.0 5795392f7a3SLiteSpeed Tech && bytes_in_flight <= get_target_cwnd(bbr, 1)) 5805392f7a3SLiteSpeed Tech should_advance_gain_cycling = 1; 5815392f7a3SLiteSpeed Tech 5825392f7a3SLiteSpeed Tech if (should_advance_gain_cycling) 5835392f7a3SLiteSpeed Tech { 5845392f7a3SLiteSpeed Tech bbr->bbr_cycle_current_offset = 5855392f7a3SLiteSpeed Tech (bbr->bbr_cycle_current_offset + 1) % kGainCycleLength; 5865392f7a3SLiteSpeed Tech bbr->bbr_last_cycle_start = now; 5875392f7a3SLiteSpeed Tech // Stay in low gain mode until the target BDP is hit. Low gain mode 5885392f7a3SLiteSpeed Tech // will be exited immediately when the target BDP is achieved. 5895392f7a3SLiteSpeed Tech if ((bbr->bbr_flags & BBR_FLAG_DRAIN_TO_TARGET) 5905392f7a3SLiteSpeed Tech && bbr->bbr_pacing_gain < 1 5915392f7a3SLiteSpeed Tech && kPacingGain[bbr->bbr_cycle_current_offset] == 1 5925392f7a3SLiteSpeed Tech && bytes_in_flight > get_target_cwnd(bbr, 1)) 5935392f7a3SLiteSpeed Tech return; 5945392f7a3SLiteSpeed Tech bbr->bbr_pacing_gain = kPacingGain[bbr->bbr_cycle_current_offset]; 5955392f7a3SLiteSpeed Tech LSQ_DEBUG("advanced gain cycle, pacing gain set to %.2f", 5965392f7a3SLiteSpeed Tech bbr->bbr_pacing_gain); 5975392f7a3SLiteSpeed Tech } 5985392f7a3SLiteSpeed Tech} 5995392f7a3SLiteSpeed Tech 6005392f7a3SLiteSpeed Tech 6015392f7a3SLiteSpeed Tech/* BbrSender::InRecovery() */ 6025392f7a3SLiteSpeed Techstatic int 6035392f7a3SLiteSpeed Techin_recovery (const struct lsquic_bbr *bbr) 6045392f7a3SLiteSpeed Tech{ 6055392f7a3SLiteSpeed Tech return bbr->bbr_recovery_state != BBR_RS_NOT_IN_RECOVERY; 6065392f7a3SLiteSpeed Tech} 6075392f7a3SLiteSpeed Tech 6085392f7a3SLiteSpeed Tech 6095392f7a3SLiteSpeed Tech/* See BbrSender::CheckIfFullBandwidthReached() */ 6105392f7a3SLiteSpeed Techstatic void 6115392f7a3SLiteSpeed Techcheck_if_full_bw_reached (struct lsquic_bbr *bbr) 6125392f7a3SLiteSpeed Tech{ 6135392f7a3SLiteSpeed Tech struct bandwidth target, bw; 6145392f7a3SLiteSpeed Tech 6155392f7a3SLiteSpeed Tech if (bbr->bbr_flags & BBR_FLAG_LAST_SAMPLE_APP_LIMITED) 6165392f7a3SLiteSpeed Tech { 6175392f7a3SLiteSpeed Tech LSQ_DEBUG("last sample app limited: full BW not reached"); 6185392f7a3SLiteSpeed Tech return; 6195392f7a3SLiteSpeed Tech } 6205392f7a3SLiteSpeed Tech 6215392f7a3SLiteSpeed Tech target = BW_TIMES(&bbr->bbr_bw_at_last_round, kStartupGrowthTarget); 6225392f7a3SLiteSpeed Tech bw = BW(minmax_get(&bbr->bbr_max_bandwidth)); 6235392f7a3SLiteSpeed Tech if (BW_VALUE(&bw) >= BW_VALUE(&target)) 6245392f7a3SLiteSpeed Tech { 6255392f7a3SLiteSpeed Tech bbr->bbr_bw_at_last_round = bw; 6265392f7a3SLiteSpeed Tech bbr->bbr_round_wo_bw_gain = 0; 6275392f7a3SLiteSpeed Tech if (bbr->bbr_flags & BBR_FLAG_EXPIRE_ACK_AGG_IN_STARTUP) 6285392f7a3SLiteSpeed Tech // Expire old excess delivery measurements now that bandwidth 6295392f7a3SLiteSpeed Tech // increased. 6305392f7a3SLiteSpeed Tech minmax_reset(&bbr->bbr_max_ack_height, 6315392f7a3SLiteSpeed Tech ((struct minmax_sample) { bbr->bbr_round_count, 0, })); 6325392f7a3SLiteSpeed Tech LSQ_DEBUG("BW estimate %"PRIu64"bps greater than or equal to target " 6335392f7a3SLiteSpeed Tech "%"PRIu64"bps: full BW not reached", 6345392f7a3SLiteSpeed Tech BW_VALUE(&bw), BW_VALUE(&target)); 6355392f7a3SLiteSpeed Tech return; 6365392f7a3SLiteSpeed Tech } 6375392f7a3SLiteSpeed Tech 6385392f7a3SLiteSpeed Tech ++bbr->bbr_round_wo_bw_gain; 6395392f7a3SLiteSpeed Tech if ((bbr->bbr_round_wo_bw_gain >= bbr->bbr_num_startup_rtts) 6405392f7a3SLiteSpeed Tech || ((bbr->bbr_flags & BBR_FLAG_EXIT_STARTUP_ON_LOSS) 6415392f7a3SLiteSpeed Tech && in_recovery(bbr))) 6425392f7a3SLiteSpeed Tech { 6435392f7a3SLiteSpeed Tech assert(bbr->bbr_flags & BBR_FLAG_HAS_NON_APP_LIMITED); /* DCHECK */ 6445392f7a3SLiteSpeed Tech bbr->bbr_flags |= BBR_FLAG_IS_AT_FULL_BANDWIDTH; 6455392f7a3SLiteSpeed Tech LSQ_DEBUG("reached full BW"); 6465392f7a3SLiteSpeed Tech } 6475392f7a3SLiteSpeed Tech else 6485392f7a3SLiteSpeed Tech LSQ_DEBUG("rounds w/o gain: %u, full BW not reached", 6495392f7a3SLiteSpeed Tech bbr->bbr_round_wo_bw_gain); 6505392f7a3SLiteSpeed Tech} 6515392f7a3SLiteSpeed Tech 6525392f7a3SLiteSpeed Tech 6535392f7a3SLiteSpeed Tech/* See BbrSender::OnExitStartup */ 6545392f7a3SLiteSpeed Techstatic void 6555392f7a3SLiteSpeed Techon_exit_startup (struct lsquic_bbr *bbr, lsquic_time_t now) 6565392f7a3SLiteSpeed Tech{ 6575392f7a3SLiteSpeed Tech assert(bbr->bbr_mode == BBR_MODE_STARTUP); 6585392f7a3SLiteSpeed Tech /* Apparently this method is just to update stats, something that we 6595392f7a3SLiteSpeed Tech * don't do yet. 6605392f7a3SLiteSpeed Tech */ 6615392f7a3SLiteSpeed Tech} 6625392f7a3SLiteSpeed Tech 6635392f7a3SLiteSpeed Tech 6645392f7a3SLiteSpeed Tech/* See BbrSender::EnterProbeBandwidthMode */ 6655392f7a3SLiteSpeed Techstatic void 6665392f7a3SLiteSpeed Techenter_probe_bw_mode (struct lsquic_bbr *bbr, lsquic_time_t now) 6675392f7a3SLiteSpeed Tech{ 6685392f7a3SLiteSpeed Tech set_mode(bbr, BBR_MODE_PROBE_BW); 6695392f7a3SLiteSpeed Tech bbr->bbr_cwnd_gain = kCwndGain; 6705392f7a3SLiteSpeed Tech 6715392f7a3SLiteSpeed Tech // Pick a random offset for the gain cycle out of {0, 2..7} range. 1 is 6725392f7a3SLiteSpeed Tech // excluded because in that case increased gain and decreased gain would not 6735392f7a3SLiteSpeed Tech // follow each other. 6745392f7a3SLiteSpeed Tech bbr->bbr_cycle_current_offset = rand() % (kGainCycleLength - 1); 6755392f7a3SLiteSpeed Tech if (bbr->bbr_cycle_current_offset >= 1) 6765392f7a3SLiteSpeed Tech ++bbr->bbr_cycle_current_offset; 6775392f7a3SLiteSpeed Tech 6785392f7a3SLiteSpeed Tech bbr->bbr_last_cycle_start = now; 6795392f7a3SLiteSpeed Tech bbr->bbr_pacing_gain = kPacingGain[bbr->bbr_cycle_current_offset]; 6805392f7a3SLiteSpeed Tech} 6815392f7a3SLiteSpeed Tech 6825392f7a3SLiteSpeed Tech 6835392f7a3SLiteSpeed Tech/* See BbrSender::EnterStartupMode */ 6845392f7a3SLiteSpeed Techstatic void 6855392f7a3SLiteSpeed Techenter_startup_mode (struct lsquic_bbr *bbr, lsquic_time_t now) 6865392f7a3SLiteSpeed Tech{ 6875392f7a3SLiteSpeed Tech set_mode(bbr, BBR_MODE_STARTUP); 6885392f7a3SLiteSpeed Tech set_startup_values(bbr); 6895392f7a3SLiteSpeed Tech} 6905392f7a3SLiteSpeed Tech 6915392f7a3SLiteSpeed Tech 6925392f7a3SLiteSpeed Tech/* See BbrSender::MaybeExitStartupOrDrain() */ 6935392f7a3SLiteSpeed Techstatic void 6945392f7a3SLiteSpeed Techmaybe_exit_startup_or_drain (struct lsquic_bbr *bbr, lsquic_time_t now, 6955392f7a3SLiteSpeed Tech uint64_t bytes_in_flight) 6965392f7a3SLiteSpeed Tech{ 6975392f7a3SLiteSpeed Tech uint64_t target_cwnd; 6985392f7a3SLiteSpeed Tech 6995392f7a3SLiteSpeed Tech if (bbr->bbr_mode == BBR_MODE_STARTUP 7005392f7a3SLiteSpeed Tech && (bbr->bbr_flags & BBR_FLAG_IS_AT_FULL_BANDWIDTH)) 7015392f7a3SLiteSpeed Tech { 7025392f7a3SLiteSpeed Tech on_exit_startup(bbr, now); 7035392f7a3SLiteSpeed Tech set_mode(bbr, BBR_MODE_DRAIN); 7045392f7a3SLiteSpeed Tech bbr->bbr_pacing_gain = bbr->bbr_drain_gain; 7055392f7a3SLiteSpeed Tech bbr->bbr_cwnd_gain = bbr->bbr_high_cwnd_gain; 7065392f7a3SLiteSpeed Tech } 7075392f7a3SLiteSpeed Tech 7085392f7a3SLiteSpeed Tech if (bbr->bbr_mode == BBR_MODE_DRAIN) 7095392f7a3SLiteSpeed Tech { 7105392f7a3SLiteSpeed Tech target_cwnd = get_target_cwnd(bbr, 1); 7115392f7a3SLiteSpeed Tech LSQ_DEBUG("%s: bytes in flight: %"PRIu64"; target cwnd: %"PRIu64, 7125392f7a3SLiteSpeed Tech __func__, bytes_in_flight, target_cwnd); 7135392f7a3SLiteSpeed Tech if (bytes_in_flight <= target_cwnd) 7145392f7a3SLiteSpeed Tech enter_probe_bw_mode(bbr, now); 7155392f7a3SLiteSpeed Tech } 7165392f7a3SLiteSpeed Tech} 7175392f7a3SLiteSpeed Tech 7185392f7a3SLiteSpeed Tech 7195392f7a3SLiteSpeed Techstatic int 7205392f7a3SLiteSpeed Techin_slow_start (const struct lsquic_bbr *bbr) 7215392f7a3SLiteSpeed Tech{ 7225392f7a3SLiteSpeed Tech return bbr->bbr_mode == BBR_MODE_STARTUP; 7235392f7a3SLiteSpeed Tech} 7245392f7a3SLiteSpeed Tech 7255392f7a3SLiteSpeed Tech 7265392f7a3SLiteSpeed Tech/* See QuicByteCount BbrSender::ProbeRttCongestionWindow() */ 7275392f7a3SLiteSpeed Techstatic uint64_t 7285392f7a3SLiteSpeed Techget_probe_rtt_cwnd (const struct lsquic_bbr *bbr) 7295392f7a3SLiteSpeed Tech{ 7305392f7a3SLiteSpeed Tech if (bbr->bbr_flags & BBR_FLAG_PROBE_RTT_BASED_ON_BDP) 7315392f7a3SLiteSpeed Tech return get_target_cwnd(bbr, kModerateProbeRttMultiplier); 7325392f7a3SLiteSpeed Tech else 7335392f7a3SLiteSpeed Tech return bbr->bbr_min_cwnd; 7345392f7a3SLiteSpeed Tech} 7355392f7a3SLiteSpeed Tech 7365392f7a3SLiteSpeed Tech 7375392f7a3SLiteSpeed Techstatic uint64_t 7385392f7a3SLiteSpeed Techlsquic_bbr_get_cwnd (void *cong_ctl) 7395392f7a3SLiteSpeed Tech{ 7405392f7a3SLiteSpeed Tech struct lsquic_bbr *const bbr = cong_ctl; 7415392f7a3SLiteSpeed Tech uint64_t cwnd; 7425392f7a3SLiteSpeed Tech 7435392f7a3SLiteSpeed Tech if (bbr->bbr_mode == BBR_MODE_PROBE_RTT) 7445392f7a3SLiteSpeed Tech cwnd = get_probe_rtt_cwnd(bbr); 7455392f7a3SLiteSpeed Tech else if (in_recovery(bbr) && 7465392f7a3SLiteSpeed Tech !((bbr->bbr_flags & BBR_FLAG_RATE_BASED_STARTUP) 7475392f7a3SLiteSpeed Tech && bbr->bbr_mode == BBR_MODE_STARTUP)) 7485392f7a3SLiteSpeed Tech cwnd = MIN(bbr->bbr_cwnd, bbr->bbr_recovery_window); 7495392f7a3SLiteSpeed Tech else 7505392f7a3SLiteSpeed Tech cwnd = bbr->bbr_cwnd; 7515392f7a3SLiteSpeed Tech 7525392f7a3SLiteSpeed Tech return cwnd; 7535392f7a3SLiteSpeed Tech} 7545392f7a3SLiteSpeed Tech 7555392f7a3SLiteSpeed Tech 7565392f7a3SLiteSpeed Tech/* See BbrSender::MaybeEnterOrExitProbeRtt */ 7575392f7a3SLiteSpeed Techstatic void 7585392f7a3SLiteSpeed Techmaybe_enter_or_exit_probe_rtt (struct lsquic_bbr *bbr, lsquic_time_t now, 7595392f7a3SLiteSpeed Tech int is_round_start, int min_rtt_expired, uint64_t bytes_in_flight) 7605392f7a3SLiteSpeed Tech{ 7615392f7a3SLiteSpeed Tech if (min_rtt_expired 7625392f7a3SLiteSpeed Tech && !(bbr->bbr_flags & BBR_FLAG_EXITING_QUIESCENCE) 7635392f7a3SLiteSpeed Tech && bbr->bbr_mode != BBR_MODE_PROBE_RTT) 7645392f7a3SLiteSpeed Tech { 7655392f7a3SLiteSpeed Tech if (in_slow_start(bbr)) 7665392f7a3SLiteSpeed Tech on_exit_startup(bbr, now); 7675392f7a3SLiteSpeed Tech set_mode(bbr, BBR_MODE_PROBE_RTT); 7685392f7a3SLiteSpeed Tech bbr->bbr_pacing_gain = 1; 7695392f7a3SLiteSpeed Tech // Do not decide on the time to exit PROBE_RTT until the 7705392f7a3SLiteSpeed Tech // |bytes_in_flight| is at the target small value. 7715392f7a3SLiteSpeed Tech bbr->bbr_exit_probe_rtt_at = 0; 7725392f7a3SLiteSpeed Tech } 7735392f7a3SLiteSpeed Tech 7745392f7a3SLiteSpeed Tech if (bbr->bbr_mode == BBR_MODE_PROBE_RTT) 7755392f7a3SLiteSpeed Tech { 7765392f7a3SLiteSpeed Tech lsquic_bw_sampler_app_limited(&bbr->bbr_bw_sampler); 7775392f7a3SLiteSpeed Tech LSQ_DEBUG("%s: exit probe at: %"PRIu64"; now: %"PRIu64 7785392f7a3SLiteSpeed Tech "; round start: %d; round passed: %d; rtt: %"PRIu64" usec", 7795392f7a3SLiteSpeed Tech __func__, bbr->bbr_exit_probe_rtt_at, now, is_round_start, 7805392f7a3SLiteSpeed Tech !!(bbr->bbr_flags & BBR_FLAG_PROBE_RTT_ROUND_PASSED), 7815392f7a3SLiteSpeed Tech lsquic_rtt_stats_get_min_rtt(bbr->bbr_rtt_stats)); 7825392f7a3SLiteSpeed Tech if (bbr->bbr_exit_probe_rtt_at == 0) 7835392f7a3SLiteSpeed Tech { 7845392f7a3SLiteSpeed Tech // If the window has reached the appropriate size, schedule exiting 7855392f7a3SLiteSpeed Tech // PROBE_RTT. The CWND during PROBE_RTT is 7865392f7a3SLiteSpeed Tech // kMinimumCongestionWindow, but we allow an extra packet since QUIC 7875392f7a3SLiteSpeed Tech // checks CWND before sending a packet. 7885392f7a3SLiteSpeed Tech if (bytes_in_flight 7895392f7a3SLiteSpeed Tech < get_probe_rtt_cwnd(bbr) + kMaxOutgoingPacketSize) 7905392f7a3SLiteSpeed Tech { 7915392f7a3SLiteSpeed Tech bbr->bbr_exit_probe_rtt_at = now + kProbeRttTime; 7925392f7a3SLiteSpeed Tech bbr->bbr_flags &= ~BBR_FLAG_PROBE_RTT_ROUND_PASSED; 7935392f7a3SLiteSpeed Tech } 7945392f7a3SLiteSpeed Tech } 7955392f7a3SLiteSpeed Tech else 7965392f7a3SLiteSpeed Tech { 7975392f7a3SLiteSpeed Tech if (is_round_start) 7985392f7a3SLiteSpeed Tech bbr->bbr_flags |= BBR_FLAG_PROBE_RTT_ROUND_PASSED; 7995392f7a3SLiteSpeed Tech if (now >= bbr->bbr_exit_probe_rtt_at 8005392f7a3SLiteSpeed Tech && (bbr->bbr_flags & BBR_FLAG_PROBE_RTT_ROUND_PASSED)) 8015392f7a3SLiteSpeed Tech { 8025392f7a3SLiteSpeed Tech bbr->bbr_min_rtt_timestamp = now; 8035392f7a3SLiteSpeed Tech if (!(bbr->bbr_flags & BBR_FLAG_IS_AT_FULL_BANDWIDTH)) 8045392f7a3SLiteSpeed Tech enter_startup_mode(bbr, now); 8055392f7a3SLiteSpeed Tech else 8065392f7a3SLiteSpeed Tech enter_probe_bw_mode(bbr, now); 8075392f7a3SLiteSpeed Tech } 8085392f7a3SLiteSpeed Tech } 8095392f7a3SLiteSpeed Tech } 8105392f7a3SLiteSpeed Tech 8115392f7a3SLiteSpeed Tech bbr->bbr_flags &= ~BBR_FLAG_EXITING_QUIESCENCE; 8125392f7a3SLiteSpeed Tech} 8135392f7a3SLiteSpeed Tech 8145392f7a3SLiteSpeed Tech 8155392f7a3SLiteSpeed Tech/* See BbrSender::CalculatePacingRate */ 8165392f7a3SLiteSpeed Techstatic void 8175392f7a3SLiteSpeed Techcalculate_pacing_rate (struct lsquic_bbr *bbr) 8185392f7a3SLiteSpeed Tech{ 8195392f7a3SLiteSpeed Tech struct bandwidth bw, target_rate; 8205392f7a3SLiteSpeed Tech 8215392f7a3SLiteSpeed Tech bw = BW(minmax_get(&bbr->bbr_max_bandwidth)); 8225392f7a3SLiteSpeed Tech if (BW_IS_ZERO(&bw)) 8235392f7a3SLiteSpeed Tech return; 8245392f7a3SLiteSpeed Tech 8255392f7a3SLiteSpeed Tech LSQ_DEBUG("BW estimate: %"PRIu64, BW_VALUE(&bw)); 8265392f7a3SLiteSpeed Tech 8275392f7a3SLiteSpeed Tech target_rate = BW_TIMES(&bw, bbr->bbr_pacing_gain); 8285392f7a3SLiteSpeed Tech if (bbr->bbr_flags & BBR_FLAG_IS_AT_FULL_BANDWIDTH) 8295392f7a3SLiteSpeed Tech { 8305392f7a3SLiteSpeed Tech bbr->bbr_pacing_rate = target_rate; 8315392f7a3SLiteSpeed Tech return; 8325392f7a3SLiteSpeed Tech } 8335392f7a3SLiteSpeed Tech 8345392f7a3SLiteSpeed Tech // Pace at the rate of initial_window / RTT as soon as RTT measurements are 8355392f7a3SLiteSpeed Tech // available. 8365392f7a3SLiteSpeed Tech if (BW_IS_ZERO(&bbr->bbr_pacing_rate) 8375392f7a3SLiteSpeed Tech && 0 != lsquic_rtt_stats_get_min_rtt(bbr->bbr_rtt_stats)) 8385392f7a3SLiteSpeed Tech { 8395392f7a3SLiteSpeed Tech bbr->bbr_pacing_rate = BW_FROM_BYTES_AND_DELTA( 8405392f7a3SLiteSpeed Tech bbr->bbr_init_cwnd, 8415392f7a3SLiteSpeed Tech lsquic_rtt_stats_get_min_rtt(bbr->bbr_rtt_stats)); 8425392f7a3SLiteSpeed Tech return; 8435392f7a3SLiteSpeed Tech } 8445392f7a3SLiteSpeed Tech 8455392f7a3SLiteSpeed Tech // Slow the pacing rate in STARTUP once loss has ever been detected. 8465392f7a3SLiteSpeed Tech const int has_ever_detected_loss = bbr->bbr_end_recovery_at != 0; 8475392f7a3SLiteSpeed Tech if (has_ever_detected_loss 8485392f7a3SLiteSpeed Tech && (bbr->bbr_flags & (BBR_FLAG_SLOWER_STARTUP 8495392f7a3SLiteSpeed Tech |BBR_FLAG_HAS_NON_APP_LIMITED)) 8505392f7a3SLiteSpeed Tech == (BBR_FLAG_SLOWER_STARTUP|BBR_FLAG_HAS_NON_APP_LIMITED)) 8515392f7a3SLiteSpeed Tech { 8525392f7a3SLiteSpeed Tech bbr->bbr_pacing_rate = BW_TIMES(&bw, kStartupAfterLossGain); 8535392f7a3SLiteSpeed Tech return; 8545392f7a3SLiteSpeed Tech } 8555392f7a3SLiteSpeed Tech 8565392f7a3SLiteSpeed Tech // Slow the pacing rate in STARTUP by the bytes_lost / CWND. 8575392f7a3SLiteSpeed Tech if (startup_rate_reduction_multiplier_ != 0 8585392f7a3SLiteSpeed Tech && has_ever_detected_loss 8595392f7a3SLiteSpeed Tech && (bbr->bbr_flags & BBR_FLAG_HAS_NON_APP_LIMITED)) 8605392f7a3SLiteSpeed Tech { 8615392f7a3SLiteSpeed Tech bbr->bbr_pacing_rate = BW_TIMES(&target_rate, 8625392f7a3SLiteSpeed Tech (1 - (bbr->bbr_startup_bytes_lost 8635392f7a3SLiteSpeed Tech * startup_rate_reduction_multiplier_ * 1.0f 8645392f7a3SLiteSpeed Tech / bbr->bbr_cwnd_gain))); 8655392f7a3SLiteSpeed Tech // Ensure the pacing rate doesn't drop below the startup growth target 8665392f7a3SLiteSpeed Tech // times the bandwidth estimate. 8675392f7a3SLiteSpeed Tech if (BW_VALUE(&bbr->bbr_pacing_rate) 8685392f7a3SLiteSpeed Tech < BW_VALUE(&bw) * kStartupGrowthTarget) 8695392f7a3SLiteSpeed Tech bbr->bbr_pacing_rate = BW_TIMES(&bw, kStartupGrowthTarget); 8705392f7a3SLiteSpeed Tech return; 8715392f7a3SLiteSpeed Tech } 8725392f7a3SLiteSpeed Tech 8735392f7a3SLiteSpeed Tech // Do not decrease the pacing rate during startup. 8745392f7a3SLiteSpeed Tech if (BW_VALUE(&bbr->bbr_pacing_rate) < BW_VALUE(&target_rate)) 8755392f7a3SLiteSpeed Tech bbr->bbr_pacing_rate = target_rate; 8765392f7a3SLiteSpeed Tech} 8775392f7a3SLiteSpeed Tech 8785392f7a3SLiteSpeed Tech 8795392f7a3SLiteSpeed Tech/* See BbrSender::CalculateCongestionWindow */ 8805392f7a3SLiteSpeed Techstatic void 8815392f7a3SLiteSpeed Techcalculate_cwnd (struct lsquic_bbr *bbr, uint64_t bytes_acked, 8825392f7a3SLiteSpeed Tech uint64_t excess_acked) 8835392f7a3SLiteSpeed Tech{ 8845392f7a3SLiteSpeed Tech if (bbr->bbr_mode == BBR_MODE_PROBE_RTT) 8855392f7a3SLiteSpeed Tech return; 8865392f7a3SLiteSpeed Tech 8875392f7a3SLiteSpeed Tech uint64_t target_window = get_target_cwnd(bbr, bbr->bbr_cwnd_gain); 8885392f7a3SLiteSpeed Tech if (bbr->bbr_flags & BBR_FLAG_IS_AT_FULL_BANDWIDTH) 8895392f7a3SLiteSpeed Tech // Add the max recently measured ack aggregation to CWND. 8905392f7a3SLiteSpeed Tech target_window += minmax_get(&bbr->bbr_max_ack_height); 8915392f7a3SLiteSpeed Tech else if (bbr->bbr_flags & BBR_FLAG_ENABLE_ACK_AGG_IN_STARTUP) 8925392f7a3SLiteSpeed Tech // Add the most recent excess acked. Because CWND never decreases in 8935392f7a3SLiteSpeed Tech // STARTUP, this will automatically create a very localized max filter. 8945392f7a3SLiteSpeed Tech target_window += excess_acked; 8955392f7a3SLiteSpeed Tech 8965392f7a3SLiteSpeed Tech // Instead of immediately setting the target CWND as the new one, BBR grows 8975392f7a3SLiteSpeed Tech // the CWND towards |target_window| by only increasing it |bytes_acked| at a 8985392f7a3SLiteSpeed Tech // time. 8995392f7a3SLiteSpeed Tech const int add_bytes_acked = 9005392f7a3SLiteSpeed Tech !FLAGS_quic_bbr_no_bytes_acked_in_startup_recovery || !in_recovery(bbr); 9015392f7a3SLiteSpeed Tech if (bbr->bbr_flags & BBR_FLAG_IS_AT_FULL_BANDWIDTH) 9025392f7a3SLiteSpeed Tech bbr->bbr_cwnd = MIN(target_window, bbr->bbr_cwnd + bytes_acked); 9035392f7a3SLiteSpeed Tech else if (add_bytes_acked && 9045392f7a3SLiteSpeed Tech (bbr->bbr_cwnd_gain < target_window || 9055392f7a3SLiteSpeed Tech lsquic_bw_sampler_total_acked(&bbr->bbr_bw_sampler) 9065392f7a3SLiteSpeed Tech < bbr->bbr_init_cwnd)) 9075392f7a3SLiteSpeed Tech // If the connection is not yet out of startup phase, do not decrease 9085392f7a3SLiteSpeed Tech // the window. 9095392f7a3SLiteSpeed Tech bbr->bbr_cwnd += bytes_acked; 9105392f7a3SLiteSpeed Tech 9115392f7a3SLiteSpeed Tech // Enforce the limits on the congestion window. 9125392f7a3SLiteSpeed Tech if (bbr->bbr_cwnd < bbr->bbr_min_cwnd) 9135392f7a3SLiteSpeed Tech bbr->bbr_cwnd = bbr->bbr_min_cwnd; 9145392f7a3SLiteSpeed Tech else if (bbr->bbr_cwnd > bbr->bbr_max_cwnd) 9155392f7a3SLiteSpeed Tech { 9165392f7a3SLiteSpeed Tech LSQ_DEBUG("exceed max cwnd"); 9175392f7a3SLiteSpeed Tech bbr->bbr_cwnd = bbr->bbr_max_cwnd; 9185392f7a3SLiteSpeed Tech } 9195392f7a3SLiteSpeed Tech} 9205392f7a3SLiteSpeed Tech 9215392f7a3SLiteSpeed Tech 9225392f7a3SLiteSpeed Tech/* See BbrSender::CalculateRecoveryWindow */ 9235392f7a3SLiteSpeed Techstatic void 9245392f7a3SLiteSpeed Techcalculate_recovery_window (struct lsquic_bbr *bbr, uint64_t bytes_acked, 9255392f7a3SLiteSpeed Tech uint64_t bytes_lost, uint64_t bytes_in_flight) 9265392f7a3SLiteSpeed Tech{ 9275392f7a3SLiteSpeed Tech if ((bbr->bbr_flags & BBR_FLAG_RATE_BASED_STARTUP) 9285392f7a3SLiteSpeed Tech && bbr->bbr_mode == BBR_MODE_STARTUP) 9295392f7a3SLiteSpeed Tech return; 9305392f7a3SLiteSpeed Tech 9315392f7a3SLiteSpeed Tech if (bbr->bbr_recovery_state == BBR_RS_NOT_IN_RECOVERY) 9325392f7a3SLiteSpeed Tech return; 9335392f7a3SLiteSpeed Tech 9345392f7a3SLiteSpeed Tech // Set up the initial recovery window. 9355392f7a3SLiteSpeed Tech if (bbr->bbr_recovery_window == 0) 9365392f7a3SLiteSpeed Tech { 9375392f7a3SLiteSpeed Tech bbr->bbr_recovery_window = bytes_in_flight + bytes_acked; 9385392f7a3SLiteSpeed Tech bbr->bbr_recovery_window = MAX(bbr->bbr_min_cwnd, 9395392f7a3SLiteSpeed Tech bbr->bbr_recovery_window); 9405392f7a3SLiteSpeed Tech return; 9415392f7a3SLiteSpeed Tech } 9425392f7a3SLiteSpeed Tech 9435392f7a3SLiteSpeed Tech // Remove losses from the recovery window, while accounting for a potential 9445392f7a3SLiteSpeed Tech // integer underflow. 9455392f7a3SLiteSpeed Tech if (bbr->bbr_recovery_window >= bytes_lost) 9465392f7a3SLiteSpeed Tech bbr->bbr_recovery_window -= bytes_lost; 9475392f7a3SLiteSpeed Tech else 9485392f7a3SLiteSpeed Tech bbr->bbr_recovery_window = kMaxSegmentSize; 9495392f7a3SLiteSpeed Tech 9505392f7a3SLiteSpeed Tech // In CONSERVATION mode, just subtracting losses is sufficient. In GROWTH, 9515392f7a3SLiteSpeed Tech // release additional |bytes_acked| to achieve a slow-start-like behavior. 9525392f7a3SLiteSpeed Tech if (bbr->bbr_recovery_state == BBR_RS_GROWTH) 9535392f7a3SLiteSpeed Tech bbr->bbr_recovery_window += bytes_acked; 9545392f7a3SLiteSpeed Tech 9555392f7a3SLiteSpeed Tech // Sanity checks. Ensure that we always allow to send at least an MSS or 9565392f7a3SLiteSpeed Tech // |bytes_acked| in response, whichever is larger. 9575392f7a3SLiteSpeed Tech bbr->bbr_recovery_window = MAX(bbr->bbr_recovery_window, 9585392f7a3SLiteSpeed Tech bytes_in_flight + bytes_acked); 9595392f7a3SLiteSpeed Tech if (FLAG_quic_bbr_one_mss_conservation) 9605392f7a3SLiteSpeed Tech bbr->bbr_recovery_window = MAX(bbr->bbr_recovery_window, 9615392f7a3SLiteSpeed Tech bytes_in_flight + kMaxSegmentSize); 9625392f7a3SLiteSpeed Tech bbr->bbr_recovery_window = MAX(bbr->bbr_recovery_window, bbr->bbr_min_cwnd); 9635392f7a3SLiteSpeed Tech} 9645392f7a3SLiteSpeed Tech 9655392f7a3SLiteSpeed Tech 9665392f7a3SLiteSpeed Techstatic void 9675392f7a3SLiteSpeed Techlsquic_bbr_end_ack (void *cong_ctl, uint64_t in_flight) 9685392f7a3SLiteSpeed Tech{ 9695392f7a3SLiteSpeed Tech struct lsquic_bbr *const bbr = cong_ctl; 9705392f7a3SLiteSpeed Tech int is_round_start, min_rtt_expired; 9715392f7a3SLiteSpeed Tech uint64_t bytes_acked, excess_acked, bytes_lost; 9725392f7a3SLiteSpeed Tech 9735392f7a3SLiteSpeed Tech assert(bbr->bbr_flags & BBR_FLAG_IN_ACK); 9745392f7a3SLiteSpeed Tech bbr->bbr_flags &= ~BBR_FLAG_IN_ACK; 9755392f7a3SLiteSpeed Tech 9765392f7a3SLiteSpeed Tech LSQ_DEBUG("end_ack; mode: %s; in_flight: %"PRIu64, mode2str[bbr->bbr_mode], 9775392f7a3SLiteSpeed Tech in_flight); 9785392f7a3SLiteSpeed Tech 9795392f7a3SLiteSpeed Tech bytes_acked = lsquic_bw_sampler_total_acked(&bbr->bbr_bw_sampler) 9805392f7a3SLiteSpeed Tech - bbr->bbr_ack_state.total_bytes_acked_before; 9815392f7a3SLiteSpeed Tech if (bbr->bbr_ack_state.acked_bytes) 9825392f7a3SLiteSpeed Tech { 9835392f7a3SLiteSpeed Tech is_round_start = bbr->bbr_ack_state.max_packno 9845392f7a3SLiteSpeed Tech > bbr->bbr_current_round_trip_end 9855392f7a3SLiteSpeed Tech || !is_valid_packno(bbr->bbr_current_round_trip_end); 9865392f7a3SLiteSpeed Tech if (is_round_start) 9875392f7a3SLiteSpeed Tech { 9885392f7a3SLiteSpeed Tech ++bbr->bbr_round_count; 9895392f7a3SLiteSpeed Tech bbr->bbr_current_round_trip_end = bbr->bbr_last_sent_packno; 9905392f7a3SLiteSpeed Tech LSQ_DEBUG("up round count to %"PRIu64"; new rt end: %"PRIu64, 9915392f7a3SLiteSpeed Tech bbr->bbr_round_count, bbr->bbr_current_round_trip_end); 9925392f7a3SLiteSpeed Tech } 9935392f7a3SLiteSpeed Tech min_rtt_expired = update_bandwidth_and_min_rtt(bbr); 9945392f7a3SLiteSpeed Tech update_recovery_state(bbr, is_round_start); 9955392f7a3SLiteSpeed Tech excess_acked = update_ack_aggregation_bytes(bbr, bytes_acked); 9965392f7a3SLiteSpeed Tech } 9975392f7a3SLiteSpeed Tech else 9985392f7a3SLiteSpeed Tech { 9995392f7a3SLiteSpeed Tech is_round_start = 0; 10005392f7a3SLiteSpeed Tech min_rtt_expired = 0; 10015392f7a3SLiteSpeed Tech excess_acked = 0; 10025392f7a3SLiteSpeed Tech } 10035392f7a3SLiteSpeed Tech 10045392f7a3SLiteSpeed Tech if (bbr->bbr_mode == BBR_MODE_PROBE_BW) 10055392f7a3SLiteSpeed Tech update_gain_cycle_phase(bbr, in_flight); 10065392f7a3SLiteSpeed Tech 10075392f7a3SLiteSpeed Tech if (is_round_start && !(bbr->bbr_flags & BBR_FLAG_IS_AT_FULL_BANDWIDTH)) 10085392f7a3SLiteSpeed Tech check_if_full_bw_reached(bbr); 10095392f7a3SLiteSpeed Tech 10105392f7a3SLiteSpeed Tech maybe_exit_startup_or_drain(bbr, bbr->bbr_ack_state.ack_time, in_flight); 10115392f7a3SLiteSpeed Tech 10125392f7a3SLiteSpeed Tech maybe_enter_or_exit_probe_rtt(bbr, bbr->bbr_ack_state.ack_time, 10135392f7a3SLiteSpeed Tech is_round_start, min_rtt_expired, in_flight); 10145392f7a3SLiteSpeed Tech 10155392f7a3SLiteSpeed Tech // Calculate number of packets acked and lost. 10165392f7a3SLiteSpeed Tech bytes_lost = bbr->bbr_ack_state.lost_bytes; 10175392f7a3SLiteSpeed Tech 10185392f7a3SLiteSpeed Tech // After the model is updated, recalculate the pacing rate and congestion 10195392f7a3SLiteSpeed Tech // window. 10205392f7a3SLiteSpeed Tech calculate_pacing_rate(bbr); 10215392f7a3SLiteSpeed Tech calculate_cwnd(bbr, bytes_acked, excess_acked); 10225392f7a3SLiteSpeed Tech calculate_recovery_window(bbr, bytes_acked, bytes_lost, in_flight); 10235392f7a3SLiteSpeed Tech 10245392f7a3SLiteSpeed Tech /* We don't need to clean up BW sampler */ 10255392f7a3SLiteSpeed Tech} 10265392f7a3SLiteSpeed Tech 10275392f7a3SLiteSpeed Tech 10285392f7a3SLiteSpeed Techstatic void 10295392f7a3SLiteSpeed Techlsquic_bbr_cleanup (void *cong_ctl) 10305392f7a3SLiteSpeed Tech{ 10315392f7a3SLiteSpeed Tech struct lsquic_bbr *const bbr = cong_ctl; 10325392f7a3SLiteSpeed Tech 1033a6cdaedbSDmitri Tikhonov lsquic_bw_sampler_cleanup(&bbr->bbr_bw_sampler); 10345392f7a3SLiteSpeed Tech LSQ_DEBUG("cleanup"); 10355392f7a3SLiteSpeed Tech} 10365392f7a3SLiteSpeed Tech 10375392f7a3SLiteSpeed Tech 10385392f7a3SLiteSpeed Techstatic void 10395392f7a3SLiteSpeed Techlsquic_bbr_loss (void *cong_ctl) { /* Noop */ } 10405392f7a3SLiteSpeed Tech 10415392f7a3SLiteSpeed Tech 10425392f7a3SLiteSpeed Techstatic void 10435392f7a3SLiteSpeed Techlsquic_bbr_timeout (void *cong_ctl) { /* Noop */ } 10445392f7a3SLiteSpeed Tech 10455392f7a3SLiteSpeed Tech 10465392f7a3SLiteSpeed Techconst struct cong_ctl_if lsquic_cong_bbr_if = 10475392f7a3SLiteSpeed Tech{ 10485392f7a3SLiteSpeed Tech .cci_ack = lsquic_bbr_ack, 10495392f7a3SLiteSpeed Tech .cci_begin_ack = lsquic_bbr_begin_ack, 10505392f7a3SLiteSpeed Tech .cci_end_ack = lsquic_bbr_end_ack, 10515392f7a3SLiteSpeed Tech .cci_cleanup = lsquic_bbr_cleanup, 10525392f7a3SLiteSpeed Tech .cci_get_cwnd = lsquic_bbr_get_cwnd, 10535392f7a3SLiteSpeed Tech .cci_init = lsquic_bbr_init, 10545392f7a3SLiteSpeed Tech .cci_pacing_rate = lsquic_bbr_pacing_rate, 10555392f7a3SLiteSpeed Tech .cci_loss = lsquic_bbr_loss, 10565392f7a3SLiteSpeed Tech .cci_lost = lsquic_bbr_lost, 10575392f7a3SLiteSpeed Tech .cci_timeout = lsquic_bbr_timeout, 10585392f7a3SLiteSpeed Tech .cci_sent = lsquic_bbr_sent, 10595392f7a3SLiteSpeed Tech .cci_was_quiet = lsquic_bbr_was_quiet, 10605392f7a3SLiteSpeed Tech}; 1061