root labs rdist

While discussion about how to implement traffic shaping was occurring, Comcast and BitTorrent.com made a joint announcement last week.  Comcast will apply bulk rate-limiting to customer connections and not target BitTorrent uploads.  And BitTorrent (the company) will cooperate with Comcast to make the protocol more amenable to ISP control in some way to be determined.

My claim was that this was all about centralized control of applications, not about congestion management.  After Comcast began to get heat from the FCC for not announcing their ad-hoc filtering, they decided it would be best to exit this experiment for now.  Comcast’s move seems to confirm my analysis.

Note what was absent in this announcement.  No complaints that aggregate rate-limiting is too hard or expensive to deploy.  No argument that only they knew what was good for their network and that seeding needed to be stopped at all costs.  They simply announced they would move to rate-limiting, which was a simpler and more appropriate response all along.

The strangest part of this whole affair was the MPAA announcement praising BitTorrent for cooperating with Comcast.  However, if you accept the theory that this is all about control, it makes more sense.  The *AA organizations have been stymied by protocols that don’t have a single responsible entity that can be petitioned or shut down.

They may assume this BitTorrent announcement is the start of a new era where ISPs can be used as a lever to bring application and protocol authors back to the negotiating table.  Under cover of “network management”, the ISPs will provide the necessary pressure to get changes made to allow more centralized control.  Only time will tell if this is just a historical footnote or the start of something new.

After my post about enforcing fair bandwidth allocation in over-subscribed networks like consumer broadband, George Ou and I had an email exchange.

If you recall, George was advocating a swapout of all client TCP stacks or a static penalty for using an old stack.  The root issue he was trying to solve was making sure bandwidth allocation was fair between users when they shared a congested gateway.  His concern was that opening multiple TCP connections allowed one user to gain an unfair share of the total bandwidth.

When I proposed RED (”Random Early Detection”) as a solution, George disagreed and said it doesn’t solve anything.  I asked why and he responded:

“RED merely starts dropping packets randomly and before you have full congestion on the router link. Random packet dropping statistically slows all flow rates down the same so it makes flow rates ‘fair’. What RED does not account for is per user fairness and how many flows each user opens up. RED does not neutralize the multi-stream advantage/cheat.”

This seemed like a good opportunity to explain how RED actually works.  It’s a neat approach that requires little intelligence and keeps no state.  For a brief overview, try its Wikipedia article or the original paper by Sally Floyd and Van Jacobson.  RED takes advantage of randomness to introduce fairness when managing congestion.

When a gateway is uncongested, all packets are forwarded.  In the case of consumer broadband, this means that subscribers can “burst” to higher speeds when others aren’t using the network.  Once the gateway reaches some high water mark, RED is enabled with a varying probability of drop based on how much congestion is encountered.

For each packet, a gateway using RED rolls the dice.  For example, if there’s a lot of congestion the probability might be 50%, equivalent to flipping a coin (”heads: forward the packet, tails: drop it”).  The gateway knows nothing about the packet including who sent it, the type of application being used, etc.  Each packet is considered in isolation and nothing is remembered about it afterward.

After thinking about this a bit, you can see how this enforces fairness even if one user has opened multiple TCP connections to try to gain a greater allocation of the bandwidth.  Let’s say the current drop rate is 33% and there are two users, one that has opened two connections and the other who has one.  Before the gateway enables RED, each connection is taking up 33% of the bandwidth but the user with two connections is getting 66% of the total, twice as much.

Once RED is activated, each packet coming in has a 33% chance of being dropped, independent of who sent it.  For the user with two connections who is using twice the bandwidth, there is twice the probability that one of their two connections will be the victim.  When their connection is hit, ordinary TCP congestion control will back off to half the bandwidth it was using before.  In the long run, occasionally the user with one connection will have a packet dropped but this will happen twice as often to the heavy user.  If the heavy user drops back to one connection, that connection will expand its sending rate until it is using about half the total available bandwidth but they will actually get better throughput.

This is because TCP backs off to half its bandwidth estimator when congestion is encountered and then linearly increases it from there (the good old AIMD method).  If a user has one connection and packets are being randomly dropped, they are more likely to spend more time transmitting at the correctly-estimated rate than if they have multiple connections.  It’s actually worse for total throughput to have two connections in the back-off state than one.  This is because a connection that is re-probing the available bandwidth spends a lot of time using less than its fair share. This is an incentive for applications to go back to opening one connection per transfer.

Getting back to consumer broadband, Comcast and friends could enable what’s called Weighted RED on the shared gateways.  The simplest approach is to enable normal RED with a fixed drop ratio of 1/N where N is the number of subscribers sharing that gateway.  For example, ten subscribers sharing a gateway would give a drop ratio of 10%.  This enforces per-user fairness, no matter how many parallel TCP connections or even computers each user has.   With Weighted RED, subscribers that have paid for more bandwidth can be sorted into queues that have lower drop ratios.  This enforces fairness across the network while allowing differentiated subscriptions.

