Subject: [tcpm] Linux doesn’t implement RFC3465

From: Vidhi Goel <[email-masked]>
Date: Tue, 05 Nov 2019 14:08:06 -0800

Hi All,

RFC 3465 suggests to increase the congestion window by the number of previously unacknowledged bytes ACKed by each ACK limiting the increase to L (L = 2MSS or 1MSS in certain conditions). The limiting factor L helps to avoid the large bursts that could occur due to stretch ACKs, ACK loss or compressed ACKs (GRO/GSO).

But, when I looked at Linux source code, it implements one aspect of ABC (byte counting to defend from ACK attacks) but doesn’t  “cap” the increase to L. 
 https://github.com/torvalds/linux/blob/master/net/ipv4/tcp_cong.c#L385 <https://github.com/torvalds/linux/blob/master/net/ipv4/tcp_cong.c#L385>

This is a bit confusing. How should we address this discrepancy?

Thanks,
Vidhi

---

From: Neal Cardwell <[email-masked]>
Date: Tue, 5 Nov 2019 18:25:01 -0500

On Tue, Nov 5, 2019 at 5:08 PM Vidhi Goel <vidhi_goel=
[email-masked]> wrote:

> Hi All,
>
> RFC 3465 suggests to increase the congestion window by the number of
> previously unacknowledged bytes ACKed by each ACK limiting the increase to
> L (L = 2MSS or 1MSS in certain conditions). The limiting factor L helps to
> avoid the large bursts that could occur due to stretch ACKs, ACK loss or
> compressed ACKs (GRO/GSO).
>
> But, when I looked at Linux source code, it implements one aspect of ABC
> (byte counting to defend from ACK attacks) but doesn’t  “cap” the increase
> to L.
>  https://github.com/torvalds/linux/blob/master/net/ipv4/tcp_cong..c#L385
> <https://github.com/torvalds/linux/blob/master/net/ipv4/tcp_cong.c#L385>
>

