Resolving the bandwidth-delay uncertainty through asymptotic pacing
TCP Reno and CUBIC asymptotically converge to an optimal value of the cwnd control parameter by applying the combination of a linear and cubic function of the lapsed time respectively when increasing cwnd, and a multiplicative decrease in the congestion window – that is – cwnd = (1 – β) × W_max following a packet loss event.
BBR v1 and v2 apply a similar principle to cwnd (and on in-flight in the case of the latter), and it is interesting to consider how this principle might fully extend to another key control parameter – the pacing rate.
We note that distributed congestion control algorithms resolve Zeno’s classical paradox (by asymptotically converging to an optimal value of the control parameter) principally because the control parameter has an associated rate of increase (or decrease).
For BBRs pacing rate, such considerations are important because steady-state flows (operating in PROBE_BW) are once again subjected to the uncertainty principle (that is, having to overfill the Pipe to find capacity and thereby obscuring the length of the Pipe) when contending with START-UP flows.
This article describes simple rule changes to BBR v1 pacing that improve fairness and minimise queue pressure in homogeneous (BBR v1 only) and heterogenous (BBR v1 v CUBIC) environments in shallow, deep and bloated buffers (including with random losses).
Long-lived BBR flows repeatedly probe for additional bandwidth while maintaining a small, bounded queue by “pulsing” the gain value during an 8-round cycle: [1.25, 0.75, 1, 1, 1, 1, 1, 1].
The rate of increase of the pacing rate is therefore determined by the “amplitude” of the pulse which, in the case of BBR v1 and v2, is 1.25. In other words, BBR probes for additional bandwidth by deliberately sending 25% more packets than the BDP for one round trip time which (when delivered) increase the Rate Sampled Delivery Rate.
Asymptotic pacing can be achieved by defining a rule whereby the bottleneck bandwidth increases by a fraction beta of the rate sampled delivery rate.
Bottleneck bandwidth = (1 - beta) × Rate Sampled Delivery Rate
By setting the beta value to half of the percent increase in the number of packets sent during cycle phase zero of PROBE_BW (that is a beta of 12.5%), BBR is set to conservatively pace at a margin that is lower than the measured delivery rate in each 8-round cycle.
A beta value that is greater than half produces faster convergence at the cost of increased queue pressure which then affects fairness. Beta values that are less than half are unstable and may not converge as required in all cases.
The asymptotic pacing rule can easily be implemented in BBR v1 by adding the bbr_pacing_margin_percent variable to the tcp_rate_gen function.
Another key point to consider is when this rule change (asymptotic pacing) is applied – we propose that bottleneck bandwidth is asymptotically modelled on every ACK ONLY – that is – when BBR is NOT in RECOVERY – during which time BBR receives duplicate and Partial (selective) ACKs.
A previous blog discussed in detail how observing strict packet conservation during RECOVERY has the effect of greatly reducing the number of packets from opportunistic flows (which tend to lose more packets during congestion events) thus greatly improving fairness.
To evaluate the effects of the above rule changes on BBR v1s performance and fairness, the Goodput was measured for various RTT ratios, for shallow, deep and bloated buffers.
Goodput is measured by counting the number of in-order data packet arrivals over a 180-second interval for flows that are not application limited (long-lived, high-demand flows). Deep buffers are set at 4 × BDP and random losses are evaluated by using a RED gateway that marks packets by dropping them with 10% probability for min-max thresholds of 0.15 × N × BDP and 0.45 × N × BDP respectively - where N is the RTT ratio.
Packet-level modelling show that asymptotic pacing stabilises BBR v1 in homogeneous settings where BBR is very fair and exerts minimal queue pressure in deep and shallow buffers. BBR v1 with asymptotic pacing also outperforms CUBIC in terms of fairness and queue pressure exerted with and without AQM for RTT ratios of 2X -10X – CUBIC is comparable in terms of fairness only with AQM.
AE: God does not play dice with the universe (on the Heisenberg uncertainty principle and quantum mechanics)
NB: (responding to AE) Stop telling God what to do.