Switch Routing

16.1 built the switch's structure: what a port admits, how the three protocols are separated, where a flit waits.

Every one of those stages assumed a destination had been chosen. This chapter is where that happens.

1. The Engineering Problem — A Lookup That Must Be A Function

Routing sounds like a table read. Six things make it not that.

The lookup must be a function. The same destination always yields the same port, and every port it yields is a port the switch has. A table that answers from an uninitialised slot is not "sometimes wrong" — it is not a function. Section 5.

A destination nobody knows is a policy decision, and the wrong answer is to guess. Forwarding to a default port delivers the flit somewhere, which is worse than not delivering it, because something at the other end will act on it. Section 6.

The three protocols do not route to the same places. A CXL.mem request goes to the device that owns the address; a CXL.io completion goes back to the host that issued it. One table for all three is a table that is right for a third of the traffic. Section 8.

The table is read every cycle and written occasionally, and the write is the interesting one. A flit that reads mid-update sees neither the old route nor the new one. Section 9.

One flit sometimes goes to many ports, and what separates a multicast from a broadcast-and-hope is knowing when every recipient has it. For an invalidation that is the difference between correct and silent. Section 10.

And a table can resolve a destination to the port the flit arrived on. Nothing about the flit is wrong and it will circulate until something counts hops. Section 11.

This chapter against 16.1 and 16.3, stated precisely. 16.1 owns the structure a flit moves through. This one owns how the destination is decided. 16.3 owns credits, buffering and arbitration. If a section here could be moved into either without loss, it is in the wrong chapter.

2. The One-Sentence Model

A routing decision is a lookup that resolves, in the flit's own protocol domain, against a table that is not mid-change, to a port that exists and is fit to receive — and every defect below is one of resolves, own domain, not mid-change or fit missing.

3. What This Chapter Owns

Deferred:

4. Teaching-Model Boundary

Sixteen table entries, four ports, three protocols, an eight-hop limit. A real switch's tables are far larger and its lookup is pipelined.

What is faithful: the lookup-as-a-function property, the miss policy, per-protocol domains, atomic table update, multicast completion tracking, the reflection and hop-limit guards, destination fitness as three separate facts, and the hit rate as the number that decides the design.

What is not: the table size, every latency, and the hop limit.

Every model is parameterised so the correct behaviour and a specific plausible failure are the same source under a different parameter, driven by one stimulus stream.

5. RTL 1 — The Table That Decides Where A Flit Goes

module route_lut #(parameter int STALE_ENTRY = 0) (
  input  logic clk, rst_n,
  input  logic       lookup,
  input  logic [3:0] dest_id,
  input  logic       write_en,
  input  logic [3:0] write_dest,
  input  logic [2:0] write_port,
  output logic [2:0] egress_port,
  output logic       hit,
  output logic       bad_port_err,
  output logic [7:0] n_lookups, n_hits, n_misses
);
  localparam logic [2:0] N_PORTS = 3'd4;
  logic [2:0]  tbl [0:15];
  logic [15:0] valid_q;
  assign hit         = lookup && valid_q[dest_id];
  assign egress_port = tbl[dest_id];
  // Every port a lookup yields must be a port the switch has.
  assign bad_port_err = (hit || ((STALE_ENTRY != 0) && lookup))
                        && (egress_port >= N_PORTS);
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      valid_q <= 16'd0;
      n_lookups <= 8'd0; n_hits <= 8'd0; n_misses <= 8'd0;
      // Deliberately an out-of-range port, so an answer from an
      // uninitialised slot is visible rather than plausible.
      for (i=0;i<16;i=i+1) tbl[i] <= 3'd7;
    end else begin
      if (write_en) begin
        tbl[write_dest] <= write_port;
        valid_q[write_dest] <= 1'b1;
      end
      if (lookup) begin
        n_lookups <= n_lookups + 8'd1;
        if (valid_q[dest_id]) n_hits   <= n_hits + 8'd1;
        else                  n_misses <= n_misses + 8'd1;
      end
    end
  end
endmodule

  table   : 8 lookups, 5 hits, 3 misses | stale-entry build answered a miss with port 2

The property being tested is that the lookup is a function, and three separate stimuli establish it:

• The same lookup twice gives the same answer. Driven explicitly.
• A second entry does not disturb the first. Both are written and both are read back.
• A write lands on the entry it names. During every write, dest_id is deliberately set to a different entry, so a write that lands on the read index instead of the write index is visible. That was a surviving mutation.

The reset value is 3'd7 on purpose — a port the switch does not have. STALE_ENTRY answers without consulting the valid bit, and what it returns is that value: bad_port_err fires, and the transcript shows the port number. A reset value inside the valid range would make the same bug look like a plausible answer.

The range test is >= N_PORTS, and the testbench writes a port number of exactly 4 to prove it. One off admits a port index the switch has no port for.

6. RTL 2 — A Destination Nobody Knows

