TCP-brutal: Congestion control algorithm that increase speed on packet lost
github.com
github.com
China only has a handful nodes for connecting to the rest of the world. Each of the node is conceptually a single router handling billions of connections. The conventional model of congestion control algorithm breaks down:
1. The exit nodes are always under congestion. By conventional wisdom of congestion control, we should reduce our speed to wait until the congestion is resolved. That is, to reduce speed to 0 and wait until infinity.
2. The exit nodes cannot do real time traffic shaping of individual connections due to the sheer amount of them. As a result, the packet loss and RTT changes are mostly random noise. Basing the send rate on random noise does not make sense.
3. Even if one connection halves its rate, it only improves the situation by less than 0.000000001%.
4. If I sustain a high speed (300 Mbps) for several hours, my connection to the same server will be throttled heavily for at least a week. So the exit nodes probably have an offline batch job picking out outliers and put them in a naughty list.
So the only thing that matters to an end user like me is to stay below the naughty threshold. Beyond that, dynamically adjusting the send rate on packet loss or RTT is mostly behavioral art.
Per my own experiment, keeping around 90 Mbps for long will not trigger the punishment of the exit node (or my ISP). Meanwhile, BBR gives only about 45 Mbps, and Cubic 15 Mbps (barely usable).
This is all assuming that the exit nodes are the bottleneck. When other parts of the network can be the bottleneck too, such as a crowded restaurant WiFi, I switch to BBR for the congestion control.
In addition, rest assured that Brutal will not see widespread adoption. In most cases, the sever does not know the bandwidth of the client, and cannot or will not trust the bandwidth data sent from the client. It's only in the special case where both the server and client are controlled by the same person where Brutal can be applied.
Maybe BBR is just misbehaving due to too much noise? Wouldn't a better approach be to tweak BBR to spend more time probing or change the model parameters that it uses to estimate link bandwidth?
I believe OP meant RTT fluctuate somewhere between 150ms to 250ms completely randomly even with no load at all, hence (the delta is) mostly random noice. Not that the RTT is below 0.1ms and barely measurable.
> Proceeds to post a lot of interesting commentary.
Well, there you have it :P that’s why it gets posted and upvoted and commented on, because it is interesting to HN readers :D
Now, in certain limited domains something like Brutal can work, but you really wouldn't want everyone to do it.
They don't quite say that this is a bad idea for use over WAN. If they intentionally avoided ruling out such usage in this qualification, they're making an implicit assumption here that either the last-mile connection or the endpoints themselves are going to be the bottleneck. If some router in between is having a bad day, it would definitely make its day worse.
edit: I wasn't familiar with Hysteria but now that I'm reading those docs, I guess the intent is for this to be used on the internet. In that case, it does seem pretty like it'd be pretty adversarial to run this. I bet if it saw widespread adoption it'd make ISPs pretty upset.
edit 2: Going slightly off-topic now, but I wonder if the bandwidth profile of Hysteria compromises its HTTP/3 masquerade?
Most likely so. GFW is not able to reassemble and analyze QUIC (and AFAIK, any UDP-based multiplexed protocol) traffic, yet. If Hysteria takes off, GFW will try to kill it and so far it's likely to be degraded severely just as Shadowsocks, V2Ray or (ironically) Trojan.
Very few "censorship-resistance" proxy implementations out of China were designed to systematically evade traffic analysis, they usually just avoid general techniques and rely on being niche enough to fly under radar. Which is not wrong: being diverse is also a good strategy.
In large routers at ISPs, the best tool that is likely to be available is WFQ, with a limited number of hash buckets available. Likely WFQ will bundle many other flows together in the same bucket with a Brutal flow, so Brutal will still cause collareral damage if it encounters congestion.
I wonder how well these would work on the GFW?
- Destination IP and port
- Bytes per second
- Files to transfer
On the receiving end there was the counterpart.
The tool would send the data from the beginning to the end with given BPS and then start again from the beginning, skipping frames that it had received acknowledgements for, until all frames were acked.
Worked great! I was able to just select a bitrate that worked well and let it churn.
I don't remember the name of the tool, but I doubt there would be many use cases for it today—nor would it be very difficult to reimplement, given its brutal nature.
I wondered whether you could add a VPN-like layer that retransmits and potentially reorders TCP packets itself without letting the actual endpoint TCP stack handle it. That way it should transparently remove the packet loss at the cost of additional complexity and higher latency.
I wish I knew about Hysteria, but I never made the connection to censored networks. It seems like it could be (ab)used for this use case.
Edit: bbr essentially builds and fits a model - in some ways it’s learning ( it’s stats essentially).
Did they try it on a real network?
Also, it seems unclear that using a Remy congestion control algorithm while all the machines around you are using Cubic will help very much.
Regarding your second point, the way congestion avoidance algorithms typically work is to punish the local client for the state of the global congestion. If Remy can do that in a more efficient way (ie greater throughput or fairness for the local client) then it would be beneficial to use the algorithm before others switch.
Pass everyone fast in the left lane, get to within 50 yards of the target exit (where they are are all also going) and then hit your brakes to cut back in, sending a peristaltic wave of stoppage backward in the fast lane.
In networking, packets can disappear due to hardware (mainly on wireless) or due to being deliberately dropped due to congestion. You can't tell these two scenarios apart. It makes sense to try harder in the former scenario, but trying harder in the latter scenario makes the congestion worse for the entire network, while eking out a minor improvement for that connection. If every node does it, the entire network will be far worse off, so it is counterproductive.
TCP congestion control depends on cooperation: that every node complies with the RFC requirements to implement all the necessary algorithms. That unfortunately leaves room for idiots and dickheads, hence from time to time we may see work like this. "Hey, if I blatantly break the RFC, I get faster transfers. Holy shit, how come nobody knows about this?"
Maybe my intuition is wrong but there are no graphs and real world measurements.
That circuit had a 1% packet loss on it due to a dodgy SFP. This devastated cubic, with peak TCP transfer dropping from 150mbit (we police it to about that) to less than 1mbit. BBR was better but still down a fair bit.
Using this algorithm I presume it would have continued at about 140-150mbit.
I don't really do TCP so haven't looked too closely at different algorithms in different latency/loss (burst or constant) conditions, but I can see where this type of algorithm could be useful.
But if many people start using it this will fail on congestion (and even if there is little congestion to begin with, this will amplify it so there is sure to be some).
A router that is dropping packets due to being congested is still forwarding some packets. If you wallop that router with your own packets, that's your best chance of getting more of your packets to be forwarded, at the expense of someone else's being dropped. (Assuming the router has no countermeasure against that behavior.)
If we take a simple leaky bucket model: the router drops the packet because it has no resources in that moment. A moment later, space opens up because of transmitted/cleared data, so when a packet is received in that later moment, is not dropped. There is likely a chain of leaky buckets: multiple points in the router traversal where packets can be dropped due to resource issues: dropping could be on the receive side or transmit. Wherever there is a queue whose length is capped or a memory allocation operation.
If you wallop that machine with your packets, you increase the chances that when those moments come when resources are available that allow a packet to be retained rather than leaked onto the floor, that opportunity goes to one of your packets rather than someone else's.
[1] https://packetlife.net/blog/2010/jun/17/tcp-selective-acknow...
The main example behavior I remember was that these clients would sort of cheat by downloading the file chunks in sequential order (so they could start playing the media sooner) rather than in random order (which is a big part of what makes bittorrent a pretty effective protocol/algorithm)
Or is there a specific advantage to random order?
For anyone who doesn't feel like clicking on a PDF, the section title is "Rarest First".
But for "normal" Bittorrent usage, oh hell naaaaah.
Where you are trying to actually obtain a complete file, that can be a disaster. What happens is the chunks at the end of the file will be much rarer than the chunks at the beginning. Getting the blocks sequentially offers a small convenience benefit (you can start viewing a video while the torrent is still downloading) but if significant numbers of people did that it would harm every other use case including your own ability to actually download the entire file.
If you have a surplus of seeders this isn't a problem, but for sparsely-seeded torrents that is not good.
Densely seeded torrents may be slightly different and play out more like you describe, but it doesn't really matter as much there as the first parts can be sourced from those watching sequentially and the end parts left to those that actually seed after getting a full file.
This implies the reason most sparsely seeded torrents
have chunk availability is because the transient leechers
just happen to arrive consistently in time to hand off to
one another.
This is a pathological and unrealistic example but please try to extrapolate to more realistic scenarios. Imagine a file with three pieces. 200 torrent users have zero pieces, 100 torrent users have the first piece, 50 have the first and second piece, and "Joe" is the sole seeder that has all three.
Obviously, assuming Joe doesn't have godlike bandwidth, there are 350 users who want that third piece and only a single Joe and there is going to be contention. In this pathological situation things will work itself out as soon as supply of the third piece increases, assuming people don't kill their clients as soon as they hit 100%, but things will be slower than they need to be at first.
What I think you're trying to point out is that there are situations where sequential torrent downloads aren't harmful to download speed or overall availability. Yes, that is true. If seeder bandwidth for a given piece is more than sufficient for leecher demand for that piece then... yes, no harm done.
As another user posted, http://bittorrent.org/bittorrentecon.pdf section 2.4.2 "Rarest first"
You're free to disagree with the design of bittorrent, obviously.
If people download the complete file eventually, it should average out
Notice the implicit fact up there. The uneven distribution of chunks causes problems.
then the earlier chunks being more available is optimal.
There are some (or were?) torrent clients that let you start watching incomplete downloads while they're still downloading. This is a dubious use case. I do not notice many people using these nonstandard clients.
Also even for some kind of livestreaming scenario, what are even the "first" chunks? The start of the stream? The stream at the current time? It's probably a moot point anyway because it seems like Bittorrent livestreaming hasn't exactly taken the world by storm but maybe there are uses of it with which I'm not familiar: https://www.google.com/search?client=firefox-b-1-d&q=bittorr...
Sure but we just established that people are dropping out in mid-watch. For most use cases, people aren't interested in downloading the first chunks first; those cases where they are, and where it doesn't eventually average out, are exactly the cases where the earlier chunks are more important.
Interesting. Looking into it.
So basically it's an algorithm designed to push out people who play nice?
This seems like an absolutely terrible idea. It seems like in terms of congestion control algorithms, the Internet has been balancing in the good quadrant of the Prisoner's Dilemma, probably mostly because the people who work on that low of a level are nerds with a functioning moral compass. Is that era coming to an end?
On consumer networks at least, there is normally a queue scheduling stage where customers are weighted equally. So this would just sieze bandwidth from other connections from the same household. I think a similar thing usually happens on hosting platforms etc
I am not certain this is due to the censorship, but this issue is sitting there for at least a decade.
Big Corps in China usually setup their own VPN/Private Line to workaround this situation.
If the degraded performance some kind of artificial throttling, then I have a hard time understanding how an antisocial congestion control algorithm would help. If there's some middle box tasked with providing every IP address no more than 2kbit/s, then it should be able to do that job just fine even if you keep throwing lots of packets at it, right?
If the degraded performance is simply due to intentionally terrible infrastructure and there's real congestion going on due to many Chinese people trying to access the Internet at the same time, then using an antisocial congestion control algorithm might give you faster transfers, at the cost of everyone else. If everyone started using these antisocial congestion control algorithms, the end result would simply be that nobody would get to communicate with those "soft-blocked" parts of the Internet, not even at those 2 kbit/s.
In short, I don't understand how this could even in principle be an effective tool for fighting censorship. I'm happy to reconsider if anyone describes such a use case in technical detail though.
> And if you insist on sending packets, even though the other traffic does not give way, since your packets are taken more proportion of the traffic, they would more likely to be selected. Whether it's "ethical" to "grab" bandwidth in this way is a subjective question, but the objective root cause is the urgent need to expand the operator's equipment with insufficient bandwidth. Operators should not expect users to be "sympathetic" to the lack of backbone capacity - the operator has contracted a rate with the user and the user is not cracking that limit, just using the bandwidth that the operator has committed to them, which is reasonable behavior.
Personally I don't think it is a good idea, but I was in that situation during my high school, and it was terrible. I get the idea why this project would exist sooner or later and just trying to present some context for discussion.
there's circumvention techniques that abuse the fact that they can't: https://upb-syssec.github.io/blog/2023/record-fragmentation
the intentionally terrible speeds are decided by software heuristics, so antisocial limits are fought with antisocial techniques, with continued brutality being enough to skip the slow deep packet inspection path via force
Perhaps should be renamed TCP-Peking in contrast to TCP-HongKong where queuing is accepted behavior.
I can tell you, hosting files in such an environment and trying to work from the same machine is not a pleasant experience.
(After I limited connections to one per IP address, 90% of the problems went away. After I started blackholing users ignoring 503 responses, the remaining 10% were solved. I get the occasional “I didn't knooow, please give me access again” email now and then.)
So if there's one TCP flow using Brutal, all other traffic gets pushed out. Fair queuing can prevent this. If one can be sure that there's fair queuing, one can do much smoother congestion control: https://github.com/muxamilian/fair-queuing-aware-congestion-...
I'm a big fan of fair queuing, and have it enabled for my home network. But in core routers, the best approximation is likely to be WFQ, where you're likely to have each flow hashed to one of something like 256 queues. This means one badly behaved flow can't force well-behaved traffic out of the way and take over the whole link, but it can take over its WFQ queue, starving well behaved flows that hash to the same queue.
I'm not aware of any backbone router that implements true fair queuing. But even if all routers did, it's not a complete solution. Typically flows are mapped to queues based on the 5-tuple (src IP, dst IP, src port, dst port, proto). If you do this, then all Brutal-NG needs to do is use many source ports so it gets many queues, thus many times its fair share, and take over the link again. In fact, this would enable DoS attacks on router state, so no-one is going to do this.
An alternative would be to map to queues using just the source and destination IP addresses. But this has problems too. Brutal-NG could spoof the source address of most of the packets (but send ACKs back to the one unspoofed address), again taking over the link. And it could still cause DoS issues on router state.
The only thing you can't spoof if you want to actually exchange data (as opposed to DoSing the network) is the destination IP address. But now one Brutal flow can achieve the same fair share as all the traffic headed for a busy Google server or an entire ISP's CGNAT. Equally, one flow Brutal flow sending to a host behind the CGNAT can deny service to everyone else sending to the same CGNAT IP address.
So in the end, while I really like what fair queuing does for my VoIP latency on my home network, it is unlikely to ever be a complete solution for constraining misbehaving flows.
Example:
https://www.reddit.com/r/eero/comments/u7xm83/gen_2_sqm_vs_g...
The 8 way set associative hash is also much better than the direct map hash other things use, and I agree 256 flows is too small, 1024 set associative is great, 16k direct map comparable.
1) The data paths MUST prepend a timestamp to every packet 2) HW invsqrt for codel or cobalt AQM is 3k gates, checked on output 3) 32k 4 way set associative cache is a std IP block 4) HW Packet hasher - three different outputs
There are a few states in cake that are optional, but I remain boggled that step 1!! did not happen within 2 hardware releases of switch chips after van Jacobson and kathie Nichols published codel as a replacement for RED in 2012.
increase -> increases
packet lost -> packet loss