6 ms·
Things we finally know about network queues (2017)
- derefr 5y agoHow much of this applies further up the stack, to e.g. HTTP requests being handled by load balancers that demux to web-app backends?
- kqr 5y agoThis is a good collection of recommendations. At a new job, I often end up making changes to internal queues that (it turns out) conform to these recommendations, and get better performance and reliability out of it. Though I didn't learn it by engineering networks like the author -- I took the ideas from lean product development and applied them also to software. > Corollary: limit queue length to a statistically large burst (eg. 99th percentile). This is somewhat underspecified -- at what time frame are we calling it a burst? How much money/memory/resources are we willing to spend to maintain the queue? But, critically, are we willing to make a queue so long that we sacrifice throughput during a sustained overload? Sometimes it makes sense to handle only a 20 % burst or even less, because the shorter queues lead to nicer behaviour when the burst draws out into sustained overload.
- wtallis 5y agoRound-trip times provide an upper bound on what should be considered a burst, since one RTT is enough time to provide feedback to throttle a burst. Of course, different traffic flows through a bottleneck can have drastically different RTTs, so this isn't too helpful. In practice, CoDel works well for almost all current network technologies with its target parameter at the default of 5ms of allowable queueing delay. Given the structure of today's networks, an individual packet is unlikely to pass through more than a handful of congested bottlenecks, and a small multiple of 5ms of added delay is a tolerable worst-case comparable to the speed of light delays of long-distance connections. It's definitely somewhat unsatisfying to not have formal derivations of optimal parameters. But reasonable defaults that have been tested in the real world are still a huge improvement over the old way of having network devices that don't even attempt to handle congestion intelligently.
- Dowwie 5y agoI'm very interested in your approach applying lean product development patterns to network engineering.
- kqr 5y agoIt's really nothing special, just some general principles that are sensible to me: - Production levelling/burst smoothing early in the process, so other steps don't have to bother with variability. - WIP constraints/limited queue sizes both to reveal problems and improve latency. - Kanban/backpressure to stop the problems at the source, and help troubleshooting. - Using Little's law as a guideline in tradeoffs between batch size and latency and size of system. - Deliberately shed load when it cannot be served in time, rather than vainly holding on to it for dear life because "surely we cannot outright reject work?!" - Dropping at the head of queues to improve latency and serve the fresher requests sooner. There's probably a lot more, and TFA covers some of it too.
- dtaht 5y agoFair queueing makes a huge difference for a large percentage of traffic, and generally makes an AQM work better by better muxing packets. I have a long list of things that can be done listed here: http://www.taht.net/~d/broadcom_aug9_2018.pdf http://www.taht.net/~d/broadcom_aug9_2018.pdf A new one that has cropped up recently in terms of shortening queues, is rigorous application of the TCP_NOTSENT_LOWAT option, everywhere, but especially in containers.
- moonchild 5y agoWhy do we know these things? Why are they true? Does anyone have resources for someone who doesn't know that much about networking justifying these statements?
- Terry_Roll 5y agoI found it to be quite educational to get a DDOS carried out on a public ip of mine to see how a firewall device faired. Lets just say, it was quite interesting seeing various networking queues fill up and different daemons trying to cope. There is certainly an element of fine tuning and knowledge needed across multiple daemons on a firewall device which includes the network stack, not only so that a daemon has the resource to function, but also to play its part in the device function as a whole. When a daemon falls over, it can create a new temporary attack vector, in much the same way as a device rebooting shouldn't be online until everything is loaded and running, but I dont even see that in some switches. You might find some willing individuals on the dark web who can provide such DDOS services, if you wanted to test some things out.
- Jtsummers 5y agoA lot of that follows from a network-specific application of queuing theory: https://en.wikipedia.org/wiki/Queueing_theory https://en.wikipedia.org/wiki/Queueing_theory I'd start there, and branch out to the various links from it or use the keywords you come across to make more searches.
- apenwarr 5y agoThis article was me trying to write down my internal notes on the topic at the time, after having dived very deeply into problems with the set of interlocking network queues inside embedded wifi devices we were working on. I was probably not the first to realize that this set of rules probably applies to all kinds of networks, not just ones in embedded device firmware, but I hadn’t really seen it written down before. But I’m surprised the article ever made it to the HN front page, even 5 years later, since it doesn’t even attempt to address the how/why/how do you know sorts of questions. It’s mainly a placeholder just so I don’t forget. (Those rules for muxes and demuxes and backpressure are really confusing, but I believe them to be strictly correct.) The rule about bottlenecks (there is only ever one) I borrowed from the TCP BBR paper. The rule about queues on a path always being empty except for exactly one that is always full, I think I borrowed from a talk by Stuart Cheshire that I can never seem to find when I look.
- rkeene2 5y agoI haven't had time to read through the whole text but lots of it rings true with my understanding. I wrote an article that, if you like this one, you will probably also gain from: https://dev.to/rkeene/why-is-there-packet-loss-1p8a https://dev.to/rkeene/why-is-there-packet-loss-1p8a
- Bluecobra 5y agoWhy wasn’t the speed of the WAN circuit questioned? To paraphrase Google, OC-12 is so slow I forgot how to count that low. If your link is fast enough, you don’t need to worry about QoS, the switch buffer size, or have to buy an expensive WAN traffic shaping device. :)
- rkeene2 5y agoThe link speed of the circuit doesn't indicate the bandwidth of a channel (MPLS or PVC/SVC), and there is no way to know the possible bandwidth since it's a variable (with upper and lower bounds) and so you always have to worry about this (which is why there's packet loss)
- Bluecobra 5y agoYou realize you can get point to point Ethernet circuits with a fixed speed/fiber path right? I have 100G between my data centers and QoS/buffering is something I don’t need to worry about on my network. Some are these paths are dark fiber and can be easily upgraded to 400G when the time comes.
- rkeene2 5y agoI do, of course, know about the possibility of changing the characteristics of a channel -- it's very likely that this question is not meant to be inflammatory but because it's such a basic thing that I cannot read it any other way. For what it's worth, at the time you could not get 100 Gbps links, but it's unrelated to the fundamental queuing problem and how they are solved in packet switched networks (by dropping packets in the best-effort systems such as IP/Ethernet and by managing credits/counters in guaranteed bandwidth systems like Fibre Channel/ATM). You will still have packet loss if you try to send packets at 600 Gbps in the case of a channel whose upper and lower bounds of capacity are 400 Gbps. There are no infinity capacity channels. Since you have likely more than 400 systems connected at 1Gbps in each data center, you have over provisioned that 400 Gbps link and if each node does 1Gbps you will have packet loss. The value of each packet is probably not equal and so it may make sense to do some kind of QoS for those scenarios (or not, I certainly don't have enough information to answer). This is a problem you can have at any time. If you are in data center operations, you'll do capacity planning to try to mitigate this, but it's still a problem (until there are no overprovisioned paths, which is wasteful and bad engineering in most circumstances). The point of the essay wasn't to describe the scale of a data center, it was to talk about packet loss in a network with queues using a system that was designed around this, and what that means for users of the network.
- HALtheWise 5y agoIt occurs to me that most of these queue size tradeoffs would be eliminated if the queue operated in a LIFO manner (a stack) instead of FIFO. That way, a burst can naturally get absorbed and re-emitted, but steady state high load doesn't result in increased latency, just packet loss. Can someone with more knowledge of networking enlighten me on why this is a terrible idea?
- toast0 5y agoThis isn't a great idea at the packet level. You get really bad results by intentionally reordering packet in a tcp connection. It's not going to be good for any flow that expects packets to arrive in order for the most part (voip calls etc). Plus accumulating old packets isn't great. FIFO preserves order, but the typical behavior is to drop incomming packets when the buffer is full (or to make an absurdly sized buffer), when it's usually better to drop older packets than fresh packets.
- HALtheWise 5y agoCan you elaborate more on why applications handle packet reordering badly? Is it just that applications are written to assume in-order packets are the "fast path" and need to use less optimized code when things come in out-of-order, or is there some other heuristics that assume packet reordering is rare that would misfire here?
- toast0 5y agoTCP is going to be not great because when you receive packets out of order, there's a feedback loop that leads to the source retransmitting the presumed missing, but possibly just delayed packets. Adding more duplicate data to your congested queue makes things worse / keeps them bad. It's much better to drop some packets from the flow than to intentionally misorder them. This property does make it harder to load balance tcp over multiple connections; you get better results if you hash flows, so one tcp connection always goes over the same physical connection, and should remain ordered... Round robin packet sending might be nice, since you wouldn't end up with uneven utilization of individual physical connections in an aggregated connection, but the tcp stack behavior would be much worse and real world bandwidth would not be useful. Actually handling tcp packets out of order isn't nice either, but if the options are drop a packet or delay an earlier packet to send after a later one, we're going to have to handle some packets out of order. This is what ECN (explicit congestion notification) was supposed to help, if you could mark packets as congested before the congestion got bad enough to drop packets; of course, that was hard to get deployed. Things like voip or gaming are going to have trouble with out of order packets too. If you already did something to workaround the missing packet, if it eventually arrives late, you may not have any use for it. If I already played silence (or ??) to get through a missed sample, I can't go back and put in the late sample. Etc. Late at that point is not better than never. There are certainly ways to make protocols where late is better than never; you could have a bulk file transfer protocol that sent all data once before resending or something, but that's not common.
- iforgotpassword 5y ago> Drop packets when demuxing. From y to o, it's best to drop packets at o rather than use backpressure from o to y. Otherwise, a single full output queue could starve the others by stopping y. (Example: imagine if a full queue to a 1 Mbps wifi station could stop traffic to a 100 Mbps wifi station. Some Linux wifi drivers suffer from this.) Aaah, memories. Combined with point 11, pause frames. I was debugging a weird issue with a gbit switch about 15 years ago. Port A is a server sending to port B and C. C is only capable of 100mbits. I could send from A to B at 950mbits, and A to C at 50, all good. As soon as I didn't artificially throttle the rate to C at A, it would eventually hit 100mbits for A -> C, which resulted in the rate from A to B also dropping to 100mbits, so a total output of 200 at A. After a lot of trying and poking I saw these mysterious pause frames in Wireshark, which I glanced over before because who'd wanna look at anything below IP... Once I looked them up and disabled pause frames on all the machines, I got the expected result of 900 to B and 100 to C. And once I figured that out it was trivial to formulate a google query that resulted in exactly this problem and the solution to it, which I failed at before. So ever since then disabling pause frames is one of the first things I do when networking is acting weird. Bonus: Back then when I told an older colleague about my findings, he basically confirmed "pause frames are evil" with another story: Late 90s they started having a problem in another department that entire network segments sometimes became completely unreachable. And the machines in that segment couldn't even communicate with each other. Randomly power-cycling switches and replugging machines solved the problem. After quite some time they tracked it down: Some folks in said department got shiny new laptops, and whenever those entered standby, the NIC "didn't get the message". Its buffer would eventually fill up (as there was no OS running to handle any packets) and from then on, the network segment would get spammed into oblivion with pause frames.
- Bluecobra 5y agoFunnily enough there’s another excellent article by apenwarr that touches on this a bit. Ethernet is designed to go as fast as possible/line rate and assumes that everything is the same speed. When you disabled pause frames, it likely prevented the switch from interfering and punting the issue to the TCP stack of the server/client. https://apenwarr.ca/log/20170810 https://apenwarr.ca/log/20170810
- 5y ago
- w_t_payne 5y agoHow should these lessons be understood in the context of queue oriented models of computation like Lee & Park's Dataflow Process networks, Kahn process network semantics etc? It seems like these models mainly formalise (and aid understanding of) backpressure based mechanisms for message rate control, but have little to say about dropping packets (as this would break the model). I wonder if there are stochastic models of computation that could help to formalize packet drop? (These probably exist -- and now I'm motivated to go and look for them).
- deleted 5y ago[deleted]
- Bluecobra 5y agoTo add to this, there is some inherent latency when queuing packets as well so it’s best to avoid it as much as possible if latency is a concern. Low latency/cut-through switches have really shallow buffers on purpose and will quickly drop packets. To avoid queuing/drops you need to make sure you have ample bandwidth to absorb any microbursts. For example, if you have a 1Gb NIC that is constantly bursting at 1.2Gbps you should upgrade it to 10Gb.
- kloch 5y agoExcessively large buffers confuses TCP windowing. On network devices like switches and routers buffers are only actually needed for two things: internal switching/routing latency (which is usually constant and very small) and serialization onto output interfaces (which varies by input/output port speed mismatch and/or number of inputs multiplexed to one output). Handling network "burstiness" should be left up to the endpoint TCP stack or applications in the case of UDP. Ethernet flow control should be disabled unless you find it actually helps (unlikely). On servers buffers have more work to do since the CPU may be busy with many other tasks. It is rare that I have had to adjust the default buffer sizes but keep in mind server buffers too large can increase jitter as well as confuse TCP windowing (depending on when ACK's are sent). Some applications may prefer that packets be dropped instead of queued for excessively long times. The most important thing is to ensure that selective ACK's and window scaling TCP options are enabled. They are enabled by default in modern operating systems but you might be surprised how often they are disabled by clueless sysadmins. A common cause of this is/was buggy TCP offloading drivers where the apparent "solution" was to disable ALL tcp options instead of just TCP offload. Window scaling in particular is essential with modern port speeds.
- dtaht 5y agoI tried to leave people laughing, here: https://blog.apnic.net/2020/01/22/bufferbloat-may-be-solved-but-its-not-over-yet/ https://blog.apnic.net/2020/01/22/bufferbloat-may-be-solved-... And the online book, freely available and primarily on applying fq_codel to everything (and also sch_cake) is here: https://bufferbloat-and-beyond.net/ https://bufferbloat-and-beyond.net/ In the last decade we've managed to eliminate fifos from most of linux, most 3rd party firmwares notably with openwrt and sqm, ios and OSX. The only major things left unfixed are unfortunately home routers and edges.
- reidjs 5y agoThat was an amazing way of explaining a complex topic. Glad to know there are people much smarter than me keeping the internet alive. Thanks for putting so much work into the demonstration.