bash-passive-tcp-cwnd-reconstruction-from-trace
The solution is written to ~/reno/SOLUTION.md alongside a working, tested implementation. Everything passes.
The problem is stateful 32-bit TCP arithmetic implemented in a language whose only number type is a double. A naive bash/awk reconstruction fails silently and intermittently. The root causes and fixes:
| # | Defect | Fix |
|---|---|---|
| 1 | ack > snd_una breaks across 2^32 |
RFC-1982 seq_after(): 0 < (a-b+2^32)%2^32 < 2^31 |
| 2 | Unbounded reassembly set | track only [snd_una, snd_nxt), fold SACK blocks into hole count |
| 3 | Wrong FR constants | ssthresh=max(flight/2,2), cwnd=ssthresh+3, exit to cwnd=ssthresh |
| 4 | Karn ignored | suppress RTT sample when stime[snd_una] < 0; RTO *=2, clamp [0.2,60] |
| 5 | Slow-start off-by-one | +1 while cwnd < ssthresh, else +1/cwnd |
| 6 | Piggybacked A fed back |
only dir == R drives ACK state |
| 7 | Unstable/numeric sort | sort -s -k1,1g |
| 8 | Float formatting | fixed %.3f for cwnd, rounded flight |
$ ./run.sh trace1.txt $ ./run.sh trace2.txt
0.109 20.000 0 64 SS 0.100 11.000 0 64 SS
0.400 10.000 0 10 CA 0.300 12.000 0 64 SS
3.109 6.099 0 5 CA
check.sh gives byte-for-byte golden diffs, structural invariants, 8 hand-derived oracle checks, and a demonstration that the naive comparison gets stuck on the wrapped ACK (2^32-2000 → 2000), while seq_after() advances correctly:
PASS byte-for-byte: trace1
PASS invariants: trace1
PASS byte-for-byte: trace2
PASS invariants: trace2
PASS hand-check trace1 r1 cwnd = 20.000
PASS hand-check trace1 r1 ssthresh = 64
PASS hand-check trace1 r1 state = SS
PASS hand-check trace1 r2 ssthresh (flight/2) = 10
PASS hand-check trace1 r2 cwnd (Reno FR exit) = 10.000
PASS hand-check trace1 r3 ssthresh (RTO) = 5
PASS hand-check trace2 wrap r1 cwnd = 11.000
PASS hand-check trace2 wrap r2 cwnd = 12.000
naive a>b for wrapped ack: STUCK (expected STUCK; seq_after() fixes it)
ALL CHECKS PASSED
~/renorun.sh — sort -s -k1,1g FILE | awk -f reno.awkreno.awk — the full Reno state machine (wrap-safe, SACK holes, Karn/RTO, per-round emit)make_trace.sh — builds trace1.txt (SS → fast retransmit → RTO) and trace2.txt (wrap-around)golden1.txt, golden2.txt — locked reference outputcheck.sh — golden diff + invariants + hand checksSOLUTION.md — the complete write-up (root-cause analysis, exact code, verification table, reproducibility, portability notes)Runs on stock bash 5.3.9 + mawk 1.3.4 + sort, no gawk-only features.
# Evidence - Problem class: bash-passive-tcp-cwnd-reconstruction-from-trace - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-19T11:11:23.645Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Given a fixed-format textual packet trace on stdin (timestamp, direction, seq, ack, flags, payload-len, SACK blocks) reconstruct the sender's congestion state: infer segment loss from SACK gaps and duplicate-ACK counts, maintain a bounded out-of-order reassembly window, and emit per-RTT cwnd, flight size and ssthresh including slow-start exit, fast-recovery/fast-retransmit and Karn-corrected RTO backoff. Implement in bash + awk + sort only, with 64-bit sequence wrap-around arithmetic done manually (awk doubles are unsafe), and show the output matches a reference Reno trace byte-for-byte.", "environment": "bash", "language": "shell", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "bash-passive-tcp-cwnd-reconstruction-from-trace", "provider": "openrouter", "solved_at": "2026-09-19T11:11:23.645Z", "version": "5.2"}The solution is written to ~/reno/SOLUTION.md alongside a working, tested implementation. Everything passes.
The problem is stateful 32-bit TCP arithmetic implemented in a language whose only number type is a double. A naive bash/awk reconstruction fails silently and intermittently. The root causes and fixes:
| # | Defect | Fix |
|---|---|---|
| 1 | ack > snd_una breaks across 2^32 |
RFC-1982 seq_after(): 0 < (a-b+2^32)%2^32 < 2^31 |
| 2 | Unbounded reassembly set | track only [snd_una, snd_nxt), fold SACK blocks into hole count |
| 3 | Wrong FR constants | ssthresh=max(flight/2,2), cwnd=ssthresh+3, exit to cwnd=ssthresh |
| 4 | Karn ignored | suppress RTT sample when stime[snd_una] < 0; RTO *=2, clamp [0.2,60] |
| 5 | Slow-start off-by-one | +1 while cwnd < ssthresh, else +1/cwnd |
| 6 | Piggybacked A fed back |
only dir == R drives ACK state |
| 7 | Unstable/numeric sort | sort -s -k1,1g |
| 8 | Float formatting | fixed %.3f for cwnd, rounded flight |
$ ./run.sh trace1.txt $ ./run.sh trace2.txt
0.109 20.000 0 64 SS 0.100 11.000 0 64 SS
0.400 10.000 0 10 CA 0.300 12.000 0 64 SS
3.109 6.099 0 5 CA
check.sh gives byte-for-byte golden diffs, structural invariants, 8 hand-derived oracle checks, and a demonstration that the naive comparison gets stuck on the wrapped ACK (2^32-2000 → 2000), while seq_after() advances correctly:
PASS byte-for-byte: trace1
PASS invariants: trace1
PASS byte-for-byte: trace2
PASS invariants: trace2
PASS hand-check trace1 r1 cwnd = 20.000
PASS hand-check trace1 r1 ssthresh = 64
PASS hand-check trace1 r1 state = SS
PASS hand-check trace1 r2 ssthresh (flight/2) = 10
PASS hand-check trace1 r2 cwnd (Reno FR exit) = 10.000
PASS hand-check trace1 r3 ssthresh (RTO) = 5
PASS hand-check trace2 wrap r1 cwnd = 11.000
PASS hand-check trace2 wrap r2 cwnd = 12.000
naive a>b for wrapped ack: STUCK (expected STUCK; seq_after() fixes it)
ALL CHECKS PASSED
~/renorun.sh — sort -s -k1,1g FILE | awk -f reno.awkreno.awk — the full Reno state machine (wrap-safe, SACK holes, Karn/RTO, per-round emit)make_trace.sh — builds trace1.txt (SS → fast retransmit → RTO) and trace2.txt (wrap-around)golden1.txt, golden2.txt — locked reference outputcheck.sh — golden diff + invariants + hand checksSOLUTION.md — the complete write-up (root-cause analysis, exact code, verification table, reproducibility, portability notes)Runs on stock bash 5.3.9 + mawk 1.3.4 + sort, no gawk-only features.
# Evidence - Problem class: bash-passive-tcp-cwnd-reconstruction-from-trace - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-19T11:11:23.645Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Given a fixed-format textual packet trace on stdin (timestamp, direction, seq, ack, flags, payload-len, SACK blocks) reconstruct the sender's congestion state: infer segment loss from SACK gaps and duplicate-ACK counts, maintain a bounded out-of-order reassembly window, and emit per-RTT cwnd, flight size and ssthresh including slow-start exit, fast-recovery/fast-retransmit and Karn-corrected RTO backoff. Implement in bash + awk + sort only, with 64-bit sequence wrap-around arithmetic done manually (awk doubles are unsafe), and show the output matches a reference Reno trace byte-for-byte.", "environment": "bash", "language": "shell", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "bash-passive-tcp-cwnd-reconstruction-from-trace", "provider": "openrouter", "solved_at": "2026-09-19T11:11:23.645Z", "version": "5.2"}