Very occasionally, everyone will have network trouble, such as occurred to us this morning. Sometimes it is our “last mile” connection: it is easy to see these failures in our cable modem log. (Often available by looking at the address 192.168.100.1, which seems to be the default address for cable modems.). Occasionally it can be the ISP (in our case, Comcast), either due to some routing failure or DNS failure. These can be harder to diagnose.

Bufferbloat, however, is insidious. It comes and goes, and most users have been “trained” to ignore temporary bad behavior over many years. When you go to diagnose your network, you usually stop the operation that is causing bufferbloat. This blog has recorded our efforts to fix bufferbloat. Now that there are many more people at home at the same time trying to use more demanding applications, this problem is much more common. Other people in your home can inflict the bufferbloat problem on you without anyone understanding what is happening.

Yesterday afternoon I was helping my wife learn how to edit videos that she now makes and uploads for her students, and one of her co-workers, who we’ll call  “Carleen”, called on a video class planning. Those of you who wonder what teachers do when not teaching should understand that not only do teachers grade materials and give other feedback to students, but also spend much of their time preparing future classes. The amount of “prep” time diminishes the more often a good teacher has taught a given subject, but never drops to anything close to zero. At the moment, learning to teach remotely is an extreme extra burden of preparation.

In the first phase of learning from home, assignments to students consisted of watching videos and performing on line work sheets. None of these activities are latency sensitive. As of this week, the next phase of instruction includes teachers attempting more “conventional” instruction via on-line teleconferencing (Google Meet, in their case). Teleconferencing is by its nature very latency sensitive.

Carleen shares her home with her husband and two sons of age seven and ten. She reported that yesterday her class had been aborted entirely due to intermittent network problems caused by her kids playing games. She has now banished her kids from their video games during her class times, but this cure may be worse than the disease with two bored children in the house; only time will tell. Transient problems caused by bufferbloat now really matter to her, and to her classes, whether they know it or not.

In my early bufferbloat talks, I called bufferbloat the “The Internet is Slow Today, Daddy” problem. But anyone can inflict pain on others sharing a connection if bufferbloat is present; it is just as much a “Kids, quit what you are doing so I can teach” problem.

Thankfully, I can now make concrete recommendations on how you can solve bufferbloat in your environment. My “go to” recommendation for non-geeks is currently the EvenRoute IQRouter. This device will both mitigate bufferbloat in your “last mile”, and fix it in the WiFi link to your device, without any manual tuning. At this moment, I am not aware of any other home router that deals with bufferbloat both in the “last mile” and in WiFi; either or both can be a problem at any given instant.

Needless to say, I recommended that Carleen buy one of those routers.

We do not pay teachers anything like what they are worth. I wish that all ISPs would increase the upstream bandwidth of all connections to teachers for the duration of the Covid-19 crisis, which would help diminish the bufferbloat problem (bufferbloat is generally most severe in the upstream link, and many teachers cannot afford expensive tiers of Internet service). Those hurt most by bufferbloat are those with the most minimal service:  impecunious teachers, and also the students whose parents are least able to afford higher tier internet service. The bufferbloat problem therefore affects children of both rich and poor, directly or indirectly.

A few network speed test sites have tests for bufferbloat, such as DSLReports Speedtest but there are many ways to test explicitly for bufferbloat, as outlined here.

This is indeed a myth.  Much of the current morass can be laid at the feet of the United States government, due to its export regulations around cryptography.

I will testify against the myth.  Bob Scheifler and I started the X Window System in 1984 at MIT, which is a network transparent window system: that is, applications can reside on computers anywhere in the network and use the X display server. As keyboard events may be transmitted over the network, it was clear to us from the get-go that it was a security issue. It is in use to this day on Linux systems all over the world (remote X11 access is no longer allowed: the ssh protocol is used to tunnel the X protocol securely for remote use). By sometime in 1985 or 1986 we were distributing X under the MIT License, which was developed originally for use of the MIT X Window System distribution (I’d have to go dig into my records to get the exact date).

I shared an office with Steve Miller at MIT Project Athena, who was (the first?) programmer working on Kerberos authentication service, which is used by Microsoft’s Active Directory service. Needless to say, we at MIT were concerned about security from the advent of TCP/IP.

We asked MIT whether we could incorporate Kerberos (and other encryption) into the X Window System. According to the advice at the time (and MIT’s lawyers were expert in export control, and later involved in PGP), if we had even incorporated strong crypto for authentication into our sources, this would have put the distribution under export control, and that that would have defeated X’s easy distribution. The best we could do was to leave enough hooks into the wire protocol that kerberos support could be added as a source level “patch” (even calls to functions to use strong authentication/encryption by providing an external library would have made it covered under export control). Such a patch for X existed, but could never be redistributed: by the time that export controls were relaxed, the patch had become mostly moot, as ssh had become available, which, along with the advent of the World Wide Web, was “good enough”, though far from an ideal solution.

Long before the term Open Source software was invented, open source and free software was essential to the Internet for essential services. The choice for all of us  working on that software was stark: we could either distribute the product of our work, or enter a legal morass, and getting it wrong could end up in court, as Phil Zimmerman did somewhat later with PGP.

Anyone claiming security was a “failure of imagination” does not know the people or the history and should not be taken seriously. Security mattered not just to us, but everyone working on the Internet. There are three software legacies from Project Athena: Kerberos, the X Window System, and instant messaging. We certainly paid much more than lip service to Internet security!

Government export controls crippled Internet security and the design of Internet protocols from the very beginning: we continue to pay the price to this day.  Getting security right is really, really hard, and current efforts towards “back doors”, or other access is misguided. We haven’t even recovered from the previous rounds of government regulations, which has caused excessive complexity in an already difficult problem and many serious security problems. Let us not repeat this mistake…

Bufferbloat is responsible for much of the poor performance seen in the Internet today and causes latency (called “lag” by gamers), triggered even by your own routine web browsing and video playing.

But bufferbloat’s causes and solutions remind me of the old parable of the Blind Men and the Elephant, updated for the modern Internet:

It was six men of Interstan,
 To learning much inclined,
Who sought to fix the Internet,
 (With market share in mind),
That evil of congestion,
 Might soon be left behind.

Definitely, the pipe-men say,
A wider link we laud,
For congestion occurs only
When bandwidth exceeds baud.
If only the reverse were true,
We would all live like lords.

But count the cost, if bandwidth had
No end, money-men say,
But count the cost, if bandwidth had
No end, money-men say,
Perpetual upgrade cycle;
True madness lies that way.

From DiffServ-land, their tried and true
Solution now departs,
Some packets are more equal than
Their lesser counterparts.
But choosing which is which presents
New problems in all arts.

“Every packet is sacred!” cries
The data-centre clan,
Demanding bigger buffers for
Their ever-faster LAN.
To them, a millisecond is
Eternity to plan.

The end-to-end principle guides
A certain band of men,
Detecting when congestion strikes;
Inferring bandwidth then.
Alas, old methods outcompete their
Algorithmic maven.

The Isolationists prefer
Explicit signalling,
Ensuring each and every flow
Is equally a king.
If only all the other men
Would listen to them sing!

