Why did the gain in the STARTUP phase be 2/ln(2)?

[marywan...@gmail.com]

Hi ALL!

I encountered a problem while reading the source code. I hope I can get replies. Thanks!
------

In the following statement, there is a magic number, as noted, which is 2/ln(2) :

static const int bbr_high_gain = BBR_UNIT * 2885/1000 + 1;

But I don't know how it came about.
I have read the paper of BBR and have the following explanation:

To handle the Internet link bandwidths span 12 orders of magnitude,Startup implements a binary search for BtlBw by using a gain of 2 / ln2 to double the sending rate while delivery rate is increasing. This discovers BtlBw in log2BDP RTTs but creates up to 2 BDP excessThe queue in the process.

But I still don't understand the details.Why not 3/ln(3), why not 2.5, why not e?

I think there might be a smooth curve that satisfies the startup constraint, such as a two-fold increase in speed per round.And then you take the derivative of this curve, and you get some value...

There must be a mathematical explanation behind this, but I don't know what it is.

Regards.

[Neal Cardwell]

Hi,

The gain of 2/ln(2) (used for both pacing and cwnd in STARTUP mode) was derived as the gain required to allow the pacing rate (computed as pacing_gain * bw_sample) to exactly double each round trip. It arises because the pacing rate evolves as a function of time as 2^t, doubling every round trip, and the integral of 2^t is 2^t / ln(2).

cheers,

neal

--
You received this message because you are subscribed to the Google Groups "BBR Development" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bbr-dev+u...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[刘文斌]

But why 2 ^ t integral can be as gain?

I can understand f (t) = (2 ^ t) of the independent variable t represents the RTT, so what is the physical meaning of the integral?

And why the minimum?

Looking forward to your reply

在 2018年6月8日星期五 UTC+8下午11:14:25，Neal Cardwell写道：

[Jonathan Morton]

> On 8 Jun, 2018, at 6:14 pm, 'Neal Cardwell' via BBR Development <bbr...@googlegroups.com> wrote:
>
> The gain of 2/ln(2) (used for both pacing and cwnd in STARTUP mode) was derived as the gain required to allow the pacing rate (computed as pacing_gain * bw_sample) to exactly double each round trip. It arises because the pacing rate evolves as a function of time as 2^t, doubling every round trip, and the integral of 2^t is 2^t / ln(2).

This would be true if the measured rate varies continuously and smoothly over time. However, it is actually the result of discrete measurement events, and I'm not aware of a smoothing function being applied.

In a simple simulation I just conducted assuming the latter (that is, the measured BW tracks the pacing rate with an RTT lag), I got a sharply stepped pacing rate, which averaged a gain-rate of very nearly 2x per RTT when the pacing gain was 2x, and a significant higher value when the ln(2) factor was included.

So I'm afraid a little more explanation is required.

- Jonathan Morton

[marywan...@gmail.com]

Hi~

I think it is ok to take 2 as the gain value, why take into account the smooth will pick up 2 ^ t points?And why the minimum?

[marywan...@gmail.com]

Hi neal,

I thought about it a little bit again. How about the following derivation?

The startup stage of "pacing rate" relationship with time fixed point has the following:
The rate of change of the "pacing rate" is exactly equal to the current "pacing rate"

so,
let x be the time,Assuming that the RTT is constant, use it to normalize:
the BDP evolves as a function of time as f1(x)=2^x
the pacing rate evolves as a function of time as f2(x)=2^x

Let g(x) be the derivative of f1(x):
g(x)=f1'(x)=ln2*2^x

the derivative of f1'(x) is the rate, so g(x) is pacing rate.

let G be the pacing gain:
g(x+1) = G*g(x) = G*ln2*2^x = f2(x+1) = 2*2^x

so G*ln2*2^x = 2*2^x ==> G = 2/ln2

best regards.

On Friday, 8 June 2018 23:14:25 UTC+8, Neal Cardwell wrote:

[Neal Cardwell]

Hi,

Thanks for the discussion on this question.

Here's our team's latest detailed, step-by-step analytic derivation and a discussion of a simulation evaluation for the theoretical value for Startup gain, using a simplified continuous model:

  https://github.com/google/bbr/blob/master/Documentation/startup/gain/analysis/bbr_startup_gain.pdf

Hopefully this doc should provide a detailed enough answer.

Here's a quick diagram illustrating some different options for slow start and startup behavior:

  https://github.com/google/bbr/blob/master/Documentation/startup/gain/analysis/bbr_startup_gain_graph.png

And here's the code for a simulator mentioned in that doc. This simulator allows fast and deterministic exploration of different BBR gain values: 

  https://github.com/google/bbr/tree/master/Documentation/startup/gain/simulation

