TCP's congestion control saved the internet | Hacker News Reader

TCP's congestion control saved the internet

theregister.com

171 pointsmikece47 comments

The fact that such a simple endpoint-only control loop (mostly) just works is one of the most amazing parts of the Internet to me.

Still, it has its limits – the most obvious one to me is mentioned in the article: The optimal buffer size for each hop that TCP (or similarly flow-controlled traffic) traverses depends on the average delay and bandwidth, but these are per-flow quantities which an intermediate router can't properly estimate in principle.

I've played around with Linux's excellent fq_codel a bit with promising results in the past, but ultimately, that's not a solution in the spirit of the Internet (dumb routers, smart endpoints) since it depends on looking at individual flows, something routers aren't really supposed to have to do.

I really hope that something like Google's BBR will become the de-facto TCP congestion control algorithm in the end.

> The fact that such a simple endpoint-only control loop (mostly) just works is one of the most amazing parts of the Internet to me.

Me too. We really don't know what to do about congestion in the middle of a pure datagram network. What saved the Internet was cheap fiber backbones. If backbone bandwidth had remained expensive, this would never have worked.

When I was working on congestion in the early 1980s, our goal was to run at about 70% long haul link utilization. We would back off quite a bit if things got anywhere near saturation. This was fine with the DoD people who funded us. They wanted reliability under stress, not maximum performance at minimum cost. Much of the work on congestion since then has involved trying to squeeze out that last 30%, at the cost of much-increased complexity.

The "bufferbloat" mess is embarrassing. If you use FIFO queuing into a bandwidth choke point, latency is going to go way up. This is well known. It is still ignored in most cheap routers. Every home router feeding limited bandwidth should have outbound fair queuing. Looking at individual flows near the network edges is a big win.

Would you please suggest such a home router, including by flashing a free firmware?

above a few hundred mbps, you usually want a x86 box for queuing/fw (any linux will do, try some fw-distros or openwrt) and a separate wifi-ap.

There's fq_pie that's flow-agnostic.

Flow Queuing is in the name so... no?

pie is effectively (adaptive) red

the fq part does most of the work and is intended for edge-routers as bufferspace requirements diminish with growing number of flows.

exactly right. https://blog.cerowrt.org/post/juniper/

We have now produced variants of the flow queuing algorithm for fq-codel, fq-pie, and the FQ in cake, which we are now using in libreqos. It is the best form of fq ever designed, IMHO, with really good min/max fairness properties, resistence to starvation, great rtt fairness and highly complementary simultaneously time based AQM technology easily applied. I would like to see more improvements on the AQM side in the future and for it to land in more hardware.

Admittedly, I´m one of the authors... :)

thanks a lot for your work!

flow-queuing for the mainstream is a godsend in the information age.

Thank you for leveraging it.

but: Eric Dumazet came up with the flow queuing fast/slow queue concept in a single saturday afternoon in his hammock (after admittedly 9 months of hard work on every other fq and aqm algorithm), slammed it into the kernel the next day, and has been building ever more amazing things ever since.

I try to make sure people understand that I am more the acolyte of kathie, van, and Eric, than inventor here. I was proud of this thing we´d developed called SFQred, and writing a paper on it... but then kathie and van came out with codel a month later... obsoleting that part...

Eric and I implemented it over a week, saw that it was far better than RED... I went to sleep for a week, only to wake up to fq_codel, which solved everything.

We have been just re-implementing it and improving the edge cases since. I am pretty happy with cake, now. The world evolves however, and there are new demands on queuing. I cover some of these here: https://docs.google.com/document/d/1tTYBPeaRdCO9AGTGQCpoiuLO...

1. buffersize requirements are not that simple

2. fq_* is meant for end-/edge-routers where the number of flows is rather small

https://web.stanford.edu/~sarslan/files/Updating_the_Theory_...

fq+ we have been running at 25+gbit or more, for quite some time. There are typically 32k FQ_codels in a 10gbit system. I am pretty sure, that we would not have scaled past 10gbit as well as we did, without having made fq_codel and sch_fq (which does pacing), had we not. We run up to 10k instances of cake (4k queues each) in libreqos. Amazing results.