module route_miss #(parameter int GUESS_ON_MISS = 0) (
  input  logic clk, rst_n,
  input  logic       lookup, hit,
  input  logic [2:0] table_port, default_port,
  output logic [2:0] chosen_port,
  output logic       forward, drop,
  output logic       guessed_err,
  output logic [7:0] n_forwarded, n_dropped, n_guessed
);
  // On a miss the correct switch drops and reports. GUESS_ON_MISS forwards to
  // a default port, which delivers the flit somewhere -- just not there.
  assign forward = lookup && (hit || (GUESS_ON_MISS != 0));
  assign drop    = lookup && !forward;
  assign chosen_port = hit ? table_port : default_port;
  assign guessed_err = forward && !hit;
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      n_forwarded <= 8'd0; n_dropped <= 8'd0; n_guessed <= 8'd0;
    end else if (lookup) begin
      if (forward) n_forwarded <= n_forwarded + 8'd1;
      else         n_dropped   <= n_dropped + 8'd1;
      if (guessed_err) n_guessed <= n_guessed + 8'd1;
    end
  end
endmodule

  miss    : forwarded=2 dropped=1 guessed=0 | guessing build forwarded=3 guessed=1

A miss is not an error in the flit. The flit is well-formed, the destination may be perfectly real, and the table simply has not been told about it — which happens routinely during the update window in section 9.

What the switch does about it is a policy decision with two options and one right answer:

The second is worse and it looks better. Delivery counts go up, drop counts go to zero, and a flit intended for one host is now being processed by another. guessed_err is the only thing that distinguishes the two, and the guessing build's counters are otherwise indistinguishable from a healthy switch's.

7. Waveform — Nine Cycles Of An Update Across A Multicast

Transcribed from the printed trace. Both builds see one stimulus stream.

Read pending against ff_early. The fire-and-forget build declares completion in the cycle the target mask exists and nothing has been acknowledged, and stays wrong for six cycles.

8. RTL 3 — Three Protocols, Three Routing Domains