Of course the real world has discrete packets, TSO/GSO bursts, serialization delays, multiple flows, and various kinds of noise. So it does not quite fit an idealized model, particularly in the first few round trips. We are planning on running production tests to evaluate an appropriate strategy for Startup gain and other parameters using A/B tests in real YouTube and Google.com workloads.

cheers,

neal

[marywan...@gmail.com]

Hi,

The explanation is very detailed

Thanks.

But will future versions replace 2.89 with 2.77? Just because of strict doubling, right?

[Neal Cardwell]

On Tue, Jun 19, 2018 at 2:29 AM <marywan...@gmail.com> wrote:

Hi,

The explanation is very detailed

Thanks.

You're welcome!

 

But will future versions replace 2.89 with 2.77? Just because of strict doubling, right?

We would need to run production experiments to assess the real-world impact before making a change like that. So as I mentioned in my most recent note, we are planning on running production tests to evaluate an appropriate strategy for Startup gain and other parameters using A/B tests in real YouTube and Google.com workloads.

I am not sure what you mean by "Just because of strict doubling, right?" Several thoughts come to mind here.

First, because BBR has a cwnd as well, and doubles its cwnd each round trip, the cwnd would keep it from exceeding a strict doubling per round trip time, in any cas2e.

Second, the growth rate per round trip time is not the only consideration. Another big issue is the congestion window and pacing behavior in the first few round trips. I have added to the bbr github repo a zoomed-in version of the graph that illustrates the first five round trips of slow-start and Startup. This graph shows that, although a gain of 2.77 or 2.89 can basically allow the in-flight data to double each round trip, there is a large difference in the overall behavior depending on how the cwnd and pacing implementation in the first few round "seed" the growth process.

  

Finally, as mentioned previously, the 2.77 comes from an idealized model, and  the real world has discrete packets, TSO/GSO bursts, serialization delays, multiple flows, and various kinds of noise. So real-world Startup does not quite fit an idealized model, particularly in the first few round trips.

cheers,

neal

[Neal Cardwell]

I also wanted to explicitly mention these updates:

(1) I added an updated version of the zoomed-out Slow-Start/Startup graph, with a fix for the unpaced CUBIC flow. Previously I had accidentally shown the result for an unpaced CUBIC flow with IW20. I have fixed the graph to show an unpaced CUBIC flow with IW10. With this fix the graph makes much more sense, and the result looks quite nice for BBR with IW32.

(2) I added a zoomed-in version of the graph that illustrates the first five round trips of slow-start and Startup. This graph shows that, although a gain of 2.77 or 2.89 can basically allow the in-flight data to double each round trip, there is a large difference in the overall behavior of the various approaches depending on how the cwnd and pacing implementation in the first few round "seed" the growth process.

cheers,
neal

[marywan...@gmail.com]

Thank you very much!

That's a great explanation
But can you tell me the reason for the change in gain from 2/ln2 to 4ln2 and the original derivation of 2/ln2.

Thanks again.

Best regards.

[Neal Cardwell]

On Fri, Jun 22, 2018 at 1:05 AM <marywan...@gmail.com> wrote:

Thank you very much!

You are very welcome!

 

That's a great explanation

Thanks!

 

But can you tell me the reason for the change in gain from 2/ln2 to 4ln2 and the original derivation of 2/ln2.

The team member who did the original derivation that arrived at 2/ln(2)=2.89 did not have easy access to his notes from that original derivation (which was several years ago at this point). So our team undertook to reconstruct the derivation, and in this process we ended up with 4*ln(2)=2.77.

Note that the 2.77 gain is only 4% lower than the original 2.89. And the original 2.89 is indeed sufficient to double the pacing rate each round trip. It's just that, in an idealized system, the 2.77 gain appears to be the theoretical lower limit on a gain that can double the pacing rate each round trip, when calculating the pacing rate as a multiple of the estimated bandwidth. 

cheers,

neal

[赵亚]

Oh,i see..

I see why gain is 2/ln2 or 4*ln2. Thank you very much!

But as you say "Another big issue is the congestion window and pacing behaviors in the first what round trips.".Why did pacing_rate start with (high_gain*init_cwnd/RTT) instead of (init_cwnd/RTT)?
I did several rounds of experiments (init_cwnd=4), and the tcptrace of the first round trip almost showed the following

The reason for "the window of silence" seems to be the coefficient high_gain.

If the initial pacing_rate did not gain multiplied by the coefficient high_gain, So it looks like the delivery of init_cwnd packets will be evenly distributed in one round trip, but on the other hand, when connecting the initial, the round trip time measurement has not been smooth, affected by the fluctuation is great, the round trip time is not reliable.

So what is the latest development in this area for the BBR team? Can this problem be solved now?

Looking forward to your clarification

Best regards.

[Jonathan Morton]

