An Minor Diversion into DNSSEC….

I realised recently an interesting milestone has been reached, that will thrill the people who have slaved on DNSSEC for over a decade: DNSSEC running end-to-end, into the house the way “it should really work” without requiring any configuration or intervention has happened.  After all the SOPA/PIPA anguish, seeing DNSSEC come to life is really, really nice. This post may also interest router hackers who’d like a real home router they can afford, particularly one that will do mesh routing.

Diagnosing Bufferbloat

People (including in my family) ask how to diagnose bufferbloat.

Bufferbloat’s existence is pretty easy to figure out; identifying which hop is the current culprit is harder.  For the moment, let’s concentrate on the edge of the network.

The ICSI Netalyzr project is the easiest way for most to identify problems: you should run it routinely on any network you visit. as it will tell you of lots of problems, not just bufferbloat.  For example, I often take the Amtrak Acela express, which has WiFi service (of sorts).  It’s DNS server did not randomize its ports properly, leaving you vulnerable to man-in-the-middle attacks (so it would be unwise to do anything that requires security); this has since been fixed, as today’s report shows (look at the “network buffer measurements”).  This same report shows very bad buffering, in both directions, of about 6 seconds up, and 1.5 seconds downstream.  Other runs today show much worse performance, including an inability to determine the buffering entirely (netalyzr cannot always determine the buffering in the face of cross traffic or other problems; it conservatively only reports buffering if it makes sense).

Netalyzer Uplink buffer test results

As you’d expect, performance is terrible (you can see what even “moderate” bufferbloat does in my demo video on a fast cable connection).  The train buffering is similar to what my brother has on his DSL connection at home; but as the link is busy with other users, the performance is continually terrible, rather than intermittently terrible.  6 seconds is commonplace; but the lower right hand netalyzr data is cut off since ICSI does not want their test to run for too long.

In this particular case,  with only a bit more investigation, we can guess most of the problems are in the train<->ISP hop, because my machine reports high bandwidth on its WiFi interface (130Mbps 802.11n), with the uplink speeds a small fraction of that, so the bottleneck to the public internet is usually in that link, rather than the WiFi hop (remember, it’s just *before* the lowest bandwidth hop that the buffers fill in either direction).  In your home (or elsewhere on this train), you’d have to worry about the WiFi hop as well unless you are plugged directly into the router. But further investigation shows additional problems.

If netalyzr isn’t your cup of tea, you may be able to observe what is happening with “ping”, while you (or others) load your network.

By “ping”ing the local router on the train and also somewhere else, you can glean additional information. As usual, a dead giveaway for bufferbloat is high and variable RTT’s with little packet loss (but sometimes packets are terribly delayed and out of order; packets stuck in buffers for even 10′s of seconds are not unusual). Local pings vary much more that you might like, sometimes as much as several hundred milliseconds, but occassionally even multiple seconds on occasion.  Here, I hypothesize bloat in the router on the train, just as I saw inside my house when I first understood that bufferbloat was a generic problem with many causes. Performance is terrible at times due to the train’s connection; but also a fraction of the time due to serving local content with bloat in the router.

Home router bloat

Specifically, if the router has lots of buffering (as most modern routers do; often 256-1250 packets), and is using a default FIFO queuing discipline, it is easy for a router to fill these buffers with packets all destined for the same machine that is operating at a fraction of the speed that WiFi might go.  Ironically, modern home routers tend to have much larger buffering than old routers, due to changes in upstream operating systems optimized toward bandwidth, whose systems were not tested for latency.

Even if “correct” buffering were present (actually an oxymoron), the bandwidth can drop from the 130 Mbps I see to the local router all the way down to 1Mbps, the minimum speed WiFi will operate at, so your buffering can be very much too high even at the best of times.  Moving your laptop/pad/device a few centimeters can make a big difference in bandwidth. But since we have no AQM algorithm to control the amount of buffering, recent routers have been tuned (to the extent they’ve been tuned at all) to operate at maximum bandwidth, even though this means the buffering available can easily be 100 times too much when running slowly (which all turns into delay).  One might also hope that a router would prevent starvation to other connections in such circumstances, but as these routers are typically running with a FIFO queuing disciple, they won’t.  A local (low RTT) flow can get a much higher fraction of bandwidth than a long distance flow.

