Karn's algorithm

When the original transmission and most recent transmission both fail to provide round trip times, TCP should not up the round time estimate for retransmitted segments. This algorithm avoids ambigous acknowledgements by only adjusting the estimated round trip for unambigous acknowledgements(acknowledgements that arrive and have been transmitted once). Basically, it ignores retransmitted segment times.

Problem

Consider what happens when TCP sends a segment after a sharp increase in delay. The TCP computes a timeout using the existing round trip estimate, and since the timeout ibecomes too small, forced retransmission occurs. Therefore, if TCP ignores acknowledgments from retransmitted segments, the estimate does not become updated the the cycle goes on forever.

Solution

By using this algorithm, the sender is required to combine retransmitted timeouts with a timer backoff. The timer backoff computes an initial timeout by the following formula:

                                 new_timeout = y * timeout

y is usually 2

If the timer expires and causes a retransmission, TCP increases the timeout which most implementations limit the increases to an upper bound that is larger than the delay along any path.

Why use this algorithm?

When the internet misbehaves, this algorithm separates computation of the timeout value from the current round trip estimate. It uses this round trip estimate to compute an initial timeout value and backs off the timeout until a successful segment gets tranferred. When acknowledgement arrives, which a segment does not require retransmission, TCP recomputes the round trip estimate and resets the timeout accordingly.

Further Reading