Slashdot Mirror
Linux 3.3: Making a Dent In Bufferbloat?
mtaht writes "Has anyone, besides those that worked on byte queue limits, and sfqred, had a chance to benchmark networking using these tools on the Linux 3.3 kernel in the real world? A dent, at least theoretically, seems to be have made in bufferbloat, and now that the new kernel and new iproute2 are out, should be easy to apply in general (e.g. server/desktop) situations."
Dear readers: Have any of you had problems with bufferbloat that were alleviated by the new kernel version?
I've had all sort of trouble with bloat of all kinds since I turned 40.
You name it, it's become bloated: buffers, bellies, butts, pretty much everything.
Bufferbloat...is the result of our misguided attempt to protect streaming applications (now 80 percent of Internet packets) by putting large memory buffers in modems, routers, network cards, and applications. These cascading buffers interfere with each other and with the flow control built into TCP from the very beginning, ultimately breaking that flow control, making things far worse than they’d be if all those buffers simply didn’t exist.
In my day, if your modem had a 16550A UART protecting you with its mighty 16 byte FIFO buffer protecting you, you were a blessed man. That little thing let you potentially multitask. In OS/2, you could even format a floppy disk while downloading something thanks to that sucker.
Has there been widespread empirical analysis of bufferbloat?
No - it is a meme started by one guy ( he of X11 protocol fame ) and there is still quite a sceptical audience.
If your TCP flow-control packets are subject to QoS prioritisation ( as they should be ) then bufferbloat is pretty much moot.
People might be sceptical how big the problem is, but the analysis itself and the diagnosis is sound. Most people are only suprised they did not think about it before.
The math is simple: If you have a buffer that is never empty, every package will have to wait in the buffer. If you have a buffer full all the time, it serves no purpose but only defers every packet. And given that RAM got so cheap that buffers in devices grew so much more than bandwidth, you now often have buffers big enough to hold packets needing full seconds to send them all. Such a buffer running in always-full mode means high latency for no gain.
All additional factors of TCP going harvoc when latency is too high and no longer being able to compute how fast to optimally send if no packages get dropped only make the situation worse, but the basic is simple: A buffer always full is a buffer only having downsizes. The more the bigger it is....
TCP flow-control makes the assumption that dropped packets and retransmission requests are a sufficient method of feedback. When it doesn't receive them, it assumes everything upstream is going perfectly and keeps sending data over (in whatever amounts your QoS setup dictates, but that's not the point).
Except everything upstream is maybe not going well. Other devices on the way may be masking problems -- instead of saying "I didn't get that, resend", they use their local buffers and tell downstream nothing. So TCP flow-control is being kept in the dark. Eventually a buffer runs out and that's when that device starts asking for a huge pile of fresh data at once... which is not how it was supposed to work. So the speed of the connection keeps fluctuating up and down even though pipes seem clear and underused.
The immediate workaround is to trim buffers down everywhere. Small buffers are good... but they shouldn't grow so much as to take a life of their own, so to speak.
One thing done in Linux 3.3 to start adressing this properly is the ability to express buffer size in bytes (Byte Queue Limits (BQL)). Historically they worked with packet amounts only, because they were designed in an era where packets were small... but nowadays they get big too. It gives us better control and somewhat alleviates the problem.
The even better solution is to make buffers work together with TCP flow-control. That would be Active Queue Management (AQM), which is still being developed. It will basically be an algorithm that decides how to adapt use of buffers to traffic bursts. But a good enough algorithm has not been found yet (there's one but it's not very good). When it will be found it will need testing, then wide-scale deployment and so on. That might still take years.
It seems to me that people blame cheap memory and making larger buffers possible for this problem, but no - if there is a problem, it's from bad programming.
Buffering serves a purpose where the rate of receiving data is potentially faster than the rate of sending data in unpredictable conditions. A proper event driven system should always be draining the buffer whenever there is data in it that can possibly be transmitted.
Simply increasing the size of a buffer should absolutely not increase the time that data waits in that buffer.
A large buffer serves to minimize potential dropped packets when there is a large burst of incoming data or the transmitter is slow for some reason.
If a buffer actually adds delay to the system because it's always full beyond the ideal, one of two things is done totally wrong:
a) Data is not being transmitted (draining the buffer) when it should be for some stupid reason.
b) The characteristics of the data (average rate, burstiness, etc.), was not properly analyzed and the system with the buffer does not meet its requirements to handle such data.
In the end, it's about bad design and bad programming. It is not about "bigger buffers" slowing things down.
the alternative is data loss
TCP was designed to work around this by putting predictably sized retransmit buffers on the endpoints, and then the endpoints would scale their transmission rate based on the rate of packet loss that the host on the other end reports. Bufferbloat happens when unpredictably sized buffers in the network interfere with this automatic rate control.
The bufferbloat "movement" infuriates me because it's light on science and heavy on publicity. It reminds me of my dad's story about his buddy who tried to make his car go faster by cutting a hole in the firewall underneath the gas petal so he could push it down further.
There's lots of research on this dating back to the 90's, starting with CBQ and RED. The existing research is underdeployed, and merely shortening the buffers is definitely the wrong move. We should use an adaptive algorithm like BLUE or DBL, which are descendents of RED. These don't have constants that need tuning like queue-length (FIFO/bufferbloat) or drop probability (RED), and they're meant to handle TCP and non-TCP (RTP/UDP) flows differently. Linux does support these in 'tc', but (1) we need to do it by default, not after painful amounts of undocumented configuration, and (2) to do them at >1Gbit/s ideally we need NIC support. FWIH Cisco supports DBL in cat45k sup4 and newer but I'm not positive, and they leave it off by default.
For file sharing, HFSC is probably more appropriate. It's the descendent of CBQ, and is supported in 'tc'. But to do any queueing on cable Internet, Linux needs to be running, with 'tc', *on the cable modem*. With DSL you can somewhat fake it because you know what speed the uplink is, so you can simulate the ATM bottleneck inside the kernel and then emit prescheduled packets to the DSL modem over Ethernet. The result is that no buffer accumulates in the DSL modem, and packets get layed out onto the ATM wire with tiny gaps between them---this is what I do, and it basically works. With cable you don't know the conditions of the wire so this trick is impossible. Also, end users can only effectively schedule their upstream bandwidth, so ISP's need to somehow give you control of the downstream, *configurable* control through reflected upstream TOS/DSCP bits or something, to mark your filesharing traffic differently since obviously we can't trust them to do it.
Buffer bloat infuriates me because it's blitheringly ignorant of implemented research more than a decade old and is allowing people to feel like they're doing something about the problem when really they're just swapping one bad constant for another. It's the wrong prescription. The fact he's gotten this far shows our peer review process is broken.
There is a similar, and well known situation that comes up in database optimization. For example, the Oracle database has over the years optimized its internal disk cache based on its own LRU algorithms, and performance tuning involves a combination of finding the right cache size (there is a point where too much causes performance issues), and manually pinning objects to the cache. If the database is back-ended by a SAN with its own cache and LRU algorithms, you wind up with the same data needlessly cached in multiple places and performance statistics reported incorrectly.
As a result I've run across recommendations from Oracle and other tuning experts to disable the SAN cache completely in favor of the database disk cache. That, or perhaps keep the SAN write dache and disable read cache, because the fact is that Oracle knows better than the SAN the best way to cache data for the application. Add in caching at the application server level, which involves much of the same data, and we have caching of the same information needlessly cached at many tiers.
Then, of course, every vendor at every tier will tell you that you should keep their cache enabled because caching is good and of course it doesn't comflict with other caching, but reality is that caching is not 100% free... there is overhead to manage the LRU chains, do garbage collection, etc. So in the end you wind up dealing with a very similar database buffer bloat issue to Cringely's network buffer bloat. Let's not discount the fact that many serverdisk communications are migrating toward similar communications protocols as networks (NAS, iSCSI, etc). Buffer bloat is not a big deal at home or even a mid-sized corporate intranet, but for super high speed communications like on-demand video, and mission critical multi terrabyte databases, these things matter
Unfortunately, I think you haven't quite got this right.
The problem isn't buffering at the *ends* of the link (the two applications talking to one another), rather, it's buffering in the middle of the link.
TCP flow control works by getting (timely notification of) dropped packets when the network begins to saturate. Once the network reaches about 95% of full capacity, it's important to drop some packets so that *all* users of the link back off and slow down a bit.
The easiest way to imagine this is by considering a group of people all setting off in cars along a particular journey. Not all roads have the same capacity, and perhaps there is a narrow bridge part way along.
So the road designer thinks: that bridge is a choke point, but the flow isn't perfectly smooth. So I'll build a car-park just before the bridge: then we can receive inbound traffic as fast as it can arrive, and always run the bridge at maximum flow. (The same thing happens elsewhere: we get lots of carparks acting as stop-start FIFO buffers).
What now happens is that everybody ends up sitting in a car-park every single time they hit a buffer. It makes the end-to-end latency much much larger.
What should happen (and TCP flow-control will autodetect if it gets dropped packet notifications promptly) is that people know that the bridge is saturated, and fewer people set off on their journey every hour. The link never saturates, buffers don't fill, and nobody has to wait.
Bufferbloat is exactly like this: we try to be greedy and squeeze every last baud out of a connection: what happens is that latency goes way too high, and ultimately we waste packets on retransmits (because some packets arrive so late that they are given up for lost). So we end up much much worse off.
A side consequence of this is that the traffic jams can sometimes oscillate wildly in unpredictable manners.
If you've ever seen your mobile phone take 15 seconds to make a simple request for a search result, despite having a good signal, you've observed buffer bloat.
Why would my buffer be never empty? Just because you have more buffers doesn't mean you process anything slower than you have to. It just means if you can't get around to something immediately, you can catch up later.
That's exactly the problem. TCP relies on packets being dropped in order to manage connections. When buffers are instead allowed to fill up, delaying packets instead of outright dropping them, the application relying on those packets experiences extremely high latency instead of being rate-limited to fit inside of the available bandwidth.
The problem has come to pass because of how counterintuitive this really is. It's a GOOD THING to discard data you can't transfer RIGHT NOW, rather than wait around and send it later.
I suppose one of the only analogs I can think of might be the Blackbird stealth plane. Leaks like a sieve on the ground, spitting fuel all over the place, because at altitude the seals expand so much that they'd pop if it hadn't been designed to leak on the ground. Using gigantic packet buffers would be like "fixing" a Blackbird so that it didn't leak on the runway.
Boot Windows, Linux, and ESX over the network for free.
You are correct that replacing one bad constant with another is a problem, though I certainly argue many of our existing constants are egregiously bad and substituting a less bad one makes the problem less severe: that is what the cable industry is doing this year in a DOCSIS change that I hope starts to see the light of day later this year. That can take bloat in cable systems down by about an order of magnitude, from typically > 1 second to of order 100-200ms; but that's not really good enough for VOIP to work as well as it should. The enemy of the good is the perfect: I'm certainly going to encourage obvious mitigation such as the DOCSIS changes while trying encourage real long term solutions, which involve both re-engineering of systems and algorithmic fixes. There are other places where similar "no brainer" changes can help the situation.
I'm very aware of the research over a decade old, and the fact that what exists is either *not available* where it is now needed (e.g. any of our broadband gear, our OS's, etc.), and *doesn't work* in today's network environment. I was very surprised to be told that even where AQM was available, it was often/usually not enabled, for reasons that are now pretty clear: classic RED and derivatives (the most common available) require manual tuning, and if untuned, can hurt you. As you, I had *thought* this problem was a *solved* problem in the 1990's; it isn't....
RED and related algorithms are a dead end: see my blog entry on the topic: http://gettys.wordpress.com/2010/12/17/red-in-a-different-light/ and in particular the "RED in a different light" paper referenced there (which was never formally published, due to reasons I cover in the blog posting). So thinking we just apply what we have today is *not correct*; when Van Jacobson tells me RED won't hack it (which was originally designed by Sally Floyd and Van Jacobson) I tend to believe him.... We have an unsolved research problem at the core of this headache.
If you were tracking kernel changes, you'd see "interesting" recent patches to RED and other queuing mechanisms in Linux; this shows you just how much such mechanisms have been used, that bugs are being found in this day and age in such algorithms in Linux: in short, what we have had in Linux has often been broken, showing little active use.
We have several problems here:
1) basic mistakes in buffering, where semi-infinite statically sized buffers have been inserted in lots of hardware/software. BQL goes a long way toward addressing some of this in Linux (the device driver/ring buffer bufferbloat that is present in Linux and other operating systems).
2) variable bandwidth is now commonplace, in both wireless and wired technologies. Ethernet scales from 10Mbps to 10 or 40Gps.... Yet we've typically had static buffering, sized for the "worst case". So even stupid things like cutting the buffers proportionately to the bandwidth you are operating at can help a lot (similar to the DOCSIS change), though with BQL we're now in a better place than before.
3) the need for an AQM that actually *works* and never hurts you. RED's requirement for tuning is a fatal flaw; and we need an AQM that adapts dynamically over orders of magnitude of bandwidth *variation* on timescales of tens of milliseconds, a problem not present when RED was designed or most of the AQM research of the 1990's done. Wireless was a gleam in people's eyes in that era.
I'm now aware of at two different attempts at a fully adaptable AQM algorithms; I've seen simulation results of one of those which look very promising. But simulations are ultimately a guide (and sometimes a real improving insight): running code is the next steps, and comparison with existing AQM's in real systems. Neither of these AQM's have been published, though I'm hoping to see either/both published soon and their implementation happening immediately thereafter.
So no, existing AQM algorithms won't hack it; the size of t
Let's assume we do not have TCP first. Assume you have one slowest connection, like the cable from your house to the internet, with both the internet and the net within your house can handle all the load instantly that cable can generate.
Let's take a look at the case where one person in the house (or one program of the person) has a long download running (like serveral hours). If nothing else is happening, you want to utialize the full cable. Let's assume further that by some way he sending server actually get the speed right, so sends exactly as much as the cable to your house can handle. So far, so go.
Now some other program or someone else takes a look at some sites or downloads a small file that takes one second over the cable (if it was only this). This causes some additional traffic, so you get more data than your cable can handle. Your ISP has a buffer at its side of the cable, so the packets will end up in the buffer. But the side you are downloading from still sends as much as the cable, so if the buffer before the cable is big enough, you have exactly one second worth of pakets in your data. The download is still running, nothing else is running, the buffer keeps exactly one second of data in the buffer. Everything still arrives, but everything arrives one second later. There is no advantage of the buffer here, everything is still slowed down by a full second. If you would have dropped one second of data, the server would first have to retransmit this, so being a second late. Thus without the buffer, essentially everything would still arrive at the same time, but any other requests going over the same line would be there immidietly and not a full second later.
Now you won't have something that exactly sends the amount of data your cable can handle. But it will try (everything of course tries to send stuff as good as it can). If they manage to somehow messure your problem and send slower so the buffer empties again, the buffer makes sense. If they can come up with enough data for your buffer to never come empty, your buffer is too big and only creating problems.
For bigger problems now enter TCP (or anything else that wants to introduce realiability to the internet). Some packets might get lost, so you need to retransmit packets if they get lost. For this you wait a bit on the packet and if it does not arrive, you ask for it to be resent. You cannot wait very long for packets, as the user does not like waiting for a long time if it was part of something interactive. So if a packet only arrives a longer time late, the computer will already have sent a request to have the packet resent. So if you have buffers big enough to cache say a whole second of data, and the buffers are even there both ways, then the buffers might already contain multiple requests to resend the same packet and thus also multiple copies of the packet send out (remember, a request to resend a packet might have got lost, too). So while buffers big enough avoid packets being resent, buffers too big cause uncessesary resends.
Now enter the specifics of TCP. Sending as fast is possible is solved in TCP by getting faster and faster till you are too fast (detected by too many packets getting lost) and then getting slower again. If you have buffers around that can cope a big amount of data, one side can send too fast quite a long time, while everything will arrive still (sometimes a bit later, but it does). Sot it gets faster and faster and faster. The latency will get bigger and bigger. Finally the buffer will be full, so packets need to be dropped. But you usually drop the packets arriving latest, so once this moment takes place, there can still be a long time before the other side realizes stuff is missing (like, say a whole second, which is half an eternity for a positronic android ^H^H^H^H^H a computer) so the sending side was still speeding the whole time. Now all TCP connections running over that buffer will collapse, causing all of them to go back to a very slow speed and you lost a whole of packets, much more than if you did not have a buffer at all (some of them even multiple times).
A stealth plane analogy. I didn't see that coming!
(very informative post, btw - thank you:)
May we live long and die out