To do justice to the situation, it is also possible that the local latency variation is partially caused by device driver problems in the router: Dave Taht’s experience has been that 802.11n WiFi device drives often buffer many more packets than they should (beyond that required for good performance when aggregating packets for 802.11n), and he, Andrew McGregor, and Felix Fietkau spent a lot of time last fall reworking one of those Linux device drivers. Since wireless on the train supports 802.11n, we know implies that these device drivers are in play; fixing these problems for the CeroWrt project was a prerequisite for later work on queuing and AQM algorithms.

Bufferbloat demonstration videos

If people have heard of bufferbloat at all, it is usually just an abstraction despite having personal experience with it. Bufferbloat can occur in your operating system, your home router, your broadband gear, wireless, and almost anywhere in the Internet.  They still think that if experience poor Internet speed means they must need more bandwidth, and take vast speed variation for granted. Sometimes, adding bandwidth can actually hurt rather than help. Most people have no idea what they can do about bufferbloat.

So I’ve been working to put together several demos to help make bufferbloat concrete, and demonstrate at least partial mitigation. The mitigation shown may or may not work in your home router, and you need to be able to set both upload and download bandwidth.

Two  of four cases we commonly all suffer from at home are:

1. Broadband bufferbloat (upstream)
2. Home router bufferbloat (downstream)

Rather than attempt to show worst case bufferbloat which can easily induce complete failure, I decided to demonstrate these two cases of “typical” bufferbloat as shown by the ICSI data. As the bufferbloat varies widely as the ICSI data shows, your mileage will also vary widely.

There are two versions of the video:

1. A short bufferbloat video, of slightly over 8 minutes, which includes both demonstrations, but elides most of the explanation. It’s intent is to get people “hooked” so they will want to know more.
2. The longer version of the video clocks in at 21 minutes, includes both demonstrations, but gives a simplified explanation of bufferbloat’s cause, to encourage people to dig yet further.

Since bufferbloat only affects the bottleneck link(s), and broadband and WiFi bandwidth are often similar and variable, it’s very hard to predict where you will have trouble. If you to understand that the bloat grows just before the slowest link in a path, (including in your operating system!) you may be able to improve the situation. You have to take action where the queues grow. You may be able to artificially move the bottleneck from a link that is bloated to one that is not. The first demo moves the bottleneck from the broadband equipment to the home router, for example.

To reduce bufferbloat in the home (until the operating systems and home routers are fixed), your best bet is to ensure your actual wireless bandwidth is always greater than your broadband bandwidth (e.g., by using 802.11n and possibly multiple access points) and use bandwidth shaping in the router to “hide” the broadband bufferbloat.  You’ll still see problems inside your house, but at least, if you also use the mitigation demonstrated in the demo, you can avoid problems accessing external web sites.

The most adventurous of you may come help out on the CeroWrt project, an experimental OpenWrt router where we are working on both mitigating and eventually fixing bufferbloat in home routers. Networking and ability to reflash routers required!

CACM: BufferBloat: What’s Wrong with the Internet?

Communications of the ACM: Bufferbloat: What’s Wrong with the Internet?

February issue of the Communications of the ACM.

A discussion with Vint Cerf, Van Jacobson, Nick Weaver, and Jim Gettys

This is part of an ACM Queue case study, accompanying Kathie Nichols and my article that appeared in the January 2012 CACM (Communications of the ACM).

CACM: Bufferbloat: Dark Buffers in the Internet

Vint Cerf recommended that I start immediately blogging about bufferbloat a year or so ago, given the severity of the problem to avoid the usual publication delays; that’s why things appeared here first.

But more formal publication has its merits; in particular, having articles for less directly involved in networking and/or more managerially oriented technical managers is very important. So I’ve been working with/in ACM queue to put together a case study. It has now appeared as an article in the January 2012 issue of CACM (Communications of the ACM) in dead-tree form.  There will also be a full paper posted in ACM queue, but to make the January CACM, we put that aside to finish the (much shorter) article.

Apple Patents Portrait-Landscape Flipping: the patent system is broken…

I noticed with interest Slashdot’s article last week on Apple Patenting Portrait-Landscape flipping based on control of one or more accelerometers in Slashdot last week.  As I work at Bell Labs these days, I don’t read patents, so I’ll just go on the summary I read there.

