Subject: [iccrg] exclusive versus shared bottleneck for BBR

From: Alejandro Popovsky <[email-masked]>
Date: Wed, 30 Nov 2016 07:52:12 -0300

Hi Yuchung & Neal,

As shown in your IETF 97 presentation, BBR walks towards an optimum point
having max BW and min RTT.

(taken from presentation)

But that point (or elbow in the curve) is found only when the connection
is the exclusive user of the bottleneck.

In the test below, a TCP connection rate is shown for different values 
of its window,
for a bottleneck with 10mbps bw, and a bandwidth-delay product of 125KBytes.
The red curve is when being the exclusive user, and the*green***curve when
sharing the bottleneck with another connection with the same path delay and
a congestion window fixed at 200KBytes. The bottleneck buffer is big enough
for not dropping datagrams at the test window sizes (and big enough for 
buffer bloat)

In the shared bottleneck case there is no elbow, and the delivery rate is
dependent upon the share of bytes the connection has in the
bottleneck queue.

May be to prevent BBR explore looking for an elbow that does not exist
(or requires to grow the queue very large and starve the other connections)
it may help to use the estimation of the bw share of the connection 
using the
measurements as presented in ICCRG IETF 95 ("Peeking at the bottleneck...").
This would help BBR stop exploring when sensing a predefined acceptable
share.

The bottom of the graph shows the proportional rate variations with 
respect to
proportional window variation (X), that helps estimate the share of the 
BW as
aproximately 1-X when the capacity is jointly taken.

Best Regards, Alejandro.

---

From: Neal Cardwell <[email-masked]>
Date: Wed, 30 Nov 2016 10:50:01 -0500

> is the exclusive user of the bottleneck.

Just so I understand the context: what is that assertion based on? In our
experience with tests and live traffic over Google's backbone, BBR tends to
converge to an operating point close to the elbow (BDP): specifically,
within 1.0*BDP to 2.5*BDP in the current release, and more frequently
closer to 1.0*BDP in the curent development version mentioned in the ICCRG
talk.

>
> In the test below, a TCP connection rate is shown for different values of
> its window,
> The red curve is when being the exclusive user, and the *green* curve when

> May be to prevent BBR explore looking for an elbow that does not exist

Thanks for the nice diagram.

I am not sure what you mean by saying "an elbow that does not exist". I
think perhaps you mean that there is an elbow in the curve when we view the
system in aggregate, but an individual flow sharing with others would not
be able to find it by searching for a point in the curve that looks like an
elbow, because the measurable curve visible to a single flow sharing with
others does not have an obvious elbow. I agree with that.

But BBR does not find an operating point by looking for a point on the
delivery rate curve that looks like an elbow. It probes for its fair share
of available bandwidth, and then uses that bandwidth estimate and an
estimate of round-trip propagation delay to keep its pacing delay near its
fair share of bandwidth and its number of inflight packets near its fair
share of the estimated BDP. In our experience this tends to allow BBR flows
sharing a bottleneck to usually operate at the elbow in aggregate.

The slides are probably not clear on this point, but in the paper and the
talks at netdev and ICCRG I hope we made it clear that BBR is not designed
around seeking an elbow in the curve, but rather pacing in a manner to keep
the amount of data in flight near the BDP of the flow's fair share of the
bottleneck.

We realize the shape of the curve, from the perspective of a single flow
among many, does not have an obvious elbow. For the presentations and
paper, to simplify and ease the explication, we focused on the shape of the
RTT and delivery rate curves that one sees for (a) a single flow, or (b)
the system in aggregate.

> it may help to use the estimation of the bw share of the connection using
> the
> proportional window variation (X), that helps estimate the share of the BW
> as

Thanks for the pointer! I had not seen that presentation. Interesting work.
Is there a related paper or perhaps code with more details?

I have a few questions about the slide deck:

(1) The approach in that presentation seems to be a modification to receive
window autotuning. How, specifically, would this approach be integrated
into a sender-side congestion control scheme, to choose pacing rate and
cwnd?

(2) The slides say: "Goal: estimate the share of the joint available
capacity". Is that fair share or current share?

(3) Assuming this approach allows a flow to determine whether the
bottleneck is shared or exclusive, and if shared then possibly what the
flow's current share is, how do the flows use this information to converge
to a fair share of the bottleneck? For example, if a flow determines that
it is using 1/3 of the capacity, what does it do to achieve its fair share?
Its fair share may actually be higher (1/2, if there are 2 flows), the
current value (1/3, if there are 3 flows), or lower (1/4, if there are 4
flows). What is the mechanism to determine how to evolve toward a fair
share, once the determination is made that a flow currently is using some
fraction of the bottleneck's bandwidth?

(4)  The slides say: "If possible prevent bufferbloat, else revert to
regular behavior". How, specifically, does your approach determine whether
it's possible to "prevent bufferbloat"?

thanks,
neal

---

From: Alejandro Popovsky <[email-masked]>
Date: Wed, 30 Nov 2016 20:15:26 -0300

Hi Neal,

