/* Bottleneck Bandwidth and RTT (BBR) congestion control
*
* BBR congestion control computes the sending rate based on the delivery
* rate (throughput) estimated from ACKs. In a nutshell:
*
* On each ACK, update our model of the network path:
* bottleneck_bandwidth = windowed_max(delivered / elapsed, 10 round trips)
* min_rtt = windowed_min(rtt, 10 seconds)
* pacing_rate = pacing_gain * bottleneck_bandwidth
* cwnd = max(cwnd_gain * bottleneck_bandwidth * min_rtt, 4)
*
* The core algorithm does not react directly to packet losses or delays,
* although BBR may adjust the size of next send per ACK when loss is
* observed, or adjust the sending rate if it estimates there is a
* traffic policer, in order to keep the drop rate reasonable.
*
* Here is a state transition diagram for BBR:
*
* |
* V
* +---> STARTUP ----+
* | | |
* | V |
* | DRAIN ----+
* | | |
* | V |
* +---> PROBE_BW ----+
* | ^ | |
* | | | |
* | +----+ |
* | |
* +---- PROBE_RTT <--+
*
* A BBR flow starts in STARTUP, and ramps up its sending rate quickly.
* When it estimates the pipe is full, it enters DRAIN to drain the queue.
* In steady state a BBR flow only uses PROBE_BW and PROBE_RTT.
* A long-lived BBR flow spends the vast majority of its time remaining
* (repeatedly) in PROBE_BW, fully probing and utilizing the pipe's bandwidth
* in a fair manner, with a small, bounded queue. *If* a flow has been
* continuously sending for the entire min_rtt window, and hasn't seen an RTT
* sample that matches or decreases its min_rtt estimate for 10 seconds, then
* it briefly enters PROBE_RTT to cut inflight to a minimum value to re-probe
* the path's two-way propagation delay (min_rtt). When exiting PROBE_RTT, if
* we estimated that we reached the full bw of the pipe then we enter PROBE_BW;
* otherwise we enter STARTUP to try to fill the pipe.
*
* BBR is described in detail in:
* "BBR: Congestion-Based Congestion Control",
* Neal Cardwell, Yuchung Cheng, C. Stephen Gunn, Soheil Hassas Yeganeh,
* Van Jacobson. ACM Queue, Vol. 14 No. 5, September-October 2016.
*
* There is a public e-mail list for discussing BBR development and testing:
* https://groups.google.com/forum/#!forum/bbr-dev
*
* NOTE: BBR might be used with the fq qdisc ("man tc-fq") with pacing enabled,
* otherwise TCP stack falls back to an internal pacing using one high
* resolution timer per TCP socket and may use more resources.
*/
#include <linux/module.h>
#include <net/tcp.h>
#include <linux/inet_diag.h>
#include <linux/inet.h>
#include <linux/random.h>
#include <linux/win_minmax.h>
/* Scale factor for rate in pkt/uSec unit to avoid truncation in bandwidth
* estimation. The rate unit ~= (1500 bytes / 1 usec / 2^24) ~= 715 bps.
* This handles bandwidths from 0.06pps (715bps) to 256Mpps (3Tbps) in a u32.
* Since the minimum window is >=4 packets, the lower bound isn't
* an issue. The upper bound isn't an issue with existing technologies.
*/
#define BW_SCALE 24
#define BW_UNIT (1 << BW_SCALE)
#define BBR_SCALE 8 /* scaling factor for fractions in BBR (e.g. gains) */
#define BBR_UNIT (1 << BBR_SCALE)
/* BBR has the following modes for deciding how fast to send: */
enum bbr_mode {
BBR_STARTUP, /* ramp up sending rate rapidly to fill pipe */
BBR_DRAIN, /* drain any queue created during startup */
BBR_PROBE_BW, /* discover, share bw: pace around estimated bw */
BBR_PROBE_RTT, /* cut inflight to min to probe min_rtt */
};
/* BBR congestion control block */
struct bbr {
u32 min_rtt_us; /* min RTT in min_rtt_win_sec window */
u32 min_rtt_stamp; /* timestamp of min_rtt_us */
u32 probe_rtt_done_stamp; /* end time for BBR_PROBE_RTT mode */
struct minmax bw; /* Max recent delivery rate in pkts/uS << 24 */
u32 rtt_cnt; /* count of packet-timed rounds elapsed */
u32 next_rtt_delivered; /* scb->tx.delivered at end of round */
u64 cycle_mstamp; /* time of this cycle phase start */
u32 mode:3, /* current bbr_mode in state machine */
prev_ca_state:3, /* CA state on previous ACK */
packet_conservation:1, /* use packet conservation? */
round_start:1, /* start of packet-timed tx->ack round? */
idle_restart:1, /* restarting after idle? */
probe_rtt_round_done:1, /* a BBR_PROBE_RTT round at 4 pkts? */
unused:13,
lt_is_sampling:1, /* taking long-term ("LT") samples now? */
lt_rtt_cnt:7, /* round trips in long-term interval */
lt_use_bw:1; /* use lt_bw as our bw estimate? */
u32 lt_bw; /* LT est delivery rate in pkts/uS << 24 */
u32 lt_last_delivered; /* LT intvl start: tp->delivered */
u32 lt_last_stamp; /* LT intvl start: tp->delivered_mstamp */
u32 lt_last_lost; /* LT intvl start: tp->lost */
u32 pacing_gain:10, /* current gain for setting pacing rate */
cwnd_gain:10, /* current gain for setting cwnd */
full_bw_reached:1, /* reached full bw in Startup? */
full_bw_cnt:2, /* number of rounds without large bw gains */
cycle_idx:3, /* current index in pacing_gain cycle array */
has_seen_rtt:1, /* have we seen an RTT sample yet? */
unused_b:5;
u32 prior_cwnd; /* prior cwnd upon entering loss recovery */
u32 full_bw; /* recent bw, to estimate if pipe is full */
/* For tracking ACK aggregation: */
u64 ack_epoch_mstamp; /* start of ACK sampling epoch */
u16 extra_acked[2]; /* max excess data ACKed in epoch */
u32 ack_epoch_acked:20, /* packets (S)ACKed in sampling epoch */
extra_acked_win_rtts:5, /* age of extra_acked, in round trips */
extra_acked_win_idx:1, /* current index in extra_acked array */
unused_c:6;
};
#define CYCLE_LEN 8 /* number of phases in a pacing gain cycle */
/* Window length of bw filter (in rounds): */
static const int bbr_bw_rtts = CYCLE_LEN + 2;
/* Window length of min_rtt filter (in sec): */
static const u32 bbr_min_rtt_win_sec = 10;
/* Minimum time (in ms) spent at bbr_cwnd_min_target in BBR_PROBE_RTT mode: */
static const u32 bbr_probe_rtt_mode_ms = 200;
/* Skip TSO below the following bandwidth (bits/sec): */
static const int bbr_min_tso_rate = 1200000;