8 ms·

Remy – Computer-generated TCP congestion algorithm

274 points by JoachimS 12y ago

GhotiFish 12y ago
Oh man, this is a heady subject, and I feel I might not be getting the full effect for how much of it is going over my head. As I'm coming to terms with this topic now, what kinds of applications could this get applied to? A program to produce routing rules automatically based on assumed and then derived network infrastructure, would that make more organic networks more feasible in organizations? Or is this more a tool for telecoms? Is there much history of machine learning when it comes to packet routing technologies? I would of thought yes. required reading I think: https://www.youtube.com/watch?v=nLrBisNqEwQ https://www.youtube.com/watch?v=nLrBisNqEwQ https://en.wikipedia.org/wiki/Network_congestion_avoidance https://en.wikipedia.org/wiki/Network_congestion_avoidance https://en.wikipedia.org/wiki/CUBIC_TCP https://en.wikipedia.org/wiki/CUBIC_TCP http://www.isi.edu/nsnam/ns/doc/node239.html http://www.isi.edu/nsnam/ns/doc/node239.html
deleted 12y ago
[deleted]
luu 12y ago
I love that this has a big fat "reproduce the results" button with detailed build instructions. Why isn't reproducibility required to publish in CS? Unlike in fields like psychology or chemistry, reproducing results should be trivial if the authors provide instructions on how to do it.
- justinpombrio 12y ago
  http://www.artifact-eval.org/ http://www.artifact-eval.org/
- marcosscriven 12y ago
  Completely agree - any work on 3D algorithms seems particularly prone to this (presumably due to funding sources?) I once went so far as to email the author of a paper to ask for their implementation of a Minkowski 3D hull algorithm, and they point blank refused. Now I don't believe I'm entitled to this of course, it's just strange you can claim something in a paper and for it to not be reproducible. Oddly I think it's the triviality of sharing implementations that make them more guarded.
  - kibibu 12y ago
    Don't discount embarrassment at the state of research-quality code!
- _delirium 12y ago
  In the natural sciences, reproducibility means that a separate team run an experiment on independent apparatus, configured from written information (e.g., the paper). Not that you re-run the experiment on the original apparatus set up by and made available by the original authors. Clicking a button is not "reproducibility" in that sense, though it is better than not being able to do even that. Shipping code/VMs/etc. and having a 2nd team just re-run it has too much of the original lab in it to be real replication; it's more like just inspection of the 1st setup. Which is better than no inspection, but worse than independent reproduction of the results. Applied to CS, there's really no way around it: reproduction requires that researchers claiming to replicate a result implement it independently. If there are not two independently produced implementations that both confirm the result, the research hasn't been reproduced. The process of doing so helps to discover cases where the original results were due to idiosyncracies of the original implementation, test setup, etc. It'd even be ideal if replication was done in as dissimilar a setup as possible, to find cases where the results unexpectedly depend on details of the original setup not thought to be important. If anything I think there are quite some dangers that reproduction will be decreased by the current trend towards what's questionably called "reproducible research" as a euphemism for "code reuse". If people reuse code rather than doing their own independent reimplementation of methods as stated in papers, erroneous results can lurk for years and infect other research as well. (I think code reuse is good for engineering practicality, and making permissively licensed code available is also a good way of getting researchy methods out of academia into the real world. But I think it is quite wrong to call reusing the original researcher's setup, rather than independently producing your own, "reproduction" in the scientific sense.)
  - sjwright 12y ago
    The necessity of truly independent reproduction diminishes when the researchers/engineers can supply an implementation that does real work in real situations. A very high bar of self-evidence, if you will. True reproduction remains necessary to confirm that the stated underlying science is the cause, and not some other variable that might be legitimate and remarkable but undocumented.
    - 12y ago
contingencies 12y ago
Wow, this looks pretty impressive. My general understanding is that congestion control algorithms seek to provide performance and efficiency in end to end TCP (transport-layer) connections that are well-matched to the underlying network path characteristics (latency, throughput, lossiness). Unfortunately, obtaining reliable information about these characteristics can be difficult, and this is particularly the case with dynamic paths (IP mobility, mobile while moving between congested/non-congested cells, shared near-capacity networks, etc.). Previously, the areas in which customizing these sorts of algorithms has yielded particularly high returns have been satellite communications and other extremely long distance/high latency/known characteristic deployments with outlying or extreme properties. My main two questions would then be: (1) To what range of network layer path or individual link-layer characteristics do the claimed benefits of this algorithm apply? (2) How much difference will this make to mobile access or IPv6 IP mobility under a range of different realistic network link issue scenarios? If the claims in this paper are true (broadly applicable increase in throughput and fairness) then I suppose we'll see a switch to this algorithm en-masse, thus providing another handy covert operating system detection mechanism to delimit the new generation of kernels.
- 3rd3 12y ago
  Why is it actually the case that the sender has to care about congestion and not the link itself?
  - contingencies 12y ago
    Some researchers have argued eloquently that network operators and implementers should modify the infrastructure to have shorter buffers or intelligent queue-management schemes, such as the recent CoDel and separate queues for different flows. But modifying every place there is too much buffering — every LTE base station, every LTE baseband chip inside a cell phone, and every cable modem — may be an uphill battle. Our work demonstrates that in some cases, comparable or higher performance is possible without modifying network infrastructure at all—just by modifying the contending endpoints.
    - deleted 12y ago
