10 ms·

TCP-brutal: Congestion control algorithm that increase speed on packet lost

88 points by NeverBehave 3y ago

mhandley 3y ago
The Internet only works because TCP (and QUIC) congestion control does a reasonable job of matching offered load to available capacity. Without congestion control, the network is apt to get into congestion collapse, where the network is increasingly busy but getting no useful work done. We saw such congestion collapses in the 1980s. Van Jacobson's TCP congestion control algorithm was the response and its descendents have kept the Internet working ever since. Now, in certain limited domains something like Brutal can work, but you really wouldn't want everyone to do it.
- lq0000 3y ago
  > Like Hysteria, Brutal is designed for environments where the user knows the bandwidth of their connection, as this information is essential for Brutal to work. 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?
  - NeverBehave 3y ago
    It is intentionally used on WAN. Brutal part of Hysteria(https://news.ycombinator.com/item?id=38026756 https://news.ycombinator.com/item?id=38026756) internal components, and Hysteria is a proxy made for people in China under censorship, where outbound Internet access is heavily degraded.
  - rfoo 3y ago
    > 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.
- neilalexander 3y ago
  I would think that more intelligent packet scheduling (like fair queuing) is also playing a significant role these days, with routers on the path being empowered to drop packets from one flow in order to service another. That helps to bully most TCP congestion control algorithms into throttling back to a fairer pace, as they'll just end up with lots of retries otherwise.
  - mhandley 3y ago
    At the edge, if Brutal comes up against FQ-Codel or Cake in your (recent) Linux router, then if it causes congestion it should shoot itself in the foot, and other traffic shouldn't see too much adverse impact. When Brutal is limited to its fair share and sees loss, it will likely increase, get more loss, and only cause itself pain. Unfortunately Cake isn't all that widespread yet in home routers. 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.
    - dtaht 3y ago
      We are making significant progress with CAKE & fq_codel in the WISP & and fiber markets as a middlebox. See Preseem, Bequant, and LibreQos.io. Still best to get these native on the CPE as Mikrotik and many many others have one. I wonder how well these would work on the GFW?
- _flux 3y ago
  A long time ago I had a bad cable internet connection (high packet loss), but I also had good shell access to Uni's computers, so what I did was that I downloaded large files there and then I had encountered a tool that would be given three parameters: - 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.
  - wbl 3y ago
    Fountain codes would be another choice for that application
  - don-code 3y ago
    Norton Ghost could do something similar, but with UDP multicast. You'd boot a room full of machines to Ghost, have them join a multicast group, multicast an OS image to them, and then have the host machine just send the image out once (from its perspective), saving a ton of bandwidth in the process. The individual machines would then rerequest any chunks that they missed.
    - phyzome 3y ago
      Sounds very torrent-y.
    - ale42 3y ago
      Except that Ghost was using (or still uses? I switched to udpcast since ages) ACKs from the destination hosts to adapt the bandwidth dynamically. So you didn't have to give/impose the bandwidth. The funny part was when a machine in a room with 45 PCs was misbehaving (read: failing HD), basically bringing the transfer rate close to zero for the whole deployment... and good luck finding out which machine it was.
sam0x17 3y ago
I remember as an undergrad thinking it was crazy that a lot of congestion control is essentially left up to the client to play nice.
- AnthonyMouse 3y ago
  It's because everyone knows what would happen if they didn't. If you deploy this kind of algorithm at scale, multiple clients fail to back off which only causes the router to drop both of their packets. Then they have to retransmit them instead of transmitting them to begin with at a rate that causes them to not be dropped, which is actually slower.
- muxamilian 3y ago
  It sounds crazy but fortunately fair queuing is becoming more and more prevalent, making sure everyone plays nice. Every iPhone has it: https://blog.cerowrt.org/post/state_of_fq_codel/ https://blog.cerowrt.org/post/state_of_fq_codel/
BillFranklin 3y ago
If you're interested in recent state-of-art improvements to TCP congestion control, check out the Remy project, it's pretty amazing https://web.mit.edu/remy/ https://web.mit.edu/remy/.
- joelthelion 3y ago
  Out of curiosity, what do modern OSes use?
  - Agingcoder 3y ago
    Cubic, or bbr I’ve seen in practice. Bbr is extremely efficient in particular ( and I’d like to know how Rémy compares to it ) Edit: bbr essentially builds and fits a model - in some ways it’s learning ( it’s stats essentially).
  - hnav 3y ago
    cubic and bbr
- twic 3y ago
  > But there is a closely-related question, which is to ask: how much does Remy depend on the way the simulator works? Will it work on real networks? We have some confidence that the results don't depend on fine details of the simulator, because RemyCCs are optimized within Remy's own simulator but evaluated inside ns-2 and its TCP implementations, which were developed independently and long predate Remy. But the only way to know for sure is to try it on a real network, which we haven't done yet. 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.
  - BillFranklin 3y ago
    I’m not sure if much more research has been done here from this team. I was able to produce similar results in my dissertation, also not in a production setting. 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.
mort96 3y ago
> It's particularly effective at seizing bandwidth in congested, best-effort delivery networks, hence its name. 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?
- ajb 3y ago
  True, it's a pretty dumb idea 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
- ta1243 3y ago
  You should see what products like Signiant do
  - MadnessASAP 3y ago
    What does Signiant do? And what does Signiant DO?
    - ta1243 3y ago
      Uses UDP to aggressively use every drop of bandwidth to spray files in a way which makes brutal look like cubic
- elitepleb 3y ago
  it's main use is in censorship resistant proxies, where the network at large does not have a good quadrant. https://hysteria.network/ https://hysteria.network/
  - mort96 3y ago
kazinator 3y ago
Car-brutal: new congestion control algorithm! 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?"
- progbits 3y ago
  I don't think you even get faster transfers, at least beyond some short term gain. You will overload some router on the path and just increase packetloss for everyone without improving your goodput. Maybe my intuition is wrong but there are no graphs and real world measurements.
  - ta1243 3y ago
    In some cases you could. I had an issue last week with my 1G leased circuit with a 160ms rtt 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.
    - progbits 3y ago
      OK I suppose that is what GP meant with the first category - if there is no congestion but your physical layer is dodgy this can indeed help. 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).