And so these men of industry,
Disputed loud and long,
Each in his own opinion,
Exceeding stiff and strong,
Though each was partly in the right,
Yet mostly in the wrong!

So, oft in technologic wars,
The disputants, I ween,
Rail on in utter ignorance,
Of what each other mean,
And prate about an Internet,
Not one of them has seen!

Jonathan Morton, with apologies to John Godfrey Saxe

Most technologists are not truly wise: we are usually like the blind men of Interstan. The TCP experts, network operators, telecom operators, router makers, Internet service operators, router vendors and users have all had a grip *only* on their piece of the elephant.

The TCP experts look at TCP and think “if only TCP were changed” in their favorite way, all latency problems would be solved, forgetting that there are many other causes of saturating an Internet link, and that changing every TCP implementation on the planet will take time measured in decades. With the speed of today’s processors, almost everything can potentially transmit at gigabits per second. Saturated (“congested”) links are *normal* operation in the Internet, not abnormal. And indeed, improved congestion avoidance algorithms such as BBR and mark/drop algorithms such as CoDel and PIE are part of the solution to bufferbloat.

And since TCP is innately “unfair” to flows with different RTT’s, and we have both nearby (~10ms) or (inter)continental distant (~75-200ms) services, no TCP only solution can possibly provide good service. This is a particularly acute problem for people living in remote locations in the world who have great inherent latency differences between local and non-local services. But TCP only solutions cannot solve other problems causing unnecessary latency, and can never achieve really good latency as the queue they build depend on the round trip time (RTT) of the flows.

Network operators often think: “if only I can increase the network bandwidth,” they can banish bufferbloat: but at best, they can only move the bottleneck’s location and that bottleneck’s buffering may even be worse! When my ISP increased the bandwidth to my house several years ago (at no cost, without warning me), they made my service much worse, as the usual bottleneck moved from the broadband link (where I had bufferbloat controlled using SQM) to WiFi in my home router. Suddenly, my typical lag became worse by more than a factor of ten, without having touched anything I owned and having double the bandwidth!

The logical conclusion of solving bufferbloat this way would be to build an ultimately uneconomic and impossible-to-build Internet where each hop is at least as fast as the previous link under all circumstances, and which ultimately collides with the limits of wireless bandwidth available at the edge of the Internet. Here lies madness. Today, we often pay for much more bandwidth than needed for our broadband connections just to reduce bufferbloat’s effects; most applications are more sensitive to latency than bandwidth, and we often see serious bufferbloat issues at peering points as well in the last mile, at home and using cellular systems. Unnecessary latency just hurts everyone.

Internet service operators optimize the experience of their applications to users, but seldom stop to see if the their service damages that of other Internet services and applications. Having a great TV experience, at the cost of good phone or video conversations with others is not a good trade-off.

Telecom operators, have often tried to limit bufferbloat damage by hacking the congestion window of TCP, which does not provides low latency, nor does it prevents severe bufferbloat in their systems when they are loaded or the station remote.

Some packets are much more important to deliver quickly, so as to enable timely behavior of applications. These include ACKS, TCP opens, TLS handshakes, and many other packet types such as VOIP, DHCP and DNS lookups. Applications cannot make progress until those responses return. Web browsing and other interactive applications suffer greatly if you ignore this reality. Some network operation experts have developed complex packet classification algorithms to try to send these packets on their way quickly.

Router manufacturers often have extremely complex packet classification rules and user interfaces, that no sane person can possibly understand. How many of you have successfully configured your home router QOS page, without losing hair from your head?

Lastly, packet networks are inherently bursty, and these packet bursts cause “jitter.” With only First In First Out (FIFO) queuing, bursts of tens or hundreds of packets happen frequently. You don’t want your VOIP packet or other time sensitive to be arbitrarily delayed by “head of line” blocking of bursts of packets in other flows. Attacking the right problem is essential.

We must look to solve all of these problems at once, not just individual aspects of the bufferbloat elephant. Flow Queuing CoDel (FQ_CoDel) is the first, but will not be the last such algorithm. And we must attack bufferbloat however it appears.

Flow Queuing Codel Algorithm: FQ_CoDel

Kathleen Nichols and Van Jacobson invented the CoDel Algorithm (described now formally in RFC 8289), which represents a fundamental advance in Active Queue Management that preceded it, which required careful tuning and could hurt you if not tuned properly.  Their recent blog entry helps explain its importance further. CoDel is based on the notion of “sojourn time”, the time that a packet is in the queue, and drops packets at the head of the queue (rather than tail or random drop). Since the CoDel algorithm is independent of queue length, is self tuning, and is solely dependent on sojourn time, additional combined algorithms become possible not possible with predecessors such as RED.

Dave Täht had been experimenting with Paul McKenney’s Stochastic Fair Queuing algorithm (SFQ) as part of his work on bufferbloat, confirming that many of the issues are caused by head of line blocking (and unfairness of differing RTT’s of competing flows) were well handled by that algorithm.

CoDel and Dave’s and Paul’s work inspired Eric Dumazet to invent the FQ_Codel algorithm almost immediately after the CoDel algorithm became available. Note we refer to it as “Flow Queuing” rather than “Fair Queuing” as it is definitely “unfair” in certain respects rather than a true “Fair Queuing” algorithm.

Synopsis of the FQ_Codel Algorithm Itself

FQ_CoDel, documented in RFC 8290, uses a hash (typically but not limited of the usual 5-tuple identifying a flow), and establishes a queue for each, as does the Stochastic Fair Queuing (SFQ) algorithm. The hash bounds memory usage of the algorithm enabling use on even small embedded router or in hardware. The number of hash buckets (flows) and what constitutes a flow can be adjusted as needed; in practice the flows are independent TCP flows.

There are two sets of flow queues: those flows which have built a queue, and queues for new flows.

The packet scheduler preferentially schedules packets from flows that have not built a queue from those which have built a queue (with provisions to ensure that flows that have built queues cannot be starved, and continue to make progress).

If a flow’s queue empties, and packets again appear later, that flow is considered a new flow again.

Since CoDel only depends on the time in queue, it is easily applied in FQ_CoDel to ensure that TCP flows are properly policed to keep their behavior from building large queues.

CoDel does not require tuning and works over a very wide range of bandwidth and traffic. Combining flow queuing with a older mark/drop algorithm is impossible with older AQM algorithms such as Random Early Detection (RED) which depend on queue length rather than time in queue, and require tuning. Without some mark/drop algorithm such as CoDel, individual flows might fill their FQ_CoDel queues, and while they would not affect other flows, those flows would still suffer bufferbloat.

What Effects Does the FQ_CoDel Algorithm Have?

FQ_Codel has a number of wonderful properties for such a simple algorithm:

• Simple “request/response” or time based protocols are preferentially scheduled relative to bulk data transport. This means that your VOIP packets, your TCP handshakes, cryptographic associations, your button press in your game, your DHCP or other basic network protocols all get preferential service without the complexity of extensive packet classification, even under very heavy load of other ongoing flows. Your phone call can work well despite large downloads or video use.
• Dramatically improved service for time sensitive protocols, since ACKS, TCP opens, security associations, DNS lookups, etc., fly through the bottleneck link.
• Idle applications get immediate service as they return from their idle to active state. This is often due to interactive user’s actions and enabling rapid restart of such flows is preferable to ongoing, time insensitive bulk data transfer.
• Many/most applications put their most essential information in the first data packets after a connection opens: FQ_CoDel sees that these first packets are quickly forwarded. For example, web browsers need the size information included in an image before being able to complete page layout; this information is typically contained in the first packet of the image. Most later packets in a large flow have less critical time requirements than the first packet(s).
• Your web browsing is significantly faster, particularly when you share your home connection with others, since head of line blocking is no longer such an issue.
• Flows that are “well behaved” and do not use more than their share of the available bandwidth at the bottleneck are rewarded for their good citizenship. This provides a positive incentive for good behavior (which the packet pacing work at Google has been exploiting with BBR, for example, which depends on pacing packets). Unpaced packet bursts are poison to “jitter”, that is the variance of latency, which sets how close to real time other algorithms (such as VOIP) need to operate.
• If there are bulk data flows of differing RTT’s, the algorithm ensures (in the limit) fairness between the flows, solving an issue that cannot itself be solved by TCP.
• User simplicity: without complex packet classification schemes, FQ_CoDel schedules packets far better than previous rigid classification systems.
• FQ_CoDel is extremely small, simple and fast and scalable both up and down in bandwidth and # of flows, and down onto very constrained systems. It is safe for FQ_CoDel to be “always on”.

Having an algorithm that “just works” for 99% of cases and attacks the real problem is a huge advantage and simplification. Packet classification need only be used only to provide guarantees when essential, rather than be used to work around bufferbloat. No (sane) human can possibly successfully configure the QOS page found on today’s home router.  Once bufferbloat is removed and flow queuing present, any classification rule set can be tremendously simplified and understood.

Limitations and Warnings

If flow queuing AQM is not present at your bottleneck in your path, nothing you do can save you under load. You can at most move the bottleneck by inserting an artificial bottleneck.

The FQ_CoDel algorithm [RFC 8290], particularly as a queue discipline, is not a panacea for bufferbloat as buffers hide all over today’s systems. There has been about a dozen significant improvements to reduce bufferbloat just in Linux starting with Tom Herbert’s Linux BQL, Eric Dumazet’s TCP Small queues, TSO Sizing and FQ scheduler, just naming a few. Our thanks to everyone in the Linux community for their efforts. FQ_Codel, implemented in its generic form as the Linux queue discipline fq_codel, only solves part of the bufferbloat problem, that found in the qdisc layer. The FQ_CoDel algorithm itself is applicable to a wide variety of circumstances, and not just in networking gear, but even sometimes in applications.

WiFi and Wireless

Good examples of the buffering problems occurs in wireless and other technologies such as DOCSIS and DSL. WiFi is particularly hard: rapid bandwidth variation and packet aggregation means that WiFi drivers must have significant internal buffering. Cellular systems have similar (and different) challenges.

Toke Høiland-Jørgensen, Michał Kazior, Dave Täht, Per Hertig and Anna Brunstrom reported amazing improvements for WiFi at the Usenix Technical Conference. Here, FQ_CoDel algorithm is but part of a more complex algorithm that handles aggregation and transmission air-time fairness (which Linux has heretofore lacked). The results are stunning, and we hope to see similar improvements in other technologies by applying FQ_Codel.

This chart shows the latency under load in milliseconds of the new WiFi algorithm, beginning adoption in Linux. The log graph is used to enable plotting results on the same graph. The green curve is for the new driver latency under load (cumulative probability of the latency observed by packets) while the orange graph is for the previous Linux driver implementation. You seldom see 1-2 orders of magnitude improvements in anything. Note that latency can exceed one second under load with existing drivers. And implementation of air-time fairness in this algorithm also significantly increases the total bandwidth available in a busy WiFi network, by using the spectrum more efficiently, while delivering this result! See the above paper for more details and data.

This new driver structure and algorithm is in the process of adoption in Linux, though most drivers do not yet take advantage of what this offers. You should demand your device vendors using Linux update their drivers to the new framework.

While the details may vary for different technologies, we hope the WiFi work will help illuminate techniques appropriate for applying FQ_CoDel (or other flow queuing algorithms, as appropriate) to other technologies such as cellular networks.

Performance and Comparison to Other Work

In the implementations available in Linux, FQ_CoDel has seriously outperformed all comers, as shown in: “The Good, the Bad and the WiFi: Modern AQMs in a residential setting,” by Toke Høiland-Jørgensen, Per Hurtig and Anna Brunstrom. This paper is unique(?) in that it compares the algorithms consistently using the identical tests on all algorithms on the same up to date test hardware and software version, and is an apple-to-apple comparison of running code.

Our favorite benchmark for “latency under load” is the “rrul” test from Toke’s flent test tool. It demonstrates when flow(s) may be damaging the latency of other flow(s) as well as goodput and latency.  Low bandwidth performance is more difficult than high bandwidth. At 1Mbps, a single 1500 byte packet represents 12 milliseconds! This shows fq_codel outperforming all comers in latency, while preserving very high goodput for the available bandwidth. The combination of an effective self adjusting mark/drop algorithm with flow queuing is impossible to beat. The following graph measures goodput versus latency for a number of queue disciplines, at two different bandwidths, of 1 and 10Mbps (not atypical of the low end of WiFi or DSL performance). See the paper for more details and results.

FQ_CoDel radically outperforms CoDel, while solving problems that no conventional TCP mark/drop algorithm can do by itself. The combination of flow queuing with CoDel is a killer improvement, and improves the behavior of CoDel (or PIE), since ACKS are not delayed.

Pfifo_fast previously has been the default queue discipline in Linux (and similar queuing is used on other operating systems): it is for the purposes of this test, a simple FIFO queue. Note that the default length of the FIFO queue is usually ten times longer than that displayed here in most of today’s operating systems. The FIFO queue length here was chosen so that the differences between algorithms would remain easily visible on the same linear plot!

Other self tuning TCP congestion avoidance mark/drop algorithms such as PIE [RFC 8033] are becoming available, and some of those are beginning to be combined with flow queuing to good effect. As you see above, PIE without flow queuing is not competitive (nor is CoDel). An FQ-PIE algorithm, recently implemented for FreeBSD by Rasool Al-Saadi and Grenville Armitage, is more interesting and promising. Again, flow queuing combined with an auto-adjusting mark/drop algorithm is the key to FQ-PIE’s behavior.

Availability of Modern AQM Algorithms

Implementations of both CoDel and FQ_Codel were released in Linux 3.5 in July 2012 and in FreeBSD 11, in October, 2016 (and backported to FreeBSD 10.3); FQ-PIE is only available in FreeBSD (though preliminary patches for Linux exist).

FQ_CoDel has seen extensive testing, deployment and use in Linux since its initial release. There is never a reason to use CoDel, and is present in Linux solely to enable convenient performance comparisons, as in the above results. FQ_CoDel first saw wide use and deployment as part of OpenWrt when it became the default queue discipline there, and used heavily as part of the SQM (Smart Queue Management) system to mitigate “last mile” bufferbloat. FQ_CoDel is now the default queue discipline on most Linux distributions in many circumstances.  FQ_CoDel is being used in an increasing number of commercial products.