impressive and interesting

i assume performance optimizations for the fast-path were successful, or is this scale-up rooted in advances with multithreading and packetsteering?

fq_codel was successfully offloaded in a few products, however, no offload here, just a xeon with a ton of cores and a big L3. On the libreqos case we leveraged some ebpf to do packet steering in what we call the heimdal bridge, and also kathie nichol´s wonderful passive ping concept: https://github.com/thebracket/cpumap-pping

src here: https://github.com/LibreQoE/LibreQoS/

You can get a transparent high speed bridge with shaping capability up pretty rapidly with supported hardware.

I still long for an ethernet card that can do a trie lookup natively! The flamegraphs are mostly getting the right packet to the right cpu, still.

Dumb enough to me, includes basic fq and aqm technology at the router. FIFOs are the worst form of queuing.

FQ solves most of the problem thoroughly enabling delay based transports, Van and Kathie´s codel, most of the rest. Van was also on the team that produced BBR, which spends most of it´s time in delay based mode when fq_codel is on the path.

I do wish more folk were actively applying cake nowadays. It works wonders.

https://blog.cerowrt.org/post/juniper/

Libreqos is doing nice things with cake.

I looked into congestion control earlier in the year.

It's hilarious to see the things which were hard coded in the first BSD implementation, like a 4 KiB socket buffer size.

Also, as far as I can see, Bill Joy DID actually have linear backoff but it was hidden behind an always-false condition, so his hand-written lesser float backoffs were chosen instead. This seems like a fairly tragic coding error to me.

Probably a case of “Logically this makes sense but let me branch and do it manually to make sure” and never got back to it.

I have code like that. A return then some body of sane looking but outcome unknown code.

The old adage of "There is nothing more permanent than a temporary fix" comes to mind.

the PoC is production

I use `#####` as a sentinel for things that must not be committed, and have a git hook that checks my commits to ensure that marker is not present in the `+` side of a commit delta.

I try not to let code like that make it into git and into the wild. But this is a sane solution to prevent a very bad day.

I feel like it's fine to commit and push that code to some non-master branch, and what really helps is a CI check to verify that code doesn't merge to master.

I use git to sync work between multiple computers, and I want to be able to sync work-in-progress code that should absolutely never see the light of day, so I feel like committing and pushing it to a WIP branch is fine.

Even if you only use one computer, I think it's a good idea to push these things so that if your HDD fails you can pick back up where you left off, even if it's code that's not ready to actually merge yet.

This is a really good (and rare) interview with van, where he and mike finally asked the question - "how did this EVER work?": https://www.youtube.com/watch?v=QP4A6L7CEqA

The ATM part was amusing.

It's still used in the telco space; xDSL runs over ATM, generally speaking.

It's not obvious that TCP/IP would win. I wonder how much of its victory was because it was basically free; the specs were public, and pretty much everyone build an implementation.

Compare that to the other protocols, which tended to be stuck to a vendor (DECnet, AppleTalk, IPX, token ring). That makes interoperability difficult, since in general companies didn't want to license their tech to someone else because it was a competitive advantage.

You can still find the free TCP/IP implementations out there (like tinytcp, which is still floating around).

The stuff that was wild to me was the ATM LAN products, it was out there for a couple years, but then vanished almost as quickly as it arrived.

It wasn't obvious TCP/IP would win for a surprisingly long time[0]. IIUC it was MPLS that addressed the latency issues at the backbone layer for TCP/IP. That, at least IIUC, obviated the major latency advantage ATM had over pure IP backbones.

[0] https://www.cs.columbia.edu/sip/articles/tdc0598cover1_side1...

MPLS didn’t really address latency issues in the core - it scaled PE to PE connectivity by removing full table lookups at the P layer and replacing it with truncated labels.

However the main long-staying effect of MPLS is enabling L2 and L3 VPNs (VRFs).

> I wonder how much of its victory was because it was basically free