The differences between the Linux code and the ABC RFC  (
https://tools.ietf.org/html/rfc3465 ) are intentional. The Linux TCP code
in this area is largely from:

9f9843a751d0 tcp: properly handle stretch acks in slow start
95224ac1801c Merge branch 'tcp_stretch_acks'
d6b1a8a92a14 tcp: fix timing issue in CUBIC slope calculation
9cd981dcf174 tcp: fix stretch ACK bugs in CUBIC
c22bdca94782 tcp: fix stretch ACK bugs in Reno
814d488c6126 tcp: fix the timid additive increase on stretch ACKs
e73ebb0881ea tcp: stretch ACK fixes prep

That code is based on experience at Google, both with internal traffic and
google.com and YouTube traffic. Experience was showing that preventing the
full use of ACKs in growing the cwnd in slow start and CUBIC's rapid growth
phase causes anemic growth in real-world situations.

The basic principle in the Linux code is that the sender should use the
ACKs to learn about the capacity of the path (both in volumetric and rate
dimensions), and should not ignore that information. This allows the sender
to quickly grow and achieve high throughput, even in the presence of
stretch ACKs, which are pervasive, due to TSO/GSO, GRO/LRO, etc.

Considering bursts is important, but that can be tackled as an orthogonal
issue. Bursts are avoided in the Linux TCP ecosystem by the combination of
TSO autosizing, pacing, TSQ, and fair queueing.

Here is a summary of the Linux TCP design in this area:
  https://netdevconf.info/1.2/papers/bbr-netdev-1.2.new.new.pdf

best,
neal

---

From: Vidhi Goel <[email-masked]>
Date: Tue, 12 Nov 2019 13:44:49 -0800

+Mark Allman

Thank you Neal for the detailed explanation.

I believe that ABC was written to solve the problem with ACK counting by counting the number of bytes acknowledged for misbehaving receivers. Limiting the increase to 2*MSS was a good solution to avoid bursts at the time.

I agree that increasing the congestion window and controlling the burst rate are orthogonal issues. ABC intended to solve them by regulating the congestion window itself and this approach might have become outdated with implementations trying to solve these two issues separately.

Is it worth investing time in writing another draft to document what Linux (and possibly other implementations) do for more accurate congestion window growth and for solving the burst send issue via pacing, TSQ etc.?

Thanks,
Vidhi

> On Nov 5, 2019, at 3:25 PM, Neal Cardwell <ncardwell=[email-masked]> wrote:
> 
> 
> 
> On Tue, Nov 5, 2019 at 5:08 PM Vidhi Goel <vidhi_goel=[email-masked] <mailto:[email-masked]>> wrote:
> Hi All,
> 
>  https://github.com/torvalds/linux/blob/master/net/ipv4/tcp_cong..c#L385 <https://github.com/torvalds/linux/blob/master/net/ipv4/tcp_cong.c#L385>
> 
> The differences between the Linux code and the ABC RFC  ( https://tools.ietf.org/html/rfc3465 <https://tools.ietf.org/html/rfc3465> ) are intentional.. The Linux TCP code in this area is largely from:
> 
> That code is based on experience at Google, both with internal traffic and google.com <http://google.com/> and YouTube traffic. Experience was showing that preventing the full use of ACKs in growing the cwnd in slow start and CUBIC's rapid growth phase causes anemic growth in real-world situations.
> 
> The basic principle in the Linux code is that the sender should use the ACKs to learn about the capacity of the path (both in volumetric and rate dimensions), and should not ignore that information. This allows the sender to quickly grow and achieve high throughput, even in the presence of stretch ACKs, which are pervasive, due to TSO/GSO, GRO/LRO, etc.
> 
> Considering bursts is important, but that can be tackled as an orthogonal issue. Bursts are avoided in the Linux TCP ecosystem by the combination of TSO autosizing, pacing, TSQ, and fair queueing.
> 
>   https://netdevconf.info/1.2/papers/bbr-netdev-1.2.new.new.pdf <https://netdevconf.info/1.2/papers/bbr-netdev-1.2.new.new.pdf>
> 
> best,
> neal
>

---

From: Lars Eggert <[email-masked]>
Date: Wed, 13 Nov 2019 08:53:00 +0200

Hi,

> +Mark Allman

oh, is he at BBN now? Not [email-masked]?

> Is it worth investing time in writing another draft to document what Linux (and possibly other implementations) do for more accurate congestion window growth and for solving the burst send issue vi…

That is IMO the key question. *If* there is an alternative mechanism to ABC that solves (some of) the same problems, and potentially in a better way, or in a way that has a different implementation footprint, that may be worth documenting.

I'm not up to speed with the Linux code, but from what Neal writes, it seems that the Linux mechanism is tied in with or relying on a bunch of lower-level packet I/O functionality that is maybe pretty Linux-specific? In other words, can something like the Linux mechanism even be instantiated without (much of) this underpinning?

Lars

---

From: Vidhi Goel <[email-masked]>
Date: Wed, 13 Nov 2019 00:10:53 -0800

Adding Mark again as the bbn email doesn’t exist.

Vidhi

> On Nov 12, 2019, at 10:53 PM, Lars Eggert <[email-masked]> wrote:
> 
> Hi,
>

---

From: Vidhi Goel <[email-masked]>
Date: Tue, 26 Nov 2019 17:11:01 -0800

>> That is IMO the key question. *If* there is an alternative mechanism to ABC that solves (some of) the same problems, and potentially in a better way, or in a way that has a different implementatio…

I think we can combine the byte counting mechanism of ABC for increasing congestion window and come up with an alternate way for controlling the burst sending. This will allow us to keep the two issues separate.

>> I'm not up to speed with the Linux code, but from what Neal writes, it seems that the Linux mechanism is tied in with or relying on a bunch of lower-level packet I/O functionality that is maybe pr…

If we can come up with a generic approach (like pacing) to do it, an implementation wouldn’t require Linux specific mechanisms.

Vidhi

> On Nov 13, 2019, at 12:10 AM, Vidhi Goel <[email-masked]> wrote:
>

---

From: "Mark Allman" <[email-masked]>
Date: Wed, 27 Nov 2019 08:14:26 -0500

> +Mark Allman

Just to clear it up, I *was* at BBN long ago when the ABC document
was written.  It's a cool place to work.  I recommend it.  But, I
now hang out at ICSI.

> I believe that ABC was written to solve the problem with ACK
> counting by counting the number of bytes acknowledged for
> misbehaving receivers. Limiting the increase to 2*MSS was a good
> solution to avoid bursts at the time.

The main motivation behind ABC was to counteract delayed ACKs.  The
common approach at the time was to just bump cwnd by one MSS every
time an ACK rolled in.  So, if an ACK covered two segments because
the receiver was delaying the ACKs then the growth rate during slow
start was 1.5x per RTT instead of the 2x that was really
envisioned.  During congestion avoidance the growth was 1 MSS every
2 RTTs instead of the envisioned every RTT.

A secondary motivation was to counteract these ACK division attacks
that Savage taught us about.  I.e., we could ACK an MSS-sized packet
one byte at a time and the sender would then increase the cwnd by
MSS*MSS bytes in the prevalent ACK counting scheme (i.e., cwnd would
get bumped by MSS bytes for every ACK).

The limit has two roots ...

(1) The limit is important in slow starts that follow an RTO.  As
    the RFC discusses, in this case we might retransmit a single
    packet and this will cause the receiver's window to slide a
    great deal.  Therefore, an ACK may indicate that a ton of data
    has left the network, but that isn't really the case.  So, we
    don't want to increase the cwnd based on all the new bytes
    ACKed.

    I have since mostly decided that this use of L is crude.
    Probably there is a more elegant way to do it by using the
    scoreboard and the SACK information to get a better
    understanding of what left the network and when.  That said, in
    this case L is simple and probably about right most of the
    time.

(2) I think there was some general conservativeness to bursts and
    using L everywhere quelled some of the worry.  Here L=2 was used
    to exactly offset delayed ACKs.

> I agree that increasing the congestion window and controlling the
> burst rate are orthogonal issues.

Yes.  In fact, we did subsequent research on mitigating bursts
because we never really thought of ABC as somehow the way to control
bursts (research papers available, but never went into RFCs).

And, in a world that leverages stretch ACKs as a routine I think
Linux's approach of not using an L may well be correct.  Documenting
that and the reasoning behind it in modern networks seems useful to
me.

allman