Karn's algorithm

Karn's algorithm addresses the problem of getting accurate estimates of the round-trip time for messages when using the Transmission Control Protocol (TCP) in computer networking. The algorithm, also sometimes termed as the Karn-Partridge algorithm [1] was proposed in a paper by Phil Karn and Craig Partridge in 1987.[2]

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 ignores the round-trip time of all retransmitted packets, the round trip estimate will never be updated, and TCP will continue retransmitting every segment, never 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 two. This algorithm has proven to be extremely effective in balancing performance and efficiency in networks with high packet loss.[3][page needed] Ideally, Karn's algorithm would not be needed. Networks that have high round-trip time and retransmission timeouts should be investigated using root cause analysis techniques.[4]

References

  1. ^ Computer Networks: A Systems Approach, The Morgan Kaufmann Series in Networking, Larry L. Peterson, Bruce S. Davie Edition 5, Elsevier, 2011 p.418
  2. ^ Karn, Phil; Partridge, Craig (1987). Improving Round-Trip Time Estimates in Reliable Transport Protocols (PostScript). Proc. ACM SIGCOMM. pp. 2–7.
  3. ^ Comer, Douglas (2006). Internetworking with TCP/IP (Fifth ed.). Prentice Hall.
  4. ^ "What Is Karn's Algorithm?". Archived from the original on 2016-11-14. Retrieved 2016-09-07.
  • RFC 2581 - TCP Congestion Control
  • RFC 2988 - Computing TCP's Retransmission Timer (obsoleted by RFC 6298)
  • RFC 6298 - Computing TCP's Retransmission Timer

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.