4 ms·

A key point that's glossed over is computational complexity on the senders side. The existing congestion & flow control mechanisms are quite simple. In contrast

A key point that's glossed over is computational complexity on the senders side. The existing congestion & flow control mechanisms are quite simple. In contrast these "algorithms have more than 150 rules." Additional state and computation time on the sender side is non trivial when managing tens or hundreds of thousands of concurrent flows. These algorithms vary based on link/endpoint characteristics. This would require a priori knowledge of the path & quality to each TCP receiver in order to select an appropriate congestion control algorithm. This problem is probably tractable for large scale implementations. The number of unique networks an endpoint is exposed to is in the few million range, and roughly stable over time. Collapsing adjacent and similar networks would get down in to the tens of thousands of variant prefixes. The characteristics of each prefix are roughly stable over time; a subnet of consumer cable endpoints does not flip to become a CDMA mobile subnet. At a guess the rate of change is 1-5% per day. If you can track the performance of millions of subnets a 1% delta per day is certainly feasible. In practice any single sender would need dozens, or hundreds, of different congestion control variants. And lastly they appear to simulate receivers with similar network characteristics on a single contended link. In practice receivers will have wildly different characteristics. Traffic to mobile, consumer fixed line isp, and datacenter networks will all travel on common transit carriers. Additionally even a single IP endpoint can have variable hidden receivers; think 802.11, gbe, embedded clients, and a desktop OS behind a consumer NAT device. Now the sender must track, and adapt, congestion control per flow. In summary synthetic testing of a simplistic use case has out performed generalized solutions. This should surprise no one. The details of practical implementation are ignored, and significant.

ryangittins 12y ago
Excellent post; this is a very astute point. It seems that so often some algorithm is optimized in a microcosm, but would just never hold up in practice. This sort of optimization would almost certainly have more overhead than it would be worth. The real question is whether or not we can take these 150+ rules and distill from them some heuristics which perform better than our current protocols in practice. Perhaps these findings could inform future optimizations, but are not likely to be viable in and of themselves. Whether we'd need human eyes to look over these rules and distill them or if a machine could still generate them is a question for people much smarter than I.
- userbinator 12y ago
  The real question is whether or not we can take these 150+ rules and distill from them some heuristics which perform better than our current protocols in practice This seems to be a very common problem in machine learning, evolutionary algorithms, and similar AI-like approaches: computers creating solutions that work very well, but ones whose functioning we have little or no understanding of.
keithwinstein 12y ago
Thanks for these comments! Humans have been designing congestion-control schemes for 30 years; what's interesting about our work is that we are starting to learn how to teach a computer to do the same thing from first principles. (And then learning from what the computer comes up with to inform human designs...) I can't tell you yet exactly how computationally taxing the computer-generated algorithms will turn out to be, compared with TCP CUBIC or similar. So far we've found that because the RemyCC's rules are just dumb lookups into a precalculated lookup table, the CPU requirements are pretty mild. But we need to play around with RemyCCs a lot more before I can speak more confidently. We're close but not there yet. To your other point about whether the algorithms "vary based on link/endpoint characteristics" -- I don't think they will have to. Quantitatively, a single RemyCC has been able to outperform TCP CUBIC over a thousand-fold range of link rates, and with similar results for ranges of latencies, etc. Just as servers currently use a single TCP congestion-control scheme (often CUBIC) to talk to many different clients over diverse network paths, there's no particular reason you wouldn't use a single computer-generated algorithm to do the same. Trying to "learn" different parameters for different ranges of remote IP addresses is an interesting idea, but not one we have explored or are proposing.
- donavanm 12y ago
  Yes, I definitely think this interesting as a prototype & framework for investigating congestion control. I suppose the parent was aimed more at readers who assumed this was a direct replacement for existing congestion control. Your comment about functional improvements with thousand fold variants is interesting. I (naively) assumed it only worked on an order of magnitude. With regards to varying congestion control based on client subnets, it's entirely feasible. Some networks today vary congestion control, mss, initial window, etc based on previous observed tcp flows.
