1 /* Bottleneck Bandwidth and RTT (BBR) congestion control
3 * BBR congestion control computes the sending rate based on the delivery
4 * rate (throughput) estimated from ACKs. In a nutshell:
6 * On each ACK, update our model of the network path:
7 * bottleneck_bandwidth = windowed_max(delivered / elapsed, 10 round trips)
8 * min_rtt = windowed_min(rtt, 10 seconds)
9 * pacing_rate = pacing_gain * bottleneck_bandwidth
10 * cwnd = max(cwnd_gain * bottleneck_bandwidth * min_rtt, 4)
12 * The core algorithm does not react directly to packet losses or delays,
13 * although BBR may adjust the size of next send per ACK when loss is
14 * observed, or adjust the sending rate if it estimates there is a
15 * traffic policer, in order to keep the drop rate reasonable.
17 * Here is a state transition diagram for BBR:
27 * +---> PROBE_BW ----+
32 * +---- PROBE_RTT <--+
34 * A BBR flow starts in STARTUP, and ramps up its sending rate quickly.
35 * When it estimates the pipe is full, it enters DRAIN to drain the queue.
36 * In steady state a BBR flow only uses PROBE_BW and PROBE_RTT.
37 * A long-lived BBR flow spends the vast majority of its time remaining
38 * (repeatedly) in PROBE_BW, fully probing and utilizing the pipe's bandwidth
39 * in a fair manner, with a small, bounded queue. *If* a flow has been
40 * continuously sending for the entire min_rtt window, and hasn't seen an RTT
41 * sample that matches or decreases its min_rtt estimate for 10 seconds, then
42 * it briefly enters PROBE_RTT to cut inflight to a minimum value to re-probe
43 * the path's two-way propagation delay (min_rtt). When exiting PROBE_RTT, if
44 * we estimated that we reached the full bw of the pipe then we enter PROBE_BW;
45 * otherwise we enter STARTUP to try to fill the pipe.
47 * BBR is described in detail in:
48 * "BBR: Congestion-Based Congestion Control",
49 * Neal Cardwell, Yuchung Cheng, C. Stephen Gunn, Soheil Hassas Yeganeh,
50 * Van Jacobson. ACM Queue, Vol. 14 No. 5, September-October 2016.
52 * There is a public e-mail list for discussing BBR development and testing:
53 * https://groups.google.com/forum/#!forum/bbr-dev
55 * NOTE: BBR might be used with the fq qdisc ("man tc-fq") with pacing enabled,
56 * otherwise TCP stack falls back to an internal pacing using one high
57 * resolution timer per TCP socket and may use more resources.
59 #include <linux/module.h>
61 #include <linux/inet_diag.h>
62 #include <linux/inet.h>
63 #include <linux/random.h>
64 #include <linux/win_minmax.h>
66 /* Scale factor for rate in pkt/uSec unit to avoid truncation in bandwidth
67 * estimation. The rate unit ~= (1500 bytes / 1 usec / 2^24) ~= 715 bps.
68 * This handles bandwidths from 0.06pps (715bps) to 256Mpps (3Tbps) in a u32.
69 * Since the minimum window is >=4 packets, the lower bound isn't
70 * an issue. The upper bound isn't an issue with existing technologies.
73 #define BW_UNIT (1 << BW_SCALE)
75 #define BBR_SCALE 8 /* scaling factor for fractions in BBR (e.g. gains) */
76 #define BBR_UNIT (1 << BBR_SCALE)
78 /* BBR has the following modes for deciding how fast to send: */
80 BBR_STARTUP
, /* ramp up sending rate rapidly to fill pipe */
81 BBR_DRAIN
, /* drain any queue created during startup */
82 BBR_PROBE_BW
, /* discover, share bw: pace around estimated bw */
83 BBR_PROBE_RTT
, /* cut inflight to min to probe min_rtt */
86 /* BBR congestion control block */
88 u32 min_rtt_us
; /* min RTT in min_rtt_win_sec window */
89 u32 min_rtt_stamp
; /* timestamp of min_rtt_us */
90 u32 probe_rtt_done_stamp
; /* end time for BBR_PROBE_RTT mode */
91 struct minmax bw
; /* Max recent delivery rate in pkts/uS << 24 */
92 u32 rtt_cnt
; /* count of packet-timed rounds elapsed */
93 u32 next_rtt_delivered
; /* scb->tx.delivered at end of round */
94 u64 cycle_mstamp
; /* time of this cycle phase start */
95 u32 mode
:3, /* current bbr_mode in state machine */
96 prev_ca_state
:3, /* CA state on previous ACK */
97 packet_conservation
:1, /* use packet conservation? */
98 restore_cwnd
:1, /* decided to revert cwnd to old value */
99 round_start
:1, /* start of packet-timed tx->ack round? */
100 tso_segs_goal
:7, /* segments we want in each skb we send */
101 idle_restart
:1, /* restarting after idle? */
102 probe_rtt_round_done
:1, /* a BBR_PROBE_RTT round at 4 pkts? */
104 lt_is_sampling
:1, /* taking long-term ("LT") samples now? */
105 lt_rtt_cnt
:7, /* round trips in long-term interval */
106 lt_use_bw
:1; /* use lt_bw as our bw estimate? */
107 u32 lt_bw
; /* LT est delivery rate in pkts/uS << 24 */
108 u32 lt_last_delivered
; /* LT intvl start: tp->delivered */
109 u32 lt_last_stamp
; /* LT intvl start: tp->delivered_mstamp */
110 u32 lt_last_lost
; /* LT intvl start: tp->lost */
111 u32 pacing_gain
:10, /* current gain for setting pacing rate */
112 cwnd_gain
:10, /* current gain for setting cwnd */
113 full_bw_cnt
:3, /* number of rounds without large bw gains */
114 cycle_idx
:3, /* current index in pacing_gain cycle array */
115 has_seen_rtt
:1, /* have we seen an RTT sample yet? */
117 u32 prior_cwnd
; /* prior cwnd upon entering loss recovery */
118 u32 full_bw
; /* recent bw, to estimate if pipe is full */
121 #define CYCLE_LEN 8 /* number of phases in a pacing gain cycle */
123 /* Window length of bw filter (in rounds): */
124 static const int bbr_bw_rtts
= CYCLE_LEN
+ 2;
125 /* Window length of min_rtt filter (in sec): */
126 static const u32 bbr_min_rtt_win_sec
= 10;
127 /* Minimum time (in ms) spent at bbr_cwnd_min_target in BBR_PROBE_RTT mode: */
128 static const u32 bbr_probe_rtt_mode_ms
= 200;
129 /* Skip TSO below the following bandwidth (bits/sec): */
130 static const int bbr_min_tso_rate
= 1200000;
132 /* We use a high_gain value of 2/ln(2) because it's the smallest pacing gain
133 * that will allow a smoothly increasing pacing rate that will double each RTT
134 * and send the same number of packets per RTT that an un-paced, slow-starting
135 * Reno or CUBIC flow would:
137 static const int bbr_high_gain
= BBR_UNIT
* 2885 / 1000 + 1;
138 /* The pacing gain of 1/high_gain in BBR_DRAIN is calculated to typically drain
139 * the queue created in BBR_STARTUP in a single round:
141 static const int bbr_drain_gain
= BBR_UNIT
* 1000 / 2885;
142 /* The gain for deriving steady-state cwnd tolerates delayed/stretched ACKs: */
143 static const int bbr_cwnd_gain
= BBR_UNIT
* 2;
144 /* The pacing_gain values for the PROBE_BW gain cycle, to discover/share bw: */
145 static const int bbr_pacing_gain
[] = {
146 BBR_UNIT
* 5 / 4, /* probe for more available bw */
147 BBR_UNIT
* 3 / 4, /* drain queue and/or yield bw to other flows */
148 BBR_UNIT
, BBR_UNIT
, BBR_UNIT
, /* cruise at 1.0*bw to utilize pipe, */
149 BBR_UNIT
, BBR_UNIT
, BBR_UNIT
/* without creating excess queue... */
151 /* Randomize the starting gain cycling phase over N phases: */
152 static const u32 bbr_cycle_rand
= 7;
154 /* Try to keep at least this many packets in flight, if things go smoothly. For
155 * smooth functioning, a sliding window protocol ACKing every other packet
156 * needs at least 4 packets in flight:
158 static const u32 bbr_cwnd_min_target
= 4;
160 /* To estimate if BBR_STARTUP mode (i.e. high_gain) has filled pipe... */
161 /* If bw has increased significantly (1.25x), there may be more bw available: */
162 static const u32 bbr_full_bw_thresh
= BBR_UNIT
* 5 / 4;
163 /* But after 3 rounds w/o significant bw growth, estimate pipe is full: */
164 static const u32 bbr_full_bw_cnt
= 3;
166 /* "long-term" ("LT") bandwidth estimator parameters... */
167 /* The minimum number of rounds in an LT bw sampling interval: */
168 static const u32 bbr_lt_intvl_min_rtts
= 4;
169 /* If lost/delivered ratio > 20%, interval is "lossy" and we may be policed: */
170 static const u32 bbr_lt_loss_thresh
= 50;
171 /* If 2 intervals have a bw ratio <= 1/8, their bw is "consistent": */
172 static const u32 bbr_lt_bw_ratio
= BBR_UNIT
/ 8;
173 /* If 2 intervals have a bw diff <= 4 Kbit/sec their bw is "consistent": */
174 static const u32 bbr_lt_bw_diff
= 4000 / 8;
175 /* If we estimate we're policed, use lt_bw for this many round trips: */
176 static const u32 bbr_lt_bw_max_rtts
= 48;
178 /* Do we estimate that STARTUP filled the pipe? */
179 static bool bbr_full_bw_reached(const struct sock
*sk
)
181 const struct bbr
*bbr
= inet_csk_ca(sk
);
183 return bbr
->full_bw_cnt
>= bbr_full_bw_cnt
;
186 /* Return the windowed max recent bandwidth sample, in pkts/uS << BW_SCALE. */
187 static u32
bbr_max_bw(const struct sock
*sk
)
189 struct bbr
*bbr
= inet_csk_ca(sk
);
191 return minmax_get(&bbr
->bw
);
194 /* Return the estimated bandwidth of the path, in pkts/uS << BW_SCALE. */
195 static u32
bbr_bw(const struct sock
*sk
)
197 struct bbr
*bbr
= inet_csk_ca(sk
);
199 return bbr
->lt_use_bw
? bbr
->lt_bw
: bbr_max_bw(sk
);
202 /* Return rate in bytes per second, optionally with a gain.
203 * The order here is chosen carefully to avoid overflow of u64. This should
204 * work for input rates of up to 2.9Tbit/sec and gain of 2.89x.
206 static u64
bbr_rate_bytes_per_sec(struct sock
*sk
, u64 rate
, int gain
)
208 rate
*= tcp_mss_to_mtu(sk
, tcp_sk(sk
)->mss_cache
);
211 rate
*= USEC_PER_SEC
;
212 return rate
>> BW_SCALE
;
215 /* Convert a BBR bw and gain factor to a pacing rate in bytes per second. */
216 static u32
bbr_bw_to_pacing_rate(struct sock
*sk
, u32 bw
, int gain
)
220 rate
= bbr_rate_bytes_per_sec(sk
, rate
, gain
);
221 rate
= min_t(u64
, rate
, sk
->sk_max_pacing_rate
);
225 /* Initialize pacing rate to: high_gain * init_cwnd / RTT. */
226 static void bbr_init_pacing_rate_from_rtt(struct sock
*sk
)
228 struct tcp_sock
*tp
= tcp_sk(sk
);
229 struct bbr
*bbr
= inet_csk_ca(sk
);
233 if (tp
->srtt_us
) { /* any RTT sample yet? */
234 rtt_us
= max(tp
->srtt_us
>> 3, 1U);
235 bbr
->has_seen_rtt
= 1;
236 } else { /* no RTT sample yet */
237 rtt_us
= USEC_PER_MSEC
; /* use nominal default RTT */
239 bw
= (u64
)tp
->snd_cwnd
* BW_UNIT
;
241 sk
->sk_pacing_rate
= bbr_bw_to_pacing_rate(sk
, bw
, bbr_high_gain
);
244 /* Pace using current bw estimate and a gain factor. In order to help drive the
245 * network toward lower queues while maintaining high utilization and low
246 * latency, the average pacing rate aims to be slightly (~1%) lower than the
247 * estimated bandwidth. This is an important aspect of the design. In this
248 * implementation this slightly lower pacing rate is achieved implicitly by not
249 * including link-layer headers in the packet size used for the pacing rate.
251 static void bbr_set_pacing_rate(struct sock
*sk
, u32 bw
, int gain
)
253 struct tcp_sock
*tp
= tcp_sk(sk
);
254 struct bbr
*bbr
= inet_csk_ca(sk
);
255 u32 rate
= bbr_bw_to_pacing_rate(sk
, bw
, gain
);
257 if (unlikely(!bbr
->has_seen_rtt
&& tp
->srtt_us
))
258 bbr_init_pacing_rate_from_rtt(sk
);
259 if (bbr_full_bw_reached(sk
) || rate
> sk
->sk_pacing_rate
)
260 sk
->sk_pacing_rate
= rate
;
263 /* Return count of segments we want in the skbs we send, or 0 for default. */
264 static u32
bbr_tso_segs_goal(struct sock
*sk
)
266 struct bbr
*bbr
= inet_csk_ca(sk
);
268 return bbr
->tso_segs_goal
;
271 static void bbr_set_tso_segs_goal(struct sock
*sk
)
273 struct tcp_sock
*tp
= tcp_sk(sk
);
274 struct bbr
*bbr
= inet_csk_ca(sk
);
277 min_segs
= sk
->sk_pacing_rate
< (bbr_min_tso_rate
>> 3) ? 1 : 2;
278 bbr
->tso_segs_goal
= min(tcp_tso_autosize(sk
, tp
->mss_cache
, min_segs
),
282 /* Save "last known good" cwnd so we can restore it after losses or PROBE_RTT */
283 static void bbr_save_cwnd(struct sock
*sk
)
285 struct tcp_sock
*tp
= tcp_sk(sk
);
286 struct bbr
*bbr
= inet_csk_ca(sk
);
288 if (bbr
->prev_ca_state
< TCP_CA_Recovery
&& bbr
->mode
!= BBR_PROBE_RTT
)
289 bbr
->prior_cwnd
= tp
->snd_cwnd
; /* this cwnd is good enough */
290 else /* loss recovery or BBR_PROBE_RTT have temporarily cut cwnd */
291 bbr
->prior_cwnd
= max(bbr
->prior_cwnd
, tp
->snd_cwnd
);
294 static void bbr_cwnd_event(struct sock
*sk
, enum tcp_ca_event event
)
296 struct tcp_sock
*tp
= tcp_sk(sk
);
297 struct bbr
*bbr
= inet_csk_ca(sk
);
299 if (event
== CA_EVENT_TX_START
&& tp
->app_limited
) {
300 bbr
->idle_restart
= 1;
301 /* Avoid pointless buffer overflows: pace at est. bw if we don't
302 * need more speed (we're restarting from idle and app-limited).
304 if (bbr
->mode
== BBR_PROBE_BW
)
305 bbr_set_pacing_rate(sk
, bbr_bw(sk
), BBR_UNIT
);
309 /* Find target cwnd. Right-size the cwnd based on min RTT and the
310 * estimated bottleneck bandwidth:
312 * cwnd = bw * min_rtt * gain = BDP * gain
314 * The key factor, gain, controls the amount of queue. While a small gain
315 * builds a smaller queue, it becomes more vulnerable to noise in RTT
316 * measurements (e.g., delayed ACKs or other ACK compression effects). This
317 * noise may cause BBR to under-estimate the rate.
319 * To achieve full performance in high-speed paths, we budget enough cwnd to
320 * fit full-sized skbs in-flight on both end hosts to fully utilize the path:
321 * - one skb in sending host Qdisc,
322 * - one skb in sending host TSO/GSO engine
323 * - one skb being received by receiver host LRO/GRO/delayed-ACK engine
324 * Don't worry, at low rates (bbr_min_tso_rate) this won't bloat cwnd because
325 * in such cases tso_segs_goal is 1. The minimum cwnd is 4 packets,
326 * which allows 2 outstanding 2-packet sequences, to try to keep pipe
327 * full even with ACK-every-other-packet delayed ACKs.
329 static u32
bbr_target_cwnd(struct sock
*sk
, u32 bw
, int gain
)
331 struct bbr
*bbr
= inet_csk_ca(sk
);
335 /* If we've never had a valid RTT sample, cap cwnd at the initial
336 * default. This should only happen when the connection is not using TCP
337 * timestamps and has retransmitted all of the SYN/SYNACK/data packets
338 * ACKed so far. In this case, an RTO can cut cwnd to 1, in which
339 * case we need to slow-start up toward something safe: TCP_INIT_CWND.
341 if (unlikely(bbr
->min_rtt_us
== ~0U)) /* no valid RTT samples yet? */
342 return TCP_INIT_CWND
; /* be safe: cap at default initial cwnd*/
344 w
= (u64
)bw
* bbr
->min_rtt_us
;
346 /* Apply a gain to the given value, then remove the BW_SCALE shift. */
347 cwnd
= (((w
* gain
) >> BBR_SCALE
) + BW_UNIT
- 1) / BW_UNIT
;
349 /* Allow enough full-sized skbs in flight to utilize end systems. */
350 cwnd
+= 3 * bbr
->tso_segs_goal
;
352 /* Reduce delayed ACKs by rounding up cwnd to the next even number. */
353 cwnd
= (cwnd
+ 1) & ~1U;
358 /* An optimization in BBR to reduce losses: On the first round of recovery, we
359 * follow the packet conservation principle: send P packets per P packets acked.
360 * After that, we slow-start and send at most 2*P packets per P packets acked.
361 * After recovery finishes, or upon undo, we restore the cwnd we had when
362 * recovery started (capped by the target cwnd based on estimated BDP).
364 * TODO(ycheng/ncardwell): implement a rate-based approach.
366 static bool bbr_set_cwnd_to_recover_or_restore(
367 struct sock
*sk
, const struct rate_sample
*rs
, u32 acked
, u32
*new_cwnd
)
369 struct tcp_sock
*tp
= tcp_sk(sk
);
370 struct bbr
*bbr
= inet_csk_ca(sk
);
371 u8 prev_state
= bbr
->prev_ca_state
, state
= inet_csk(sk
)->icsk_ca_state
;
372 u32 cwnd
= tp
->snd_cwnd
;
374 /* An ACK for P pkts should release at most 2*P packets. We do this
375 * in two steps. First, here we deduct the number of lost packets.
376 * Then, in bbr_set_cwnd() we slow start up toward the target cwnd.
379 cwnd
= max_t(s32
, cwnd
- rs
->losses
, 1);
381 if (state
== TCP_CA_Recovery
&& prev_state
!= TCP_CA_Recovery
) {
382 /* Starting 1st round of Recovery, so do packet conservation. */
383 bbr
->packet_conservation
= 1;
384 bbr
->next_rtt_delivered
= tp
->delivered
; /* start round now */
385 /* Cut unused cwnd from app behavior, TSQ, or TSO deferral: */
386 cwnd
= tcp_packets_in_flight(tp
) + acked
;
387 } else if (prev_state
>= TCP_CA_Recovery
&& state
< TCP_CA_Recovery
) {
388 /* Exiting loss recovery; restore cwnd saved before recovery. */
389 bbr
->restore_cwnd
= 1;
390 bbr
->packet_conservation
= 0;
392 bbr
->prev_ca_state
= state
;
394 if (bbr
->restore_cwnd
) {
395 /* Restore cwnd after exiting loss recovery or PROBE_RTT. */
396 cwnd
= max(cwnd
, bbr
->prior_cwnd
);
397 bbr
->restore_cwnd
= 0;
400 if (bbr
->packet_conservation
) {
401 *new_cwnd
= max(cwnd
, tcp_packets_in_flight(tp
) + acked
);
402 return true; /* yes, using packet conservation */
408 /* Slow-start up toward target cwnd (if bw estimate is growing, or packet loss
409 * has drawn us down below target), or snap down to target if we're above it.
411 static void bbr_set_cwnd(struct sock
*sk
, const struct rate_sample
*rs
,
412 u32 acked
, u32 bw
, int gain
)
414 struct tcp_sock
*tp
= tcp_sk(sk
);
415 struct bbr
*bbr
= inet_csk_ca(sk
);
416 u32 cwnd
= 0, target_cwnd
= 0;
421 if (bbr_set_cwnd_to_recover_or_restore(sk
, rs
, acked
, &cwnd
))
424 /* If we're below target cwnd, slow start cwnd toward target cwnd. */
425 target_cwnd
= bbr_target_cwnd(sk
, bw
, gain
);
426 if (bbr_full_bw_reached(sk
)) /* only cut cwnd if we filled the pipe */
427 cwnd
= min(cwnd
+ acked
, target_cwnd
);
428 else if (cwnd
< target_cwnd
|| tp
->delivered
< TCP_INIT_CWND
)
430 cwnd
= max(cwnd
, bbr_cwnd_min_target
);
433 tp
->snd_cwnd
= min(cwnd
, tp
->snd_cwnd_clamp
); /* apply global cap */
434 if (bbr
->mode
== BBR_PROBE_RTT
) /* drain queue, refresh min_rtt */
435 tp
->snd_cwnd
= min(tp
->snd_cwnd
, bbr_cwnd_min_target
);
438 /* End cycle phase if it's time and/or we hit the phase's in-flight target. */
439 static bool bbr_is_next_cycle_phase(struct sock
*sk
,
440 const struct rate_sample
*rs
)
442 struct tcp_sock
*tp
= tcp_sk(sk
);
443 struct bbr
*bbr
= inet_csk_ca(sk
);
444 bool is_full_length
=
445 tcp_stamp_us_delta(tp
->delivered_mstamp
, bbr
->cycle_mstamp
) >
449 /* The pacing_gain of 1.0 paces at the estimated bw to try to fully
450 * use the pipe without increasing the queue.
452 if (bbr
->pacing_gain
== BBR_UNIT
)
453 return is_full_length
; /* just use wall clock time */
455 inflight
= rs
->prior_in_flight
; /* what was in-flight before ACK? */
458 /* A pacing_gain > 1.0 probes for bw by trying to raise inflight to at
459 * least pacing_gain*BDP; this may take more than min_rtt if min_rtt is
460 * small (e.g. on a LAN). We do not persist if packets are lost, since
461 * a path with small buffers may not hold that much.
463 if (bbr
->pacing_gain
> BBR_UNIT
)
464 return is_full_length
&&
465 (rs
->losses
|| /* perhaps pacing_gain*BDP won't fit */
466 inflight
>= bbr_target_cwnd(sk
, bw
, bbr
->pacing_gain
));
468 /* A pacing_gain < 1.0 tries to drain extra queue we added if bw
469 * probing didn't find more bw. If inflight falls to match BDP then we
470 * estimate queue is drained; persisting would underutilize the pipe.
472 return is_full_length
||
473 inflight
<= bbr_target_cwnd(sk
, bw
, BBR_UNIT
);
476 static void bbr_advance_cycle_phase(struct sock
*sk
)
478 struct tcp_sock
*tp
= tcp_sk(sk
);
479 struct bbr
*bbr
= inet_csk_ca(sk
);
481 bbr
->cycle_idx
= (bbr
->cycle_idx
+ 1) & (CYCLE_LEN
- 1);
482 bbr
->cycle_mstamp
= tp
->delivered_mstamp
;
483 bbr
->pacing_gain
= bbr_pacing_gain
[bbr
->cycle_idx
];
486 /* Gain cycling: cycle pacing gain to converge to fair share of available bw. */
487 static void bbr_update_cycle_phase(struct sock
*sk
,
488 const struct rate_sample
*rs
)
490 struct bbr
*bbr
= inet_csk_ca(sk
);
492 if ((bbr
->mode
== BBR_PROBE_BW
) && !bbr
->lt_use_bw
&&
493 bbr_is_next_cycle_phase(sk
, rs
))
494 bbr_advance_cycle_phase(sk
);
497 static void bbr_reset_startup_mode(struct sock
*sk
)
499 struct bbr
*bbr
= inet_csk_ca(sk
);
501 bbr
->mode
= BBR_STARTUP
;
502 bbr
->pacing_gain
= bbr_high_gain
;
503 bbr
->cwnd_gain
= bbr_high_gain
;
506 static void bbr_reset_probe_bw_mode(struct sock
*sk
)
508 struct bbr
*bbr
= inet_csk_ca(sk
);
510 bbr
->mode
= BBR_PROBE_BW
;
511 bbr
->pacing_gain
= BBR_UNIT
;
512 bbr
->cwnd_gain
= bbr_cwnd_gain
;
513 bbr
->cycle_idx
= CYCLE_LEN
- 1 - prandom_u32_max(bbr_cycle_rand
);
514 bbr_advance_cycle_phase(sk
); /* flip to next phase of gain cycle */
517 static void bbr_reset_mode(struct sock
*sk
)
519 if (!bbr_full_bw_reached(sk
))
520 bbr_reset_startup_mode(sk
);
522 bbr_reset_probe_bw_mode(sk
);
525 /* Start a new long-term sampling interval. */
526 static void bbr_reset_lt_bw_sampling_interval(struct sock
*sk
)
528 struct tcp_sock
*tp
= tcp_sk(sk
);
529 struct bbr
*bbr
= inet_csk_ca(sk
);
531 bbr
->lt_last_stamp
= div_u64(tp
->delivered_mstamp
, USEC_PER_MSEC
);
532 bbr
->lt_last_delivered
= tp
->delivered
;
533 bbr
->lt_last_lost
= tp
->lost
;
537 /* Completely reset long-term bandwidth sampling. */
538 static void bbr_reset_lt_bw_sampling(struct sock
*sk
)
540 struct bbr
*bbr
= inet_csk_ca(sk
);
544 bbr
->lt_is_sampling
= false;
545 bbr_reset_lt_bw_sampling_interval(sk
);
548 /* Long-term bw sampling interval is done. Estimate whether we're policed. */
549 static void bbr_lt_bw_interval_done(struct sock
*sk
, u32 bw
)
551 struct bbr
*bbr
= inet_csk_ca(sk
);
554 if (bbr
->lt_bw
) { /* do we have bw from a previous interval? */
555 /* Is new bw close to the lt_bw from the previous interval? */
556 diff
= abs(bw
- bbr
->lt_bw
);
557 if ((diff
* BBR_UNIT
<= bbr_lt_bw_ratio
* bbr
->lt_bw
) ||
558 (bbr_rate_bytes_per_sec(sk
, diff
, BBR_UNIT
) <=
560 /* All criteria are met; estimate we're policed. */
561 bbr
->lt_bw
= (bw
+ bbr
->lt_bw
) >> 1; /* avg 2 intvls */
563 bbr
->pacing_gain
= BBR_UNIT
; /* try to avoid drops */
569 bbr_reset_lt_bw_sampling_interval(sk
);
572 /* Token-bucket traffic policers are common (see "An Internet-Wide Analysis of
573 * Traffic Policing", SIGCOMM 2016). BBR detects token-bucket policers and
574 * explicitly models their policed rate, to reduce unnecessary losses. We
575 * estimate that we're policed if we see 2 consecutive sampling intervals with
576 * consistent throughput and high packet loss. If we think we're being policed,
577 * set lt_bw to the "long-term" average delivery rate from those 2 intervals.
579 static void bbr_lt_bw_sampling(struct sock
*sk
, const struct rate_sample
*rs
)
581 struct tcp_sock
*tp
= tcp_sk(sk
);
582 struct bbr
*bbr
= inet_csk_ca(sk
);
587 if (bbr
->lt_use_bw
) { /* already using long-term rate, lt_bw? */
588 if (bbr
->mode
== BBR_PROBE_BW
&& bbr
->round_start
&&
589 ++bbr
->lt_rtt_cnt
>= bbr_lt_bw_max_rtts
) {
590 bbr_reset_lt_bw_sampling(sk
); /* stop using lt_bw */
591 bbr_reset_probe_bw_mode(sk
); /* restart gain cycling */
596 /* Wait for the first loss before sampling, to let the policer exhaust
597 * its tokens and estimate the steady-state rate allowed by the policer.
598 * Starting samples earlier includes bursts that over-estimate the bw.
600 if (!bbr
->lt_is_sampling
) {
603 bbr_reset_lt_bw_sampling_interval(sk
);
604 bbr
->lt_is_sampling
= true;
607 /* To avoid underestimates, reset sampling if we run out of data. */
608 if (rs
->is_app_limited
) {
609 bbr_reset_lt_bw_sampling(sk
);
613 if (bbr
->round_start
)
614 bbr
->lt_rtt_cnt
++; /* count round trips in this interval */
615 if (bbr
->lt_rtt_cnt
< bbr_lt_intvl_min_rtts
)
616 return; /* sampling interval needs to be longer */
617 if (bbr
->lt_rtt_cnt
> 4 * bbr_lt_intvl_min_rtts
) {
618 bbr_reset_lt_bw_sampling(sk
); /* interval is too long */
622 /* End sampling interval when a packet is lost, so we estimate the
623 * policer tokens were exhausted. Stopping the sampling before the
624 * tokens are exhausted under-estimates the policed rate.
629 /* Calculate packets lost and delivered in sampling interval. */
630 lost
= tp
->lost
- bbr
->lt_last_lost
;
631 delivered
= tp
->delivered
- bbr
->lt_last_delivered
;
632 /* Is loss rate (lost/delivered) >= lt_loss_thresh? If not, wait. */
633 if (!delivered
|| (lost
<< BBR_SCALE
) < bbr_lt_loss_thresh
* delivered
)
636 /* Find average delivery rate in this sampling interval. */
637 t
= div_u64(tp
->delivered_mstamp
, USEC_PER_MSEC
) - bbr
->lt_last_stamp
;
639 return; /* interval is less than one ms, so wait */
640 /* Check if can multiply without overflow */
641 if (t
>= ~0U / USEC_PER_MSEC
) {
642 bbr_reset_lt_bw_sampling(sk
); /* interval too long; reset */
646 bw
= (u64
)delivered
* BW_UNIT
;
648 bbr_lt_bw_interval_done(sk
, bw
);
651 /* Estimate the bandwidth based on how fast packets are delivered */
652 static void bbr_update_bw(struct sock
*sk
, const struct rate_sample
*rs
)
654 struct tcp_sock
*tp
= tcp_sk(sk
);
655 struct bbr
*bbr
= inet_csk_ca(sk
);
658 bbr
->round_start
= 0;
659 if (rs
->delivered
< 0 || rs
->interval_us
<= 0)
660 return; /* Not a valid observation */
662 /* See if we've reached the next RTT */
663 if (!before(rs
->prior_delivered
, bbr
->next_rtt_delivered
)) {
664 bbr
->next_rtt_delivered
= tp
->delivered
;
666 bbr
->round_start
= 1;
667 bbr
->packet_conservation
= 0;
670 bbr_lt_bw_sampling(sk
, rs
);
672 /* Divide delivered by the interval to find a (lower bound) bottleneck
673 * bandwidth sample. Delivered is in packets and interval_us in uS and
674 * ratio will be <<1 for most connections. So delivered is first scaled.
676 bw
= (u64
)rs
->delivered
* BW_UNIT
;
677 do_div(bw
, rs
->interval_us
);
679 /* If this sample is application-limited, it is likely to have a very
680 * low delivered count that represents application behavior rather than
681 * the available network rate. Such a sample could drag down estimated
682 * bw, causing needless slow-down. Thus, to continue to send at the
683 * last measured network rate, we filter out app-limited samples unless
684 * they describe the path bw at least as well as our bw model.
686 * So the goal during app-limited phase is to proceed with the best
687 * network rate no matter how long. We automatically leave this
688 * phase when app writes faster than the network can deliver :)
690 if (!rs
->is_app_limited
|| bw
>= bbr_max_bw(sk
)) {
691 /* Incorporate new sample into our max bw filter. */
692 minmax_running_max(&bbr
->bw
, bbr_bw_rtts
, bbr
->rtt_cnt
, bw
);
696 /* Estimate when the pipe is full, using the change in delivery rate: BBR
697 * estimates that STARTUP filled the pipe if the estimated bw hasn't changed by
698 * at least bbr_full_bw_thresh (25%) after bbr_full_bw_cnt (3) non-app-limited
699 * rounds. Why 3 rounds: 1: rwin autotuning grows the rwin, 2: we fill the
700 * higher rwin, 3: we get higher delivery rate samples. Or transient
701 * cross-traffic or radio noise can go away. CUBIC Hystart shares a similar
702 * design goal, but uses delay and inter-ACK spacing instead of bandwidth.
704 static void bbr_check_full_bw_reached(struct sock
*sk
,
705 const struct rate_sample
*rs
)
707 struct bbr
*bbr
= inet_csk_ca(sk
);
710 if (bbr_full_bw_reached(sk
) || !bbr
->round_start
|| rs
->is_app_limited
)
713 bw_thresh
= (u64
)bbr
->full_bw
* bbr_full_bw_thresh
>> BBR_SCALE
;
714 if (bbr_max_bw(sk
) >= bw_thresh
) {
715 bbr
->full_bw
= bbr_max_bw(sk
);
716 bbr
->full_bw_cnt
= 0;
722 /* If pipe is probably full, drain the queue and then enter steady-state. */
723 static void bbr_check_drain(struct sock
*sk
, const struct rate_sample
*rs
)
725 struct bbr
*bbr
= inet_csk_ca(sk
);
727 if (bbr
->mode
== BBR_STARTUP
&& bbr_full_bw_reached(sk
)) {
728 bbr
->mode
= BBR_DRAIN
; /* drain queue we created */
729 bbr
->pacing_gain
= bbr_drain_gain
; /* pace slow to drain */
730 bbr
->cwnd_gain
= bbr_high_gain
; /* maintain cwnd */
731 } /* fall through to check if in-flight is already small: */
732 if (bbr
->mode
== BBR_DRAIN
&&
733 tcp_packets_in_flight(tcp_sk(sk
)) <=
734 bbr_target_cwnd(sk
, bbr_max_bw(sk
), BBR_UNIT
))
735 bbr_reset_probe_bw_mode(sk
); /* we estimate queue is drained */
738 /* The goal of PROBE_RTT mode is to have BBR flows cooperatively and
739 * periodically drain the bottleneck queue, to converge to measure the true
740 * min_rtt (unloaded propagation delay). This allows the flows to keep queues
741 * small (reducing queuing delay and packet loss) and achieve fairness among
744 * The min_rtt filter window is 10 seconds. When the min_rtt estimate expires,
745 * we enter PROBE_RTT mode and cap the cwnd at bbr_cwnd_min_target=4 packets.
746 * After at least bbr_probe_rtt_mode_ms=200ms and at least one packet-timed
747 * round trip elapsed with that flight size <= 4, we leave PROBE_RTT mode and
748 * re-enter the previous mode. BBR uses 200ms to approximately bound the
749 * performance penalty of PROBE_RTT's cwnd capping to roughly 2% (200ms/10s).
751 * Note that flows need only pay 2% if they are busy sending over the last 10
752 * seconds. Interactive applications (e.g., Web, RPCs, video chunks) often have
753 * natural silences or low-rate periods within 10 seconds where the rate is low
754 * enough for long enough to drain its queue in the bottleneck. We pick up
755 * these min RTT measurements opportunistically with our min_rtt filter. :-)
757 static void bbr_update_min_rtt(struct sock
*sk
, const struct rate_sample
*rs
)
759 struct tcp_sock
*tp
= tcp_sk(sk
);
760 struct bbr
*bbr
= inet_csk_ca(sk
);
763 /* Track min RTT seen in the min_rtt_win_sec filter window: */
764 filter_expired
= after(tcp_jiffies32
,
765 bbr
->min_rtt_stamp
+ bbr_min_rtt_win_sec
* HZ
);
766 if (rs
->rtt_us
>= 0 &&
767 (rs
->rtt_us
<= bbr
->min_rtt_us
|| filter_expired
)) {
768 bbr
->min_rtt_us
= rs
->rtt_us
;
769 bbr
->min_rtt_stamp
= tcp_jiffies32
;
772 if (bbr_probe_rtt_mode_ms
> 0 && filter_expired
&&
773 !bbr
->idle_restart
&& bbr
->mode
!= BBR_PROBE_RTT
) {
774 bbr
->mode
= BBR_PROBE_RTT
; /* dip, drain queue */
775 bbr
->pacing_gain
= BBR_UNIT
;
776 bbr
->cwnd_gain
= BBR_UNIT
;
777 bbr_save_cwnd(sk
); /* note cwnd so we can restore it */
778 bbr
->probe_rtt_done_stamp
= 0;
781 if (bbr
->mode
== BBR_PROBE_RTT
) {
782 /* Ignore low rate samples during this mode. */
784 (tp
->delivered
+ tcp_packets_in_flight(tp
)) ? : 1;
785 /* Maintain min packets in flight for max(200 ms, 1 round). */
786 if (!bbr
->probe_rtt_done_stamp
&&
787 tcp_packets_in_flight(tp
) <= bbr_cwnd_min_target
) {
788 bbr
->probe_rtt_done_stamp
= tcp_jiffies32
+
789 msecs_to_jiffies(bbr_probe_rtt_mode_ms
);
790 bbr
->probe_rtt_round_done
= 0;
791 bbr
->next_rtt_delivered
= tp
->delivered
;
792 } else if (bbr
->probe_rtt_done_stamp
) {
793 if (bbr
->round_start
)
794 bbr
->probe_rtt_round_done
= 1;
795 if (bbr
->probe_rtt_round_done
&&
796 after(tcp_jiffies32
, bbr
->probe_rtt_done_stamp
)) {
797 bbr
->min_rtt_stamp
= tcp_jiffies32
;
798 bbr
->restore_cwnd
= 1; /* snap to prior_cwnd */
803 bbr
->idle_restart
= 0;
806 static void bbr_update_model(struct sock
*sk
, const struct rate_sample
*rs
)
808 bbr_update_bw(sk
, rs
);
809 bbr_update_cycle_phase(sk
, rs
);
810 bbr_check_full_bw_reached(sk
, rs
);
811 bbr_check_drain(sk
, rs
);
812 bbr_update_min_rtt(sk
, rs
);
815 static void bbr_main(struct sock
*sk
, const struct rate_sample
*rs
)
817 struct bbr
*bbr
= inet_csk_ca(sk
);
820 bbr_update_model(sk
, rs
);
823 bbr_set_pacing_rate(sk
, bw
, bbr
->pacing_gain
);
824 bbr_set_tso_segs_goal(sk
);
825 bbr_set_cwnd(sk
, rs
, rs
->acked_sacked
, bw
, bbr
->cwnd_gain
);
828 static void bbr_init(struct sock
*sk
)
830 struct tcp_sock
*tp
= tcp_sk(sk
);
831 struct bbr
*bbr
= inet_csk_ca(sk
);
834 bbr
->tso_segs_goal
= 0; /* default segs per skb until first ACK */
836 bbr
->next_rtt_delivered
= 0;
837 bbr
->prev_ca_state
= TCP_CA_Open
;
838 bbr
->packet_conservation
= 0;
840 bbr
->probe_rtt_done_stamp
= 0;
841 bbr
->probe_rtt_round_done
= 0;
842 bbr
->min_rtt_us
= tcp_min_rtt(tp
);
843 bbr
->min_rtt_stamp
= tcp_jiffies32
;
845 minmax_reset(&bbr
->bw
, bbr
->rtt_cnt
, 0); /* init max bw to 0 */
847 bbr
->has_seen_rtt
= 0;
848 bbr_init_pacing_rate_from_rtt(sk
);
850 bbr
->restore_cwnd
= 0;
851 bbr
->round_start
= 0;
852 bbr
->idle_restart
= 0;
854 bbr
->full_bw_cnt
= 0;
855 bbr
->cycle_mstamp
= 0;
857 bbr_reset_lt_bw_sampling(sk
);
858 bbr_reset_startup_mode(sk
);
860 cmpxchg(&sk
->sk_pacing_status
, SK_PACING_NONE
, SK_PACING_NEEDED
);
863 static u32
bbr_sndbuf_expand(struct sock
*sk
)
865 /* Provision 3 * cwnd since BBR may slow-start even during recovery. */
869 /* In theory BBR does not need to undo the cwnd since it does not
870 * always reduce cwnd on losses (see bbr_main()). Keep it for now.
872 static u32
bbr_undo_cwnd(struct sock
*sk
)
874 return tcp_sk(sk
)->snd_cwnd
;
877 /* Entering loss recovery, so save cwnd for when we exit or undo recovery. */
878 static u32
bbr_ssthresh(struct sock
*sk
)
881 return TCP_INFINITE_SSTHRESH
; /* BBR does not use ssthresh */
884 static size_t bbr_get_info(struct sock
*sk
, u32 ext
, int *attr
,
885 union tcp_cc_info
*info
)
887 if (ext
& (1 << (INET_DIAG_BBRINFO
- 1)) ||
888 ext
& (1 << (INET_DIAG_VEGASINFO
- 1))) {
889 struct tcp_sock
*tp
= tcp_sk(sk
);
890 struct bbr
*bbr
= inet_csk_ca(sk
);
893 bw
= bw
* tp
->mss_cache
* USEC_PER_SEC
>> BW_SCALE
;
894 memset(&info
->bbr
, 0, sizeof(info
->bbr
));
895 info
->bbr
.bbr_bw_lo
= (u32
)bw
;
896 info
->bbr
.bbr_bw_hi
= (u32
)(bw
>> 32);
897 info
->bbr
.bbr_min_rtt
= bbr
->min_rtt_us
;
898 info
->bbr
.bbr_pacing_gain
= bbr
->pacing_gain
;
899 info
->bbr
.bbr_cwnd_gain
= bbr
->cwnd_gain
;
900 *attr
= INET_DIAG_BBRINFO
;
901 return sizeof(info
->bbr
);
906 static void bbr_set_state(struct sock
*sk
, u8 new_state
)
908 struct bbr
*bbr
= inet_csk_ca(sk
);
910 if (new_state
== TCP_CA_Loss
) {
911 struct rate_sample rs
= { .losses
= 1 };
913 bbr
->prev_ca_state
= TCP_CA_Loss
;
915 bbr
->round_start
= 1; /* treat RTO like end of a round */
916 bbr_lt_bw_sampling(sk
, &rs
);
920 static struct tcp_congestion_ops tcp_bbr_cong_ops __read_mostly
= {
921 .flags
= TCP_CONG_NON_RESTRICTED
,
923 .owner
= THIS_MODULE
,
925 .cong_control
= bbr_main
,
926 .sndbuf_expand
= bbr_sndbuf_expand
,
927 .undo_cwnd
= bbr_undo_cwnd
,
928 .cwnd_event
= bbr_cwnd_event
,
929 .ssthresh
= bbr_ssthresh
,
930 .tso_segs_goal
= bbr_tso_segs_goal
,
931 .get_info
= bbr_get_info
,
932 .set_state
= bbr_set_state
,
935 static int __init
bbr_register(void)
937 BUILD_BUG_ON(sizeof(struct bbr
) > ICSK_CA_PRIV_SIZE
);
938 return tcp_register_congestion_control(&tcp_bbr_cong_ops
);
941 static void __exit
bbr_unregister(void)
943 tcp_unregister_congestion_control(&tcp_bbr_cong_ops
);
946 module_init(bbr_register
);
947 module_exit(bbr_unregister
);
949 MODULE_AUTHOR("Van Jacobson <vanj@google.com>");
950 MODULE_AUTHOR("Neal Cardwell <ncardwell@google.com>");
951 MODULE_AUTHOR("Yuchung Cheng <ycheng@google.com>");
952 MODULE_AUTHOR("Soheil Hassas Yeganeh <soheil@google.com>");
953 MODULE_LICENSE("Dual BSD/GPL");
954 MODULE_DESCRIPTION("TCP BBR (Bottleneck Bandwidth and RTT)");