5 ms·
TCP's congestion control saved the internet
- dtaht 3y agoThe 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?
- lxgr 3y agoThe 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.
- sambazi 3y ago1. 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_of_Buffer_Sizing.pdf https://web.stanford.edu/~sarslan/files/Updating_the_Theory_...
- dtaht 3y agofq+ 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.
- sambazi 3y agoimpressive and interesting i assume performance optimizations for the fast-path were successful, or is this scale-up rooted in advances with multithreading and packetsteering?
- dtaht 3y agofq_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 https://github.com/thebracket/cpumap-pping src here: https://github.com/LibreQoE/LibreQoS/ 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.
- dtaht 3y agoDumb 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/ https://blog.cerowrt.org/post/juniper/ Libreqos is doing nice things with cake.
- Animats 3y ago> 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.
- the8472 3y agoThere's fq_pie that's flow-agnostic.
- wmf 3y agoFlow Queuing is in the name so... no?
- sambazi 3y agopie 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.
- dtaht 3y agoexactly right. https://blog.cerowrt.org/post/juniper/ 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... :)
- sambazi 3y agothanks a lot for your work! flow-queuing for the mainstream is a godsend in the information age.
- dtaht 3y agoThank 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/1tTYBPeaRdCO9AGTGQCpoiuLORQzN_bG3TAkEolJPh28/edit#heading=h.vbbnfu73wlpp https://docs.google.com/document/d/1tTYBPeaRdCO9AGTGQCpoiuLO...
- 0xDEF 3y agoThe 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://news.ycombinator.com/user?id=animats https://datatracker.ietf.org/doc/html/rfc896 https://datatracker.ietf.org/doc/html/rfc896
- anonymousiam 3y agoThirty 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.)
- 1letterunixname 3y agoSlotted aloha enters the chat to talk about the good ol' days. Unfortunately, there was a collision during TX and they had to start over.
- Animats 3y ago> 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 https://www.rfc-editor.org/pdfrfc/rfc970.txt.pdf
- zdw 3y agoThis is a syndicated from the upstream blog, which gets content from Bruce and Larry earlier: https://systemsapproach.substack.com/p/how-congestion-control-saved-the https://systemsapproach.substack.com/p/how-congestion-contro...
- suprjami 3y agoI 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.
- dtaht 3y agoThis 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 https://www.youtube.com/watch?v=QP4A6L7CEqA
- gabereiser 3y agoProbably 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.
- PNewling 3y agoThe old adage of "There is nothing more permanent than a temporary fix" comes to mind.
- throwawaaarrgh 3y agothe PoC is production
- pcl 3y agoI 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.
- TheDong 3y ago
- mannyv 3y agoThe 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).
- bsder 3y ago> 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.
- bewo001 3y agoI 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.
- 1letterunixname 3y agoWhen 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/10.1145/1592681.1592693 https://dl.acm.org/doi/pdf/10.1145/1592681.1592693 https://dl.acm.org/doi/pdf/10.1145/1592681.1592693
- ikekkdcjkfke 3y agoWhy would something drop packets?
- sambazi 3y agoare you talking about [0]? [0] https://en.wikipedia.org/wiki/TCP_global_synchronization https://en.wikipedia.org/wiki/TCP_global_synchronization
- dtaht 3y agoHere 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/ https://blog.cerowrt.org/post/juniper/
- the8472 3y agoThese are probably outdated. A lot has changed in TCP stacks since 2009.
- throwawaaarrgh 3y agoThe greatest sin of the engineer is to believe that superior technology is all that's needed to succeed.