Ethernet hubs were much cheaper than anything else. This was the big win. At that point, the only question was TCP/IP or IPX/SPX (Novell).

You could use Ethernet to hook a couple computers in a room together directly and it worked (mostly). Every other technology required some expensive thing to sit in the middle and direct it all.

Then, when you needed to connect a couple rooms together, you could throw a cable over a wall and hook them together.

Finally, when you got tired of debugging the inevitable continuous failures due to the "idiots in that one room", you threw an Ethernet hub into the mix to hook the rooms together. This was a bit more expensive, but still not as expensive as the idiotic middlebox for the other technologies. And the improvement in reliability and debugging was palpable enough that your boss didn't give you too much static. This was THE big win that other technologies couldn't deal with.

Finally, when you had enough computers that even hubs just weren't cutting it, you bought an Ethernet switch. Yeah, that Ethernet switch was about as expensive as the middlebox from all the other technolgies. However, by now, Moore's Law had been running for a few years so an Ethernet switch was simply expensive rather than outrageous. And you had all this installed Ethernet kit, so your sure as hell weren't going to rip it all out.

At this point, the installed base made sure that Ethernet was going to win.

I once worked in a project where the plan was to have 3 switches in a box, ethernet, ATM, and TDM. The 622 Mbps ATM switch chip was much more expensive than a 1 Gig-Ethernet chip. So ATM was dropped pretty quickly from the concept.

ATM-based DSL was a compromise of the different factions inside telcos. The 'net heads' got a fast Internet access technology. The 'Bell heads' got ATM into every home in preparation of all the glorious ATM applications that would be available any moment now.

The author of the original RFC 896 from 1984 and namesake of Nagle's algorithm is John Nagle who is an active user here on Hacker News:

https://news.ycombinator.com/user?id=animats

https://datatracker.ietf.org/doc/html/rfc896

Thirty years ago when I was doing amateur packet radio, the digipeaters would often get crowded and collisions were frequent. If everyone played nice, the exponential backoff timers would work as expected, but it did not take long for people to learn that they could disable the Nagle algorithm, and/or increase the length of their (AX25) preamble so they would own the channel. Increasing the preamble meant that even if there was a collision, the longer preamble would use up enough time so that the "enemy" packet would be finished before the "evil" packet began to send the important bits, so it would be received properly. Disabling the Nagle algorithm (by hard-coding the backoff timer length to zero) would ensure that the "evil" transmitter would be the first one to key up after a collision.

CSMA/CD works pretty well on a shared wire, but not very well on a single radio frequency where you cannot "hear" other people trying to reach the same mountain-top receiver. I'm glad that aspect of congestion is now a thing of the past. (Now that everything (wired) is switched, it's all point-to-point, so the only congestion we get is from insufficient bandwidth on the trunk, and we have ECN for that.)

Slotted aloha enters the chat to talk about the good ol' days. Unfortunately, there was a collision during TX and they had to start over.

> If everyone played nice, the exponential backoff timers would work as expected,

Yes. As I wrote in 1985, in [1], under "Game Theoretic Aspects of Network Congestion" and "Fairness in Packet Switching Systems", about fair queuing,

We would like to protect the network from hosts that are not well-behaved. More specifically, we would like, in the presence of both well-behaved and badly-behaved hosts, to insure that well-behaved hosts receive better service than badly-behaved hosts. We have devised a means of achieving this.

The goal of fair queuing is not to improve network performance overall. The goal of fair queuing is to reward well-behaved hosts over badly-behaved hosts. If everyone is well-behaved, the queue lengths are the same, usually 1 or 0, and fair queuing does little.

There is an inherent conflict between this goal and achieving maximum data transfer rates. If you try for near 100% utilization, the problems become much worse. You can run comfortably at maybe 70%. This was an accepted tradeoff for DoD systems. DoD wants things to keep working in a crisis, even if normal operation is a bit slower.

This is why I'm not a big fan of HTTP/3. It's a attempt to get about 10% more performance in the good case, at the cost of considerable extra complexity and less immunity to gaming the system.