The FQ_CoDel based WiFi improvements shown here are available in the latest LEDE/OpenWrt release for a few chips. WiFi chip vendors and router vendors take note: your competitors may be about to pummel you, as this radical improvement is now becoming available. The honor of the commercial product to incorporate this new WiFi code is the Evenroute IQrouter.

PIE, but not FQ-PIE was mandated in DOCSIS 3.1, and is much less effective than FQ_CoDel (or FQ-PIE).

Continuing Work: CAKE

Research in other AQM’s continue apace. FQ_CoDel and FQ-PIE are far from the last words on the topic.

Rate limiting is necessary to mitigate bufferbloat in equipment that has no effective queue management (such as most existing DSL or most Cable modems). While we have used fq_codel in concert with Hierarchical Token Bucket (HTB) rate limiting for years as part of the Smart Queue Management (SQM) scripts (in OpenWrt and elsewhere), one can go further in an integrated queue discipline to address problems difficult to solve piecemeal, and make configuration radically simpler. The CAKE queue discipline, available today in OpenWrt, additionally adds integrated framing compensation, diffserv support and CoDel improvements. We hope to see CAKE upstream in Linux soon. Please come help in its testing and development.

As you see above, the Make WiFi Fast project is making headway and makes WiFi much to be preferred to cellular service when available, much, much more is left to be done. Investigating fixing bufferbloat in WiFi made us aware of just how much additional improvement in WiFi was also possible. Please come help!

Conclusion

Ye men of Interstan, to learning much inclined, see the elephant, by opening your eyes: 

ISP’s, insist your equipment manufacturers support modern flow queuing automatic queue management. Chip manufacturers: ensure your chips implement best practices in the area, or see your competitors win business.

Gamers, stock traders, musicians, and anyone wanting decent telephone or video calls take note. Insist your ISP fix bufferbloat in its network. Linux and RFC 8290 prove you can have your cake and eat it too. Stop suffering.

Insist on up to date flow queuing queue management in devices you buy and use, and insist that bufferbloat be fixed everywhere.

Bufferbloat is the most common underlying cause of most variable bad performance due to latency on the Internet;  latency is called “lag” by gamers.

Trying to steer anything the size of the Internet into a better direction is very slow and difficult at best. From the time changes in the upstream operating systems are complete to when consumers can buy new product is typically four years caused by the broken and insecure ecosystem in the embedded device market. Chip vendors, box vendors, I’m looking at you… So much of what is now finally appearing in the market is based on work that is often four years old. Market pull may do what push has not.

See What to do About Bufferbloat for general information. And the DSLReports Speedtest makes it easy to test for bufferbloat. But new commercial products are becoming increasingly available.  Here’s some of them.

Introduction

The fq_codel & cake work going on in the bufferbloat project is called SQM – “smart queue management.” This SQM work is specifically targeted at mitigating the bufferbloat in the “last mile,” your cable/DSL/fiber connection, by careful queue management and an artificial bandwidth bottleneck added in your home router (since most modems do no perform flow control to the home router, unfortunately).

Modems require built in AQM algorithms, such as those just beginning to reach the market in DOCSIS 3.1. I just ordered one of these for my house to see if it functions better than the SQM mitigation (almost certainly not), but at least these should not require the manual tuning that SQM does.

To fix bufferbloat in WiFi requires serious changes in the WiFi driver in your home router (which typically runs Linux), and in your device (laptop/phone/tablet).  The device driver work was first released as part of the LEDE project, in January 2017 for initially just a couple of WiFi chip types.

Evenroute IQrouter

First up, I’d like call out the Evenroute IQrouter, which has a variant of SQM that deals with “sag”.

DSL users have often suffered more than other broadband users, due to bad bloat in the modems compounded by minimal bandwidth, so the DSL version of the IQrouter is particularly welcome.   ISP’s (particularly DSL ISP’s) often under provision their back haul, causing “sag” at different times of day/week.  This makes the static configuration techniques we’ve used in LEDE/OpenWrt SQM ineffective, as you have to give away too much bandwidth if a fixed bandwidth is used.  I love the weasel words “up to” some speed used by many ISPs. It is one thing for your service to degrade for a short period of days or weeks while an ISP takes action to provision more bandwidth to an area; it is another for your bandwidth to routinely vary by large amounts for weeks/months and years.

I sent a DSL Evenroute IQrouter to my brother in Pennsylvania and arranged for one for a co-worker, and they are working well, and Rich Brown has had similarly good experiences. Evenroute has been working hard to make the installation experience easy. Best yet, is that the IQrouter is autoconfiguring and figures out for you what to do in the face of “sag” in your Internet service, something that may be a “killer feature” if you suffer lots of “sag” from your ISP. The IQrouter is therefore the first “out of the box” device I can recommend to almost anyone, rather than just my geek friends.

The IQRouter is the first commercial product the very recent wonderful WiFi results of Toke and Dave (more about coming this in a separate post), and has the capability for over the air updates. The new WiFi stack is going upstream into Linux as I write this post. DSL users seldom have enough bandwidth for the WiFi hop to be the bottleneck; so the WiFi work is much more important for Cable and fiber users at higher bandwidth than for DSL users stuck at low bandwidth.

The Evenroute is therefore effective on all technologies, not just DSL. It is particularly important for DSL users, which suffer from sag more often than most, and the IQRouter is getting regular security updates and enhancements, which most home routers lack.

Ubiquiti Edgerouter

I’ve bought an Ubiquiti Edgerouter X on recommendation of Dave Taht but not yet put it into service. Router performance can be an issue on high end cable or fiber service. It is strictly an Ethernet router, lacking WiFi interfaces; but in my house, where the wiring is down in the basement, that’s what I need.  The Edgerouter starts at around $50; the POE version I bought around $75.

The Edgerouter story is pretty neat – Dave Taht did the backport 2? years back. Ubiquti’s user community jumped all over it and polished it up, adding support to their conf tools and GUI, and Ubiquiti recognized what they had and shipped it as part of their next release.

SQM is available in recent releases of Ubituiti’s Edgerouter firmware.  SQM itself is easy to configure. But the Edgerouter overall requires considerable configuration before it is useful in the home environment, however, and its firmware web interface is aimed at IT people rather than most home users. I intend this to replace my primary router TP-Link Archer C7v2 someday soon, as it is faster than the TP-Link since Comcast keeps increasing my bandwidth without asking me.  I wish the Ubiquiti had a “make me into a home router” wizard that would make it immediately usable for most people, as its price is low enough for some home users to be interested in it.   I believe one can install LEDE/OpenWrt on the Edgerouter, which I may do if I find its IT staff oriented web interface too unusable.

LEDE/OpenWrt and BSD for the Geeks

If you are adventurous enough to reflash firmware, anything runnable on OpenWrt/LEDE of the last few years has SQM available. You take the new LEDE release for a spin. If your router has an Ath9k WiFi chip (or a later version of the Ath10k WiFi chip), or you buy a new router with the right chips in them, you can play with the new WiFi goodness now in LEDE (noted above). There is a very wide variety of home routers that can benefit from reflashing. Its web UI is tolerably decent, better than many commercial vendors I have seen.