- baruch 12y ago
  In my work on improving performance of the Linux TCP stack (part of my involvement with HTCP) I never saw the congestion-control part in the performance monitoring. There are such long linked lists that one goes over that any small computation is lost in the noise, most of the time was spent reaching uncached memory lines.
cbsmith 12y ago
I do think there is a lot more work to make this practical, but one could deploy a TCP stack that "learns" the right congestion strategy, much as was done by the experiment. While it'd burn more processing power, that is comparatively "affordable" to make an efficient TCP stack.
nanofortnight 12y ago
150+ isn't terribly much since each is basically an `if` statment. All 150 rules can be reduced to a single table lookup if necessary for performance. (Memory requirement for the table on the order of tens of kilobytes, though.)

ryangittins 12y ago

Excellent post; this is a very astute point. It seems that so often some algorithm is optimized in a microcosm, but would just never hold up in practice. This sort of optimization would almost certainly have more overhead than it would be worth. The real question is whether or not we can take these 150+ rules and distill from them some heuristics which perform better than our current protocols in practice. Perhaps these findings could inform future optimizations, but are not likely to be viable in and of themselves. Whether we'd need human eyes to look over these rules and distill them or if a machine could still generate them is a question for people much smarter than I.

userbinator 12y ago
The real question is whether or not we can take these 150+ rules and distill from them some heuristics which perform better than our current protocols in practice This seems to be a very common problem in machine learning, evolutionary algorithms, and similar AI-like approaches: computers creating solutions that work very well, but ones whose functioning we have little or no understanding of.

keithwinstein 12y ago

Thanks for these comments! Humans have been designing congestion-control schemes for 30 years; what's interesting about our work is that we are starting to learn how to teach a computer to do the same thing from first principles. (And then learning from what the computer comes up with to inform human designs...) I can't tell you yet exactly how computationally taxing the computer-generated algorithms will turn out to be, compared with TCP CUBIC or similar. So far we've found that because the RemyCC's rules are just dumb lookups into a precalculated lookup table, the CPU requirements are pretty mild. But we need to play around with RemyCCs a lot more before I can speak more confidently. We're close but not there yet. To your other point about whether the algorithms "vary based on link/endpoint characteristics" -- I don't think they will have to. Quantitatively, a single RemyCC has been able to outperform TCP CUBIC over a thousand-fold range of link rates, and with similar results for ranges of latencies, etc. Just as servers currently use a single TCP congestion-control scheme (often CUBIC) to talk to many different clients over diverse network paths, there's no particular reason you wouldn't use a single computer-generated algorithm to do the same. Trying to "learn" different parameters for different ranges of remote IP addresses is an interesting idea, but not one we have explored or are proposing.

donavanm 12y ago
Yes, I definitely think this interesting as a prototype & framework for investigating congestion control. I suppose the parent was aimed more at readers who assumed this was a direct replacement for existing congestion control. Your comment about functional improvements with thousand fold variants is interesting. I (naively) assumed it only worked on an order of magnitude. With regards to varying congestion control based on client subnets, it's entirely feasible. Some networks today vary congestion control, mss, initial window, etc based on previous observed tcp flows.
baruch 12y ago
In my work on improving performance of the Linux TCP stack (part of my involvement with HTCP) I never saw the congestion-control part in the performance monitoring. There are such long linked lists that one goes over that any small computation is lost in the noise, most of the time was spent reaching uncached memory lines.

cbsmith 12y ago

I do think there is a lot more work to make this practical, but one could deploy a TCP stack that "learns" the right congestion strategy, much as was done by the experiment. While it'd burn more processing power, that is comparatively "affordable" to make an efficient TCP stack.

nanofortnight 12y ago

150+ isn't terribly much since each is basically an `if` statment. All 150 rules can be reduced to a single table lookup if necessary for performance. (Memory requirement for the table on the order of tens of kilobytes, though.)