On 30/11/2016 12:50 p. m., Neal Cardwell wrote:
>
> On Wed, Nov 30, 2016 at 5:52 AM, Alejandro Popovsky 
> <[email-masked] <mailto:[email-masked]>> wrote:
>
>     Hi Yuchung & Neal,
>
> Just so I understand the context: what is that assertion based on? In 
> our experience with tests and live traffic over Google's backbone, BBR 
> tends to converge to an operating point close to the elbow (BDP): 
> specifically, within 1.0*BDP to 2.5*BDP in the current release, and 
> more frequently closer to 1.0*BDP in the curent development version 
> mentioned in the ICCRG talk.
>
>
>     In the test below, a TCP connection rate is shown for different
>     values of its window,
>     for not dropping datagrams at the test window sizes (and big
>     enough for buffer bloat)
>
> I am not sure what you mean by saying "an elbow that does not exist". 
> I think perhaps you mean that there is an elbow in the curve when we 
> view the system in aggregate, but an individual flow sharing with 
> others would not be able to find it by searching for a point in the 
> curve that looks like an elbow, because the measurable curve visible 
> to a single flow sharing with others does not have an obvious elbow. I 
> agree with that.
>
> delivery rate curve that looks like an elbow. It probes for its fair 
> share of available bandwidth, and then uses that bandwidth estimate 
> and an estimate of round-trip propagation delay to keep its pacing 
> delay near its fair share of bandwidth and its number of inflight 
> packets near its fair share of the estimated BDP. In our experience 
> this tends to allow BBR flows sharing a bottleneck to usually operate 
> at the elbow in aggregate.
>
> The slides are probably not clear on this point, but in the paper and 
> the talks at netdev and ICCRG I hope we made it clear that BBR is not 
> designed around seeking an elbow in the curve, but rather pacing in a 
> manner to keep the amount of data in flight near the BDP of the flow's 
> fair share of the bottleneck.
>
> We realize the shape of the curve, from the perspective of a single 
> flow among many, does not have an obvious elbow. For the presentations 
> and paper, to simplify and ease the explication, we focused on the 
> shape of the RTT and delivery rate curves that one sees for (a) a 
> single flow, or (b) the system in aggregate.
>
>
>     it may help to use the estimation of the bw share of the
>     connection using the
>     The bottom of the graph shows the proportional rate variations
>     with respect to
>     proportional window variation (X), that helps estimate the share
>     of the BW as
> Thanks for the pointer! I had not seen that presentation. Interesting 
> work. Is there a related paper or perhaps code with more details?

It is at the review process for publication at the moment but I can send 
it to you beforehand.

> (1) The approach in that presentation seems to be a modification to 
> receive window autotuning. How, specifically, would this approach be 
> integrated into a sender-side congestion control scheme, to choose 
> pacing rate and cwnd?

Our receiver algorithm works when the sender is not source limited, and 
it waits for the sender to grow its cwnd until it is larger than the 
receive window. It can then control the in-flight bytes and measure the 
effect of their variations in the data arrival rate.

We could have implemented the algorithm in the sender also. But chose to 
try it first from the receiver because we observed in the IXP traffic 
for some ISP's a significant percentage of traffic limited by flow 
control, but achieving similar rates to traffic limited by congestion 
control. Probably because of those ISP's having cache or cdn servers 
with no receive window scaling, but but with rcvwnd still larger than BDP.

> capacity". Is that fair share or current share?

It is the "current share".

The "fair share" is very difficult to estimate for an individual connection
endpoint. Because a connection having a certain number B of bytes queued
in the bottleneck, will get the same rate if there are N other connections
each having C bytes queued in the bottleneck, as if there is only one other
connection having (N*C) bytes queued. And in both cases you get the
same estimation (1-X) of share... So having say 20% of capacity is fair
if there are 5 connections, but is not fair if there are only 2. And the
connection cannot tell the difference.

> bottleneck is shared or exclusive, and if shared then possibly what 
> the flow's current share is, how do the flows use this information to 
> converge to a fair share of the bottleneck? For example, if a flow 
> determines that it is using 1/3 of the capacity, what does it do to 
> achieve its fair share? Its fair share may actually be higher (1/2, if 
> there are 2 flows), the current value (1/3, if there are 3 flows), or 
> lower (1/4, if there are 4 flows). What is the mechanism to determine 
> how to evolve toward a fair share, once the determination is made that 
> a flow currently is using some fraction of the bottleneck's bandwidth?
>
Because of the individual connection not knowing the total number of 
connections
at the bottleneck, aiming for the "fair share" may be too difficult, but 
may be
to get a "reasonable share", without provoking buffer bloat, nor 
starving. So to
assure good response times to other transaction oriented connections, if 
possible.
To achieve the exact fair share for all connections may be an easier 
goal for queue
management (although we get similar shares for concurrent connections in 
our tests).

> regular behavior". How, specifically, does your approach determine 
> whether it's possible to "prevent bufferbloat"?

In a bottleneck already crowded by other buffer bloating connections, an 
arriving
connection cannot do anything to obtain a low round trip time. And if it 
keeps a delay
sensitive congestion control approach in such situation, it would assure 
its starvation.

An interesting thing is that the measured proportional rate variations 
for a connection
having a very small share of a buffer bloated bottleneck (X aprox 1), is 
almost the same
as the measured proportional rate variations (X=1) for a connection that 
is the exclusive
user of a bottleneck and having a cwnd smaller than BDP. And in both 
cases it should
grow its cwnd as fast as in slow start.

In another situation, a connection holding constant its in-flight byte 
count and having
a very small initial average number of queued bytes in an exclusive 
bottleneck, can see
its share decrease to one half, ... one fifth, ... of its initial value, 
by the arrival of several
good behaved connections, or by the arrival of a single buffer-filling 
connection. But
probably in both cases the RTT growth will be similar. So at some 
(kernel configurable)
point the buffer bloat prevention behavior does not help and can be 
switched to the
regular tcp behavior.

Best regards, Alejandro.