donavanm 12y ago
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.
keithwinstein 12y ago
Grateful to see everybody's interest in our 2013 paper! You may be interested in our follow-on work, led by my colleague Anirudh Sivaraman. This will be presented at the ACM SIGCOMM 2014 conference in a few weeks: http://web.mit.edu/keithw/www/Learnability-SIGCOMM2014.pdf http://web.mit.edu/keithw/www/Learnability-SIGCOMM2014.pdf
redxblood 12y ago
Awesome, just awesome. Is it possible to use this algorithm in my machine and replace the existing one? Would that be too hard?
- keithwinstein 12y ago
  We're trying to get there! Plan is to make a user-space process that uses Linux network namespaces to intercept the outgoing TCP connections of a subsidiary process (using DNAT) and then send datagrams according to whatever congestion-control mechanism you'd like. But not there yet -- stay tuned.
  - ultramancool 12y ago
    Any reason you're trying to do this in usermode instead of using the existing framework for pluggable congestion control already present in the kernel? Changing your algorithm is already as simple as echoing into a /proc file.
    - signa11 12y ago
      > Any reason you're trying to do this in usermode instead of using the existing framework my guess would be that doing this in userland is way more forgiving than the kernel. once the basics are in place, moving it to kernel using the aforementioned pluggable congestion control f/w would be more or less 'mechanical'
  - justincormack 12y ago
    You can run the NetBSD network stack in userspace (over real links), see http://rumpkernel.org/ http://rumpkernel.org/ which is an easy way of experimenting.
- deleted 12y ago
  [deleted]
dtaht 12y ago
I do look forward to the day where such complex congestion control protocols can be implemented in hardware... Until then... fq codel is the best thing going.
riobard 12y ago
It's from the same author who made Mosh, a mobile shell/SSH replacement that will keep you sane with high latency/lossy connections to your servers.

274 points by JoachimS 12y ago

Oh man, this is a heady subject, and I feel I might not be getting the full effect for how much of it is going over my head. As I'm coming to terms with this topic now, what kinds of applications could this get applied to? A program to produce routing rules automatically based on assumed and then derived network infrastructure, would that make more organic networks more feasible in organizations? Or is this more a tool for telecoms? Is there much history of machine learning when it comes to packet routing technologies? I would of thought yes. required reading I think: https://www.youtube.com/watch?v=nLrBisNqEwQ https://www.youtube.com/watch?v=nLrBisNqEwQ https://en.wikipedia.org/wiki/Network_congestion_avoidance https://en.wikipedia.org/wiki/Network_congestion_avoidance https://en.wikipedia.org/wiki/CUBIC_TCP https://en.wikipedia.org/wiki/CUBIC_TCP http://www.isi.edu/nsnam/ns/doc/node239.html http://www.isi.edu/nsnam/ns/doc/node239.html

deleted 12y ago

[deleted]

luu 12y ago

I love that this has a big fat "reproduce the results" button with detailed build instructions. Why isn't reproducibility required to publish in CS? Unlike in fields like psychology or chemistry, reproducing results should be trivial if the authors provide instructions on how to do it.

justinpombrio 12y ago
http://www.artifact-eval.org/ http://www.artifact-eval.org/
marcosscriven 12y ago
Completely agree - any work on 3D algorithms seems particularly prone to this (presumably due to funding sources?) I once went so far as to email the author of a paper to ask for their implementation of a Minkowski 3D hull algorithm, and they point blank refused. Now I don't believe I'm entitled to this of course, it's just strange you can claim something in a paper and for it to not be reproducible. Oddly I think it's the triviality of sharing implementations that make them more guarded.
- kibibu 12y ago
  Don't discount embarrassment at the state of research-quality code!