As I said before, all this has been known for a long time in the networking community.  If Comcast and others wanted to deal with bandwidth-hogging users and applications while still allowing “bursting”, this is an extremely simple and well-tested way to do so that is available on any decent router.  The fact that they go for more complicated approaches just reveals that they are looking for per-application control, and nothing less.  As long as they have that goal, simple approaches like RED will be ignored.

George Ou wrote a long post today about bandwidth fairness and congestion control. It was inspired by this draft article by Bob Briscoe, which spends a lot of time discussing the game theory behind bandwidth usage. While George’s post is interesting, it makes the wrong leap from “there are some problems” to “the Internet is broke, time to update all TCP stack implementations.” Since I enjoy protocol design, I’ve collected some historical documents that may be helpful to review if you need a refresher.

The claim is that there are two situations Van Jacobson’s TCP congestion control algorithm does not address: a single user with multiple TCP connections and persistence (a connection being kept open and reused for multiple transfers.) Supposedly, peer-to-peer software is exploiting these two loopholes to use more than its fair share of bandwidth, which results in ISPs like Comcast preventing BitTorrent seeding.

First, let’s analyze what these behaviors actually achieve. Multiple TCP connections will attempt to equally share bandwidth at their mutual bottleneck, whether initiated by the same user or by multiple hosts. For example, two connections from my PC to a website will result in each getting 50% of my available bandwidth, assuming my PC’s Internet connection is the bottleneck. It doesn’t matter whether each TCP connection has the same destination or not since it’s the source (client) that backs off when the bottleneck is hit.

Now, consider the case where a neighborhood gateway is the bottleneck with two competing houses. If each opens one connection, each will get 50% of the gateway’s bandwidth. But if one house opens an extra connection, it gets 66% of the gateway’s bandwidth. This is the only case that matters since the previous example would only result in “unfair” allocation between a single user’s applications, and there is little incentive to do that.

The second situation where a connection is kept open and reused has little impact and should be left out of the discussion. This behavior takes advantage of the fact that most TCP implementations are unnecessarily forgetful. If you close a connection to a website and then immediately reopen it, all the bandwidth estimation statistics would be regenerated by “slow start”. That’s wasteful since it’s unlikely the network changed very much in the split second between close and reopen. Some implementations have cached bandwidth estimates across connection restarts, which has the same effect as keeping a persistent connection open.

In any case, this has nothing to do with fairness since as long as congestion control is working, the persistent connection will exponentially back off as soon as congestion is encountered when a new connection is started (say, by another house). This situation was what caused Jacobsen to design his algorithm in the first place.

So we’re left with only one situation where there is any concern about unfairness: a user with multiple TCP connections sharing a bottleneck with another user. The simplest solution is to put a bandwidth cap at the entry point to the network. This would push the bottleneck back to the individual user. This was the assumption behind the original TCP congestion control design. However, most networks aren’t designed this way for business reasons. Instead, individual connections are made as fast as possible and the shared gateway is over-subscribed.

There’s a much simpler solution that fits in the current business model: random early detection or “RED”. With RED, a packet is randomly dropped (or marked with a congestion bit) with a probability that increases the more congested the network. The nice thing about probability is that it fairly targets the heavier user. If your house is sending twice as many packets as mine and the shared gateway increases its random drop ratio to 33%, you are twice as likely to have one of your two packets dropped as my one packet.

The nice thing about this solution is that ISPs are already installing the necessary equipment. The TCP RST spoofing approach Comcast is already using requires equipment to be able to see the entire connection. So they certainly can implement RED based on IP address since that only requires looking at the header, not the contents of the TCP stream. Even if high-end users have multiple IP addresses, those can be grouped into a common pool based on PPPoE/RADIUS login information.

RED addresses another huge problem that George Ou tries unsuccessfully to design around. Since the TCP stack is client-side software, it can be patched or configured to exploit congestion control. Apps that use pure UDP instead of TCP to avoid congestion control are a simple example. If a new scheme is dependent on the client software to be friendly, it will have this same problem. We all know you can’t trust the client.

So if RED is simpler than TCP RST spoofing and can be rolled out the same way, why would ISPs choose the more complicated option? I think the answer is simple: control. RED is completely fair since it pays no attention to the contents of the packets or streams. It targets users that are network hogs no matter what applications they are using. ISPs are all about control, the more fine-grained, the better. They want the ability to charge for how the network is being used, in addition to how much it is used.

As long as ISPs want to charge per-application instead of per-user rates, all these proposals are pointless. RED allows an ISP to over-subscribe the gateway and enforce fairness among users. They can even give users that pay extra more bandwidth by assigning them a more favorable drop ratio. But RED doesn’t discriminate how that bandwidth is used, so ISPs will continue deploying equipment that does discriminate, no matter what George Ou or Bob Briscoe say.