module proto_route #(parameter int ONE_TABLE = 0) (
  input  logic clk, rst_n,
  input  logic       lookup,
  input  logic [1:0] proto,           // 0 io, 1 cache, 2 mem
  input  logic [3:0] key,
  input  logic [2:0] io_port, cache_port, mem_port,
  output logic [2:0] egress_port,
  output logic       wrong_domain_err,
  output logic [7:0] n_io, n_cache, n_mem, n_wrong
);
  logic [2:0] correct_port;
  // Each protocol resolves in its own domain. ONE_TABLE resolves everything
  // in the io domain, which is right for a third of the traffic.
  assign correct_port = (proto == 2'd0) ? io_port
                      : (proto == 2'd1) ? cache_port
                      :                   mem_port;
  assign egress_port = (ONE_TABLE != 0) ? io_port : correct_port;
  assign wrong_domain_err = lookup && (egress_port != correct_port);
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      n_io <= 8'd0; n_cache <= 8'd0; n_mem <= 8'd0; n_wrong <= 8'd0;
    end else if (lookup) begin
      if (proto == 2'd0)      n_io    <= n_io + 8'd1;
      else if (proto == 2'd1) n_cache <= n_cache + 8'd1;
      else                    n_mem   <= n_mem + 8'd1;
      if (wrong_domain_err) n_wrong <= n_wrong + 8'd1;
    end
  end
endmodule

  domains : io=2 cache=1 mem=2 wrong=0 | one-table build wrong=3

The three protocols resolve different keys against different tables. A CXL.mem request is keyed by address and resolves to the device that owns it; a CXL.io completion is keyed by requester and resolves back to the host. They are not the same lookup with a different label.

ONE_TABLE is the design that shares one. It gets io traffic right — and the testbench asserts that explicitly, because it is the reason the bug survives. A third of the traffic works perfectly and provides all of the confidence.

wrong_domain_err is gated on a lookup. A table that would resolve incorrectly is not a routing error until something asks it, and the testbench asserts that with the mismatch present and lookup low.

9. RTL 4 — Changing The Table While It Is Being Read

module route_update #(parameter int UPDATE_LIVE = 0) (
  input  logic clk, rst_n,
  input  logic       lookup, begin_update, commit_update,
  input  logic [2:0] old_port, new_port,
  output logic [2:0] resolved_port,
  output logic       updating, resolve_ok,
  output logic       torn_route_err,
  output logic [7:0] n_resolved, n_deferred, n_torn, update_cycles, max_update
);
  logic       upd_q;
  logic [2:0] live_q;
  logic [7:0] uc_q;
  // A lookup during an update is deferred, not answered. UPDATE_LIVE answers
  // from a table that is halfway between two configurations.
  assign resolve_ok    = lookup && (!upd_q || (UPDATE_LIVE != 0));
  assign resolved_port = live_q;
  assign torn_route_err = resolve_ok && upd_q;
  ...
      if (begin_update) begin upd_q <= 1'b1; uc_q <= 8'd0; end
      else if (commit_update && upd_q) begin
        upd_q <= 1'b0;
        live_q <= new_port;       // the new route becomes visible atomically
      end else if (upd_q) begin
        uc_q <= uc_q + 8'd1;
        if (uc_q + 8'd1 > max_update) max_update <= uc_q + 8'd1;
      end
      if (lookup) begin
        if (resolve_ok) n_resolved <= n_resolved + 8'd1;
        else            n_deferred <= n_deferred + 8'd1;
      end
      if (torn_route_err) n_torn <= n_torn + 8'd1;
    end
  end
endmodule

  update  : resolved=3 deferred=4 torn=0, update took 3 cycles | live-update build torn=4

The new route becomes visible atomically, at the commit. There is no cycle in which half of it is installed, which is what makes deferring safe rather than merely cautious.

Three properties, each driven:

• A lookup during an update is deferred, not answered. Deferred is a third outcome, distinct from both hit and miss — the flit waits and the decision is made correctly a few cycles later.
• A commit with no update open installs nothing. Driven before any update begins, because a commit that lands unconditionally can install a route nobody requested.
• The update interval is measured. Three cycles here; in a real switch it bounds how long routing decisions are delayed, which is a number the fabric manager's quiesce in 15.1 has to account for.

UPDATE_LIVE answers throughout, from a table that is neither the old configuration nor the new one. Four torn resolutions against zero, on the same stimulus.

10. RTL 5 — One Flit, Many Ports

module multicast #(parameter int FIRE_AND_FORGET = 0) (
  input  logic clk, rst_n,
  input  logic       send,
  input  logic [3:0] target_mask,
  input  logic       ack,
  input  logic [1:0] ack_port,
  output logic [3:0] delivered, pending,
  output logic       complete,
  output logic       premature_complete_err,
  output logic [7:0] n_sent, n_complete, wait_cycles, max_wait
);
  logic [3:0] mask_q, del_q;
  logic [7:0] w_q;
  logic       active_q;
  assign pending = mask_q & ~del_q;
  // Complete means every target has acknowledged. FIRE_AND_FORGET declares it
  // complete the moment it is outstanding.
  assign complete = (FIRE_AND_FORGET != 0) ? (send || active_q)
                  : (active_q && (pending == 4'd0));
  assign premature_complete_err = complete && (pending != 4'd0);
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      mask_q <= 4'd0; del_q <= 4'd0; active_q <= 1'b0; w_q <= 8'd0;
      n_sent <= 8'd0; n_complete <= 8'd0; max_wait <= 8'd0;
    end else begin
      if (send) begin
        mask_q <= target_mask; del_q <= 4'd0;
        active_q <= 1'b1; w_q <= 8'd0;
        n_sent <= n_sent + 8'd1;
      end else if (active_q) begin
        if (ack) del_q[ack_port] <= 1'b1;
        w_q <= w_q + 8'd1;
        if (w_q + 8'd1 > max_wait) max_wait <= w_q + 8'd1;
        // The acknowledgement registers first; the completion is visible in
        // the cycle after it, which is the cycle `complete` asserts.
        if (pending == 4'd0) begin
          active_q <= 1'b0;
          n_complete <= n_complete + 8'd1;
        end
      end
    end
  end
endmodule

  multicast: 3 targets, complete=1 after 6 cycles | fire-and-forget premature=1

Six cycles of waiting for the last recipient. For a coherency invalidation that interval is the window in which the old value was still readable somewhere, and it is the only reason this model tracks completion at all.

pending is mask_q & ~del_q — both terms, and each was a mutation. Dropping the mask makes every port pending; dropping the delivered set makes nothing ever complete.

The completion is made visible for a cycle: the acknowledgement registers on one edge and the completion is observed on the next. An earlier version cleared the active flag on the same edge that recorded the last acknowledgement, which meant complete was never high in any observable cycle — the counter incremented and the output that named it could not be checked.

And a second multicast is driven, to different targets, immediately after the first. Its delivered set must start empty, or the first multicast's acknowledgements complete it. That is the run it twice class again.

11. RTL 6 — A Table That Sends A Flit Back Where It Came From

module route_loop #(parameter int NO_HOP_LIMIT = 0) (
  input  logic clk, rst_n,
  input  logic       forward_ev,
  input  logic [2:0] ingress_port, egress_port,
  input  logic [3:0] hop_count,
  output logic       allow,
  output logic       reflect_err, hop_exceeded,
  output logic [7:0] n_forwarded, n_reflected, n_expired, max_hops
);
  logic reflects;
  localparam logic [3:0] HOP_LIMIT = 4'd8;
  assign reflects     = (egress_port == ingress_port);
  assign hop_exceeded = forward_ev && (hop_count >= HOP_LIMIT);
  // A flit is forwarded unless it would go back the way it came, or it has
  // been around too many times. NO_HOP_LIMIT drops the second guard.
  assign allow = forward_ev && !reflects
                 && ((NO_HOP_LIMIT != 0) || !hop_exceeded);
  assign reflect_err = forward_ev && reflects;
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      n_forwarded <= 8'd0; n_reflected <= 8'd0;
      n_expired <= 8'd0; max_hops <= 8'd0;
    end else if (forward_ev) begin
      if (allow) n_forwarded <= n_forwarded + 8'd1;
      if (reflect_err) n_reflected <= n_reflected + 8'd1;
      if (hop_exceeded && !allow) n_expired <= n_expired + 8'd1;
      // The furthest a flit got before something stopped it.
      if ({4'd0, hop_count} > max_hops) max_hops <= {4'd0, hop_count};
    end
  end
endmodule

  loops   : forwarded=2 reflected=1 expired=1 worst hops=8 | no-hop-limit build forwarded=3

Two guards for two different loops, and they catch different things:

• Reflection is a local loop — this switch's table sends the flit back the port it arrived on. One comparison catches it, and it is always a table error.
• The hop limit is a fabric loop — the flit is going somewhere different at every hop and coming back around. No single switch can see it, which is why the count travels with the flit.

The testbench drives a flit at exactly the limit and one just under it, because >= and > differ by one flit's worth of circulation and both look correct in isolation.

max_hops records the furthest any flit got before something stopped it. In a fabric that number rising over time is a routing table drifting toward a cycle, visible long before any flit actually loops forever.

12. RTL 7 — Is The Destination Fit To Receive

module dest_check #(parameter int RESOLVE_ONLY = 0) (
  input  logic clk, rst_n,
  input  logic       route_ok,
  input  logic [2:0] egress_port,
  input  logic [3:0] port_present, port_up, port_bound,
  output logic       deliver,
  output logic       no_port_err, port_down_err, unbound_err,
  output logic       blind_deliver_err,
  output logic [7:0] n_delivered, n_refused, n_blind
);
  logic present, up, bound, fit;
  assign present = (egress_port < 3'd4) && port_present[egress_port[1:0]];
  assign up      = present && port_up[egress_port[1:0]];
  assign bound   = present && port_bound[egress_port[1:0]];
  assign fit     = present && up && bound;
  // RESOLVE_ONLY delivers on the strength of the lookup alone.
  assign deliver = route_ok && (fit || (RESOLVE_ONLY != 0));
  assign no_port_err   = route_ok && !present;
  assign port_down_err = route_ok && present && !up;
  assign unbound_err   = route_ok && present && !bound;
  assign blind_deliver_err = deliver && !fit;
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      n_delivered <= 8'd0; n_refused <= 8'd0; n_blind <= 8'd0;
    end else if (route_ok) begin
      if (deliver) n_delivered <= n_delivered + 8'd1;
      else         n_refused   <= n_refused + 8'd1;
      if (blind_deliver_err) n_blind <= n_blind + 8'd1;
    end
  end
endmodule

  dest    : delivered=1 refused=3 (no port=1 down=1 unbound=1) | resolve-only build blind=3

A route that resolves is not a route that will work. Three separate facts, three separate errors, and the testbench asserts that each fires alone:

up and bound both require present, so a nonexistent port is reported once as missing rather than three times as missing, down and unbound. That layering is what makes each counter mean one thing.

RESOLVE_ONLY delivers on the lookup alone and delivers all three blind.

13. RTL 8 — What The Table Costs

module route_cost (
  input  logic clk, rst_n,
  input  logic        lookup_ev, hit_ev,
  input  logic [7:0]  hit_cycles, miss_cycles,
  input  logic        entry_added, entry_evicted,
  output logic [15:0] n_lookups, n_hits, n_misses, total_cycles, n_entries,
  output logic [7:0]  hit_pct, mean_cycles, evict_pct, occupancy_pct
);
  localparam logic [15:0] TABLE_SIZE = 16'd16;
  logic [15:0] n_evicted;
  logic [31:0] w_hit, w_evict, w_occ;
  assign hit_pct     = (n_lookups == 16'd0) ? 8'd0 : (w_hit / {16'd0, n_lookups});
  assign mean_cycles = (n_lookups == 16'd0) ? 8'd0 : (total_cycles / n_lookups);
  // Evictions as a share of insertions: a table thrashing rather than filling.
  assign evict_pct = (n_entries + n_evicted == 16'd0) ? 8'd0
                   : (w_evict / {16'd0, (n_entries + n_evicted)});
  assign occupancy_pct = (w_occ / {16'd0, TABLE_SIZE});
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      n_lookups <= 16'd0; n_hits <= 16'd0; n_misses <= 16'd0;
      total_cycles <= 16'd0; n_entries <= 16'd0; n_evicted <= 16'd0;
    end else begin
      if (lookup_ev) begin
        n_lookups <= n_lookups + 16'd1;
        // A miss costs the miss path, not the lookup.
        if (hit_ev) begin
          n_hits <= n_hits + 16'd1;
          total_cycles <= total_cycles + {8'd0, hit_cycles};
        end else begin
          n_misses <= n_misses + 16'd1;
          total_cycles <= total_cycles + {8'd0, miss_cycles};
        end
      end
      if (entry_added && (n_entries < TABLE_SIZE)) n_entries <= n_entries + 16'd1;
      if (entry_evicted && (n_entries != 16'd0)) begin
        n_entries <= n_entries - 16'd1;
        n_evicted <= n_evicted + 16'd1;
      end
    end
  end
endmodule

  cost    : peaked at 12 entries (75% full), 6 left, hit rate=90%, mean=3 cycles, evictions=78%

A 90 percent hit rate and a mean of 3 cycles, when a hit costs 2. The 10 percent of lookups that missed cost 20 cycles each and contributed half the mean.

That is the whole argument for measuring the hit rate rather than the lookup latency. The lookup is fast; the miss path is what the workload experiences, and the mean is dominated by it at any realistic hit rate.

Two guards are driven to their boundaries: the table fills to exactly its size and refuses more, and evicting an empty table does not wrap the count to 65535.

occupancy_pct is measured against the table size, not against the entries in use — which would be 100 percent always, and is one of the mutations.

14. RTL 9 — Auditing The Decisions

module route_audit (
  input  logic clk, rst_n,
  input  logic       decide,
  input  logic [2:0] ingress_port, egress_port,
  input  logic [1:0] proto,
  input  logic       dest_in_domain, port_exists,
  output logic       legal,
  output logic       illegal_route_err,
  output logic [7:0] n_audited, n_illegal, run_q_o, worst_run
);
  logic [7:0] run_q;
  logic not_reflect;
  assign not_reflect = (egress_port != ingress_port);
  // Three rules, and each is a real routing mistake: back the way it came,
  // out of the protocol's domain, or to a port that does not exist.
  assign legal = not_reflect && dest_in_domain && port_exists;
  assign illegal_route_err = decide && !legal;
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      n_audited <= 8'd0; n_illegal <= 8'd0; run_q <= 8'd0; worst_run <= 8'd0;
    end else if (decide) begin
      n_audited <= n_audited + 8'd1;
      if (!legal) begin
        n_illegal <= n_illegal + 8'd1;
        run_q <= run_q + 8'd1;
        // A run is a table that is wrong; an isolated one is a flit that
        // arrived during an update.
        if (run_q + 8'd1 > worst_run) worst_run <= run_q + 8'd1;
      end else run_q <= 8'd0;
    end
  end
endmodule

  audit   : 3 illegal of 7 audited, worst run=3

The three rules are the three failures the earlier sections built, checked once more at the point of decision and against an independent plain-integer oracle.

worst_run distinguishes two causes that need different responses, exactly as 15.1 section 13 did for configuration changes:

• An isolated illegal route is a flit that arrived during a table update — a race, and the update in section 9 is what fixes it.
• A run of them is a table that is simply wrong, and it will keep producing them until it is rewritten.

The run resets on a legal route and the peak is latched: three illegal, one legal, two more illegal, and the worst run stays at 3 rather than becoming 5.

15. RTL 10 — Routing Assembled

// FORWARD_UNROUTED is the build that forwards on a lookup that never
// resolved -- the only way the unrouted-forward invariant can be tripped.
module route_top #(parameter int SKIP_AUDIT = 0,
                   parameter int FORWARD_UNROUTED = 0) (
  input  logic clk, rst_n,
  input  logic       flit,
  input  logic       resolved, dest_fit, audit_legal,
  output logic       forward,
  output logic [2:0] refused_by,
  output logic       unrouted_forward_err,
  output logic [7:0] n_flits, n_forwarded, n_refused, n_unrouted
);
  assign refused_by = {~audit_legal, ~dest_fit, ~resolved};
  assign forward = flit && (resolved || (FORWARD_UNROUTED != 0)) && dest_fit
                   && (audit_legal || (SKIP_AUDIT != 0));
  assign unrouted_forward_err = forward && !resolved;
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      n_flits <= 8'd0; n_forwarded <= 8'd0;
      n_refused <= 8'd0; n_unrouted <= 8'd0;
    end else if (flit) begin
      n_flits <= n_flits + 8'd1;
      if (forward) n_forwarded <= n_forwarded + 8'd1;
      else         n_refused   <= n_refused + 8'd1;
      if (unrouted_forward_err) n_unrouted <= n_unrouted + 8'd1;
    end
  end
endmodule

  assembled: 1 of 4 forwarded, mask for audit=4 | skip-audit build forwarded 2

Four flits: one meeting every constraint, three each failing exactly one, and the mask names which. Each bit position is asserted individually — a mask with two fields transposed passes any check that only asks whether it is non-zero.

unrouted_forward_err is the invariant: nothing is forwarded on a lookup that did not resolve. It cannot fire in a correct build, and testing it needed a third parameter — FORWARD_UNROUTED — because SKIP_AUDIT only removes the audit and leaves resolved in place. A build that removes the wrong term proves nothing about the invariant.

16. Quantitative Reasoning

Three worth a sentence.

90 percent hit rate, mean 3 cycles, hit cost 2. The tenth of lookups that missed contributed half the mean. Measuring the lookup latency measures the fast path and misses the design decision entirely.

3 wrong-domain routes out of 5, and io traffic perfect. The single-table build works flawlessly for a third of the traffic, which is exactly enough to make it look correct.

6 cycles of multicast wait. For an invalidation, that is the window the stale value was still readable — and the fire-and-forget build reports the window as zero.

17. Assertions

Every property is an immediate check written as cond !== 1'b1, sampled after a settle.

18. Mutation Testing

99 mutations, one at a time, each required to make the baseline print RESULT: FAIL.

99 of 99 were killed.

The first run killed 88 and left 11 survivors:

Two findings worth carrying forward.

A counter can be observed while the output that names it is not. complete survived being hardwired to zero, because the testbench checked n_complete — which the always block increments on its own condition, not from the output. Worse, complete was only high for a delta that no cycle could sample: the acknowledgement and the completion happened on the same edge. Making it observable meant restructuring the model so the acknowledgement registers first and the completion is visible in the cycle after.

A broken build must remove the right term. unrouted_forward_err requires forward && !resolved, and SKIP_AUDIT removes the audit while leaving resolved in place — so the invariant stayed unreachable in both builds. A third parameter, FORWARD_UNROUTED, was added specifically to falsify the term the invariant is about.

A representative sample:

19. Verification Strategy

Parameterised builds, and one model needed three parameters. STALE_ENTRY, GUESS_ON_MISS, ONE_TABLE, UPDATE_LIVE, FIRE_AND_FORGET, NO_HOP_LIMIT, RESOLVE_ONLY, SKIP_AUDIT, FORWARD_UNROUTED. The last two are on the same module because they falsify different terms of the same expression, and only one of them reaches the invariant.

Independent oracles. Per-protocol routing, multicast completeness and the three audit rules are each checked against a plain-integer function that shares no structure with the design.

A reset value chosen to be visibly wrong. The table resets to port 7, which the switch does not have. A reset inside the valid range would make an answer from an uninitialised slot look like a plausible route, and bad_port_err would never fire.

Different indices during a write. Every table write happens with dest_id pointing at a different entry, so a write that lands on the read index is visible. That is a one-character mutation that a same-index stimulus cannot see.

Assert the signal, not the counter. complete was checked directly after n_complete proved insufficient — the counter has its own path through the always block and does not observe the output.

Run it twice. A second multicast to different targets, a second entry in the routing table, a second run of illegal routes after a legal one.

Boundaries in both directions. A port number exactly at the port count. A hop count exactly at the limit and exactly one under. A table filled to exactly its size. An eviction from an empty table.

Delta discipline. Every combinational sample follows a settle, and the multicast completion is sampled in the cycle after the acknowledgement registers.

20. Synthesis and Implementation Reality

The table is a memory and its size is the design. Sixteen entries here; a real switch's is orders of magnitude larger and is the dominant area term in the routing block. Section 13's hit rate is the number that decides how large it needs to be, and the miss cost is what makes a low hit rate expensive.

Three tables, not one. Section 8's ONE_TABLE saves two thirds of the memory and is wrong for two thirds of the traffic. This is the same shape of decision as 16.1's three queues — the area saving is real, the correctness cost is total, and the failure appears only on the protocols that were not tested first.

The atomic update is the part that is subtle in silicon. Section 9's live_q updating in one edge is a model; a real table update writes many entries and cannot be atomic in one cycle. What is achievable is a shadow table with an atomic pointer swap, which is the same property by a different mechanism — and the deferral window becomes the time to write the shadow rather than the time to write the live table.

The hop count travels with the flit, which means it costs header bits on every flit in the fabric to catch a fault that should never happen. That is the actual trade in section 11, and it is why the field is small: enough hops to exceed any legitimate path and no more.

Multicast acknowledgement tracking is per-outstanding-multicast state. One mask and one delivered set per in-flight operation, which bounds how many can be outstanding at once. Section 10 tracks one; a real switch tracks several and the count is a design parameter.

The divisions are firmware. Hit rate, mean cycles, eviction share and occupancy are computed by software from raw counters. What matters in hardware is that n_lookups, n_hits, total_cycles, n_entries and n_evicted exist and mean what section 13 says they mean.

21. Silicon Observability

Three to alarm on.

n_guessed non-zero at all means flits are being delivered to hosts they were not addressed to. Every delivery counter looks healthy and something at the far end is processing traffic that was never meant for it.

max_hops rising across runs is a routing table drifting toward a cycle. It is visible long before any flit actually loops, and it is the only warning there is.

worst_run greater than one on the audit means the table is wrong rather than momentarily stale. An isolated illegal route is a flit that arrived during an update; a run of them will continue until the table is rewritten.

22. Debug Lab

22.1 A host is receiving traffic addressed to another host

Symptom. A host receives transactions it did not request. No switch reports an error. Delivery counters are clean.

The reading. n_guessed on every switch in the path.

The diagnosis. A switch missed on the lookup and forwarded to a default port rather than dropping. The flit arrived somewhere, so nothing counts it as lost, and the receiving host is doing exactly the right thing with a transaction that was never for it.

Why every other counter looks healthy. It is a successful delivery by every measure a switch keeps. n_guessed is the only counter that distinguishes "delivered to the destination" from "delivered".

22.2 One protocol misroutes and the other two are fine

Symptom. CXL.mem traffic is arriving at the wrong ports. CXL.io is perfect.

The reading. n_wrong per protocol, and whether the switch has one routing table or three.

The diagnosis. Section 8. The switch resolves every protocol in one domain, and that domain happens to be the one CXL.io uses — so io traffic is flawless and provides all of the confidence.

The trap. Bring-up almost always exercises CXL.io first, because it is what enumeration and configuration use. A single-table switch passes every early test.

22.3 A brief burst of misrouted flits after a configuration change

Symptom. Immediately after the fabric manager updates a switch's routing, a small number of flits go to the wrong ports. It stops on its own.

The reading. n_torn and worst_run on the audit.

The third row does not match the symptom — it does not stop — which is exactly why the run length is worth recording. A fault that stops and a fault that looks like it stopped need different responses.

22.4 An invalidation completed and a stale value was read

Symptom. A coherency invalidation was reported complete. A host subsequently read the old value.

The reading. premature_complete_err and max_wait on the multicast.

The diagnosis. If premature_complete_err fired, the multicast was declared complete before every recipient acknowledged — the fire-and-forget failure in section 10, and the stale read happened inside a window the switch reported as zero.

If it did not fire, the multicast genuinely completed and max_wait tells you how long the window was. A stale read inside that window is expected and is a coherency-protocol question, not a routing one — Module 13's ground. The two look identical from the host and the counter separates them.

23. Design Review

1. Is the lookup a function? Same destination, same port, every time, and every port it yields is one the switch has.

2. What does the table return for an entry nobody wrote? If it returns a plausible port, an uninitialised slot is indistinguishable from a configured one.

3. On a miss, does the switch drop or guess? Guessing delivers the flit somewhere and makes every counter look healthy.

4. One routing table or three? If one, it is right for whichever protocol was tested first.

5. How is a table update made atomic, and how long is the deferral window? A shadow table with a pointer swap is the usual answer; the window is a number the fabric manager's quiesce has to accommodate.

6. For a multicast, when is it complete? Every recipient acknowledged, not "sent". For an invalidation the difference is a window in which the stale value is still readable.

7. Is there a hop count, and does it travel with the flit? No single switch can see a fabric loop.

8. Are destination existence, health and binding three separate checks? They fail for three different reasons and need three different responses.

9. What is the hit rate, and what does a miss cost? The mean is dominated by the miss path at any realistic hit rate.

10. Is every routing decision audited, and is a run of failures distinguished from an isolated one? One is a race during an update; several is a table that is wrong.

24. How This Appears In Real Engineering

The single-table switch ships. It is a large area saving, it is correct for CXL.io, and CXL.io is what bring-up exercises. The failure arrives when memory traffic starts, by which point the table structure is deep in the design.

Guess-on-miss is added as a robustness feature. Dropping flits looks like a fault; forwarding them to a management port looks like graceful degradation. It converts a visible loss into an invisible misdelivery, and it is usually added deliberately.

The atomic update is the last thing implemented. Writing the table works; writing it while traffic uses it is a separate mechanism, and the window between them is when the torn routes happen.

Multicast completion tracking is cut for area. It is per-outstanding-operation state and it looks like bookkeeping. What it actually bounds is the invalidation window, and without it that window is unmeasured rather than zero.

Hop counts are argued about because they cost header bits on every flit to catch a fault that "cannot happen". They cannot happen until a table is misconfigured, and then nothing else in the fabric can see it.

The miss cost is discovered in silicon. The lookup latency is a design number everyone knows; the miss path is a different piece of logic with a different owner, and the mean that a workload actually sees is dominated by it.

25. Common Misconceptions

"A routing table lookup either hits or misses." There is a third outcome: deferred, during a table update. A design with only two outcomes must treat a deferral as one of them, and both choices are wrong.

"An unconfigured entry returns nothing." It returns whatever is in the memory. Section 5 resets the table to a port that does not exist precisely so that reading an unconfigured entry is visibly wrong rather than plausibly right.

"Forwarding on a miss is more robust than dropping." It delivers the flit to a host that did not ask for it, and every counter reports success. A drop is a visible, attributable loss; a guess is a silent misdelivery.

"One routing table is simpler." It is right for one protocol. The other two resolve in a domain that has nothing to do with them, and the one that works provides all of the confidence.

"The table update is fast, so nobody will notice." Four lookups were deferred in a three-cycle update here. At fabric scale that is a measurable number of flits, and the alternative — answering during the update — produces routes that are neither configuration.

"Multicast is complete when it is sent." For an invalidation, complete-when-sent means the stale value was readable for the entire acknowledgement window and the switch reported that window as zero.

"A hop count is unnecessary if the tables are correct." It is unnecessary while they are correct. It is the only mechanism that can see a loop spanning several switches, none of which sees anything wrong locally.

"A route that resolves will work." It resolves to a port that may not exist, may be down, or may be bound to nothing. Three separate facts, and the lookup establishes none of them.

26. Interview Reasoning

Q1. What property must a routing lookup have? It must be a function: the same destination always yields the same port, and every port it yields is one the switch has. A table answering from an uninitialised slot satisfies neither.

Q2. Why reset a routing table to an invalid port number? So that an answer from an unconfigured entry is visibly wrong. A reset inside the valid range makes the same bug return a plausible route, and no monitor can tell the difference.

Q3. A lookup misses. What should the switch do? Drop it and count it. Forwarding to a default port delivers the flit to a host that did not request it, and every delivery counter reports success.

Q4. Why is guessing worse than dropping, given the flit arrives either way? Because something at the far end acts on it. A drop is a visible, attributable loss; a misdelivery is a transaction being processed by the wrong host with no counter naming it.

Q5. Why do the three protocols need three routing domains? They resolve different keys. A CXL.mem request is keyed by address and goes to the device owning it; a CXL.io completion is keyed by requester and goes back to the host. They are different lookups, not one lookup with a label.

Q6. A single-table switch works perfectly in bring-up. Why? Because bring-up exercises CXL.io, which is the domain the single table resolves in. A third of the traffic is flawless, and that is exactly enough to be convincing.

Q7. A routing table must be updated while traffic is flowing. What are the options? Defer lookups during the update, or answer during it. Answering produces routes that are neither the old configuration nor the new one, so deferring is the only correct choice — and the deferral window becomes a number the fabric manager must accommodate.

Q8. How is a multi-entry table update made atomic in silicon? A shadow table with an atomic pointer swap. The entries are written at leisure into a copy nothing is reading, and one write makes the whole new configuration visible.

Q9. What is a deferred lookup, and why is it not a miss? The destination may be perfectly well known; the table just cannot be read right now. Treating it as a miss drops a flit that would have routed correctly a few cycles later.

Q10. When is a multicast complete? When every target has acknowledged. Not when it was sent, and not when the first acknowledgement arrives.

Q11. Why does that matter for a coherency invalidation specifically? Because the interval between sending and the last acknowledgement is the window in which the old value is still readable. Declaring completion at send reports that window as zero.

Q12. What are the two terms in the pending calculation and why both? The target mask and the complement of what has been delivered. Without the mask, every port is pending; without the delivered set, nothing ever completes.

Q13. Your complete output was hardwired to zero and the completion counter still worked. Explain. The counter increments from its own condition inside the always block, not from the output. A check on the counter does not observe the signal that names the same event, and the mutation survived a test that looked like coverage.

Q14. What is the difference between a reflection and a fabric loop? A reflection is local — this switch's table sends the flit back the port it arrived on, catchable with one comparison. A fabric loop spans several switches, each of which sees a perfectly normal forward, and only a hop count travelling with the flit can see it.

Q15. Why is the hop count in the flit rather than in the switch? Because no switch is present for more than one hop of the loop. State that stays in a switch cannot count something that leaves it.

Q16. What does a rising max_hops mean before any flit has actually looped? A routing table is drifting toward a cycle. Flits are taking longer paths than they should, and it is visible well before one circulates indefinitely.

Q17. A route resolves. Is the flit deliverable? Not yet. The port must exist, be up, and be bound to something. Three separate facts, and the lookup establishes none of them.

Q18. Why layer the fitness checks so up and bound both require present? So a nonexistent port is reported once as missing rather than three times as missing, down and unbound. Each counter then means exactly one thing.

Q19. Hit rate 90 percent, hit cost 2 cycles, mean 3. Where did the third cycle come from? The 10 percent of lookups that missed, at 20 cycles each. The mean is dominated by the miss path at any realistic hit rate, which is why the hit rate — not the lookup latency — sizes the table.

Q20. Why measure occupancy against the table size rather than the entries in use? Against the entries in use it reads 100 percent always. The table size is the fixed quantity and it is what the metric is about.

Q21. What does a high eviction share tell you? The table is thrashing rather than filling. Entries are being installed and removed rather than accumulating, which means the working set exceeds the table.

Q22. Why distinguish an isolated illegal route from a run of them? An isolated one is a flit that arrived during a table update — a race, and the deferral window is what fixes it. A run is a table that is wrong and will keep producing them until it is rewritten.

Q23. Your invariant forward && !resolved could not fire in either build. What did you do? Added a third parameter that falsifies the term the invariant is about. SKIP_AUDIT removes the audit and leaves resolved in place, so it proves nothing — a broken build has to break the right thing.

Q24. Why does the refusal mask matter more than a boolean? Because "refused" sends an engineer to check everything. A mask naming the constraint sends them to one table, one port, or one rule.

Q25. How would you test that a table write lands on the entry it names? Drive the read index to a different entry during every write. With both indices equal, a write that lands on the read index is indistinguishable from a correct one.

Q26. A brief burst of misrouted flits follows every configuration change and then stops. Where do you look? n_torn first. Non-zero means the update was not atomic and flits were answered mid-change. Zero with worst_run of one means the flits arrived during the deferral window, which is expected and bounded.

Q27. A host receives traffic addressed elsewhere and every counter is clean. First reading? n_guessed on each switch in the path. It is the only counter that separates a delivery to the destination from a delivery.

Q28. An invalidation completed and a stale read followed. Is that a routing bug? Read premature_complete_err. If it fired, the multicast lied about completion. If it did not, the multicast was honest and the stale read happened inside the acknowledgement window — which is a coherency question, not a routing one.

Q29. Which is the more dangerous failure in this chapter, and why? Guess-on-miss. Every other failure is visible in some counter that says something went wrong. That one makes the switch report a successful delivery, and it is often added on purpose as a robustness feature.

Q30. If you could expose one counter from a switch's routing block, which? n_guessed, if the design has a guess path at all — because it is the only failure here that reports itself as success. If it has no such path, max_hops, because it is the only one that predicts rather than reports.

27. Exercises

1. Add a second valid bit to route_lut marking an entry as being written. Show that the deferral in section 9 can then be per-entry rather than table-wide, and measure what that saves.

2. Implement the shadow-table update from section 20: two tables and an atomic pointer. Show that n_deferred drops to zero and identify what replaces it.

3. Give route_miss a third policy — forward to a management port and raise an interrupt. Argue whether it is closer to dropping or to guessing, using the counters.

4. Extend proto_route so CXL.mem resolves by address range rather than by a flat key. Show which of the existing assertions still hold.

5. Make multicast track two outstanding operations at once. Find the mutation that a single-operation model cannot express.

6. Add a per-flit route trace to route_loop recording which ports it visited. Show that this catches a loop the hop count would only catch later, and price the header cost.

7. Combine dest_check with 16.1's port_isolation: a port that fails while a flit is being routed to it. Decide whether the flit is dropped or re-routed, and justify it.

8. Take the 99-mutation suite and set dest_id equal to write_dest throughout. Confirm the wrong-entry mutation returns, and find every other test in Module 16 that reads and writes the same index.

28. Summary

A routing decision is a lookup that resolves, in the flit's own domain, against a table that is not mid-change, to a port that is fit to receive.

• Resolves: eight lookups, five hits, three misses — and the stale-entry build answered a miss with port 7, which the switch does not have. The reset value was chosen to make that visible.
• Or does not: one flit dropped against three forwarded by the guessing build, one of them to a port the table never named. Every counter in that build looks healthy.
• Own domain: three wrong-domain routes of five, and the single-table build gets CXL.io perfectly right — which is a third of the traffic and all of the confidence.
• Not mid-change: four lookups deferred against four answered from a table that was neither configuration.
• Fit: three destinations refused for three separate reasons — missing, down, and unbound — against three delivered blind.

And two numbers to carry: 90 percent hit rate with a mean of 3 cycles when a hit costs 2 — the miss path dominates at any realistic hit rate — and 6 cycles of multicast wait, which for an invalidation is exactly how long the stale value stayed readable.

99 mutations, 99 killed. The one worth remembering: complete was hardwired to zero and the completion counter still counted correctly, because the counter increments from its own condition and never observes the output. If a design exposes both a level and a count of the same event, assert the level.

16.3 takes the destination as decided and asks who gets the buffer.