ADR-015: ctm — Daganzo (1994/1995) cell transmission model link

Status: accepted (implemented) Date: 2026-07-09 Deciders: DNL-models track — the first shipped DNL link model, on the adr-010 core File: docs/design/adr-015-ctm.md

Context

dnl-core (adr-010) built the generic sending/receiving foundation “five later sprints must share without rework” and named ctm (Daganzo 1994/1995) first. The Cell Transmission Model is a finite-cell Godunov discretisation of the LWR kinematic-wave PDE: the road is cut into equal cells, and the flux between adjacent cells is min(upstream sending, downstream receiving), which produces shocks, queues and spillback automatically. It is a link loading model, not an equilibrium principle — the inner map a DTA equilibrium (a later sprint) iterates.

Decision

1. CTMLink(LinkModel) in src/tabench/dnl/ctm.py, a subclass on the frozen sending/receiving/_advance_state interface — no change to link.py, loader.py, node.py, or the certifier. At the sanctioned CFL = 1 operating point the cell length is dx = vf·dt, so a link of length L is n = L/dx equal cells (a free-flow vehicle crosses exactly one cell per step). Internal state is the per-cell occupancy occ[i] (vehicles), all zero at t = 0.

2. Lebacque demand/supply flux the FD already exposes. fd.demand_at(k) = Δ and fd.supply_at(k) = Σ, so the CTM needs no new FD algebra:

   • sending(k) = last cell’s demand demand_at(k_last)·dt, capped by occ[-1];

   • receiving(k) = first cell’s supply supply_at(k_first)·dt;

   • interior Godunov flux y_i = min(demand_at(k_i), supply_at(k_{i+1}))·dt (i = 0..n-2), then the conservation update occ[:-1] -= y; occ[1:] += y; occ[0] += inflow; occ[-1] -= outflow, where inflow/outflow are the node-allocated boundary transfers. A single cell (L = vf·dt) reduces to occ[0] += inflow - outflow.

3. No turning logic (division of responsibility). A LinkModel sees only two aggregate scalars (inflow into cell 0, outflow out of the last cell); the node models allocate transfers. So the CTM link is single-corridor cell dynamics only — Daganzo (1995) Part II’s network merge/diverge extension is the node-model sprint’s (daganzo1995cell stays unshipped until then), exactly the adr-010 division.

4. Finite jam, cell alignment, and the backward-wave CFL enforced. CTM models bounded storage, so kappa = inf (point queue) raises — the unbounded point queue stays the test-only reference. A non-cell-aligned L (not an integer multiple of vf·dt) raises rather than silently loading off the certificates’ gating point. And at CFL = 1 the standard stability requirement dt <= dx/max(vf, w) reduces to w <= vf (the backward wave must be resolved per cell too); w > vf — a legal TriangularFD — would let the congested-branch flux supply_at(k)·dt = w·(kappa-k)·dt overfill a cell past kappa·dx, so it raises. This per-cell condition is invisible to the scenario-level assert_wave_resolved, which uses the whole-link length L (dt <= L/w), so the guard lives in CTMLink — a defect the adversarial review caught (66% of w > vf configs otherwise produced C3-censored, physically impossible output).

Exactness and the Tier-B backward wave

At CFL = 1 the free-flow branch is linear advection at Courant number 1 — the classical zero-numerical-diffusion case — so n_out(t) = n_in(t - L/vf) is bit-exact (anchor a). The congested branch runs at Courant number w/vf < 1 (the grid is tuned to the faster forward speed), so a backward shock spreads by O(one cell): standard CTM is provably diffusive for backward waves whenever w < vf (Daganzo’s open 1999 ISTTT restatement; Boyles TNA §10.5). This is expected scheme physics, and is exactly why the harness demotes the backward-wave envelope (C5) to a non-gating Tier-B residual — a correct CTM shows a bounded, resolution-shrinking kw_backward_residual under spillback, not a censoring bug. The gating certificates (C1 conservation, C2 capacity, C3 storage, C4 causality, C6 FIFO) all hold.

Analytic anchors (hand-derived, machine-verified — test_dnl_ctm.py)

FD vf = w = 1, kappa = 4 ⇒ capacity = vf·w·kappa/(vf+w) = 2, k_c = 2; dt = 1.

• (a) Free-flow translation: L = 4, inflow 1.0 < 2. n_out(t) = n_in(t-4) exactly, TSTT = (L/vf)·D = 4·4 = 16, zero delay.

• (b) Queue spillback: the L = 4 link feeds a 0.5 bottleneck at inflow 1.5. Rankine–Hugoniot shock speed s = (q_A-q_B)/(k_A-k_B) = (1.5-0.5)/(1.5-3.5) = -0.5, starting at x = 4, t = 4 and reaching x = 0 (full spillback) at t = 12; exact bottleneck boundary curves n_in = 1.5t, n_out = max(0, 0.5(t-4)); storage at t = 12 = k_B·L = 3.5·4 = 14.

• (c) Congested density: every fully-queued cell settles at k_B = kappa - q_B/w = 3.5, the root of supply_at(k) = q_B — the entropy state Lebacque’s supply selects by construction.

Alternatives considered

• Density (not occupancy) state: equivalent; occupancy keeps the update pure counts (no dx bookkeeping in the conservation step), matching the node models’ vehicle-count convention.

• Trapezoidal-FD rarefaction anchor: deferred — a strictly triangular FD discharges as two clean shocks, not a smooth fan, so the three anchors above already cover free-flow, shock, and steady-congested without it.

• Registering CTM in a road model registry: rejected — a LinkModel is selected as the loader’s link_factory, exercised through NetworkLoader, not the road CLI/runner (same standalone treatment the DNL core set).

Consequences

The benchmark gains its first dynamic-loading model and the template the ltm / newell-kw / godunov sprints follow (LinkModel subclasses, same interface). All changes are additive (a new module + new tests + exports), so the 552-test suite, every road/DNL hash, and the golden Braess content hash are byte-untouched.

Sourcing

Daganzo (1994) TR-B 28(4):269-287 and (1995) Part II TR-B 29(2) are paywalled, attributed unread. The min(sending, receiving) recipe, the (vf, w, kappa) triangular FD, and all three anchors were cross-verified from open sources — Boyles Transportation Network Analysis §10.5 and Daganzo’s own open ISTTT (1999) restatement of the identical base scheme — and hand-derived here from LWR / Rankine–Hugoniot theory. No DOIs or page-precise quotes are reproduced from the paywalled primaries.