Credit-Based Flow Control and Retry
Explain how a link avoids buffer overflow without a ready wire, and how it recovers a corrupted packet.
You Will Be Able To
- Explain why a ready signal does not work over a link with a long delay.
- Choose between a running credit limit and "+1" credit updates.
- Predict what a lost credit update costs under each scheme.
- Explain how sequence numbers, Ack, Nak and a replay buffer deliver every packet once and in order.
- Lesson
- P10.14
- Time
- 35 min
- Runs on
- Your browser
- Check
- 5 questions
A receiver has 8 slots and frees one every 4 cycles. A transmitter that just sends overflows it 2,990 times in 4,000 cycles. With credits it never overflows. With the wrong kind of credit update, one lost update in 50 stops the link for good at cycle 1,795.
| 4,000 cycles | Sent | Delivered | Overflows | Last send at cycle |
|---|---|---|---|---|
| No credits (sends every cycle) | 4,000 | 999 | 2,990 | 3,999 |
| Running limit | 1,006 | 999 | 0 | 3,999 |
| Running limit, every 50th update lost | 1,006 | 999 | 0 | 3,999 |
| "+1" updates | 1,006 | 999 | 0 | 3,999 |
| "+1" updates, every 50th update lost | 400 | 400 | 0 | 1,795 |
Bench runs: 8 receive slots, a 3-cycle link each way, one packet drained every 4 cycles. A lost "+1" update loses its credit for good.
Why a Ready Wire Fails
On a chip, a receiver says "ready" and the sender sees it in the same clock. Across a serial link the answer takes several cycles to come back.
By the time "not ready" arrives, the sender has already sent more packets. They have nowhere to go.
- I/O
- Storage
- Channel / handshake
- Data
- Control
- Send
The transmitter sends a packet only while it holds a credit, and keeps a copy in the replay buffer.
- Receive
The receiver checks the CRC and the sequence number, then stores the packet in a slot.
- Return a credit
When the slot is freed, an update goes back. The transmitter may send one more packet.
- Ack or Nak
An Ack frees copies from the replay buffer. A Nak, or a timeout, makes the transmitter resend from the oldest copy.
Read the diagram as text
- Transmitter: credit count, sequence numbers
- Replay buffer: every packet not yet Acked
- Link: delay, corruption
- Receiver: checks the number and the CRC
- Receive slots: freed as data is used
- Transmitter → Link: packets
- Link → Receiver
- Receiver → Receive slots: store
- Receive slots → Transmitter: credit updates
- Receiver → Replay buffer: Ack or Nak
Flow control (credits) and retry (Ack, Nak, replay) are separate loops. A link needs both.
The fix is to let the sender know, in advance, how much room the receiver has. That room is counted in credits: one credit is space for one packet.
USB4 says exactly this: one credit is one transport packet of up to the maximum size (§5.3.2). It also defines a scheme with flow control off, where the receiver drops what it cannot hold.
Credits as a Running Limit
The transmitter starts with the receiver's free slots. It spends one per packet. When the receiver frees a slot, it sends an update back.
- Cycle 0
The transmitter starts with the 8 credits of the empty receiver and sends one packet per cycle.
- Cycle 1
The first packets reach the receiver after the 3-cycle link. It frees one every 4 cycles.
- Cycle 2
Eight packets sent, limit 8: no credit left. The transmitter waits.
- Cycle 4
The first update arrives: the limit is now 9, so one more packet may go.
- Cycle 6
From here on, one update in, one packet out. The receiver never overflows.
Bench run of the running-limit scheme. Values are read at the end of each cycle.
The update can say "one more": a +1 update. Or it can carry a running total, the slots plus every packet freed so far: a running limit. Both work while nothing is lost.
A lost "+1" update is a lost credit, for ever. The bench lost every 50th: after 400 packets the transmitter had no credits left and stopped at cycle 1,795.
A lost running limit costs nothing. The next update carries a total that includes the one that was lost.
USB 3.2 returns header buffer credits one at a time, but names each one: LCRD_A, B, C, D, then A again (§7.2.4.1.2). A port starts with four credits (§7.2.4.1.7).
The names are how a lost credit is noticed. A credit that arrives out of order means one went missing, and the link goes to Recovery to set things right.
USB4 handles lost packets with Credit Sync Packets. They carry the number of packets sent so far, a running count, so the two ends can agree again (§5.3.2.3).
Sequence Numbers, Ack and Nak
Credits stop overflow. They do not fix a packet that the channel corrupted. For that, each packet carries a sequence number.
The receiver delivers packets only in order. For each good packet it sends an Ack with its number. For a bad or out-of-order packet it sends one Nak carrying the last good number.
The transmitter keeps every packet in a replay buffer until an Ack covers it. A Nak, or silence for too long, makes it go back and resend from the oldest packet not acknowledged. That is go-back-N.
- Cycle 0
Packet 3 is corrupted on the way. The transmitter does not know yet and keeps sending.
- Cycle 1
Packets 0, 1 and 2 are delivered and Acked. The receiver now expects packet 3.
- Cycle 2
The bad packet 3 arrives. The receiver sends one Nak naming packet 2, the last good one. That Nak is corrupted too and lost.
- Cycle 3
Acks for 0 to 2 have freed those slots. Packets 3 to 10 fill the window of 8. The receiver discards 4 to 10: they are out of order.
- Cycle 5
Forty cycles with no news: the replay timer fires. The transmitter rewinds to packet 3, the oldest not acknowledged.
- Cycle 6
Packet 3 is delivered at last, then 4 and the rest, in order and once each.
Bench run (seed 21). Go-back-N: the transmitter resends everything from the oldest packet not acknowledged.
| 2,000 packets | Delivered | Lost | Duplicates | Out of order | Transmissions |
|---|---|---|---|---|---|
| No corruption | 2,000 | 0 | 0 | 0 | 2,000 |
| 1 packet or reply in 100 corrupted | 2,000 | 0 | 0 | 0 | 2,150 |
| 1 in 10 corrupted | 2,000 | 0 | 0 | 0 | 3,866 |
rp.no_replay = 1, 1 in 100 | 17 | 1,983 | 0 | 0 | 2,000 |
rp.accept_any_seq = 1, 1 in 100 | 2,000 | 0 | 82 | 24 | 2,095 |
Bench runs: window 8, link delay 4 cycles, replay timeout 40 cycles. Corruption hits packets and Acks or Naks alike.
At 1 in 10 corrupted, every packet still arrived once and in order. It took 3,866 transmissions for 2,000 packets.
Free the buffer on send, and nothing can be resent: 1,983 of 2,000 packets were lost at 1 in 100. Accept any good packet, and 82 were delivered twice and 24 out of order.
A receiver that sends a Nak for every bad packet, not one per run, still delivers everything. It is wasteful: 1,449 Naks against 213, and 5,032 transmissions against 3,866.
USB 3.2 works this way for header packets (§7.2.4.1.5). A good packet gets one LGOOD_n with its number. A bad one gets a single LBAD, and later packets are ignored until LRTY.
On LBAD the sender sends LRTY and resends every header packet not yet acknowledged (§7.2.4.1.3). A resent packet uses no new credit.
Sizing Credits, the Replay Buffer and the Timers
A credit returns only after a packet has crossed the link and its update has come back. To keep the link busy, the receiver needs at least one slot for every packet in flight during that round trip.
| Link delay (cycles) | Credits 2 / 4 / 8 / 16: packets per cycle | Replay window 2 / 4 / 8 / 16: packets per cycle |
|---|---|---|
| 1 | 0.50 / 0.99 / 0.99 / 0.99 | 0.66 / 0.99 / 0.99 / 0.99 |
| 3 | 0.25 / 0.50 / 0.99 / 0.99 | 0.28 / 0.57 / 0.99 / 0.99 |
| 7 | 0.12 / 0.25 / 0.50 / 0.99 | 0.13 / 0.26 / 0.53 / 0.99 |
| 15 | 0.06 / 0.12 / 0.25 / 0.50 | 0.06 / 0.12 / 0.25 / 0.51 |
Bench runs: the receiver frees a slot every cycle and nothing is corrupted. Only the credits or the window limit the rate.
With a 3-cycle link the round trip is 8 cycles, and 8 slots reach full rate; 4 slots give half. The same rule sizes the replay buffer: it holds every packet until its Ack returns.
Sequence numbers need room too. Go-back-N must keep its window smaller than the number space, or a resent old packet looks like a new one.
| Numbers 0 to 7, every Ack lost | Resent packets accepted as new |
|---|---|
| window 4 | 0 |
| window 7 | 0 |
| window 8 | 8 |
Bench model: the transmitter resends its whole window after its timer fires.
USB 3.2 SuperSpeed numbers header packets 0 to 7 (LGOOD_0 to LGOOD_7, Table 7-4) and gives each port four header credits (§7.2.4.1.7). The window of four stays well inside the eight numbers.
The replay timer must outlast the round trip. With a 4-cycle link, timers of 4 and 8 cycles fired early: 1 needless replay each. Timers of 12 and 16 caused none.
USB 3.2 runs two such timers on header packets (§7.2.4.1.13, Table 7-7). PENDING_HP_TIMER, 10 µs, waits for the LGOOD_n or LBAD of a sent packet. CREDIT_HP_TIMER, 5000 µs, waits for a credit to come back.
Either one expiring sends the link to Recovery. So does failing to receive a header packet three times in a row (§7.2.4.1.5).
Try It
Every packet arrives once and in order, even though 1 packet or reply in 100 was corrupted.
The extra transmissions are the replays: each one resends from the oldest packet not yet acknowledged.
Add rp.no_replay = 1; before rp.restart. The transmitter now frees each packet as soon as it is sent, and the first corrupted packet is lost for good.
delivered 2000 of 2000, 0 duplicates, 0 out of order 2150 transmissions, 19 Naks, 19 replays, done at cycle 2428Read included file: hs_pkg.sv
`timescale 1ns/1ns
// hs_pkg.sv: shared pure functions, and the bench random generator (read-only).
package hs_pkg;
// xorshift32 (Marsaglia 2003): a linear generator over GF(2), period 2^32 - 1. A zero state is
// replaced by 1, because zero maps to itself.
function automatic [31:0] xs32(input [31:0] s);
reg [31:0] x;
x = (s == 32'd0) ? 32'd1 : s;
x = x ^ (x << 13); x = x ^ (x >> 17); x = x ^ (x << 5);
return x;
endfunction
// A Fibonacci PRBS generator x^n + x^m + 1 (PRBS7: 7,6; PRBS9: 9,5; PRBS15: 15,14; PRBS23: 23,18;
// PRBS31: 31,28). The output bit is s[n-1]; the next state shifts the feedback into bit 0.
function automatic [31:0] prbs_next(input [31:0] s, input int n, input int m);
reg fb;
fb = s[n-1] ^ s[m-1];
return ((s << 1) | {31'd0, fb}) & ((n == 32) ? 32'hffffffff : ((32'd1 << n) - 32'd1));
endfunction
function automatic int ones(input [63:0] v);
int n; n = 0;
for (int i = 0; i < 64; i++) n += v[i];
return n;
endfunction
// GF(16) with x^4 + x + 1, and GF(1024) with x^10 + x^3 + 1: shift-and-add multiply, no tables.
function automatic [3:0] gf16_mul(input [3:0] a, input [3:0] b);
reg [3:0] p, x; p = 4'd0; x = a;
for (int i = 0; i < 4; i++) begin
if (b[i]) p = p ^ x;
x = x[3] ? ({x[2:0], 1'b0} ^ 4'b0011) : {x[2:0], 1'b0};
end
return p;
endfunction
function automatic [3:0] gf16_pow(input int e); // alpha^e, alpha = x
reg [3:0] p; int k; p = 4'd1; k = e % 15; if (k < 0) k += 15;
for (int i = 0; i < k; i++) p = gf16_mul(p, 4'd2);
return p;
endfunction
function automatic int gf16_log(input [3:0] a); // -1 for 0
reg [3:0] p; p = 4'd1;
if (a == 4'd0) return -1;
for (int i = 0; i < 15; i++) begin if (p == a) return i; p = gf16_mul(p, 4'd2); end
return -1;
endfunction
function automatic [9:0] gf1024_mul(input [9:0] a, input [9:0] b);
reg [9:0] p, x; p = 10'd0; x = a;
for (int i = 0; i < 10; i++) begin
if (b[i]) p = p ^ x;
x = x[9] ? ({x[8:0], 1'b0} ^ 10'b0000001001) : {x[8:0], 1'b0};
end
return p;
endfunction
function automatic [9:0] gf1024_pow(input int e);
reg [9:0] p; int k; p = 10'd1; k = e % 1023; if (k < 0) k += 1023;
for (int i = 0; i < k; i++) p = gf1024_mul(p, 10'd2);
return p;
endfunction
endpackage
// hs_rng: the bench's random numbers. Same seed, same numbers, on every engine.
module hs_rng;
int unsigned s = 32'h2545f491;
function automatic void seed(input int unsigned v); s = (v == 0) ? 32'd1 : v; endfunction
function automatic int unsigned next(); s = hs_pkg::xs32(s); return s; endfunction
function automatic int below(input int n); s = hs_pkg::xs32(s); return (n <= 0) ? 0 : int'(s % n); endfunction
function automatic bit bit1(); s = hs_pkg::xs32(s); return s[16]; endfunction
function automatic bit chance_ppm(input int ppm); s = hs_pkg::xs32(s); return (s % 1000000) < ppm; endfunction
function automatic [7:0] byte8(); s = hs_pkg::xs32(s); return s[23:16]; endfunction
endmodule
Read included file: hs_link.sv
`timescale 1ns/1ns
// hs_link.sv: link training, credit flow control and Ack/Nak replay (read-only).
// Every count, delay and timeout here is a bench value, not a specification's.
//
// hs_train_port: a toy state machine in the shape of an LTSSM, one ordered set per clock.
// Ordered sets: 0 EI (electrical idle), 1 TS1, 2 TS2, 3 IDLE, 4 a corrupted set.
// The rule, clock by clock. Clock 0 is the first clock after reset is released; the state is DETECT.
// - tx at clock c is the set chosen at clock c-1 for the state of clock c-1: EI in DETECT, TS1 in
// POLL_TS1, TS2 in POLL_TS2, IDLE in CONFIG and L0 (EI during reset and at clock 0).
// - A decision at clock c uses the sets received at clocks before c: run_ts1 is the number of TS1 or TS2
// received in a row ending at clock c-1, run_ts2 the same for TS2, run_idle for IDLE.
// - time_in_state at clock c is the number of clocks since the state began (0 at its first clock).
// - DETECT: after detect_wait clocks (time_in_state >= detect_wait) go to POLL_TS1.
// POLL_TS1: when run_ts1 >= need_ts1 go to POLL_TS2.
// POLL_TS2: when run_ts2 >= need_ts2 and at least min_ts2_sent TS2 have been sent in this state go to
// CONFIG (the TS2 count at clock c is time_in_state: one TS2 is sent per clock of the state).
// CONFIG: when run_idle >= need_idle go to L0.
// In POLL_TS1, POLL_TS2 and CONFIG, when no transition is due and time_in_state >= timeout, go to
// DETECT and count a retrain. So no state but L0 lasts more than timeout + 1 clocks.
// - A transition decided at clock c takes effect at clock c + 1. Counters hold up to 65535.
// Faults: never_ts2 (never leaves POLL_TS1 for POLL_TS2), count_total_not_consecutive (the run counts
// count every matching set since reset: a bad set does not reset them), no_timeout (never times out).
// hs_train_link: two ports a and b. b receives at clock c what a sent at clock c - 6 (a delay line of 5
// registers), and the reverse; before that they receive EI. When corrupt_every > 0, the set b receives at
// every clock c with c % corrupt_every == 0 is replaced by a corrupted set. up_at is the first clock at
// which both ports are in L0 (-1: not yet). Hold rst high from time 0 (before reset Icarus shows x), and
// read up_at at a negedge: it is written at the posedge. trace = 1 logs "c<clock> A <state>" lines.
//
// hs_fc: credit flow control, stepped once per cycle by step(). The rule, for cycle t (from 0):
// 1. A packet sent in cycle t - delay - 1 arrives: the receiver stores it, or counts an overflow if it
// already holds slots packets.
// 2. An update sent in cycle t - delay - 1 arrives at the transmitter. Cumulative (the default): it
// carries the running limit, slots + packets freed so far. incremental_credits: it means "+1".
// 3. When t % drain_every == drain_every - 1 and the receiver holds a packet, it frees one and sends an
// update, except that every drop_every-th update (0: none) is lost.
// 4. The transmitter always has a packet and sends one when it may: cumulative, while limit - sent > 0;
// incremental, while its credit count > 0; no_credits, always.
// Counters: sent, delivered, overflows, max_fill, last_send. delay is at most 15.
// incremental_credits is "+1 updates with no index": USB 3.2 §7.2.4 also returns one credit at a time
// (LCRD_A..D) but names each credit, so a lost one is noticed and recovered; this twin has no names.
//
// hs_replay: sequence numbers, Ack/Nak and a go-back-N replay buffer of window packets. The rule, for cycle
// t (from 0): a packet sent in cycle t - delay - 1 arrives (marked bad if it was corrupted); an Ack or
// Nak sent in cycle t - delay arrives. In each cycle, in order:
// 1. The receiver takes the arriving packet: a good packet whose number is the next expected one is
// delivered and Acked; a good packet with a lower number is Acked with the last good number; a bad or
// out-of-order packet gets one Nak (carrying the last good number) until a good one arrives
// (nak_every_bad: a Nak every time). If an Ack or Nak was made, one draw from the generator decides
// whether it is corrupted (and dropped) with probability loss_permille / 1000.
// 2. The transmitter: its timer counts up; an arriving Ack or Nak frees every packet up to its number
// (and restarts the timer if that frees any); a Nak rewinds the next packet to send to the oldest
// unacknowledged one and restarts the timer; so does a timer above timeout while packets are
// unacknowledged. Each rewind counts a replay.
// 3. If fewer than window packets are unacknowledged and any are left, the next one is sent; one draw
// decides whether it is corrupted. done_at is the first cycle that ends with every packet
// acknowledged (no_replay: with every packet sent and none in flight).
// Counters: delivered, dup, out_of_order, tx_count, naks, replays, done_at. delay is at most 15.
// Faults: no_replay (the buffer is freed on send), accept_any_seq (delivers any good packet),
// nak_every_bad (a Nak for every bad packet, not one per run: wasteful rather than wrong).
module hs_train_port(input wire clk, input wire rst, input wire [2:0] rx, output reg [2:0] tx = 3'd0, output reg [2:0] state = 3'd0, output reg [15:0] retrains = 16'd0);
localparam EI = 3'd0, TS1 = 3'd1, TS2 = 3'd2, IDL = 3'd3;
localparam DETECT = 3'd0, POLL_TS1 = 3'd1, POLL_TS2 = 3'd2, CONFIG = 3'd3, L0 = 3'd4;
int detect_wait = 12, need_ts1 = 8, need_ts2 = 8, min_ts2_sent = 16, need_idle = 8, timeout = 400;
bit never_ts2 = 0, count_total_not_consecutive = 0, no_timeout = 0;
reg [15:0] run1 = 16'd0, run2 = 16'd0, runi = 16'd0, timer = 16'd0;
wire tmo = (timer >= timeout) && !no_timeout;
wire keep = count_total_not_consecutive;
function automatic [15:0] up(input [15:0] v); return v + (v != 16'hffff); endfunction
always @(posedge clk) if (rst) begin state <= DETECT; tx <= EI; run1 <= 0; run2 <= 0; runi <= 0; timer <= 0; retrains <= 0; end
else begin
run1 <= (rx == TS1 || rx == TS2) ? up(run1) : keep ? run1 : 16'd0;
run2 <= (rx == TS2) ? up(run2) : keep ? run2 : 16'd0;
runi <= (rx == IDL) ? up(runi) : keep ? runi : 16'd0;
timer <= up(timer);
case (state)
DETECT: begin tx <= EI; if (timer >= detect_wait) begin state <= POLL_TS1; timer <= 0; end end
POLL_TS1: begin tx <= TS1;
if (run1 >= need_ts1 && !never_ts2) begin state <= POLL_TS2; timer <= 0; end
else if (tmo) begin state <= DETECT; timer <= 0; retrains <= retrains + 1; end end
POLL_TS2: begin tx <= TS2;
if (run2 >= need_ts2 && timer >= min_ts2_sent) begin state <= CONFIG; timer <= 0; end
else if (tmo) begin state <= DETECT; timer <= 0; retrains <= retrains + 1; end end
CONFIG: begin tx <= IDL;
if (runi >= need_idle) begin state <= L0; timer <= 0; end
else if (tmo) begin state <= DETECT; timer <= 0; retrains <= retrains + 1; end end
default: tx <= IDL;
endcase
end
endmodule
module hs_train_link(input wire clk, input wire rst);
int corrupt_every = 0; int n = 0, up_at = -1; bit trace = 0;
localparam D = 5;
reg [2:0] ab [0:D]; reg [2:0] ba [0:D];
initial for (int i = 0; i <= D; i++) begin ab[i] = 3'd0; ba[i] = 3'd0; end
wire [2:0] atx, btx, ast, bst; wire [15:0] ar, br;
wire [2:0] b_in = (corrupt_every > 0 && n % corrupt_every == 0) ? 3'd4 : ab[D];
hs_train_port a(clk, rst, ba[D], atx, ast, ar);
hs_train_port b(clk, rst, b_in, btx, bst, br);
reg [2:0] ast_q = 0, bst_q = 0;
function automatic string sname(input [2:0] s);
case (s) 3'd0: return "DETECT"; 3'd1: return "POLL_TS1"; 3'd2: return "POLL_TS2"; 3'd3: return "CONFIG"; default: return "L0"; endcase
endfunction
always @(posedge clk) begin
n <= rst ? 0 : n + 1;
ab[0] <= rst ? 3'd0 : atx; ba[0] <= rst ? 3'd0 : btx;
for (int i = 1; i <= D; i++) begin ab[i] <= rst ? 3'd0 : ab[i-1]; ba[i] <= rst ? 3'd0 : ba[i-1]; end
if (rst) up_at = -1;
else if (up_at < 0 && ast == 3'd4 && bst == 3'd4) up_at = n;
if (trace && !rst && ast != ast_q) $display("c%0d A %s", n, sname(ast));
if (trace && !rst && bst != bst_q) $display("c%0d B %s", n, sname(bst));
ast_q <= ast; bst_q <= bst;
end
endmodule
module hs_fc;
int slots = 8, delay = 3, drain_every = 4, drop_every = 0;
bit incremental_credits = 0, no_credits = 0;
bit fv [0:15]; bit rv [0:15]; int rval [0:15];
int t = 0, fill = 0, max_fill = 0, overflows = 0, delivered = 0, sent = 0, freed = 0, consumed = 0, limit = 8, credits = 8, upd = 0, last_send = -1;
function automatic void restart();
if (delay > 15) begin $display("hs_fc: delay %0d clamped to 15", delay); delay = 15; end
t = 0; fill = 0; max_fill = 0; overflows = 0; delivered = 0; sent = 0; freed = 0; consumed = 0; limit = slots; credits = slots; upd = 0; last_send = -1;
for (int i = 0; i < 16; i++) begin fv[i] = 0; rv[i] = 0; rval[i] = 0; end
endfunction
function automatic bit can_send(); return no_credits || (incremental_credits ? credits > 0 : (limit - consumed) > 0); endfunction
function automatic void step();
if (fv[delay]) begin if (fill == slots) overflows++; else fill++; end // arrivals at the receiver
if (fill > max_fill) max_fill = fill;
if (rv[delay]) begin if (incremental_credits) credits++; else limit = rval[delay]; end // updates at the transmitter
for (int i = delay; i > 0; i--) begin fv[i] = fv[i-1]; rv[i] = rv[i-1]; rval[i] = rval[i-1]; end
rv[0] = 0; // the receiver drains and returns
if (t % drain_every == drain_every - 1 && fill > 0) begin
fill--; delivered++; freed++; upd++;
if (!(drop_every > 0 && upd % drop_every == 0)) begin rv[0] = 1; rval[0] = slots + freed; end
end
fv[0] = 0; // the transmitter always has data
if (can_send()) begin fv[0] = 1; sent++; consumed++; credits--; last_send = t; end
t++;
endfunction
endmodule
module hs_replay;
int window = 8, delay = 4, timeout = 40, loss_permille = 0, total = 2000;
bit no_replay = 0, accept_any_seq = 0, nak_every_bad = 0;
hs_rng rng();
bit fv [0:15]; int fseq [0:15]; bit fbad [0:15]; bit rv [0:15]; bit rnak [0:15]; int rseq [0:15];
bit got [0:65535]; bit nak_sent = 0;
int t = 0, base = 0, nxt = 0, expected = 0, delivered = 0, dup = 0, out_of_order = 0, tx_count = 0, naks = 0, replays = 0, timer = 0, done_at = -1;
function automatic void restart(input int pm, input int seed);
if (delay > 15) begin $display("hs_replay: delay %0d clamped to 15", delay); delay = 15; end
if (total > 65536) begin $display("hs_replay: total %0d clamped to 65536", total); total = 65536; end
loss_permille = pm; rng.seed(seed);
t = 0; base = 0; nxt = 0; expected = 0; delivered = 0; dup = 0; out_of_order = 0; tx_count = 0; naks = 0; replays = 0; timer = 0; nak_sent = 0; done_at = -1;
for (int i = 0; i < 16; i++) begin fv[i] = 0; rv[i] = 0; end
for (int i = 0; i < total; i++) got[i] = 0;
endfunction
function automatic bit bad(); return rng.below(1000) < loss_permille; endfunction
function automatic void nak(); rv[0] = 1; rnak[0] = 1; rseq[0] = expected - 1; nak_sent = 1; naks++; endfunction
function automatic void step();
rv[0] = 0; // receiver
if (fv[delay]) begin
if (fbad[delay]) begin if (!nak_sent || nak_every_bad) nak(); end
else if (fseq[delay] == expected || accept_any_seq) begin
if (got[fseq[delay]]) dup++; else begin got[fseq[delay]] = 1; delivered++; end
if (fseq[delay] != expected) out_of_order++;
expected = fseq[delay] + 1; nak_sent = 0; rv[0] = 1; rnak[0] = 0; rseq[0] = fseq[delay];
end
else if (fseq[delay] < expected) begin rv[0] = 1; rnak[0] = 0; rseq[0] = expected - 1; end
else if (!nak_sent || nak_every_bad) nak();
end
if (rv[0] && bad()) rv[0] = 0; // a corrupted Ack or Nak is dropped
timer++; // transmitter
if (rv[delay]) begin
if (rseq[delay] + 1 > base) begin base = rseq[delay] + 1; timer = 0; end
if (rnak[delay] && !no_replay) begin nxt = base; replays++; timer = 0; end
end
if (no_replay) base = nxt;
if (timer > timeout && base < nxt && !no_replay) begin nxt = base; replays++; timer = 0; end
for (int i = delay; i > 0; i--) begin fv[i] = fv[i-1]; fseq[i] = fseq[i-1]; fbad[i] = fbad[i-1]; rv[i] = rv[i-1]; rnak[i] = rnak[i-1]; rseq[i] = rseq[i-1]; end
fv[0] = 0;
if (nxt < total && nxt < base + window) begin fv[0] = 1; fseq[0] = nxt; fbad[0] = bad(); nxt++; tx_count++; end
if (done_at < 0) begin
if (base >= total) done_at = t;
else if (no_replay && nxt >= total) begin reg busy; busy = 0; for (int i = 0; i <= delay; i++) busy = busy | fv[i]; if (!busy) done_at = t; end
end
t++;
endfunction
function automatic void run(input int max_cycles); while (done_at < 0 && t < max_cycles) step(); endfunction
endmodule
Check Yourself
Common Mistakes
Wrong Send credit updates as "+1" with nothing to tell them apart.
A lost update is then a lost credit for ever; one lost in 50 stopped the bench link at cycle 1,795.
Fix Send a running limit, or name each credit so that a missing one is noticed and recovered.
if (update_in) credits <= credits + 1;
can_send = credits > 0;if (update_in) limit <= update_limit;
can_send = 8'(limit - consumed) != 8'd0; // both 8 bits; the difference wrapsWrong Free a packet from the replay buffer when it is sent.
Then a corrupted packet cannot be resent; the bench lost 1,983 of 2,000 packets at 1 in 100.
Fix Keep each packet until an Ack covers its sequence number.
Wrong Expect a Nak to name the bad packet, and resend only that one.
The bench's Nak names the last good packet and USB's LBAD names none; both mean everything after the bad packet was dropped.
Fix Resend from the oldest packet not acknowledged, in order: go-back-N.
Wrong Leave out the replay timer because every bad packet gets a Nak.
The Nak itself can be corrupted; in the bench trace a lost Nak was recovered only by the timer.
Fix Run a timer on the oldest unacknowledged packet, and replay when it expires.
Remember
- Over a long link a ready wire answers too late. Credits tell the sender in advance how much room there is.
- A running limit survives lost updates. Plain "+1" updates lose a credit with every lost update.
- Sequence numbers let the receiver deliver in order and name the last good packet.
- The replay buffer keeps every packet until an Ack covers it. A Nak or a timeout replays from the oldest one.
- Flow control prevents overflow; retry fixes corruption. A link needs both.