Karn's Algorithm for Time out Timer
Duration: 3 min
This video lesson is available to enrolled students.
AI Summary
An AI-generated summary of this video lecture.
The video lecture addresses significant limitations in TCP timeout mechanisms, specifically focusing on the "Problems with Basic Algorithm and Jacobson's Algorithm." The instructor explains that calculating the initial round-trip time (IRTT) relies heavily on the actual round-trip time (ARTT) of the previous segment using the specific formula IRTTn+1 = alpha IRTTn + (1 - alpha) ARTTn. A critical issue arises when an ACK is delayed and arrives after the timeout, forcing a retransmission. In this specific scenario, the actual RTT is unknown, making standard algorithms inapplicable for the next calculation. The lecture introduces Karn's Modification as the solution, which involves doubling the timeout timer (TOT) upon retransmission rather than using the standard estimation formulas that require actual RTT data. This ensures the sender does not make incorrect assumptions about network latency during retransmission events.
Chapters
0:00 – 2:00 00:00-02:00
The instructor introduces the formula IRTTn+1 = alpha IRTTn + (1 - alpha) ARTTn on the slide titled "Problems with Basic Algorithm and Jacobson's Algorithm". He explains that if an ACK arrives after the timeout, the sender must retransmit. He highlights the problem: determining the initial timeout value for the retransmitted segment when the actual RTT is unavailable because the ACK was delayed. He writes numbers like 10, 15, 12.5, and 25 on the screen to illustrate a scenario where the timeout needs adjustment, specifically noting that the ACK arrives after the timeout, so ARTT is not available. He emphasizes that the problem is resolved by Karn's modification.
2:00 – 2:57 02:00-02:57
The lecture transitions to "Karn's algorithm," explaining it addresses accurate RTT estimation in TCP. The slide notes the algorithm was proposed by Phil Karn and Craig Partridge in 1987, showing their photos. The next slide, "Karn's Modification," explicitly states that when a segment is retransmitted, one should not apply Basic or Jacobson's algorithms because actual RTT is unavailable. Instead, the instructor underlines the instruction to "double the time out timer (TOT)" whenever the timer times out and a retransmission occurs. He marks "Basic" and "Jacobson's" with red crosses to emphasize they are excluded in this specific case.
The video progresses from identifying a flaw in standard TCP timeout estimation—specifically the inability to calculate RTT during retransmissions due to delayed ACKs—to presenting Karn's Modification as the definitive solution. By doubling the timeout timer instead of relying on unavailable actual RTT data, the algorithm ensures reliable retransmission timing without skewing future RTT estimates. This modification prevents the confusion between original and retransmitted segments, maintaining network stability.