Implement a Simple Congestion Control Algorithm

Topic Overview

Slow Start and Congestion Avoidance

TCP congestion control prevents senders from overwhelming shared links. The congestion window (cwnd) starts at 1 MSS and doubles each RTT during slow start. For example: RTT 0 sends 1 segment, RTT 1 sends 2, RTT 2 sends 4, RTT 3 sends 8.

Once cwnd reaches ssthresh, growth switches to linear (+1 MSS per RTT) in congestion avoidance.

AIMD on Loss

Additive Increase, Multiplicative Decrease:

• Increase: +1 MSS per RTT in congestion avoidance
• Decrease: halve cwnd on loss (cwnd = cwnd / 2)

Three duplicate ACKs trigger fast recovery (Reno): set ssthresh = cwnd / 2, retransmit, then resume. A full timeout is worse: reset cwnd to 1 MSS and restart slow start.

Effective Sending Rate

The sender's real limit is min(cwnd, rwnd) where rwnd is the receiver's advertised window. Linux defaulted to Reno until CUBIC replaced it; Google's BBR uses a model-based approach for high-bandwidth-delay links.

Why This Exercise

This task asks you to simulate congestion control with printed cwnd changes. Every video call and file download rides on one of these algorithms deciding, packet by packet, how hard to push the network. Reno was the Linux default until CUBIC replaced it in 2006; Google's BBR takes a model-based approach for high-bandwidth-delay paths where AIMD's sawtooth pattern wastes capacity.

Given an initial cwnd, an initial ssthresh, and a per-RTT event trace, simulate Reno-style congestion control (RFC 5681) in MSS units. RTT events grow the window: doubling during slow start while cwnd < ssthresh (capped at ssthresh), then +1 per RTT in congestion avoidance once cwnd >= ssthresh. Loss events cut the window: 3DUPACK (fast recovery) sets ssthresh = max(cwnd/2, 2) and cwnd = ssthresh + 3; TIMEOUT sets ssthresh = max(cwnd/2, 2) and cwnd = 1 (the whole flight is lost).

Input (stdin): one line: initial_cwnd initial_ssthresh K. Then K events, one per RTT round: RTT, 3DUPACK, or TIMEOUT.

Output (stdout):

• one line per event: <event> cwnd=<c> ssthresh=<s> - the state after that round
• final cwnd=<c> ssthresh=<s>