Recover when a packet disappears

Implement retransmission deadlines, backoff, cancellation, and a retry budget.

Silence is ambiguous

A missing ACK might mean the packet was lost, the ACK was lost, or the peer is slow. Retransmitting with a new sequence number would create a gap. Retransmit the pending sequence and bytes exactly; only the acknowledgment field may reflect newly received peer data.

Time belongs to the harness

tcp_tick receives a deterministic time. If timer_active and now - sent_at >= rto, retransmit pending_flags/pending_seq/pending bytes, set sent_at=now, increment retries, and double rto up to 800 ms. For a SYN without ACK, the acknowledgment field is zero. The initial timeout is 100 ms.

original at 0 ms
retry 1 at 100 ms → RTO 200
retry 2 at 300 ms → RTO 400
retry 3 at 700 ms → RTO 800
retry 4 at 1500 ms → RTO 800
abort at 2300 ms if still unacknowledged

Stop owning acknowledged bytes

The supplied receive path clears timer_active when the outstanding bytes are acknowledged. tcp_tick must then stay quiet. At an expired timer with retries already MAX_RETRIES, close the connection and clear the timer. This deliberately small algorithm excludes RTT estimation and fast retransmit.

The boundary you own

Your callbacks run as a real C program in RV64 Linux. /course/netlab.h supplies bounded Ethernet/IP/TCP encoding, checksum validation, a virtual clock, and packet capture. You own the transport state and sequence numbers. emit_tcp(c, flags, seq, ack, bytes, length) emits actual packet bytes; the browser's program trace decodes them. Test injects packets and timer events rather than inspecting source text. This is a deliberately bounded active-open, stop-and-wait TCP implementation, not a replacement for the kernel TCP stack.

snd_una: first unacknowledged byte     snd_nxt: next unsent byte
rcv_nxt: next peer byte expected      peer_window: advertised capacity
pending_seq/flags/len/pending[]: one segment awaiting ACK
sent_at, rto, retries, timer_active: retransmission ownership
delivered[] / delivered_len: bytes accepted by the application
lab_now: deterministic clock in milliseconds

Your goal

Implement tcp_tick so a lost SYN or data acknowledgment retries the original sequence and payload with bounded exponential backoff.

What the tests observe

No premature retry
Same bytes and sequence on retry
Exponential deadlines
ACK cancellation and retry exhaustion

Need a nudge?

Hint 1

Use unsigned elapsed time now - c->sent_at, and return early unless the timer is active and due.

Hint 2

Retransmit pending_seq rather than snd_nxt. Leave snd_nxt unchanged; the same bytes still own the same sequence positions.

Hint 3

Check the retry budget before emitting. Increment retries only after a retransmission, then cap the doubled RTO at 800.

What happens inside Linux

No wall-clock sleep is involved. The peer simply withholds ACKs while the harness advances virtual time. The trace makes the repeated sequence number and widening delay visible.

Optional account sync. Exercises work without an account.

Reference headers and helper functions

Read-only lesson support. Your editable implementation is below.

netlab.h

#ifndef NETLAB_H
#define NETLAB_H
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define LAB_CAP 1600
#define LAB_MAX_FRAMES 512
#define SYN 2
#define ACK 16
#define PSH 8
#define FIN 1
#define RST 4
#define MAX_DATA 512
#define MAX_RETRIES 4

