The congestion window – Networks Practice Problem

Print TCP's congestion window (in segments) at the start of each round trip, following these rules:

Start with cwnd = 1 and the given ssthresh.
A round without a loss: if cwnd < ssthresh, slow start: cwnd doubles, but not past ssthresh. Otherwise, congestion avoidance: cwnd grows by 1.
A round with a loss: ssthresh becomes half of cwnd (rounded down), but at least 2. After a timeout, cwnd becomes 1. After a dup (three duplicate ACKs), Tahoe also sets cwnd to 1, but Reno sets it to the new ssthresh.

Input

A line with the version (tahoe or reno), the number of rounds (1 to 60) and the first ssthresh (2 to 64). A second line with the losses as round:kind (for example 9:dup 15:timeout), or none.

Output

The window at the start of each round, separated by spaces.

Examples

Example 1 · Input

reno 12 16
9:dup

Expected output

1 2 4 8 16 17 18 19 20 10 11 12

Example 2 · Input

tahoe 6 8
none

Expected output

1 2 4 8 9 10

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Start with cwnd = 1. Each round, print cwnd first, then work out the next value.

Hint 2

Without a loss: if cwnd < ssthresh, cwnd = min(2 * cwnd, ssthresh); otherwise cwnd += 1.

Hint 3

With a loss: ssthresh = max(cwnd // 2, 2). Then cwnd = 1 for a timeout or for Tahoe, and cwnd = ssthresh for Reno's dup.

Solution

Show one correct solution (try it yourself first)

version, rounds, ssthresh = input().split()
rounds, ssthresh = int(rounds), int(ssthresh)
line = input().split()
losses = {}
if line != ["none"]:
    for item in line:
        r, kind = item.split(":")
        losses[int(r)] = kind
cwnd, out = 1, []
for r in range(1, rounds + 1):
    out.append(cwnd)
    if r in losses:
        ssthresh = max(cwnd // 2, 2)
        cwnd = ssthresh if losses[r] == "dup" and version == "reno" else 1
    elif cwnd < ssthresh:
        cwnd = min(cwnd * 2, ssthresh)
    else:
        cwnd += 1
print(*out)

Lesson: TCP congestion control →