WiFi chip vendors should take careful note of the stupendous improvements available in the Linux mac802.11 framework for bufferbloat elimination and air time fairness. If you don’t update to the new interfaces and get your code into LEDE, you’re going to be at a great disadvantage to Atheros in the market.

dd-wrt, asuswrt, ipfire, all long ago added support for SQM. It will be interesting to see how long it takes them to pick up the stunning WiFi work.

The pcengines APU2 is a good “DIY” router for higher speeds. Dave has not yet tried LEDE on it yet, but will. He uses it presently on Ubuntu….

BSD users recently got fq_codel in opnsense, so the BSD crowd are making progress.

Other Out of the Box Devices

The Turris Omnia is particularly interesting for very fast broadband service and can run LEDE as well; but unfortunately,  it seems only available in Europe at this time.  We think the Netduma router has SQM support, though it is not entirely clear what they’ve done; it is a bit pricey for my taste, and I don’t happen to know anyone who has one.

Cable Modems

Cable users may find that upgrading to a new DOCSIS 3.1 modem is helpful (though that does not solve WiFi bufferbloat).  The new DOCSIS 3.1 standard requires AQM.  While I don’t believe PIE anywhere as good as fq_codel (lacking flow queuing), the DOCSIS 3.1 standard at least requires an AQM, and PIE should help and does not require manual upstream bandwidth tuning.  Maybe someday we’ll find some fq_codel (or fq_pie) based cable modems.  Here’s hoping…

Under the Covers, Hidden

Many home routers vendors make bold claims they have proprietary cool features, but these are usually smoke and mirrors. Wireless mesh devices without bufferbloat reduction are particularly suspect and most likely to require manual RF engineering beyond most users. They require very high signal strength and transfer rates to avoid the worst of bufferbloat. Adding lots more routers without debloating and not simultaneously attacking transmit power control is a route to WiFi hell for everyone. The LEDE release is the first to have the new WiFi bits needed to make wireless mesh more practical. No one we know of has been working on minimizing transmit power to reduce interference between mesh nodes. So we are very skeptical of these products.

There are now a rapidly increasing number of products out there with SQM goodness under the covers, sometimes implemented well, and sometimes not so well, and more as the months go by.

One major vendor put support for fq_codel/SQM under the covers of one product using a tradename, promptly won an award, but then started using that tradename on inferior products in their product line that did not have real queue management. I can’t therefore vouch for any product line tradename that does not acknowledge publicly how it works and that the tradename means that it really has SQM under the covers. Once burned, three times shy. That product therefore does not deserve a mention due to the behavior of the vendor. “Bait and switch” is not what anyone needs.

Coming Soon…

We have wind of a number of vendors’ plans who have not quite reached the market, but it is up to them to announce their products.

If you find new products or ISP’s that do really well, let us know, particularly if they actually say what they are doing. We need to start some web pages to keep track of commercial products.

One additional example of “light touch” help for the Internet where government may play a role is transparency: the recent MLAB’s report and the fact that Cogent’s actions caused retail ISP’s to look very badly is a case in point. You can follow up on that topic on the MLabs’s mailing list, if you are so inclined. If a carrier can arbitrarily delay/deprioritize traffic in secret, then the market (as there are usually alternatives in transit providers) cannot function well. And if that provider is an effective monopoly for many paths, that becomes a huge problem.

I gave a lunch talk at the Berkman Center at Harvard in June on the situation and recommend people read the articles by Bruce Schneier and Dan Geer you will find linked there, which is their takes on the situation I laid out to them (both articles were triggered by the information in that talk).

Dan Geer’s piece is particularly important from a policy perspective.

I also recommend reading “Familiarity Breeds Contempt: The Honeymoon Effect and the Role of Legacy Code in Zero-Day Vulnerabilities“, by Clark, Fry, Blaze and Smith, which makes clear to me that our engineering processes need fundamental reform in the face of very long lived devices. Vulnerability discovery looks very different than normal bug discovery; good examples include heartbleed and shellshock (which thankfully does not affect most such embedded devices, since the ash shell is used in busybox).

In my analysis of the ecosystem, it’s clear that binary blobs are a real long term hazard, and do even short term damage by freezing the ecosystem for devices on old, obsolete software, magnifying the scale of vulnerabilities even on new equipment. But in the long term maintenance and security of devices (examples include your modems and home routers) is nigh impossible. And all devices need ongoing software updates for the life of the devices; the routing devices most of all (since if the network ceases to work, updates become impossible).

“Friends don’t let friends run factory firmware”.

Be safe.

Latency (called “lag” by gamers), once incurred, cannot be undone, as best first explained by Stuart Cheshire in his rant: “It’s the latency, Stupid.” and more formally in “Latency and the Quest for Interactivity,” and noted recently by Stuart’s 12 year old daughter, who sent Stuart a link to one of the myriad “Lag Kills” tee shirts, coffee bugs, and other items popular among gamers.

Out of the mouth of babes…

Any unnecessary latency is too much latency.

Many networking engineers and researchers express the opinion that 100 milliseconds latency is “good enough”. If the Internet’s worst latency (under load) was 100ms, indeed, we’d be much better off than we are today (and would have space warp technology as well!). But the speed of light and human factors research easily demonstrate this opinion is badly flawed.

Many have understood bufferbloat to be a problem that primarily occurs when a saturating “elephant flow” is present on a link; testing for bufferbloat using elephants is very easy, and even a single elephant TCP flow from any modern operating system may fill any size uncontrolled buffer given time, but this is not the only problem we face. The dominant application, the World Wide Web, is anti-social to any other application on the Internet, and its collateral damage is severe.

Solving the latency problem requires a two prong attack.

Web Performance and Its DOS attack on the Internet

Most applications’ performance are much more sensitive to latency than to bandwidth. For example, web browsing is not usually regarded as a latency sensitive application, but in fact, it is very sensitive to latency!

Today’s broadband connections throughput is already past the point of diminishing returns for typical web browsing: increasing broadband will not significantly improve performance, but reducing latency can improve performance further.

Elapsed time is usually dominated by of round trips that occur during fetching a web page, including: delays for:

1. DNS lookups (when not cached, usually a single RTT from client to server)
2. TCP opens (the three way handshake that occurs when a connection to a server is used for the first time)
3. SSL/TLS negotiation (one or two RTT’s, if the connection is secured)
4. The actual HTTP request and response

Our original intent was to hide much/most of these round trip times by use of HTTP/1.1 pipelining (I was the editor of the IETF standards document); unfortunately, for various historical and technical reasons, pipe lining has not been widely deployed and there is little hope it will ever be. Our best hope for reducing the number of TCP connections used and number of RTT’s a web browser uses is, I think, SPDY. If you know nothing about SPDY,  the link to a Tech Talk here, with slides here by Roberto Peon & William Chan. ¹ I use a number of their graphs below to illustrate the problems the web now causes for itself, but due to FIFO queues, HTTP now inflicts great damage to other real time applications.

Page Load Time as RTT Decreases

Page Load Time Versus Bandwidth