Here’s some prior art from June 2001.  In that period, at Compaq/HP’s Cambridge Research Laboratory, we had ported Linux to the iPAQ handheld (with touch screen & expansion capability). Colleagues of mine, including Jamey Hicks, Andy Christian, Frank Bomba, Ben Curis had built an expansion pack for the iPAQ, called the BackPAQ (just like Apple has an I fetish, Compaq had a paq fetish and liked “i”s as well), with accelerometer, camera, and additional expansion capability including additional battery, for our (and other’s) research as part of “Project Mercury”; it was obvious that such devices would become standard in short order, but no device at the time had them integral. Quite a few BackPAQ’s were built and distributed to researchers around the world (small number of hundreds, if I remember correctly). We wrote some papers, distributed a bunch of BackPAQ’s to like minded researchers around the world, and demonstrated the code at the Usenix conference and elsewhere, and published all the code on handhelds.org (which seems down at the moment). The probability of Apple employees having seen this device and it rotating the screen is an absolute certainty; not only did we show the BackPAQ off at numerous conferences, but we built significant numbers used at universities.

It was blindingly obvious to us that hooking up the accelerometer to be able to rotate the screen would be “a good idea”.  Keith Packard and I wrote the xrandr X Window System extension specifically to support screen rotation, for the iPAQ handheld using his TinyX driver (the X extension then became a standard part of the X Window System releases in X.org).  I wrote (in an hour or two) the first version of the xaccel daemon that took the accelerometer data and controlled the screen rotation.  I first packaged it (in ipgk format, for the iPAQ Familiar Linux distribution) on June 11, 2001 to enable the code’s distribution. Ironically, I like what I remember of xaccel’s behaviour better than what I now see on the iPhone and the iPad I own.

Since I can’t go reading Apple’s patent itself, I’ll just note:

