lsquic_bbr.h revision 10c41073 
1/* Copyright (c) 2017 - 2020 LiteSpeed Technologies Inc.  See LICENSE. */
2#ifndef LSQUIC_BBR_H
3#define LSQUIC_BBR_H
4
5/* Our BBR implementation is copied from Chromium with some modifications.
6 * Besides the obvious translation from C++ to C, differences are:
7 *
8 *  1. Instead of OnCongestionEvent(), the ACK information is processed at the
9 *     same time as the ACK itself using cci_begin_ack(), cci_ack(), and
10 *     cci_end_ack() methods.  This is done to fit with the flow in
11 *     lsquic_send_ctl_got_ack().
12 *
13 *  2. The bandwidth sampler does not use a hash.  Instead, the sample
14 *     information is attached directly to the packet via po_bwp_state.
15 *
16 * In this file and in lsquic_bbr.c, C++-style comments are those copied
17 * verbatim from Chromium.  C-style comments are ours.
18 *
19 * Code is based on bbr_sender.cc 1a578a76c16abc942205a1a80584a288c262d03a in
20 * the "quiche" repository.  (Not to be confused with Cloudflare's "quiche".)
21 *
22 * The BBR I-D is here:
23 *  https://tools.ietf.org/html/draft-cardwell-iccrg-bbr-congestion-control-00
24 *
25 * As for quiche, see
26 *  http://www.bernstein-plus-sons.com/RPDEQ.html
27 *
28 * Chromium copyright notice follows.
29 */
30// Copyright 2016 The Chromium Authors. All rights reserved.
31// Use of this source code is governed by a BSD-style license that can be
32// found in the LICENSE.chrome file.
33
34struct lsquic_bbr
35{
36    const struct lsquic_conn_public  *bbr_conn_pub;
37
38    enum bbr_mode
39    {
40        BBR_MODE_STARTUP,
41        BBR_MODE_DRAIN,
42        BBR_MODE_PROBE_BW,
43        BBR_MODE_PROBE_RTT,
44    }                           bbr_mode;
45
46    enum
47    {
48        BBR_RS_NOT_IN_RECOVERY,
49        BBR_RS_CONSERVATION,
50        BBR_RS_GROWTH,
51    }                           bbr_recovery_state;
52
53    enum
54    {
55        BBR_FLAG_IN_ACK                  = 1 << 0,   /* cci_begin_ack() has been called */
56        BBR_FLAG_LAST_SAMPLE_APP_LIMITED = 1 << 1,
57        BBR_FLAG_HAS_NON_APP_LIMITED     = 1 << 2,
58        BBR_FLAG_APP_LIMITED_SINCE_LAST_PROBE_RTT
59                                         = 1 << 3,
60        BBR_FLAG_PROBE_RTT_DISABLED_IF_APP_LIMITED
61                                         = 1 << 4,
62        BBR_FLAG_PROBE_RTT_SKIPPED_IF_SIMILAR_RTT
63                                         = 1 << 5,
64        BBR_FLAG_EXIT_STARTUP_ON_LOSS    = 1 << 6,
65        BBR_FLAG_IS_AT_FULL_BANDWIDTH    = 1 << 7,
66        BBR_FLAG_EXITING_QUIESCENCE      = 1 << 8,
67        BBR_FLAG_PROBE_RTT_ROUND_PASSED  = 1 << 9,
68        BBR_FLAG_FLEXIBLE_APP_LIMITED    = 1 << 10,
69        // If true, will not exit low gain mode until bytes_in_flight drops
70        // below BDP or it's time for high gain mode.
71        BBR_FLAG_DRAIN_TO_TARGET         = 1 << 11,
72        // When true, expire the windowed ack aggregation values in STARTUP
73        // when bandwidth increases more than 25%.
74        BBR_FLAG_EXPIRE_ACK_AGG_IN_STARTUP
75                                         = 1 << 12,
76        // If true, use a CWND of 0.75*BDP during probe_rtt instead of 4
77        // packets.
78        BBR_FLAG_PROBE_RTT_BASED_ON_BDP  = 1 << 13,
79        // When true, pace at 1.5x and disable packet conservation in STARTUP.
80        BBR_FLAG_SLOWER_STARTUP          = 1 << 14,
81        // When true, add the most recent ack aggregation measurement during STARTUP.
82        BBR_FLAG_ENABLE_ACK_AGG_IN_STARTUP
83                                         = 1 << 15,
84        // When true, disables packet conservation in STARTUP.
85        BBR_FLAG_RATE_BASED_STARTUP      = 1 << 16,
86    }                           bbr_flags;
87
88    // Number of round-trips in PROBE_BW mode, used for determining the current
89    // pacing gain cycle.
90    unsigned                    bbr_cycle_current_offset;
91
92    const struct lsquic_rtt_stats
93                               *bbr_rtt_stats;
94
95    struct bw_sampler           bbr_bw_sampler;
96
97    /*
98     " BBR.BtlBwFilter: The max filter used to estimate BBR.BtlBw.
99     */
100    struct minmax               bbr_max_bandwidth;
101
102    // Tracks the maximum number of bytes acked faster than the sending rate.
103    struct minmax               bbr_max_ack_height;
104
105    // The initial value of the bbr_cwnd.
106    uint64_t                    bbr_init_cwnd;
107    // The smallest value the bbr_cwnd can achieve.
108    uint64_t                    bbr_min_cwnd;
109    // The largest value the bbr_cwnd can achieve.
110    uint64_t                    bbr_max_cwnd;
111    // The maximum allowed number of bytes in flight.
112    uint64_t                    bbr_cwnd;
113
114    // The time this aggregation started and the number of bytes acked during it.
115    lsquic_time_t               bbr_aggregation_epoch_start_time;
116    uint64_t                    bbr_aggregation_epoch_bytes;
117
118    lsquic_packno_t             bbr_last_sent_packno;
119    lsquic_packno_t             bbr_current_round_trip_end;
120
121    // Receiving acknowledgement of a packet after |bbr_end_recovery_at| will
122    // cause BBR to exit the recovery mode.  A value above zero indicates at
123    // least one loss has been detected, so it must not be set back to zero.
124    lsquic_packno_t             bbr_end_recovery_at;
125
126    /*
127     " BBR.round_count: Count of packet-timed round trips.
128     */
129    uint64_t                    bbr_round_count;
130
131    /* Not documented in the draft: */
132    uint64_t                    bbr_full_bw;
133
134    /* Not documented in the draft: */
135    uint64_t                    bbr_full_bw_count;
136
137    /*
138     " BBR.pacing_rate: The current pacing rate for a BBR flow, which
139     " controls inter-packet spacing.
140     */
141    struct bandwidth            bbr_pacing_rate;
142
143    // Sum of bytes lost in STARTUP.
144    uint64_t                    bbr_startup_bytes_lost;
145
146    /*
147     " BBR.pacing_gain: The dynamic gain factor used to scale BBR.BtlBw to
148     " produce BBR.pacing_rate.
149     */
150    float                       bbr_pacing_gain;
151
152    // The pacing gain applied during the STARTUP phase.
153    float                       bbr_high_gain;
154
155    // The CWND gain applied during the STARTUP phase.
156    float                       bbr_high_cwnd_gain;
157
158    // The pacing gain applied during the DRAIN phase.
159    float                       bbr_drain_gain;
160
161    // The number of RTTs to stay in STARTUP mode.  Defaults to 3.
162    unsigned                    bbr_num_startup_rtts;
163
164    // Number of rounds during which there was no significant bandwidth
165    // increase.
166    unsigned                    bbr_round_wo_bw_gain;
167
168    /*
169     " BBR.cwnd_gain: The dynamic gain factor used to scale the estimated
170     " BDP to produce a congestion window (cwnd).
171     */
172    float                       bbr_cwnd_gain;
173
174    // The bandwidth compared to which the increase is measured.
175    struct bandwidth            bbr_bw_at_last_round;
176
177    // The time at which the last pacing gain cycle was started.
178    lsquic_time_t               bbr_last_cycle_start;
179
180    // Time at which PROBE_RTT has to be exited.  Setting it to zero indicates
181    // that the time is yet unknown as the number of packets in flight has not
182    // reached the required value.
183    lsquic_time_t               bbr_exit_probe_rtt_at;
184
185    lsquic_time_t               bbr_min_rtt_since_last_probe;
186    lsquic_time_t               bbr_min_rtt;
187    lsquic_time_t               bbr_min_rtt_timestamp;
188
189    // A window used to limit the number of bytes in flight during loss recovery
190    uint64_t                    bbr_recovery_window;
191
192    /* Accumulate information from a single ACK.  Gets processed when
193     * cci_end_ack() is called.
194     */
195    struct
196    {
197        TAILQ_HEAD(, bw_sample) samples;
198        lsquic_time_t       ack_time;
199        lsquic_packno_t     max_packno;
200        uint64_t            acked_bytes;
201        uint64_t            lost_bytes;
202        uint64_t            total_bytes_acked_before;
203        uint64_t            in_flight;
204        int                 has_losses;
205    }                           bbr_ack_state;
206};
207
208extern const struct cong_ctl_if lsquic_cong_bbr_if;
209
210#endif
211