muxamilian 3y ago
> Unlike BBR, Brutal operates on a fixed rate model and does not reduce its speed in response to packet loss or RTT changes. [...] It's particularly effective at seizing bandwidth in congested, best-effort delivery networks, hence its name. 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-control https://github.com/muxamilian/fair-queuing-aware-congestion-...
- mhandley 3y ago
  It's interesting how long we've been waiting for fair queuing to fix congestion problems in the Internet. The first proper research on this was published in 1989: https://dl.acm.org/doi/10.1145/75246.75248 https://dl.acm.org/doi/10.1145/75246.75248 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.
chrisweekly 3y ago
mods: title grammar: increase -> increases packet lost -> packet loss
bdd8f1df777b 3y ago
I'm surprised that this got posted on Hacker News and got enough attention. It was designed mostly for China's special situation. 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.
- dkbrk 3y ago
  It's curious that you say RTT is mostly random noise yet BBR gives you only 45 Mbps. The whole idea of BBR is that it probes bandwidth vs RTT and finds the point at which RTT starts to increase. 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?
keuin 3y ago
I live in China. And I have to admit the global internet connection is very busy and limited here. But I don't think you are right. Filling the wire forcefully with retransmitted packets is a very bad behavior. It's not surprising to get blocked temporarily by your ISP.
- flemhans 3y ago
  I remember the best internet connection was my own cellphone using roaming (Three), which seemed to bypass all the China bullshit.
- dtaht 3y ago
  Wish more would look harder there at the actual delays being observed and how bad congestion collapse gets at +250ms of it. https://blog.cerowrt.org/post/juniper/ https://blog.cerowrt.org/post/juniper/

