8 ms·

Reading through it I can figure out some context to this research, but for this presentation I'm sorely missing the "introduction" part that a paper would be re

Reading through it I can figure out some context to this research, but for this presentation I'm sorely missing the "introduction" part that a paper would be required to have. - What field is this presentation about? Ok, TCP congestion control. What is congestion control? - Why is congestion control important? - What (types of) solutions exist? - Why do we want to obtain a census of the solutions in the field? - How have prior ones been obtained? - How are IETF decisions guided/impacted by these results? I understand that these introductions are often annoying to write (and they are not appropriate for a presentation held among peers that all mostly know the answers to the above), but maybe someone could provide a quick summary so that laypeople like me can approach this publication? Or maybe there actually is an associated paper?

cesarb 6y ago
Yes, as you noticed, this is a "presentation held among peers that all mostly know the answers to the above", from the URL alone you can see that it was a presentation from IETF's 109th meeting (https://www.ietf.org/how/meetings/109/ https://www.ietf.org/how/meetings/109/). The link came from the proceedings (https://datatracker.ietf.org/meeting/109/proceedings https://datatracker.ietf.org/meeting/109/proceedings), and if you search for this presentation there, you'll see that there's also a video of it. If you want some context answering your first three questions, the subject is TCP congestion control, and there's a Wikipedia article about it (https://en.wikipedia.org/wiki/TCP_congestion_control https://en.wikipedia.org/wiki/TCP_congestion_control). I don't know the answers to your last three questions, since I haven't been following the field; this presentation was mostly targetted to those who are following the field.
vitus 6y ago
To understand congestion control, we need to first understand congestion and congestive collapse. In a naive world, we might have every computer try to send all the packets at once (up to some buffer if you're working with a reliable protocol), but if you send more than fits on the network path, routers along the path _may_ buffer a few packets, but at some point they can't buffer any more, so they start dropping packets. If you have a reliable transport protocol such as TCP (which retransmits packets until the other side acknowledges them), then you'll retransmit all the packets that weren't acknowledged, thereby saturating the link again and again, ad nauseum. Network congestion is a little bit like traffic congestion. There are a bunch of dissimilarities, but the important thing is that if there's a lot of congestion, then everything slows to a halt. (My terminology will be a bit loose, since I assume laypeople aren't as interested in the nitty gritty details of the bandwidth-delay product, or the specifics of how congestion windows work.) So, the primary job of congestion control is to determine how much capacity there is on the network, and to avoid going over that. There are additional desirable properties, such as fairness (sharing the network evenly), or efficiency (sending as close to the capacity as possible), which other solutions might try to improve upon. (For all of these, the core of the congestion control is in the steady state) Some well known options in the space: - TCP (New) Reno: a series of improvements that use at their core the principle of "additive increase, multiplicative decrease (AIMD)". Basically, you're always probing the network by increasing slowly, but when you see a packet drop, assume that it's due to congestion, and immediately halve the amount of bandwidth you're using. This performs well in terms of fairness, but has poor efficiency characteristics (see: "tcp sawtooth" which in the limit might achieve efficiency of ~75%) - TCP CUBIC: the premise behind CUBIC is to improve upon New Reno's efficiency. Instead of linearly climbing back up, what if we probed via a cubic spline interpolation? Thus, we climb quickly at first, then slow down as we approach our previous sending rate (pre-drop), then speed up once we pass that limit in case there was a period of congestion that's since cleared up. - TCP BBR: stands for "bufferbloat reduction". Bufferbloat is the increase in latency that may precede drops due to congestion, whereas, say, issues with a flaky wifi connection might not manifest in the same way. So, the goal is to detect congestion earlier than relying on packet drops (which are jarring but not always due to congestion). Previous attempts to take advantage of latency as an early detection signal such as Vegas had issues with adoption around fairness, in that they would back off more quickly than, say, New Reno or CUBIC, and thus would achieve lower throughput; BBR is more aggressive in some situations but less aggressive in others. Why do we want a census? So we can see what's out there, what adoption rates look like, and how widely newer protocols are deployed in the greater ecosystem. For instance, BBR is called out as serving >40% of downstream internet traffic, but over 39% of downstream traffic is from Google properties using BBR (unsurprising, given that BBR came out of Google). How have prior reports been acquired? 2011 report: https://cse.unl.edu/~xu/research/TCPcensus.html https://cse.unl.edu/~xu/research/TCPcensus.html There's a lot of existing work around inferring TCP congestion control (especially how the congestion window evolves in reaction to loss), and I'm sure this survey made use of a fair amount of the existing literature. (I don't know how IETF decisions have been impacted in the past, so I can't answer that one. But I imagine that this helps inspire further research in the field.)
- MauranKilom 6y ago
  Thank you very much for this! With this background I can mostly make sense of the slides and appreciate the work behind them. Edit: Also thanks to the other replies that have pointed out the interesting challenges involved. Don't want to comment on each one individually.
  - h2odragon 6y ago
    You asked good questions; and got great answers. great example of what this site is for if you ask me.
- ncmncm 6y ago
  BBR, IIUC, fatally relies on round-trip time to probe the channel, which hardly ever works. Google probably can arrange to make it work between their data centers, but that doesn't help anybody else. I explain elsewhere in this thread the optimal algorithm, that is sadly not compatible with TCP's conditions.
- morning_gelato 6y ago
  Small nit but BBR stands for bottleneck bandwidth and round-trip propagation time [1]. [1] https://queue.acm.org/detail.cfm?id=3022184 https://queue.acm.org/detail.cfm?id=3022184
convolvatron 6y ago
the wiki article is fine. however it too misses some context. the internet has no flow control - any sender can issue as many packets as their egress link will bear. Since the subsequent links are over-provisioned, if the sum of the input rates exceeds the output rate, some packets may need to be dropped. good or ill - the solution is to put a controller on the sender that examines the traffic statistics and tries to adapt its sending rate so as not to overflow the network capacity. since everyone is doing this, we also kind of want to make sure that everyone sharing an output link adapts to something close to a fraction of that bandwidth divided by the total number of TCP flows. this is fairness. without getting into the highly involved details you can already see that this is a really interesting control/game theory problem. I find it particularly weird, astounding even, that this situation is really quite ideal for a tragedy of the commons. except there is no tragedy. everyone can cheat, but almost no one does. sure - you'd have to recompile your kernel, but anyone could ship 'network turbocharger 2.0' that forces all the other TCPs on the network to back off and allocate as much intermediate bandwidth as you like. a very easy way to do this as Netscape discovered is to use multiple connections. the pieces are all the same size, but you can take as many as you like. obviously that situation degenerates very quickly. but it hasn't. and it leaves the designers of wide area services that don't just use one TCP connection quite at a loss about how much bandwidth they should take. as far as the survey goes, I can think of all sorts of reasons why the IETF would care. one reason is that uptake of new work is pretty hard - and has killed lots of great protocol work. I'm pretty surprised that BBR has such rapid uptake - the technical situation remains a little unclear. for me the interesting part is the discussion of the measurement technique
- Sesse__ 6y ago
  > everyone can cheat, but almost no one does Try running a site with big files for downloads. Every week or so, you'll be visited by someone who runs 200+ simultaneous connections for the same file, keeps opening more, and ignores HTTP errors (like “too busy”). There are also the “IW wars”, where CDNs compete by increasing their initial window more and more to gain an edge. This will be exponentially worse with QUIC, when tuning these knobs becomes more accessible to non-experts.
Sesse__ 6y ago
TCP congestion control is the algorithms that determine when to delay TCP packets and by how much, in the interest of getting maximum speed but not overloading routers and links. This is crucial to the survival of the Internet and to end-user experience, because without congestion control, everybody would send at their maximum rate all the time (subject only to the receiver's stated TCP receive window, which can be huge these days), and the Internet would collapse. Imagine sitting on a 2G connection in rural Africa, and the server at the other end blasts packets at 100 Gbit/sec on you. On the converse, imagine sitting at a 100 Gbit/sec connection, but the sender being overconservative and sending only at modem speeds... Basically, this is a really hard problem, since you can measure bandwidth only indirectly (and with much delay), and the changes you do will affect the measurements. Solutions exist in the form of reacting to packet loss (ACKs don't come back, or selective ACKs come back to explicitly tell you something was missing), to ECN (routers along the path setting bits in your header to explicitly tell you it's getting tight on bandwidth) and to changes in delay (as measured by ACK timing and embedded TCP timestamps; higher delay typically means you're building up a queue somewhere, which is bad). They also differ in what rate they start at (initial window), how aggressive and how they increase the rate when things appear to go well (exponential, linear, binary search), and how they decrease the rate when they get negative signals (cut in half, other tactics). An important factor is “fairness”, usually to TCP Reno (a classic congestion algorithm from the 80s); if you and another sender send at the same time down the same path and they use some other congestion control algorithm, you should get about half of the bandwidth each. (An algorithm that's too aggressive could easily cause the other side to lose packets and just keep decreasing its bandwidth estimate, crowding it off the link entirely.) A perfect congestion algorithm would immediately detect the correct amount of bandwidth (even in the presence of changing conditions and non-congestion-related packet loss such as a bad cable or Wi-Fi errors), send evenly at that rate, never send so much that packets are lost to congestion, never send so much that routers' queues build up and latency increases (bufferbloat) and be perfectly fair to all other algorithms. As for census; it's interesting to know what exists out there, what people are doing in practice, and what algorithms we need to compete against and be fair to.
- im3w1l 6y ago
  > Basically, this is a really hard problem, since you can measure bandwidth only indirectly What do you mean? My ISP knows which package I bought and how congested the tubes are, and how full the datatanks are.
floatingatoll 6y ago
The paper supporting this is in another comment: https://news.ycombinator.com/item?id=25239684 https://news.ycombinator.com/item?id=25239684
ComputerGuru 6y ago
Not everything is intended for consumption by the general populace, especially when it comes to academic presentations. In not trying to be rude but either do the very minimum background reading if you’re interested or move on. I don’t see the point in every presenter reinventing (probably poorly) the same “bringing you up to speed on core technology xxxx” in every presentation.
- MauranKilom 6y ago
  I really tried to make clear that I had no expectations for an introduction to be present, as it would be unreasonable to do so: > they are not appropriate for a presentation held among peers that all mostly know the answers to the above My comment was merely requesting that someone else provides such a summary, so that the linked material becomes accessible to a wider audience. I expect that the majority of readers here are not particularly familiar with this problem/field, so I thought it would be beneficial to have such a complementary explanation in the thread. (Yes, you can tell people to spend 10 minutes reading through Wikipedia and other supplementary material, but few will do so.) And indeed, I could get significantly more value out of this submission after reading some of the explanations I solicited. Others hopefully/presumably had the same experience (instead of just having to move on). I didn't want to comment on the downvotes I received, but I would appreciate suggestions how my wording could've been improved to avoid the reaction that you had. It was precisely what I intended to curb with the quoted remark, but it seems it was not very effective.
  - inimino 6y ago
    OK, since you asked: Your first paragraph ("sorely missing" "required to have") reads like a criticism. The first sentence of the last paragraph ("annoying to write") sounds like "I know you don't always enjoy eating vegetables, but...". If you meant to just ask for a summary as a non-specialist, next time just say "Could someone explain the context of this to a layperson like me? Specifically, ..."

cesarb 6y ago

Yes, as you noticed, this is a "presentation held among peers that all mostly know the answers to the above", from the URL alone you can see that it was a presentation from IETF's 109th meeting (https://www.ietf.org/how/meetings/109/ https://www.ietf.org/how/meetings/109/). The link came from the proceedings (https://datatracker.ietf.org/meeting/109/proceedings https://datatracker.ietf.org/meeting/109/proceedings), and if you search for this presentation there, you'll see that there's also a video of it. If you want some context answering your first three questions, the subject is TCP congestion control, and there's a Wikipedia article about it (https://en.wikipedia.org/wiki/TCP_congestion_control https://en.wikipedia.org/wiki/TCP_congestion_control). I don't know the answers to your last three questions, since I haven't been following the field; this presentation was mostly targetted to those who are following the field.

vitus 6y ago

To understand congestion control, we need to first understand congestion and congestive collapse. In a naive world, we might have every computer try to send all the packets at once (up to some buffer if you're working with a reliable protocol), but if you send more than fits on the network path, routers along the path _may_ buffer a few packets, but at some point they can't buffer any more, so they start dropping packets. If you have a reliable transport protocol such as TCP (which retransmits packets until the other side acknowledges them), then you'll retransmit all the packets that weren't acknowledged, thereby saturating the link again and again, ad nauseum. Network congestion is a little bit like traffic congestion. There are a bunch of dissimilarities, but the important thing is that if there's a lot of congestion, then everything slows to a halt. (My terminology will be a bit loose, since I assume laypeople aren't as interested in the nitty gritty details of the bandwidth-delay product, or the specifics of how congestion windows work.) So, the primary job of congestion control is to determine how much capacity there is on the network, and to avoid going over that. There are additional desirable properties, such as fairness (sharing the network evenly), or efficiency (sending as close to the capacity as possible), which other solutions might try to improve upon. (For all of these, the core of the congestion control is in the steady state) Some well known options in the space: - TCP (New) Reno: a series of improvements that use at their core the principle of "additive increase, multiplicative decrease (AIMD)". Basically, you're always probing the network by increasing slowly, but when you see a packet drop, assume that it's due to congestion, and immediately halve the amount of bandwidth you're using. This performs well in terms of fairness, but has poor efficiency characteristics (see: "tcp sawtooth" which in the limit might achieve efficiency of ~75%) - TCP CUBIC: the premise behind CUBIC is to improve upon New Reno's efficiency. Instead of linearly climbing back up, what if we probed via a cubic spline interpolation? Thus, we climb quickly at first, then slow down as we approach our previous sending rate (pre-drop), then speed up once we pass that limit in case there was a period of congestion that's since cleared up. - TCP BBR: stands for "bufferbloat reduction". Bufferbloat is the increase in latency that may precede drops due to congestion, whereas, say, issues with a flaky wifi connection might not manifest in the same way. So, the goal is to detect congestion earlier than relying on packet drops (which are jarring but not always due to congestion). Previous attempts to take advantage of latency as an early detection signal such as Vegas had issues with adoption around fairness, in that they would back off more quickly than, say, New Reno or CUBIC, and thus would achieve lower throughput; BBR is more aggressive in some situations but less aggressive in others. Why do we want a census? So we can see what's out there, what adoption rates look like, and how widely newer protocols are deployed in the greater ecosystem. For instance, BBR is called out as serving >40% of downstream internet traffic, but over 39% of downstream traffic is from Google properties using BBR (unsurprising, given that BBR came out of Google). How have prior reports been acquired? 2011 report: https://cse.unl.edu/~xu/research/TCPcensus.html https://cse.unl.edu/~xu/research/TCPcensus.html There's a lot of existing work around inferring TCP congestion control (especially how the congestion window evolves in reaction to loss), and I'm sure this survey made use of a fair amount of the existing literature. (I don't know how IETF decisions have been impacted in the past, so I can't answer that one. But I imagine that this helps inspire further research in the field.)

MauranKilom 6y ago
Thank you very much for this! With this background I can mostly make sense of the slides and appreciate the work behind them. Edit: Also thanks to the other replies that have pointed out the interesting challenges involved. Don't want to comment on each one individually.
- h2odragon 6y ago
  You asked good questions; and got great answers. great example of what this site is for if you ask me.
ncmncm 6y ago
BBR, IIUC, fatally relies on round-trip time to probe the channel, which hardly ever works. Google probably can arrange to make it work between their data centers, but that doesn't help anybody else. I explain elsewhere in this thread the optimal algorithm, that is sadly not compatible with TCP's conditions.
morning_gelato 6y ago
Small nit but BBR stands for bottleneck bandwidth and round-trip propagation time [1]. [1] https://queue.acm.org/detail.cfm?id=3022184 https://queue.acm.org/detail.cfm?id=3022184

convolvatron 6y ago

the wiki article is fine. however it too misses some context. the internet has no flow control - any sender can issue as many packets as their egress link will bear. Since the subsequent links are over-provisioned, if the sum of the input rates exceeds the output rate, some packets may need to be dropped. good or ill - the solution is to put a controller on the sender that examines the traffic statistics and tries to adapt its sending rate so as not to overflow the network capacity. since everyone is doing this, we also kind of want to make sure that everyone sharing an output link adapts to something close to a fraction of that bandwidth divided by the total number of TCP flows. this is fairness. without getting into the highly involved details you can already see that this is a really interesting control/game theory problem. I find it particularly weird, astounding even, that this situation is really quite ideal for a tragedy of the commons. except there is no tragedy. everyone can cheat, but almost no one does. sure - you'd have to recompile your kernel, but anyone could ship 'network turbocharger 2.0' that forces all the other TCPs on the network to back off and allocate as much intermediate bandwidth as you like. a very easy way to do this as Netscape discovered is to use multiple connections. the pieces are all the same size, but you can take as many as you like. obviously that situation degenerates very quickly. but it hasn't. and it leaves the designers of wide area services that don't just use one TCP connection quite at a loss about how much bandwidth they should take. as far as the survey goes, I can think of all sorts of reasons why the IETF would care. one reason is that uptake of new work is pretty hard - and has killed lots of great protocol work. I'm pretty surprised that BBR has such rapid uptake - the technical situation remains a little unclear. for me the interesting part is the discussion of the measurement technique

Sesse__ 6y ago
> everyone can cheat, but almost no one does Try running a site with big files for downloads. Every week or so, you'll be visited by someone who runs 200+ simultaneous connections for the same file, keeps opening more, and ignores HTTP errors (like “too busy”). There are also the “IW wars”, where CDNs compete by increasing their initial window more and more to gain an edge. This will be exponentially worse with QUIC, when tuning these knobs becomes more accessible to non-experts.

Sesse__ 6y ago

TCP congestion control is the algorithms that determine when to delay TCP packets and by how much, in the interest of getting maximum speed but not overloading routers and links. This is crucial to the survival of the Internet and to end-user experience, because without congestion control, everybody would send at their maximum rate all the time (subject only to the receiver's stated TCP receive window, which can be huge these days), and the Internet would collapse. Imagine sitting on a 2G connection in rural Africa, and the server at the other end blasts packets at 100 Gbit/sec on you. On the converse, imagine sitting at a 100 Gbit/sec connection, but the sender being overconservative and sending only at modem speeds... Basically, this is a really hard problem, since you can measure bandwidth only indirectly (and with much delay), and the changes you do will affect the measurements. Solutions exist in the form of reacting to packet loss (ACKs don't come back, or selective ACKs come back to explicitly tell you something was missing), to ECN (routers along the path setting bits in your header to explicitly tell you it's getting tight on bandwidth) and to changes in delay (as measured by ACK timing and embedded TCP timestamps; higher delay typically means you're building up a queue somewhere, which is bad). They also differ in what rate they start at (initial window), how aggressive and how they increase the rate when things appear to go well (exponential, linear, binary search), and how they decrease the rate when they get negative signals (cut in half, other tactics). An important factor is “fairness”, usually to TCP Reno (a classic congestion algorithm from the 80s); if you and another sender send at the same time down the same path and they use some other congestion control algorithm, you should get about half of the bandwidth each. (An algorithm that's too aggressive could easily cause the other side to lose packets and just keep decreasing its bandwidth estimate, crowding it off the link entirely.) A perfect congestion algorithm would immediately detect the correct amount of bandwidth (even in the presence of changing conditions and non-congestion-related packet loss such as a bad cable or Wi-Fi errors), send evenly at that rate, never send so much that packets are lost to congestion, never send so much that routers' queues build up and latency increases (bufferbloat) and be perfectly fair to all other algorithms. As for census; it's interesting to know what exists out there, what people are doing in practice, and what algorithms we need to compete against and be fair to.

im3w1l 6y ago
> Basically, this is a really hard problem, since you can measure bandwidth only indirectly What do you mean? My ISP knows which package I bought and how congested the tubes are, and how full the datatanks are.

floatingatoll 6y ago

The paper supporting this is in another comment: https://news.ycombinator.com/item?id=25239684 https://news.ycombinator.com/item?id=25239684

ComputerGuru 6y ago

Not everything is intended for consumption by the general populace, especially when it comes to academic presentations. In not trying to be rude but either do the very minimum background reading if you’re interested or move on. I don’t see the point in every presenter reinventing (probably poorly) the same “bringing you up to speed on core technology xxxx” in every presentation.

MauranKilom 6y ago
I really tried to make clear that I had no expectations for an introduction to be present, as it would be unreasonable to do so: > they are not appropriate for a presentation held among peers that all mostly know the answers to the above My comment was merely requesting that someone else provides such a summary, so that the linked material becomes accessible to a wider audience. I expect that the majority of readers here are not particularly familiar with this problem/field, so I thought it would be beneficial to have such a complementary explanation in the thread. (Yes, you can tell people to spend 10 minutes reading through Wikipedia and other supplementary material, but few will do so.) And indeed, I could get significantly more value out of this submission after reading some of the explanations I solicited. Others hopefully/presumably had the same experience (instead of just having to move on). I didn't want to comment on the downvotes I received, but I would appreciate suggestions how my wording could've been improved to avoid the reaction that you had. It was precisely what I intended to curb with the quoted remark, but it seems it was not very effective.
- inimino 6y ago
  OK, since you asked: Your first paragraph ("sorely missing" "required to have") reads like a criticism. The first sentence of the last paragraph ("annoying to write") sounds like "I know you don't always enjoy eating vegetables, but...". If you meant to just ask for a summary as a non-specialist, next time just say "Could someone explain the context of this to a layperson like me? Specifically, ..."