Karn's Algorithm
Encyclopedia
Karn's Algorithm addresses the problem of getting accurate estimates of the round-trip time for messages when using TCP
. The algorithm was proposed by Phil Karn
in 1987.
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 acknowledgment was returned to the sender, but when packets are re-transmitted there is an ambiguity: the acknowledgment
may be a response to the first transmission of the segment or to a subsequent re-transmission.
Karn's Algorithm ignores retransmitted segments when updating the round trip time estimate. Round trip time estimation is based only on unambiguous acknowledgments, which are acknowledgments for segments that were sent only once.
This simplistic implementation 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.
This algorithm has proven to be extremely
effective in networks with high packet loss.
Transmission Control Protocol
The Transmission Control Protocol is one of the core protocols of the Internet Protocol Suite. TCP is one of the two original components of the suite, complementing the Internet Protocol , and therefore the entire suite is commonly referred to as TCP/IP...
. The algorithm was proposed by Phil Karn
Phil Karn
Phil Karn is an engineer from Baltimore, Maryland. He earned a bachelor's degree in electrical engineering from Cornell University in 1978 and a master's degree in electrical engineering from Carnegie Mellon University in 1979. From 1979 until 1984, Phil Karn worked at Bell Labs in Naperville,...
in 1987.
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 acknowledgment was returned to the sender, but when packets are re-transmitted there is an ambiguity: the acknowledgment
may be a response to the first transmission of the segment or to a subsequent re-transmission.
Karn's Algorithm ignores retransmitted segments when updating the round trip time estimate. Round trip time estimation is based only on unambiguous acknowledgments, which are acknowledgments for segments that were sent only once.
This simplistic implementation 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 extremely
effective in networks with high packet loss.
External links
- RFC 2581 - TCP Congestion Control
- RFC 2988 - Computing TCP's Retransmission Timer