> On 26 Jun, 2018, at 3:02 am, 赵亚 <maryw...@126.com> wrote:
>
> The reason for "the window of silence" seems to be the coefficient high_gain.

The gain is greater than unity in order to permit the bandwidth estimate to converge to the true path bandwidth as soon as possible. In a TCP that was entirely dependent on managing cwnd, you could more reasonably set the pacing rate to transmit the window over exactly one RTT.

The real reason for the "window of silence" is that the cwnd is not similarly scaled in this initial phase, and this initial cwnd is still respected by BBR. You can actually see smaller silences, with the same cause, after the packet pairs resulting from the first few acks. Later on, the cwnd ceases to be a constraint under normal conditions, as long as the bandwidth estimate matches reality on the wire.

- Jonathan Morton

[赵亚]

Thank you for your reply

On Tuesday, 26 June 2018 08:16:33 UTC+8, Jonathan Morton wrote:

> On 26 Jun, 2018, at 3:02 am, 赵亚 <maryw...@126.com> wrote:
>
> The reason for "the window of silence" seems to be the coefficient high_gain.
 

The gain is greater than unity in order to permit the bandwidth estimate to converge to the true path bandwidth as soon as possible.  In a TCP that was entirely dependent on managing cwnd, you could more reasonably set the pacing rate to transmit the window over exactly one RTT.

Yes, it is
I may not have made myself clear before.What I mean is that "only the initial of the first round trip of the initial pacing_rate calculation is not multiplied by the coefficient of high_gain", because this time has not yet formed ACK-clock,  and I think this time need to use A uniform sending rate, since when, after receipt of ACK calculation pacing_rate normal when multiplied by the coefficient of high_gain.
What do you think?

 

The real reason for the "window of silence" is that the cwnd is not similarly scaled in this initial phase, and this initial cwnd is still respected by BBR.  You can actually see smaller silences, with the same cause, after the packet pairs resulting from the first few acks.  Later on, the cwnd ceases to be a constraint under normal conditions, as long as the bandwidth estimate matches reality on the wire.

 - Jonathan Morton

Thank you

Best regards.

[Neal Cardwell]

On Mon, Jun 25, 2018 at 8:56 PM 赵亚 <maryw...@126.com> wrote:

> I may not have made myself clear before.What I mean is that "only the
> initial of the first round trip of the initial pacing_rate calculation
> is not multiplied by the coefficient of high_gain", because this time
> has not yet formed ACK-clock, and I think this time need to use A
> uniform sending rate, since when, after receipt of ACK calculation
> pacing_rate normal when multiplied by the coefficient of high_gain.
> What do you think?

I confess that I don't understand the comment or your proposal.
Perhaps your idea would be more clear when expressed as a proposed
patch?

One thing to keep in mind here is that in STARTUP, every pacing rate
calculation *is* indeed scaled by high_gain:

(1) The initial pacing rate is set to high_gain * initial_cwnd /
initial_rtt_sample (in Linux TCP BBR, see
bbr_init_pacing_rate_from_rtt()).

(2) After that, candidate pacing rates are computed with: high_gain *
estimated_bandwidth. For any of those candidates that are higher than
the current pacing rate, we increase the pacing rate to the candidate
pacing rate (in Linux TCP BBR, see bbr_set_pacing_rate()).

There are two ways I like to think about (1):

(a) To bootstrap BBR we need some initial guess as to the bandwidth
that might be available along the network path. For traditional TCP
this guess is effectively initial_bw_guess = initial_cwnd /
initial_rtt_sample. So for BBR we use the same initial guess. The
result is that when BBR calculates an initial pacing rate with
high_gain * initial_bw_guess, we get: high_gain * initial_cwnd /
initial_rtt_sample.

(b) The Linux paced CUBIC implementation uses an initial pacing rate
of 2 * initial_cwnd / initial_rtt_sample (see
tcp_update_pacing_rate()). To avoid regressions vs paced CUBIC, BBR
needs to use something similar to or slightly higher than that
expression; that's another reason why BBR uses an initial pacing rate
of high_gain * initial_cwnd / initial_rtt_sample.

Another thing to keep in mind is that any attempt to always close that
initial gap of silence is likely to result in a doubling of the
latency for request/response traffic that has less than an initial
cwnd of data to send. Because smoothing out such flights of data will
cause the latency to expand from one round trip to two round trips. So
there are costs to a simple scheme that merely tries to eliminate that
gap: either a latency cost, or a complexity cost in the form of code
to adaptively estimate whether there is enough data in the send buffer
to warrant spreading out the initial paced flight.

cheers,
neal

[MUHAMMAD AHSAN]

kindly read this.

https://github.com/google/bbr/blob/master/Documentation/startup/gain/analysis/bbr_startup_gain.pdf