88 points by NeverBehave 3y ago

The Internet only works because TCP (and QUIC) congestion control does a reasonable job of matching offered load to available capacity. Without congestion control, the network is apt to get into congestion collapse, where the network is increasingly busy but getting no useful work done. We saw such congestion collapses in the 1980s. Van Jacobson's TCP congestion control algorithm was the response and its descendents have kept the Internet working ever since. Now, in certain limited domains something like Brutal can work, but you really wouldn't want everyone to do it.

lq0000 3y ago
> Like Hysteria, Brutal is designed for environments where the user knows the bandwidth of their connection, as this information is essential for Brutal to work. 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?
- NeverBehave 3y ago
  It is intentionally used on WAN. Brutal part of Hysteria(https://news.ycombinator.com/item?id=38026756 https://news.ycombinator.com/item?id=38026756) internal components, and Hysteria is a proxy made for people in China under censorship, where outbound Internet access is heavily degraded.
- rfoo 3y ago
  > 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.
neilalexander 3y ago
I would think that more intelligent packet scheduling (like fair queuing) is also playing a significant role these days, with routers on the path being empowered to drop packets from one flow in order to service another. That helps to bully most TCP congestion control algorithms into throttling back to a fairer pace, as they'll just end up with lots of retries otherwise.
- mhandley 3y ago
  At the edge, if Brutal comes up against FQ-Codel or Cake in your (recent) Linux router, then if it causes congestion it should shoot itself in the foot, and other traffic shouldn't see too much adverse impact. When Brutal is limited to its fair share and sees loss, it will likely increase, get more loss, and only cause itself pain. Unfortunately Cake isn't all that widespread yet in home routers. 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.
  - dtaht 3y ago
    We are making significant progress with CAKE & fq_codel in the WISP & and fiber markets as a middlebox. See Preseem, Bequant, and LibreQos.io. Still best to get these native on the CPE as Mikrotik and many many others have one. I wonder how well these would work on the GFW?
_flux 3y ago
A long time ago I had a bad cable internet connection (high packet loss), but I also had good shell access to Uni's computers, so what I did was that I downloaded large files there and then I had encountered a tool that would be given three parameters: - 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.
- wbl 3y ago
  Fountain codes would be another choice for that application
- don-code 3y ago
  Norton Ghost could do something similar, but with UDP multicast. You'd boot a room full of machines to Ghost, have them join a multicast group, multicast an OS image to them, and then have the host machine just send the image out once (from its perspective), saving a ton of bandwidth in the process. The individual machines would then rerequest any chunks that they missed.
  - phyzome 3y ago
    Sounds very torrent-y.
  - ale42 3y ago
    Except that Ghost was using (or still uses? I switched to udpcast since ages) ACKs from the destination hosts to adapt the bandwidth dynamically. So you didn't have to give/impose the bandwidth. The funny part was when a machine in a room with 45 PCs was misbehaving (read: failing HD), basically bringing the transfer rate close to zero for the whole deployment... and good luck finding out which machine it was.

sam0x17 3y ago

I remember as an undergrad thinking it was crazy that a lot of congestion control is essentially left up to the client to play nice.

AnthonyMouse 3y ago
It's because everyone knows what would happen if they didn't. If you deploy this kind of algorithm at scale, multiple clients fail to back off which only causes the router to drop both of their packets. Then they have to retransmit them instead of transmitting them to begin with at a rate that causes them to not be dropped, which is actually slower.
muxamilian 3y ago
It sounds crazy but fortunately fair queuing is becoming more and more prevalent, making sure everyone plays nice. Every iPhone has it: https://blog.cerowrt.org/post/state_of_fq_codel/ https://blog.cerowrt.org/post/state_of_fq_codel/

BillFranklin 3y ago

If you're interested in recent state-of-art improvements to TCP congestion control, check out the Remy project, it's pretty amazing https://web.mit.edu/remy/ https://web.mit.edu/remy/.

joelthelion 3y ago
Out of curiosity, what do modern OSes use?
- Agingcoder 3y ago
  Cubic, or bbr I’ve seen in practice. Bbr is extremely efficient in particular ( and I’d like to know how Rémy compares to it ) Edit: bbr essentially builds and fits a model - in some ways it’s learning ( it’s stats essentially).
- hnav 3y ago
  cubic and bbr
twic 3y ago
> But there is a closely-related question, which is to ask: how much does Remy depend on the way the simulator works? Will it work on real networks? We have some confidence that the results don't depend on fine details of the simulator, because RemyCCs are optimized within Remy's own simulator but evaluated inside ns-2 and its TCP implementations, which were developed independently and long predate Remy. But the only way to know for sure is to try it on a real network, which we haven't done yet. 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.
- BillFranklin 3y ago
  I’m not sure if much more research has been done here from this team. I was able to produce similar results in my dissertation, also not in a production setting. 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.

mort96 3y ago

> It's particularly effective at seizing bandwidth in congested, best-effort delivery networks, hence its name. 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?

ajb 3y ago
True, it's a pretty dumb idea 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
ta1243 3y ago
You should see what products like Signiant do
- MadnessASAP 3y ago
  What does Signiant do? And what does Signiant DO?
  - ta1243 3y ago
    Uses UDP to aggressively use every drop of bandwidth to spray files in a way which makes brutal look like cubic
elitepleb 3y ago
it's main use is in censorship resistant proxies, where the network at large does not have a good quadrant. https://hysteria.network/ https://hysteria.network/
- mort96 3y ago

kazinator 3y ago

Car-brutal: new congestion control algorithm! 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?"

progbits 3y ago
I don't think you even get faster transfers, at least beyond some short term gain. You will overload some router on the path and just increase packetloss for everyone without improving your goodput. Maybe my intuition is wrong but there are no graphs and real world measurements.
- ta1243 3y ago
  In some cases you could. I had an issue last week with my 1G leased circuit with a 160ms rtt 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.
  - progbits 3y ago
    OK I suppose that is what GP meant with the first category - if there is no congestion but your physical layer is dodgy this can indeed help. 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).