enum tcp_state { CLOSED, SYN_SENT, ESTABLISHED, FIN_WAIT1, FIN_WAIT2, CLOSING, TIME_WAIT };
struct segment { uint32_t seq, ack; unsigned flags, window, length; unsigned char data[MAX_DATA]; };
struct tcp {
    enum tcp_state state;
    uint32_t iss, snd_una, snd_nxt, rcv_nxt;
    unsigned peer_window, local_window, mss;
    unsigned char pending[MAX_DATA], delivered[2048];
    unsigned pending_len, pending_flags, delivered_len;
    uint32_t pending_seq;
    unsigned timer_active, sent_at, rto, retries, time_wait_until;
};
struct captured { unsigned char bytes[LAB_CAP]; unsigned size, time; };
static struct captured lab_frames[LAB_MAX_FRAMES];
static unsigned lab_count, lab_now, lab_failed;
static int lab_testing;
static const unsigned char lab_mac[6] = {2,0,0,0,0,1};
static const unsigned char peer_mac[6] = {2,0,0,0,0,2};
static const unsigned char lab_ip[4] = {10,0,0,1};
static const unsigned char peer_ip[4] = {10,0,0,2};
static unsigned get16(const unsigned char *p) { return ((unsigned)p[0]<<8)|p[1]; }
static uint32_t get32(const unsigned char *p) { return ((uint32_t)get16(p)<<16)|get16(p+2); }
static void put16(unsigned char *p,unsigned n) { p[0]=(n>>8)&255; p[1]=n&255; }
static void put32(unsigned char *p,uint32_t n) { put16(p,n>>16); put16(p+2,n); }
static uint32_t sum_words(const unsigned char *p,unsigned n) {
    uint32_t sum=0; unsigned i;
    for(i=0;i+1<n;i+=2) sum+=get16(p+i);
    if(n&1) sum+=(unsigned)p[n-1]<<8;
    return sum;
}
static unsigned fold_sum(uint32_t sum) { while(sum>>16) sum=(sum&65535)+(sum>>16); return sum; }
static unsigned checksum(const unsigned char *p,unsigned n) { return (~fold_sum(sum_words(p,n)))&65535; }
static unsigned transport_checksum(const unsigned char *src,const unsigned char *dst,unsigned proto,const unsigned char *p,unsigned n) {
    return (~fold_sum(sum_words(src,4)+sum_words(dst,4)+proto+n+sum_words(p,n)))&65535;
}
static void trace_frame(const char *direction,const unsigned char *p,unsigned n) {
    unsigned i; printf("LAB_PACKET|%u|%s|",lab_now,direction);
    for(i=0;i<n;i++) printf("%02x",p[i]);
    putchar('\n');
}
static void emit_frame(const unsigned char *p,unsigned n) {
    if(n>LAB_CAP || lab_count>=LAB_MAX_FRAMES) { fprintf(stderr,"Packet capture capacity exceeded\n"); lab_failed++; return; }
    memcpy(lab_frames[lab_count].bytes,p,n); lab_frames[lab_count].size=n; lab_frames[lab_count].time=lab_now;
    lab_count++; trace_frame("tx",p,n);
}
static void lab_check(int ok,const char *id,const char *good,const char *bad) {
    if(!ok) lab_failed++;
    if(lab_testing) printf("LAB_CHECK|%s|%s|%s\n",id,ok?"pass":"fail",ok?good:bad);
    else printf("%s: %s\n",ok?"ok":"needs work",ok?good:bad);
}
static void lab_reset(void) { lab_count=0; lab_now=0; }
static unsigned make_ip_frame(unsigned char *out,int from_peer,unsigned proto,const unsigned char *payload,unsigned n) {
    unsigned char *ip=out+14;
    memcpy(out,from_peer?lab_mac:peer_mac,6); memcpy(out+6,from_peer?peer_mac:lab_mac,6); put16(out+12,0x0800);
    memset(ip,0,20); ip[0]=0x45; put16(ip+2,20+n); ip[8]=64; ip[9]=proto;
    memcpy(ip+12,from_peer?peer_ip:lab_ip,4); memcpy(ip+16,from_peer?lab_ip:peer_ip,4);
    put16(ip+10,checksum(ip,20)); memcpy(ip+20,payload,n); return 34+n;
}
static unsigned make_tcp_frame(unsigned char *out,int from_peer,unsigned flags,uint32_t seq,uint32_t ack,unsigned window,const unsigned char *data,unsigned n) {
    unsigned char tcp[20+MAX_DATA];
    if(n>MAX_DATA) return 0;
    memset(tcp,0,20); put16(tcp,from_peer?8080:40000); put16(tcp+2,from_peer?40000:8080);
    put32(tcp+4,seq); put32(tcp+8,ack); tcp[12]=0x50; tcp[13]=flags; put16(tcp+14,window);
    if(n) memcpy(tcp+20,data,n);
    put16(tcp+16,transport_checksum(from_peer?peer_ip:lab_ip,from_peer?lab_ip:peer_ip,6,tcp,20+n));
    return make_ip_frame(out,from_peer,6,tcp,20+n);
}
static int decode_tcp(const unsigned char *f,unsigned n,struct segment *s) {
    unsigned ihl,total,thl,len; const unsigned char *ip,*tcp;
    if(n<54 || get16(f+12)!=0x0800) return -1;
    ip=f+14; ihl=(ip[0]&15)*4; total=get16(ip+2);
    if((ip[0]>>4)!=4 || ihl<20 || total<ihl+20 || total+14>n || ip[9]!=6 || checksum(ip,ihl)!=0) return -1;
    if(get16(ip+6)&0x3fff) return -1; /* Fragment reassembly is a separate exercise. */
    tcp=ip+ihl; thl=(tcp[12]>>4)*4;
    if(thl<20 || thl>total-ihl || transport_checksum(ip+12,ip+16,6,tcp,total-ihl)!=0) return -1;
    len=total-ihl-thl; if(len>MAX_DATA) return -1;
    s->seq=get32(tcp+4); s->ack=get32(tcp+8); s->flags=tcp[13]; s->window=get16(tcp+14); s->length=len;
    if(len) memcpy(s->data,tcp+thl,len); return 0;
}
static void emit_tcp(struct tcp *c,unsigned flags,uint32_t seq,uint32_t ack,const unsigned char *data,unsigned n) {
    unsigned char frame[LAB_CAP]; unsigned size=make_tcp_frame(frame,0,flags,seq,ack,c->local_window,data,n);
    if(size) emit_frame(frame,size);
}
static void tcp_init(struct tcp *c,uint32_t iss) {
    memset(c,0,sizeof(*c)); c->state=CLOSED; c->iss=iss; c->snd_una=c->snd_nxt=iss;
    c->local_window=256; c->peer_window=512; c->mss=MAX_DATA; c->rto=100;
}
#ifdef NETLAB_TCP
void tcp_open(struct tcp *c);
void tcp_receive(struct tcp *c,const struct segment *s);
unsigned tcp_send(struct tcp *c,const unsigned char *p,unsigned n);
void tcp_tick(struct tcp *c,unsigned now);
void tcp_close(struct tcp *c);
static void deliver(struct tcp *c,unsigned flags,uint32_t seq,uint32_t ack,unsigned window,const unsigned char *p,unsigned n) {
    unsigned char frame[LAB_CAP]; struct segment s;
    unsigned size=make_tcp_frame(frame,1,flags,seq,ack,window,p,n);
    trace_frame("rx",frame,size);
    if(decode_tcp(frame,size,&s)==0) tcp_receive(c,&s);
}
static int last_segment(struct segment *s) { return lab_count && decode_tcp(lab_frames[lab_count-1].bytes,lab_frames[lab_count-1].size,s)==0; }
static void established(struct tcp *c) { tcp_init(c,100); c->state=ESTABLISHED; c->snd_nxt=c->snd_una=101; c->rcv_nxt=501; }
static void at(struct tcp *c,unsigned now) { lab_now=now; tcp_tick(c,now); }
#endif
#endif

C/work/tcp-retransmission.cLoading local work…

Restoring your workspace…

⌘ / Ctrl ↵

TerminalRISC-V 64 · root · /work

Your Linux machine is ready to start.

Boot a disposable environment in this browser. You’ll get a real root shell, with no remote server or account required.