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.