muxamilian 3y ago

> Unlike BBR, Brutal operates on a fixed rate model and does not reduce its speed in response to packet loss or RTT changes. [...] It's particularly effective at seizing bandwidth in congested, best-effort delivery networks, hence its name. 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-control https://github.com/muxamilian/fair-queuing-aware-congestion-...

mhandley 3y ago
It's interesting how long we've been waiting for fair queuing to fix congestion problems in the Internet. The first proper research on this was published in 1989: https://dl.acm.org/doi/10.1145/75246.75248 https://dl.acm.org/doi/10.1145/75246.75248 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.

chrisweekly 3y ago

mods: title grammar: increase -> increases packet lost -> packet loss

bdd8f1df777b 3y ago

I'm surprised that this got posted on Hacker News and got enough attention. It was designed mostly for China's special situation. 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.

dkbrk 3y ago
It's curious that you say RTT is mostly random noise yet BBR gives you only 45 Mbps. The whole idea of BBR is that it probes bandwidth vs RTT and finds the point at which RTT starts to increase. 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?

keuin 3y ago

I live in China. And I have to admit the global internet connection is very busy and limited here. But I don't think you are right. Filling the wire forcefully with retransmitted packets is a very bad behavior. It's not surprising to get blocked temporarily by your ISP.

flemhans 3y ago
I remember the best internet connection was my own cellphone using roaming (Three), which seemed to bypass all the China bullshit.
dtaht 3y ago
Wish more would look harder there at the actual delays being observed and how bad congestion collapse gets at +250ms of it. https://blog.cerowrt.org/post/juniper/ https://blog.cerowrt.org/post/juniper/