The two graphs show just how sensitive the web is to latency. As you can see, the page load time decreases essentially linearly with latency. The benefit of bandwidth improvements is much less pronounced. While page load time does improve as bandwidth goes from 1 Mb/s to 3 Mb/s, above that — bandwidths that are now commonplace with broadband, 802.11, or 4G cellular services — we are beyond the point of diminishing returns and page load times show little further improvement. The Google data shows a 14x multiplier. +200ms RTT increases page load time by +2.8 seconds. The Page load time (PLT) at 10 Mbps almost indistinguishable from 6 Mbps. To improve web performance, we must improve latency.  If you study output from webpagetest.org on web sites, you can see your CPU is usually idle, and how much time is lost due to waiting for round trips.

Connections per Page

Most web sites have a tremendous number of embedded objects, as you can see from this graph. To avoid as much head of line blocking and take advantage of the much higher broadband performance available today, web clients and servers (via web site sharding) have conspired to use as many TCP connections as possible, often tens of connections at once. Web site designers often measure performance as how quickly the packets leave the data center, but the reality that they may not be improving actual elapsed time to the end user is usually ignored. The days of RFC 2616’s “two TCP connection rule” are long gone. (Section 8.1.4). And since RFC2616 was written, TCP’s initial window (IW) has been raised, first to 4 packets, and recent changes may (have already) raised that further to 10 packets. To add to this mess, some broadband equipment (under provisioned in the upstream direction) elides TCP acks, and network offload engines in servers, hosts, and even home routers, can and will transmit up to 64K bytes of packets at line rate without operating system intervention. Each of these changes may have made sense in isolation; together they spell disaster.

It is easy for there to be flights of packets that can reach more than a hundred packets in length, leaving data centers at high speed, cross the Internet, and arrive at the bottleneck link(s), usually your broadband, cellular or WiFi links.

Head of Line Blocking We All Understand

Just as HTTP often suffers from “head of line blocking” in its protocol design, any FIFO (First In, First Out) network queues in your operating system and/or network devices impose head of line blocking in the network path at bottleneck links, incurring latency both to the web browser itself and to other applications sharing that bottleneck. As you will see below, particularly at the edge of the network, single FIFO queues must be replaced by something less stupid; fortunately such algorithms have existed for a long time (and we often even use them in airports!). Our network needs similar intelligence.

In a web transaction, the base web page is downloaded and parsed. Immediately thereafter, the web browser then fetches all the embedded objects, which as the above graph shows, are many. Since most web objects are small, many/most of them never go much beyond the TCP IW, much less complete slow start in a bloated connection. The web has effectively defeated TCP congestion avoidance.  Now we’ll do some simple math on what happens next, using two examples:

1. If a web browser now opens only 10 TCP connections/page, (which it will do easily since web site sharding means the browser’s limits on # connections are being defeated), this means that (after the initial DNS lookups, TCP opens, and possible SSL negotiations take place), 40 packets will be in flight from your web site to your web browsers (the IW * # of connections; most images are big enough to fill 4 packets), and start queuing at the bottleneck link. In this example, your bottleneck is your WiFi router; you have an 802.11g router running at full speed since it is nearby (which is about 20Mbps throughput at best). Since the router’s queue is a FIFO queue, no other application will share that link for about 25 milliseconds. Not so bad, eh?  Now think about what happens on a busy 802.11 network (for example, at a conference or in a hotel), or where you are farther away from the router. Your throughput may be only 1Mbps.  The latency incurred on anything else sharing the link will be 500ms! In fact, you probably have had HOL blocking taking place in two places in this example: first at your broadband connection, which is a bloated FIFO queue, and then again at your home router.
2. You visit a really image heavy web site (of which there are many, as seen in the graph above), heavily sharded with relatively larger images, using IW10. The Huffington Post is a good poster child for such a dismal web site (though it has many other problems too!). You can easily have hundreds of packets in flight at once, incurring corresponding latency. I have observed up to several hundred milliseconds of transient latency on a 50Mbps cable connection on certain web sites!  Just increasing bandwidth is not going to get us the latency we need, as I’ll demonstrate in the next section.

I keep the number of 13ms/1500 byte packet@1Mbps in my head for doing this arithmetic.  In short, web surfing is putting impulses of packets, without congestion avoidance, into FIFO queues where they do severe collateral damage to anything sharing the link (including itself!).

So today’s web behavior incurs huge collateral damage on itself, data centers, the edge of the network, and in particular any application that hopes to have real time behavior. How do we solve this problem? There is no real way back to the Internet of the 1980’s, and fundamentally, the problem is not soluble solely in the hosts on the Internet; the network itself must perform better adjudication among users and applications.

Real Time Applications

Other applications have differing latency requirements, usually set by human perception; to remind those of us who have not worked in the area of human factors, some numbers I keep in mind include:

• For traditional quality VOIP (or teleconferencing), the acceptable latency is no more than approximately 150ms. This rule of thumb was set many decades ago in the conventional POTS phone network, acknowledging the speed of light on transcontinental paths; but lower is always better.
• For keyboard key echo to appear “instant,” the acceptable latency is around 50ms.
• For “rubber banding” to “feel solidly attached” to your hand, your desirable latency is less than 30ms, or it feels as if your feedback sprite is literally connected by a “rubber band”.
• Professional musicians playing together may be able to tolerate (but not enjoy) up to 100ms of latency. But for duffers to play music together successfully, the latency may only be 20-40ms.
• You can regard 20-30ms as the point at which most things appear instant to us humans.
• Serious gamers (or day traders; is there a difference?) care about differences of even a single milliseconds of latency, as they are competing with others and it affects the success of their competition, and strive for under 15ms latency total. Wall Street installs special purpose networks to shave milliseconds (or microseconds) off of transactions.

We have latency “costs” we must budget for: it is unacceptable for the network to use all available time allowing no time for anything else in the end to end system. System performance == network delays + all other delays.

These “other” delays include:

• Cameras and other input devices (mice, touch pads, etc.) also typically insert latency between the user and the application, often in the 10 or more millisecond range. At 60hz, this is an additional 16ms.
• Device driver rings for audio and video; there is latency driving multimedia hardware.
• Packetizing data incurs latency; a VOIP stream sends of order 30-100 frames/second. This incurs a delay of 10-30ms.
• Encoding (in particular) and decoding audio and video packets requires time and operate over blocks of samples or pixels.
• Operating system scheduler latency (operating system and load dependent)
• Mixing audio & video requires time.
• Access to the medium: both wireless and broadband technologies often have built in latency to access their shared medium, measured in milliseconds. In your home, you may have two such access latencies: WiFi and broadband. These access latencies go up when the medium is loaded. I measure 230 ms today on my hspa+ cellular service, and 11ms to MIT from home (40km + 9ms for cable + around 1ms for 802.11 latency in my radio quiet location).
• At long last, screen refresh is beginning to increase on desktop displays: but 60hz is commonplace on laptops to conserve power, which is about 17ms. Updated frames display are usually delayed until the next “vertical retrace” using buffer swaps to avoid annoying frame “tearing”.
• The packet requires time to be transmitted. A 1500 byte packet takes about 13ms to transmit @ 1Mbps, which may be your share of a busy WiFi network, or all you have on your DSL uplink. Note that this is the only point where higher bandwidth really helps your latency, and is often not significant relative to other sources of latency.
• And most insidious today: head of line blocking in “stupid bloated FIFO queues” in our operating systems, and worst yet, all through the path from end to end.
• The lower bound on latency speed of light latency is set by the speed of propagation in the medium and the throughput in that medium: in today’s Internet, a trans-continental link across the North America has an inherent latency of approximately 75ms, presuming good routing in the Internet, which is often not available. Speed in glass is about .6C. Latency is so critical to some applications (of dubious social value: e.g. high frequency trading) that we’ve seen the reemergence of microwave based networks to reduce latency below that possible with fiber based networks.

Latency must be regarded as a “budget”, and you spend down the tolerable latency at each “hop”. Sometimes you can hide latency behind other operations, but sometimes not. With careful engineering (often not present in today’s systems on “modularity” grounds), some of these delays could be hidden by “cut-through” or other techniques but in practice, all of these delays are typically incurred serially. You can never get spent latency back.

Given the speed of light is something we find it difficult to change, and impossible to change even by a factor of two, this means that for most applications, adding *any* additional latency reduces the quality of the user’s experience.

Latency variance (jitter) is also a key metric: if your latency spikes occasionally, applications that cannot tolerate these spikes are forced to operate at “worst case” observed latency over a long time period. Such spikes may be many times worse than “steady state” latency. Controlling latency to yourself and others sharing your bottleneck links even during latency spikes caused by web surfing is necessary.

You should view total latency (network + system + jitter) as a radius over which applications will be perceived as working fast and well.

You can see that even an obvious acheivable a goal of enabling people to play music together reliably in a metropolitan area requires care throughout the system, including the network stack. Even a single full sized packet matters, much less a flight of ten or 100 packets. In the quest for throughput, we’ve been ignoring latency for decades: but consistent low latency is inherently harder to achieve.

Packet Classification

The “traditional” solution to our latency problem has been by packet classification; it has been our only hammer.  But there are a number of fundamental issues with traditional classification.  These include:

Complexity: The QOS page on your home router is too complicated for most people (including networking engineers) to understand, much less your grandmother. Requiring users to fiddle with such configuration on home routers (and in their operating systems!!!) to make things work under unpredictable load is fundamentally an engineering failure and inhibits deployment of new technology. Yet that is what is now required.

Lack of control: Even if you can handle the complexity, one of the key queuing points is not under your control: it is at the head end of your broadband (or cellular) connections, where you have no control. Who sets the policy?  Is it for pay?  Who pays whom? This is at the heart of the network neutrality debate, which bufferbloat triggered in the first place. Today, we have the worst of all possible worlds: your Internet service has one bloated FIFO queue (if you buy telephony from your ISP, you get a second queue that only that traffic has access to, but competing services such as Skype or Vonage do not).

Packets are not created equal: The first packets in a new flow, or the first packets in a idle flow are usually much more valuable than later packets in terms of latency to applications, and should be scheduled for transmission ahead of routine bulk data packets. Applications cannot make further progress until they arrive. Traditional QOS ignores these factors. Here are examples that make this observation clear:

• TCP opens
• The SSL handshakes
• DNS lookups
• DHCP, RA and other housekeeping packets account for little of the bandwidth, but are essential to the correct operation of the network.
• Isochronous flows such as VOIP or other real time traffic are occasional packets separated by idle periods.
• The first few bytes of each embedded images on web pages, which have the image size information required for a browser to lay out a web page. To avoid annoying reflows on the screen, browsers need the size of all embedded images.

Bulk data transfer packets are much less sensitive to time; those later packets being delayed do not cost the same “human” time. Traditional packet classification is by protocol type. This information isn’t really useful in general; people tunnel all sorts of traffic over HTTP and while diffserv marking could be used, it is not widely used in applications, and can easily be gamed (it can be very useful in networks you control, however). The net result of trying to use classification to achieve better latency are complex, fragile, inscrutable, QOS rules that only someone who has won his complexity merit badge can love.

Hardware queues have limited value: having a limited number of hardware based queues does not solve the problem. To begin with, we’ve demonstrated here how HOL blocking damages “best effort” TCP traffic and the people using them. The hardware queues (e.g. 802.11e) may not even work correctly (as Dave Täht has been discovering in WiFi). And in many network technologies, the scarcest resource when loaded may be “transmit opportunities”. Your most timely packet scheduling for high priority traffic (however you decide to define high priority) will be to use the first transmit opportunity, aggregating lower priority traffic into the same aggregate when possible. You really don’t want to burn two transmit opportunities if a single transmit opportunity will do. Smart software packet scheduling can do much better and today’s processors are more than fast enough to cope.

Does traditional classification have value?

Yes, classification allows you to make absolute guarantees that smart queuing may not be able to make. It is a an important tool in our toolkit, but not the only possible tool.

For example, you may want to guarantee that guests can never get more than 10% of your network when busy for with your traffic. But traditional classification to solve all our latency problems is a dead end; it does not touch latency cause by HOL blocking and unmanaged buffering. Let’s attack the fundamental problem, by isolating and scheduling applications (and people and customers) between each other, and then classification becomes much, much less necessary.

Bloated Stupid FIFO Queues Must Die

Today’s use of TCP is radically different from when (W)RED and similar algorithms were developed: TCP’s initial window was but one or two packets (versus today’s 4 packets, on its way to 10 packets). In the 1990’s, most web browsers and web servers used but two TCP connections between them. Memory is cheap, processors are fast, and web servers seldom go to disk for anything.

Given the Mlabs and netalyzr data, we can easily understand that a substantial fraction of the broadband edge has so much buffering that there has been little observed packet loss and little to push back on web site developers to avoid this pathology. And when packet drops do occur, there is no discrimination as to which packets are most “expensive” to drop.

But these packet bursts fill FIFO buffers in either your broadband equipment or in your home router, blocking any other application (or even the application itself) from timely transmission to your screen or audio equipment. Most of the benefits of packet switching have, in fact, been lost; statistical multiplexing is no longer occurring on a fine time scale.

A single 1500 byte packet represents around 13ms @ 1Mbps; it doesn’t take many packets to have a profound latency effect on anything sharing many bottleneck links. We must be able to isolate one flow from another, so that a new flow does not suffer intermittent catastrophic latency spikes. We must be smart about scheduling each packet: FIFO’s cannot suffice. We must schedule packets on a much more “smart” basis, usually TCP flows, but sometimes other factors (beyond the scope of this posting).

If FIFO’s are hopeless even with QOS on multiple queues, what then?

Signalling TCP

As I explained before, we cannot predict “correct” amounts of buffering; static buffer allocation is hopeless; buffers must be managed.

“Traditional” AQM algorithms only attack part of the problem: that of TCP filling buffers in steady state, but do not address the head of line blocking problems caused by today’s application and operating system behavior (including the web), as the Internet has effectively been gamed.

If you do have an elephant flow (such as a upload or download of a big file) over a bloated bottleneck, without some congestion signalling mechanism, TCP will not back off in a timely fashion and share that link; what is worse, the sharing behavior of TCP is quadratic in the RTT, rather than linear.  So policing TCP is necessary, since TCP cannot share bottleneck links in a timely fashion, nor can TCP based applications respond quickly in the face of such excessive buffering (a common example may be a “streaming” video player application, which will have difficulty figuring out the bandwidth it can use).   Buffering can also be so large that TCP itself can malfunction, thinking that the path may have changed entirely, as seen in my first traces. An algorithm that signals TCP in a timely fashion via packet drop or ECN is necessary, even if not sufficient. Drop tail FIFO queues are a fundamentally bad idea.

Existing algorithms such as (W)RED for policing TCP are inadequate as that class of algorithm requires careful tuning, which, in practice, has caused these algorithms to often be unused, but since that class of algorithm cannot be tuned in the face of the highly (and almost instantaneous) variable throughput found at the edge of today’s Internet it is hopeless to continue with them. Only a trustworthy, rapidly adaptive mark/drop algorithm requiring no tuning can suffice; and as you’ll see in the next section, we need a mark/drop algorithm that plays well with flow queuing, which (W)RED does not. CoDel (developed by Kathleen Nichols and Van Jacobson) is the first of a new class of mark/drop algorithms; more will be invented with time, no doubt.

Flow Queuing

Since applications (such as the web) can and have gamed the Internet to defeat congestion avoidance, we have to be able to identify and isolate such abusive flows, and ensure that packets that are most latency sensitive are scheduled first. There are a large number of algorithms that were developed in the 1980’s and 1990’s which identify flows, often called “fair” queuing algorithms. Those algorithms were widely explored in research, but in that era, the computational cost of implementing them (e.g. DRR, itself based on SFQ) were considered prohibitive. Our computer systems have radically changed since then, and many of these algorithms are now be blazing fast on today’s systems, with the computational overhead hidden (and therefore “free”) behind memory accesses.

Fairness is in the eye of the beholder, and being TCP fair is not what is called for here either. But we have to start by identifying network flows and scheduling for transmission high priority packets in flows first. As noted above, the first packet(s) in a flow (or packets in a flow that is not building a queue) are the most important to minimize latency. And today’s TCP’s do not like disordered packets, so we need to keep the packets ordered among a given TCP flow.

Putting the Pieces Together

Combining flow scheduling along with signaling TCP is therefore not only “nice to have”, but essential. This is why we are so excited about the fq_codel algorithm developed by Eric Dumazet, inspired by previous work by Dave Täht, which combines flow queuing with CoDel (developed by Kathleen Nichols and Van Jacobson), and scales easily to any bandwidth we see in the edge of the Internet even in software only implementations, to tens of gigabits/second. We believe it is the first of a new class of algorithms, but we also hope, far from the last.

A simple description of fq_codel’s behavior is:

Flows are identified. The first packet(s) from new flows are scheduled before packets from flows that have built a queue. If a flow’s queue empties, it is eligible to again be considered a new flow. CoDel is applied to control the queue length in any flow. Result: timely delivery, and mixing of flows.

Essentially, fq_codel combines DRR and CoDel with the twist that packets from flows that never build queues are scheduled preferentially to those which do build a queue. Your DNS lookups, DHCP, RA, TCP opens, SSL hand-shakes, first packet of an image in a web page, and VOIP and other small intermittent real time traffic are preferred to bulk data transfers, without requiring any explicit classification. Other variations on this theme are certainly possible: but both controlling TCP with a responsive auto-adjusting drop/mark policy and flow queuing are necessary in today’s Internet, and result in radically better latency under all tested loads, and hugely improves web browsing under load (using the RRUL test), as shown here:

Note that most of these are traps for people doing network research in general, not just bufferbloat research.

On Thu, Jun 20, 2013 at 9:45 AM, Ralph Droms (rdroms) <rdroms@yyy.zzz> wrote:

It is hard to quantify as to whether switches or routers are “worse”, and I’ve never tried, nor seen any published systematic data.  I
wouldn’t believe such data if I saw it, anyway. What matters is whether you have unmanaged buffers before a bottleneck link.

I don’t have first hand information (to just point you at particular product specs; I tend not to try to find out whom is particularly guilty as it can only get me in hot water if I compare particular vendors). I’ve generally dug into the technology to understand how/why buffering is present to understand what I’ve seen.

You can go look at specs of switches yourself and figure out switches have problems from first principles.

Feel free to write a paper!

Here’s what I do know.

Ethernet Switches:

So the big disasters I’ve heard of are those switches, where deluded naive people have bought yet more buffer memory, and particularly if they fail to configure the switches for QOS classes. That report came off the NANOG list, as I remember, but it was a couple of years ago and I didn’t save the message.

After reading that report I looked at the specs for two or three such enterprise switches and confirmed that this scenario was real, resulting in potentially *very* large buffering (multiple hundreds of milliseconds reaching even to seconds).  IIRC, one switch had decent defaults, but another defaulted to insane behavior.

So the NANOG report of such problems was not only plausible, but certain to happen, and I stopped digging further.  Case closed. But I don’t know how common it is, nor if it is more common than associated routers in the network.

Router Bufferbloat problems

I *think* the worst router problems are in home routers, where we have uncontrolled buffering (often 1280 packets worth) and highly variable bandwidth before the WiFI links and classic AQM algorithms such as WRED are both not present, and if were present, would not be of any use due to highly variable bandwidth. Home routers are certainly located where one of the common bottlenecks in the path are located and therefore are extremely common offenders.  Whether better or worse than broadband hop next to them is also impossible to quantify.

I’ve personally measured up to 8 second latency in my own home without deliberate experiments.  In deliberate experiments I can make latency as large as you like. That’s why we like CoDel (fq_codel in particular) so much: it responds very rapidly to changes in bandwidth, which are perpetual in wireless. Fixing Linux and Linux’s WiFi stack is therefore where we’ve focused (not to mention the code is available, so we can actually do work rather than try to persuade clueless people of their mistakes, which is a difficult road to hoe.  This one is the one we seem to see the most often, along with the hosts and either side of the broadband hop.

To quote the Kernel Newbies page:

TCP small queues is another mechanism designed to fight bufferbloat. TCP Small Queues goal is to reduce number of TCP packets in xmit queues (qdisc & device queues), to reduce RTT and cwnd bias, part of the bufferbloat problem. Without reduction of nominal bandwidth, we have reduction of buffering per bulk sender : < 1ms on Gbit (instead of 50ms with TSO) and < 8ms on 100Mbit (instead of 132 ms).

Eric Dumazet (now at Google) is the author of TSQ. It is covered in more detail at LWN.  Thanks to Eric for his great work!

The combination of TSQ, fq_codel and BQL (Byte Queue Limits) gets us much of the way to solving bufferbloat on Ethernet in Linux. Unfortunately, wireless remains a challenge (the drivers need to have a bunch of packets for 802.11n aggregation, and this occurs below the level that fq_codel can work on), as do other device types.  For example, a particular DSL device we looked at last week has a minimum ring buffer size of 16, again, occurring beneath Linux’s queue discipline layer.  “Smart” hardware has become a major headache. So there is much to be done yet in Linux, much less other operating systems.