_delirium 12y ago
In the natural sciences, reproducibility means that a separate team run an experiment on independent apparatus, configured from written information (e.g., the paper). Not that you re-run the experiment on the original apparatus set up by and made available by the original authors. Clicking a button is not "reproducibility" in that sense, though it is better than not being able to do even that. Shipping code/VMs/etc. and having a 2nd team just re-run it has too much of the original lab in it to be real replication; it's more like just inspection of the 1st setup. Which is better than no inspection, but worse than independent reproduction of the results. Applied to CS, there's really no way around it: reproduction requires that researchers claiming to replicate a result implement it independently. If there are not two independently produced implementations that both confirm the result, the research hasn't been reproduced. The process of doing so helps to discover cases where the original results were due to idiosyncracies of the original implementation, test setup, etc. It'd even be ideal if replication was done in as dissimilar a setup as possible, to find cases where the results unexpectedly depend on details of the original setup not thought to be important. If anything I think there are quite some dangers that reproduction will be decreased by the current trend towards what's questionably called "reproducible research" as a euphemism for "code reuse". If people reuse code rather than doing their own independent reimplementation of methods as stated in papers, erroneous results can lurk for years and infect other research as well. (I think code reuse is good for engineering practicality, and making permissively licensed code available is also a good way of getting researchy methods out of academia into the real world. But I think it is quite wrong to call reusing the original researcher's setup, rather than independently producing your own, "reproduction" in the scientific sense.)
- sjwright 12y ago
  The necessity of truly independent reproduction diminishes when the researchers/engineers can supply an implementation that does real work in real situations. A very high bar of self-evidence, if you will. True reproduction remains necessary to confirm that the stated underlying science is the cause, and not some other variable that might be legitimate and remarkable but undocumented.
  - 12y ago

contingencies 12y ago

Wow, this looks pretty impressive. My general understanding is that congestion control algorithms seek to provide performance and efficiency in end to end TCP (transport-layer) connections that are well-matched to the underlying network path characteristics (latency, throughput, lossiness). Unfortunately, obtaining reliable information about these characteristics can be difficult, and this is particularly the case with dynamic paths (IP mobility, mobile while moving between congested/non-congested cells, shared near-capacity networks, etc.). Previously, the areas in which customizing these sorts of algorithms has yielded particularly high returns have been satellite communications and other extremely long distance/high latency/known characteristic deployments with outlying or extreme properties. My main two questions would then be: (1) To what range of network layer path or individual link-layer characteristics do the claimed benefits of this algorithm apply? (2) How much difference will this make to mobile access or IPv6 IP mobility under a range of different realistic network link issue scenarios? If the claims in this paper are true (broadly applicable increase in throughput and fairness) then I suppose we'll see a switch to this algorithm en-masse, thus providing another handy covert operating system detection mechanism to delimit the new generation of kernels.

3rd3 12y ago
Why is it actually the case that the sender has to care about congestion and not the link itself?
- contingencies 12y ago
  Some researchers have argued eloquently that network operators and implementers should modify the infrastructure to have shorter buffers or intelligent queue-management schemes, such as the recent CoDel and separate queues for different flows. But modifying every place there is too much buffering — every LTE base station, every LTE baseband chip inside a cell phone, and every cable modem — may be an uphill battle. Our work demonstrates that in some cases, comparable or higher performance is possible without modifying network infrastructure at all—just by modifying the contending endpoints.
  - deleted 12y ago

donavanm 12y ago

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.

keithwinstein 12y ago

Grateful to see everybody's interest in our 2013 paper! You may be interested in our follow-on work, led by my colleague Anirudh Sivaraman. This will be presented at the ACM SIGCOMM 2014 conference in a few weeks: http://web.mit.edu/keithw/www/Learnability-SIGCOMM2014.pdf http://web.mit.edu/keithw/www/Learnability-SIGCOMM2014.pdf

redxblood 12y ago

Awesome, just awesome. Is it possible to use this algorithm in my machine and replace the existing one? Would that be too hard?

keithwinstein 12y ago
We're trying to get there! Plan is to make a user-space process that uses Linux network namespaces to intercept the outgoing TCP connections of a subsidiary process (using DNAT) and then send datagrams according to whatever congestion-control mechanism you'd like. But not there yet -- stay tuned.
- ultramancool 12y ago
  Any reason you're trying to do this in usermode instead of using the existing framework for pluggable congestion control already present in the kernel? Changing your algorithm is already as simple as echoing into a /proc file.
  - signa11 12y ago
    > Any reason you're trying to do this in usermode instead of using the existing framework my guess would be that doing this in userland is way more forgiving than the kernel. once the basics are in place, moving it to kernel using the aforementioned pluggable congestion control f/w would be more or less 'mechanical'
- justincormack 12y ago
  You can run the NetBSD network stack in userspace (over real links), see http://rumpkernel.org/ http://rumpkernel.org/ which is an easy way of experimenting.
deleted 12y ago
[deleted]

dtaht 12y ago

I do look forward to the day where such complex congestion control protocols can be implemented in hardware... Until then... fq codel is the best thing going.

riobard 12y ago

It's from the same author who made Mosh, a mobile shell/SSH replacement that will keep you sane with high latency/lossy connections to your servers.