BlogKarn's Algorithm improves the round trip time (RTT) estimation accuracy when sending data using the Transmission Control Protocol (TCP).
More specifically, Karn's Algorithm isolates smoothed round trip time (SRTT) calculations from the retransmission ambiguity problem, while still enabling retransmission timeouts (RTO) to respond to increases in RTT and other network issues, by scaling out retransmissions timers.
How Karn's Algorithm Works + Definition of Terms
The retransmission ambiguity problem occurs when a sender has retransmitted a packet and receives an acknowledgement (ACK) for the data. The sender cannot be certain whether the ACK received was for the original (presumed lost) packet or for the resent packet. If receiver is acknowledging (ACK) the original packet, the RTT sample is significantly longer than the current SRTT value. If the receiver is acknowledging (ACK) the retransmitted packet, RTT is likely closer to the current SRTT value and the original packet or ACK was lost. The first part of Karn's Algorithm states that when there is retransmission ambiguity, RTT measurements are ignored instead of being incorporated into SRTT to avoid skewing SRTT incorrectly.
Here's an analogy I like to use when explaining this algorithm: I call someone and say "hello," and get no response. I say "hello" again, and they respond slightly too quickly. It felt like they spoke the split second the word was out of my mouth. I'm uncertain if they were responding to my initial hello, or my second one. That's retransmission ambiguity. Since I don't know whether they heard me instantly and responded slowly or didn't hear me immediately and responded quickly, my estimate of round-trip time for this phone call won't be reliable, and I shouldn't assume it is.
That's what Karn's Algorithm does: throws away unreliable data that might skew the system's round-trip time estimate.
For each retransmission, TCP applies a "backoff factor" to each RTO, so subsequent retransmission timers are double the previous. The backoff factor is not reset until there is a successful data transmit that does not require a retransmission. Combined, these algorithms represent the second part of Karn's Algorithm. This process ensures that the network is not flooded with duplicate packets, allowing it to recover from potential congestion issues. It also guarantees useful RTT information is not discarded. According to the first part of Karn's Algorithm, all of the RTT measurements during the RTO backoff are ignored because data is retransmitted. When data is sent successfully without retransmission, the corresponding RTT measurement, which likely tracks closely to the current RTO value, can be incorporated into SRTT.
Here's another analogy (using the same example as our post on packet retransmission): I am talking on the phone with a friend when they stop responding. I ask if they can hear me once. Wait. Ask again. Wait a little longer. Ask for a third time. After a few seconds, they respond. When I repeat myself, I wait patiently for a few seconds on the assumption they might still be having cell issues and take a few seconds to respond. If they respond immediately, great! Everything is back to normal and we carry on our conversation. If they respond on a few seconds delay, I'll make do, giving enough pause to let them respond.
Wrapup: Why Karn's Algorithm Is Super Useful
Karn's Algorithm serves to optimize TCP behavior under less-than-ideal network conditions. By continuously tracking changes in RTOs and RTT, we can identify network issues as they arise, and from there quickly pinpoint where we can fix the problems. Maybe then we can see a little less of Karn's Algorithm, and little better performance out of the applications we support.
This post is part of a series covering some of the finer details of TCP. See our other posts on TCP optimization, including:
- TCP RTOs: Retransmission Timeouts and Application Performance Degradation
- What is TCP Silly Window Syndrome, and How Do I Troubleshoot It?
- TCP Analysis: Where the Network Meets the Application
Feel free to leave requests or questions in the comments below.