Add Retransmission for Unacknowledged Segments

Topic Overview

Detecting Loss

TCP guarantees delivery over unreliable networks by retransmitting missing segments. Two detection paths exist: timer expiry (RTO) and three duplicate ACKs (fast retransmit).

RTO Calculation

RFC 6298 defines:

• Measure RTT per segment
• Maintain smoothed RTT (SRTT) and variance (RTTVAR)
• RTO = SRTT + 4 * RTTVAR

Karn's algorithm skips RTT samples from retransmitted segments and doubles RTO on each timeout (capped around 64 seconds on Linux).

Fast Retransmit Example

Sender transmits SEQ 1000, 1100, 1200 (each 100 bytes). Segment 1100 is lost. Receiver gets 1000 and 1200, so it sends ACK=1100 repeatedly. After the third duplicate ACK, the sender retransmits SEQ 1100 immediately without waiting for the timer.

Exponential backoff doubles RTO on each consecutive timeout (1s, 2s, 4s, up to roughly 64s on Linux) until the missing segment is acknowledged. Retransmitted segments reuse the same sequence number so the receiver knows which data is being replayed.

Why This Exercise

This task requires you to simulate retransmission on packet loss. Fast retransmit on three duplicate ACKs is what keeps a video call or SSH session usable during transient loss instead of stalling for a full timeout. RFC 6298's RTO formula and Karn's algorithm for skipping RTT samples from retransmitted segments are implemented nearly verbatim in the Linux kernel's tcp_rtt_estimator().

Given a per-packet (seq, send_time, ack_time) trace and an RTO rule, run the retransmission timer. ack_time = -1 means the packet was lost and never acknowledged. A packet is acked in time if ack_time arrives at or before send_time + RTO; otherwise the timer fires, the packet is retransmitted once, and the RTO doubles (RFC 6298 exponential backoff). Backoff persists across packets until a packet is acked with zero retransmissions (Karn's algorithm), which resets the RTO to the base. A packet that exceeds max_retrans retransmissions is dropped.

Input (stdin): one line: base_rto max_retrans N (times in ms). Then N lines: seq send_time ack_time.

Output (stdout):

• one line per packet: seq=<s> ok retrans=<r> when acknowledged, or seq=<s> lost retrans=<r> when it exhausted max_retrans (r = retransmissions used)
• final_rto=<value> after the whole trace