Karn's algorithm

Karn's Algorithm addresses the problem of getting accurate estimates of the round trip time for messages when using TCP. Accurate round trip estimates in TCP can be difficult to calculate because of an ambiguity created by retransmitted segments. The round trip time is estimated as the difference between the time that a segment was sent and the time that its acknowledgement was returned to the sender, but when packets are re-transmitted there is an ambiguity: the acknowledgement may be a response to the first transmission of the segment or to a subsequent re-transmission.

Karn's Algorithm requires not using retransmitted segments when updating the round trip estimate. Round trip time estimation is based only on unambiguous acknowledgements, which are acknowledgements for segments that were sent only once.

This simplistic implementatation of Karn's algorithm can lead to problems as well. Consider what happens when TCP sends a segment after a sharp increase in delay. Using the prior round trip time estimate, TCP computes a timeout and retransmits a segment. If TCP never acknowledges retransmitted packets, the round trip estimate time will never be updated, and TCP will continue retransmitting segments without adjusting to the increased delay.

A solution to this problem is to incorporate transmission timeouts with a timer backoff strategy. The timer backoff strategy computes an initial timeout. If the timer expires and causes a retransmission, TCP increases the timeout generally by a factor of 2.

         new_timeout = 2*timeout

This algorithm has proven to be extremelly effective in networks with high packet loss.

• Comer, Douglas E. (2006). Internetworking with TCP/IP (5 ed.). Prentice Hall: Upper Saddle River, NJ..

External links

• RFC 2988 - Computing TCP's Retransmission Timer