• This is a handheld device, with 802.11 wireless (later versions of the iPAQ became phones).
• It has a touch screen
• It has an accelerometer in the BackPaq
• It used the data from the accelerometer with simple heuristics to control the orientation (portrait or landscape) of the screen (in this case, running the X Window System

Now, maybe you’d like to quibble and claim the idea of putting an accelerometer in a hand-held device is non-obvious.  I think it was pretty obvious, myself, and doing that goes to the group working on Project Mercury. I don’t remember any patent being filed there. And having done so, it seemed obvious to hook it up to the screen. I know we did not file any patents. Are either of these ideas worth a patent? Personally, I think both ideas are pretty obvious, the first idea more original than the second.

But I’m sure the first handheld device with touch screen, with accelerometer, rotating the screen under control of that accelerometer was in my hand running my code below, sometime in the year 2000 or 2001 (I haven’t tried to excavate the exact date),  and that it was widely published on the Internet and used by hundreds of people.

Since handhelds.org seems down at the moment, I spent 5 minutes digging around for the code itself elsewhere.  It’s short enough I include it below (looks like the copyright notice got cut and pasted from the xrandr code); it was called xaccel.c, strangely.

Update 1:

Comments make it clear I fired before aiming carefully: the patent at question apparently is on multitouch gestural overrides to accelerometer screen flipping, apparently. If so, my apologies to Apple.

We have three problems here:

1. prior art, which may not apply to my example certainly we did not have a multi-touch screen to play with and did not explore that area.
2. Obviousness may be in the eye of the beholder, but certainly I’ve seen ideas which were non-obvious. The current broken patent system is encouraging filing of patents just for protection of every trivial idea, and to use as weapons against competitors, whether there is merit in them or not.
3. the treble damages problem, which is why I did not go read the patent in the first place, and stifles actual innovation (independent of whether you thing software patents are a good or bad idea, being unable to know what is going on elsewhere defeats part of the original bargain of why patents were granted in the first place.

And I still like my algorithm better than what I experience on the iPad, which often flips the screen when I don’t want it to flip and begs out for overriding.

Update 2

Jaharks of CMU in a comment below notes that the Itsy folks did gesture based screen rotation on the Itsy.  Quite a few Itsy‘s (the spiritual predecessor to the iPAQ, and to my knowledge the first handheld device to run Linux, and the inspiration/cause of our handhelds.org work) were built and distributed to universities, along with the source code.

Progress on the cable front…

I know it’s not anyone’s idea of fun to monitor gigantic specs; I certainly don’t do so.  I  think the following tidbit, while public information, has not been noticed by people.

The cable data spec (DOCSIS) has an engineering change in progress to allow the control of buffering in cable modems that was published early this year.  This will allow operators to at least mitigate (reduce) bufferbloat by setting the buffering to something related to the provisioned bandwidth, rather than the current state of buffering, which is either a) whatever size RAM happened to be available in the device, or b) is sized to be the (invalid) BDP “rule of thumb” for the maximum possible bandwidth that hardware might ever be used in (resulting in greatly overbuffered devices when used by most people at the typical bandwidths (e.g. 10Mbps service with a DOCSIS 3 modem capable of 100Mbps). The feature is called “buffer control” for those who want to dig into the specs.

As a concrete example, this might allow the modem I happen to have to have its worse case latency reduced from the 1.2 seconds I observed at 20Mbps to of order 100ms.  This isn’t perfect, but it’s a whole lot better indeed.  To really solve the problem to get latencies under load where they could be, we’ll need real AQM that can work in this environment, which is more of a challenge as noted for reasons elsewhere in this blog. I have no information as to whether any deployed cable modems will ever see new firmware to support this addition to the DOCSIS specification.

I gather than new cable modems that support this change to the DOCSIS spec will be in the market by late this year; but note that deploying the support elsewhere in ISP’s networks to configure them will take more time, and probably won’t happen until next year.

I have no information of if there are similar changes underway to modify the other widespread broadband technologies (e.g. DSL and fiber).

It is a good start to getting things fixed .  Hopefully the market will now help to spread such mitigation steps in the industry.

 

Rant warning: there is no single right answer for buffering, ever… (part 2)

It’s clear my previous post was ill formed.  Let me clarify a bit.

1. I’m really, really, really, happy to see the work in Tomato USB w/reduced buffer bloat, as I am in the work going on to control buffering in DOCSIS (cable modems). Let me make this clear up front as somewhat of an apology to hechacker1.The enemy of the good is the perfect, and we can and should do what we can quickly to suffer less.
2. Work to fix bufferbloat is going to be both a “do what we can right away” activity, as well as a long term fundamental redesign problem.  I am deeply unhappy as to quite the depth of that redesign problem.

I’d been thinking of the buffer management problem as a two part problem; the OS level queuing and buffering has been divorced from the device drivers, and how to better integrate the buffer management.  But hechacker1′s post made it clear it was yet more complex. Somehow, we need to get to a more intelligent unified view of queuing across all of these to handle the dynamic range found in today’s networks. Linux queue disciplines themselves may have independent buffering as well as in this example. The integration problem  is therefore more deep. I expect we’ll find similar issues elsewhere in other systems too.

Van Jacobson had warned me last fall of just how challenging the buffering problem was, and I had understood (part) of what he had told me; but it’s clear it has yet more dimensions than I had appreciated then.  That’s my deep unhappiness.

Rant warning: there is no single right answer for buffering, ever…

I was just doing my usual google for bufferbloat, to see what’s going on out there….

I came across Tomato USB w/reduced buffer bloat; it left me deeply unhappy.

I’m unhappy as it’s missing a fundamental point to the bufferbloat mess: there is never any single right answer for buffering in a general purpose system.  To give a simple example: on a loaded 802.11 network, even a single packet of buffering can be an issue and add significant latency (1 packet = 1500 bytes = 12000 bits = 12ms/packet @ 1MBPS) ; but when operating with that identical hardware at 802.11n speeds, we’ll need potentially many packets of buffering (and AQM to boot, to control background elephant flows that would otherwise fill those buffers). And bandwidth on wireless can change by an order of magnitude (or more) when you move a machine a centimeters.  So there isn’t a simple “tuning” point either; it’s dynamic.

The buffer management problem here is really hard; and will be a real challenge to get right.  While twisting knobs to mitigate bufferbloat may be helpful at times (particularly now, while buffering is often so grossly wrong), it’s not going to really this problem.

As a final aside to the above link, so long as the device drivers are radically over buffered, all our fancy QOS queueing and traffic shaping facilities is almost impossible to work right (they can’t even be effective if the OS is dropping the packets into the device driver before noticing that the packets may need to be resorted); OS buffer management needs to be rethought end-to end, and interact much better with today’s “smart” underlying hardware.  It’s a really, interesting, difficult problem that has been under the radar for many years, while the situation stewed.

All that being said, I’m happy to see people beginning to take action in ways that may help the home mess (which seems to be where bufferbloat is most serious).

Google TechTalk video is up

I gave bufferbloat talks at Microsoft Research, Apple, Google and a workshop during the week of  April 24; the slides are available. A video of the talk is up as part of the Google TechTalk series.  My thanks to Greg Chesson, Mark Chow and Denton Gentry to pulling together the video despite technical difficulties, and my thanks to Vint Cerf for the kind introduction.

I’ll be giving an abbreviated version of this talk at the NANOG 52 meeting (North American Network Operators Group) in Denver at the Sheraton, on Tuesday, June 14, in the Grand Ballroom at 11:30AM. I’ll try to focus that talk a bit more on the consequences to those operating networks, as best I can given limited time.