4 ms·

RACK: a time-based fast loss detection algorithm for TCP (2018)

36 points by Cieplak 8y ago

peter_d_sherman 8y ago
"The main idea behind RACK is that if a packet has been delivered out of order, then the packets sent chronologically before that were either lost or reordered. This concept is not fundamentally different from [RFC5681][RFC3517][FACK]. But the key innovation in RACK is to use a per-packet transmission timestamp and widely deployed SACK options to conduct time-based inferences instead of inferring losses with packet or sequence counting approaches." Conjecture: This, at scale, plus machine learning, might grant some insights (or at least variables that statistically strongly correlate to different conditions) about network segments that were previously not known or understood...
ggm 8y ago
Solves different problem to BBR but I wonder how it stacks up against BBR in e2e performance on the Long haul?
- skyde 8y ago
  BBR try to estimate the real bandwidth available without wasting bandwidth doing additive increase/multiplicative decrease. I am not sure I understand what problem this solve. Could you explain simply? Is it trying to avoid incorrectly treating packet reordering as packet losses?
  - ggm 8y ago
    It might be minimised retransmission burden to avoid closing down the window from my reading, with a rate estimation model based in data from the packet flows not just a model maintained each side.
keithwinstein 8y ago
This is a great way to detect non-tail losses, and should definitely be a part of TCP implementations. I hope this gets turned into an RFC and pushed through the standards process and widely deployed. I do hesitate a bit about Google calling it a "new loss detection algorithm" and talking about how "the key innovation in RACK is to use a per-packet transmission timestamp." The same approach was previously described by Sprout in 2013, and I'd bet by a lot of other people before that. ("The assumption underlying this method is that while the network may reorder packets, it will not reorder two packets that were sent more than 10 ms apart. Thus, once the receiver actually gets a packet from the sender, it can mark all bytes (up to the sequence number of the first packet sent within 10 ms) as received or lost, and only keep track of more recent packets." https://www.usenix.org/system/files/conference/nsdi13/nsdi13-final113.pdf https://www.usenix.org/system/files/conference/nsdi13/nsdi13...) The IRTF awarded this one of their Applied Networking Research Prizes that year, so it's not like it was totally just on the academic plane. Which is not to say Google isn't making 90% of the important contribution by measuring and documenting how valuable this is in real life, defining and implementing it in the context of TCP, standardizing it, getting an RFC, etc. It's just not quite as new as the I-D seems to suggest.
- jsnell 8y ago
  We used per-packet tx timestamps and timer based reordering detection in Teclo's TCP stack[0] in 2011 and later. The important bits with a time-based reordering detection heuristic are to a) make it dynamically adjust to observed network conditions, b) make it take into account some of the factors that affect reordering probability. E.g. reordering is much more likely for packets of different size than of the same size. BTW, the assumption you quoted that there won't be more than 10ms of reordering is false. Reordering of up to 50ms was common in mobile networks. [0] https://www.snellman.net/blog/archive/2015-08-25-tcp-optimization-in-mobile-networks/ https://www.snellman.net/blog/archive/2015-08-25-tcp-optimiz...
- baybal2 8y ago
  > This is a great way to detect non-tail losses, and should definitely be a part of TCP implementations. Imagine implementing that on a microcontroller. Per packet timestamping on an MCU will stand in the way of having NIC poll in same loop as the program code.
londons_explore 8y ago
I feel like the days of "we hand-crafted this algorithm to solve this issue as well as we could" like this RFC are over. Instead, simply give the issue to a neural network whose loss function is to find the best strategy for timing packets to minimize retransmissions and delay. Then train that on the real internet, and preload the resulting mini neural networks in operating systems. For extra bonus points, implement the trainer too, so the networks behaviour can be auto-tweaked at runtime to improve performance based on local scenarios.

36 points by Cieplak 8y ago

"The main idea behind RACK is that if a packet has been delivered out of order, then the packets sent chronologically before that were either lost or reordered. This concept is not fundamentally different from [RFC5681][RFC3517][FACK]. But the key innovation in RACK is to use a per-packet transmission timestamp and widely deployed SACK options to conduct time-based inferences instead of inferring losses with packet or sequence counting approaches." Conjecture: This, at scale, plus machine learning, might grant some insights (or at least variables that statistically strongly correlate to different conditions) about network segments that were previously not known or understood...

ggm 8y ago

Solves different problem to BBR but I wonder how it stacks up against BBR in e2e performance on the Long haul?

skyde 8y ago
BBR try to estimate the real bandwidth available without wasting bandwidth doing additive increase/multiplicative decrease. I am not sure I understand what problem this solve. Could you explain simply? Is it trying to avoid incorrectly treating packet reordering as packet losses?
- ggm 8y ago
  It might be minimised retransmission burden to avoid closing down the window from my reading, with a rate estimation model based in data from the packet flows not just a model maintained each side.

keithwinstein 8y ago

This is a great way to detect non-tail losses, and should definitely be a part of TCP implementations. I hope this gets turned into an RFC and pushed through the standards process and widely deployed. I do hesitate a bit about Google calling it a "new loss detection algorithm" and talking about how "the key innovation in RACK is to use a per-packet transmission timestamp." The same approach was previously described by Sprout in 2013, and I'd bet by a lot of other people before that. ("The assumption underlying this method is that while the network may reorder packets, it will not reorder two packets that were sent more than 10 ms apart. Thus, once the receiver actually gets a packet from the sender, it can mark all bytes (up to the sequence number of the first packet sent within 10 ms) as received or lost, and only keep track of more recent packets." https://www.usenix.org/system/files/conference/nsdi13/nsdi13-final113.pdf https://www.usenix.org/system/files/conference/nsdi13/nsdi13...) The IRTF awarded this one of their Applied Networking Research Prizes that year, so it's not like it was totally just on the academic plane. Which is not to say Google isn't making 90% of the important contribution by measuring and documenting how valuable this is in real life, defining and implementing it in the context of TCP, standardizing it, getting an RFC, etc. It's just not quite as new as the I-D seems to suggest.

jsnell 8y ago
We used per-packet tx timestamps and timer based reordering detection in Teclo's TCP stack[0] in 2011 and later. The important bits with a time-based reordering detection heuristic are to a) make it dynamically adjust to observed network conditions, b) make it take into account some of the factors that affect reordering probability. E.g. reordering is much more likely for packets of different size than of the same size. BTW, the assumption you quoted that there won't be more than 10ms of reordering is false. Reordering of up to 50ms was common in mobile networks. [0] https://www.snellman.net/blog/archive/2015-08-25-tcp-optimization-in-mobile-networks/ https://www.snellman.net/blog/archive/2015-08-25-tcp-optimiz...
baybal2 8y ago
> This is a great way to detect non-tail losses, and should definitely be a part of TCP implementations. Imagine implementing that on a microcontroller. Per packet timestamping on an MCU will stand in the way of having NIC poll in same loop as the program code.

londons_explore 8y ago

I feel like the days of "we hand-crafted this algorithm to solve this issue as well as we could" like this RFC are over. Instead, simply give the issue to a neural network whose loss function is to find the best strategy for timing packets to minimize retransmissions and delay. Then train that on the real internet, and preload the resulting mini neural networks in operating systems. For extra bonus points, implement the trainer too, so the networks behaviour can be auto-tweaked at runtime to improve performance based on local scenarios.