I never wrote about that much at the time, because if I had, people would have realized earlier that traffic shaping is possible, which implies that you can sell and bill for bandwidth and quality of service. We might have ended up with pay per packet.

[1] https://www.rfc-editor.org/pdfrfc/rfc970.txt.pdf

Sales strategies optimize for groups of buyers, so we have pay per packet in categories. Some vendors market products based on traffic patterns, like unlimited transfer at a fixed throughput, limited transfer at unlimited throughput, rate-limited protocol layers, etc. You can absolutely find buyers who want to throw money at you for 100% utilization and then spend all their time in vain trying to get it to not be terrible.

> This is why I'm not a big fan of HTTP/3. It's a attempt to get about 10% more performance in the good case, at the cost of considerable extra complexity and less immunity to gaming the system.

To be clear, are you mainly complaining about the multiple streams aspect here, or do you have other concerns? Because while I'm no expert, using HTTP/3 (or QUIC, I'm ignoring the terminology differences here to avoid confusion with pre-standard QUIC, though I guess maybe we're past that point by now?) with just a single stream seems to be the only scalable solution to a certain problem.

The main problem I've had with TCP is that anybody can maliciously inject an RST, and for long-lived active connections, the chances of this happening approach 1. If you control both ends you can just tell your firewall to drop all RST packets so the applications can keep talking to each other, but ...

Dealing with this at the application layer is ... marginally possible I guess, but not easy unless your application looks a lot like a web browser (and even those tend to usually force the end user to manually fix it). Creating a new TCP connection sucks and you have no idea how much data got dropped after it left the application's buffer.

So we need a UDP reliability layer, since that's the only other general-purpose protocol that actually gets routed (and SCTP is flawed anyway). And dozens of those exist ... but almost none have major use, so I can't trust that they will play nice with the wider internet.

With HTTP/3, if there are major flaws found, I have confidence that - like TCP - it has enough users that someone will come up with an acceptable solution. (admittedly, since it's not part of the kernel it will be harder to actually deploy the fix)

(I guess TCP-over-VPN is also viable for some users)

That's fascinating. RST packets are being generated by a malicious entity out there just throwing them around, to the point that the chances of that approaches 1. I've not seen this in the wild. Most firewalls I've seen will just silently start blocking packets if the connection is quiet for long enough, and not generate an RST. Is there anything you can share about your corner of the Internet where this is common?

Silent blackholing is worse: in this case TCP starts retransmission with exponential delays and the connection basically hangs forever.

One nice side effect of fair queuing is that if endpoints knew that there's fair queuing on a path, they could use delay-minimizing congestion control since they don't have to be afraid of unfair competition.

https://github.com/muxamilian/fair-queuing-aware-congestion-...

I hope more folk try this code out!!

When latency decreased with faster connections but in an environment with packet loss, a new problem emerged: TCP incast collapse. There was plenty of available bandwidth but TCP transfers would slow down, sometimes to a crawl, without QoS, packet shaping, or bandwidth limitations.

Mitigations include high resolution retransmit timers (RTO) and FQCN.

Didn't help: SACK, TCP Reno, and New Reno.

https://dl.acm.org/doi/10.1145/1592681.1592693

https://dl.acm.org/doi/pdf/10.1145/1592681.1592693

These are probably outdated. A lot has changed in TCP stacks since 2009.

Why would something drop packets?

are you talking about [0]?

[0] https://en.wikipedia.org/wiki/TCP_global_synchronization

Here is a realworld example, easily duplicated by anyone with a big fifo AND enough flows, that happens all the time, with cubic: https://blog.cerowrt.org/post/juniper/

The greatest sin of the engineer is to believe that superior technology is all that's needed to succeed.

This is a syndicated from the upstream blog, which gets content from Bruce and Larry earlier:

https://systemsapproach.substack.com/p/how-congestion-contro...

The article kind of missed that Van was the author of RED, and later he and kathie nichols did codel, and later he was on the team that did BBR.

What would the internet have looked like without Van?

Reply on news.ycombinator.com