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.
rdist 
Quote:
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.
A I said to your previous post, if they want per application control, they can classify the applications, such as P2P at the entry points to the network (CMTSes, DSLAMs, etc) and mark the packets. At the choke points they can enable WRED and have different drop probabilities for different classes of traffic (P2P, http, etc) matched on the packet markings (DSCP, etc). This will give then congestion avoidance that differentiates between different classes of traffic.
Despite what they say on the ZDNet forums this is a standard QoS problem.
I agree with your arguments about fairness and the ability of this system to allow differentiable service. However, it seems a bit naive. If the subscriber knows that this is going on, what’s to prevent them from swapping out their TCP implementation for one that ignores dropped packets as a means of controlling congestion?
Quote:
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
So now I know you’re dropping my packets with probability P. I start keeping track of how many of my packets drop and get an estimate for P. As long as the number of dropped packets over the last few minutes isn’t significantly different from P, I can safely ignore dropped packets and continue on.
The principle here is that it’s not the number of packets being sent that’s important, but the number of bits/second that each client is allotted. Bittorrent and other high bandwidth applications work just as well (or better) with large packets of data versus tiny packets. Without some kind of inspection of packet size, it’s difficult to actually regulate bandwidth consumption.
Note that if all subscribers respond with a new implementation like this, then you’d imagine they all maintain a similarly large window, and dropping random packets becomes equivalent to dropping random (equal-sized) chunks of bits, which is what you want to do in the first place.
Ben C: I agree this is a standard QoS problem that is already solved by existing mechanisms if properly used. However, perhaps you misunderstand what I mean by “per-application control”. The ISPs want deep inspection and active management, not just QoS based on application type. That’s exactly why they’re not using WRED.
What they want is to be able to disable seeding while allowing BitTorrent downloading, for example. This makes their network valuable for people who want to download data while restricting the utilization of uplinks and at the same time avoiding the hassle of managing RIAA inquiries. The more they can enable/disable/control fine-grained protocol features, the better. I’m trying to point out that’s the real desire behind all this and until that motivation is addressed, proposing solutions (new or old) will have little effect.
Evan S: custom, non-compliant TCP stacks already exist. The fact that they require kernel modification has kept them out of the mainstream commercial OS’s. The Stefan Savage paper I linked earlier is a good example how a malicious client can even control a legitimate server’s estimate of the available bandwidth.
I did a quick search for TCP optimizers for Windows and most involved registry tweaks, not a new NDIS driver. Can you send me some info if such custom TCP stacks are more common than I thought?
Nate: I was imagining this in a linux/bsd context, where modifying your TCP stack and recompiling is fairly trivial. Given the prevalence of Linux-based routers, a firmware upgrade could provide a router with a new stack and a proxy service that users could use for their high bandwidth applications. However, if ISPs go with this as their primary means of congestion control, I’d bet on seeing a Windows-only alternative in the spirit of winpcap very soon.
Evan S: that’s an interesting theory. We’ll have to wait and see what happens.
Nate: They can do deep packet inspection to determine if its BitTorrent seeding and if so mark the packet. Once the packet is marked, WRED etc can be used downstream.
If the edge devices’ deep packet inspection features (NBAR, or similar) does not understand the difference between seeding and downloading (or any other protocol-specific fine granularity) it should at least be able to identify bittorrent traffic. This traffic could then be punted to a proxy that has the smarts to differentiate seeding and downloading and re-inject the packets into the network with the corresponding markings.
I think it is the wrong solution to change the TCP stacks on the client machines to mark the traffic. TCP/IP today already supports marking, and the client cannot be trusted to mark the traffic according the the service providers business rules. The SP needs to inspect the traffic and mark it themselves.
You know what would work even better then Congestion Avoidance such as WRED. Class-based Weighted Fair Queuing (CBWFQ). CBWFQ can kick in when there is congestion to guarantee classes of traffic specific amounts of bandwidth and to give priority to classes of traffic for queuing (low-latency queuing LLQ).
So P2P traffic that is clogging the choke-points can be limited in bandwidth, VoIP and gaming traffic can be give low-latency by giving them priority, and P2P traffic can be throttled, with the default-class left to use up the rest of the bandwidth as best-effort.
If a Service Provider wanted to differentiate Seeding traffic from downloading traffic, they could have them in separate classes. And if they really wanted to they could police the seeding traffic to 0, effectively blocking it.
I’d suggest you take a look at what’s happening in Canada right now.
Bell Sympatico (The ISP owned by the local telecom provider) started throttling and, taking a lesson from the ingenuity of P2P software developers, they based it on whitelisting to catch encrypted or obfuscated P2P connections. (Any traffic that hasn’t been pre-approved has to share the same 30KB per person out of the total 5Mbit the user purchased) They also switched from flat-rate bandwidth to 60GB per month combined up/down with $1.50/GB overage.
Cable providers like Rogers (outside Quebec) and Videotron (inside Quebec) have implemented the exact same pricing model but have managed to game the system so that it’s not feasible for 3rd-party ISPs to lease their lines. The customers are convinced that it’s price-fixing and the Quebec l’Union des consommateurs has filed a class action lawsuit against Videotron.
Customers started fleeing to third-party DSL ISPs like TekSavvy, and six months later, Bell moved their throttling to the GAS loops (controlled by BCE Nexxia, the bell subsidary which handles internal backbone infrastructure) without warning the 3rd-party ISPs. (Keep in mind that, according to their contracts, GAS loops are supposed to behave as if the two parties had strung their own wire between two points)
Knowing that they were on shaky ground legally, Bell claimed that their network was congested and it was a necessary measure to prevent degradation of all services on the Bell network. Surprisingly, they’re also apparently preparing an IPTV service for launch. (Surprisingly, because they seem to think they can get away with all of these blatant lies)
They claimed that 5% of users (with P2P) use over 90% of the bandwidth, but that was based on an outdated report published by a manufacturer of throlling boxes. (SandVine, I believe) A newer report indicates that, at “peak times” (when Bell throttles hardest), the biggest consumer of bandwidth is now HTTP, primarily video streaming on sites like YouTube.
In addition, according to frustrated customers and former Bell employees, Bell literally runs their infrastructure until it breaks (Apparently, they waited until the late 70s or early 80s to replace a telephone switch made in 1918) sometimes refusing to replace faulty wiring. Cost breakdowns show that Bell has gouged customers enough that we could probably have FTTC by now.
At present, CAIP (the Canadian Association of Internet Providers) has filed a complaint with the CRTC (canadian FCC) and has been joined by Vaxination Informatique and Primus (one of Bell’s telecom competitors) and most Canadians are hoping that quantity will overcome quality since the CRTC has historically been in big telecom’s pocket.
The government has been taking a lot of flack in the papers because Jim Prentice (minister of industry) essentially said “not our problem”.
Finally, keeping this account chronological, Wireless Nomad and the Quebec l’Union des consommateurs have joined CAIP in the request to the CRTC that Bell be forced to cease throttling. (More specifically, two requests. One requesting that it be stopped permanently and one requesting that it be stopped until the CRTC decides in order to prevent economic harm to Sympatico’s competitors.)
The general view on the issue from consumers like myself is that it’s a conflict of interest with BCE Nexxia being told to give Bell ExpressVu (satellite tv) and Bell Canada (telephone) a leg up on VoIP, IPTV, and P2P (They’re apparently also partnering with Microsoft to offer music downloads) since companies in Nexxia’s position usually prefer to sell as much bandwidth as client companies are willing to pay for.
In Quebec, a bill is being introduced by the Bloc Québecois to give the province it’s own CRTC-equivalent called the CRTQ and, if the current conservative (right-wing) government doesn’t support it, it’ll really bite them come election time. (Remember, this is the province which almost separated from Canada in 1995)
http://www.p2pnet.net/story/15671 provides a good way to get up to speed on it if you’d like to read more.
Stephan, fascinating stuff. Hopefully, the telcos were too blatant about this and the backlash will force them to comply with what we all want in Internet access (no interference).