nx_fabric_cc.nx source
↩ module page · 164 lines · 7856 B
1// nx_fabric_cc.nx -- R2 of the SkyHammer fabric exceed ladder: CONGESTION CONTROL +
2// TELEMETRY over RTT (closes R1's honest zero-RTT-credit caveat, ยง8).
3//
4// R1 (nx_fabric_flow) proved credit flow control is lossless+bounded with ZERO-RTT
5// feedback. Real links have RTT: window/credit signals lag by a round trip, so a
6// fixed (open-loop) window large enough to keep the link FULL builds a STANDING queue
7// = bufferbloat = high latency. SkyHammer answers this in silicon with "adaptive load
8// handling" + "real-time telemetry". The honest, grounded software expression is
9// DCTCP (RFC 8257 / the datacenter-standard ECN controller behind lossless Ethernet +
10// RoCE -- cited in knowledge/fetched/fab_ecn.raw, fab_roce.raw): the bottleneck MARKS
11// packets once its queue crosses K (the telemetry), the sender measures the marked
12// FRACTION each RTT and reduces its window PROPORTIONALLY (alpha EWMA), holding the
13// queue near the low setpoint K at full utilisation.
14//
15// This rung MEASURES that exceed vs an open-loop window over the SAME RTT link.
16// Integer-only fixed-point (no float, ecosystem law). The link/queue model is the
17// same discrete-event shape as nx_fabric_flow (R1), extended with an RTT ack delay
18// line + ECN marking + the adaptive window. expect_exit: 0 license_tier: ORIGINAL
19import "nx_syscalls.nx"
20const CC_MAGIC_4000: i64 = 4000
21
22const CC_DCTCP: i64 = 0 // R2: ECN-telemetry adaptive window
23const CC_OPEN: i64 = 1 // baseline: fixed (open-loop) window -> bufferbloat
24const CC_NC1: i64 = 2 // NC1: DCTCP machinery but IGNORE marks (reaction disabled) -> bloat
25const CC_SCALE: i64 = 1024 // fixed-point scale for the marked-fraction / alpha
26
27struct CcMetrics {
28 util_x1000: i64, // delivered / (D*ticks) * 1000 (link fullness)
29 q_p50: i64, // median bottleneck-queue depth across ticks
30 q_p99: i64, // p99 queue depth (the latency tail)
31 drops: i64, // buffer overflow (kept ~0 here: latency story, not loss)
32 tele_max_err: i64, // max |reported queue - independently recounted queue|
33 delivered: i64,
34 ticks: i64,
35}
36
37// One discrete-event run. N frames, link drain D/tick, round-trip RTT ticks, bottleneck
38// buffer cap BUFCAP, ECN mark threshold K, baseline open-loop window base_cwnd. Fills *m.
39func cc_run(mode: i64, N: i64, D: i64, RTT: i64, BUFCAP: i64, K: i64, base_cwnd: i64, m: *CcMetrics) -> i64 {
40 let MAXT: i64 = CC_MAGIC_4000
41 let RS: i64 = BUFCAP + 1 // ring size
42 let qmark: *i64 = sys_mmap(RS * 8) as *i64 // per-queued-frame ECN mark bit
43 var qhead: i64 = 0
44 var qtail: i64 = 0
45 var qocc: i64 = 0
46 let ackc: *i64 = sys_mmap(MAXT * 8) as *i64 // acks arriving at tick t: frame count
47 let ackm: *i64 = sys_mmap(MAXT * 8) as *i64 // ...and how many were ECN-marked
48 let qhist: *i64 = sys_mmap((BUFCAP + 2) * 8) as *i64 // queue-depth histogram (mmap zero-fills)
49
50 let WARMUP: i64 = RTT * 12 // skip the convergence transient; measure STEADY STATE
51 var cwnd: i64 = base_cwnd // ALL modes start at the SAME (large) window: DCTCP must
52 // DRIVE the bloated queue down to K; NC1/NC2 cannot
53 var in_flight: i64 = 0
54 var alpha: i64 = 0 // DCTCP alpha (fixed-point /CC_SCALE)
55 var acc_total: i64 = 0
56 var acc_marked: i64 = 0
57 var rtt_timer: i64 = 0
58 var next_new: i64 = 0
59 var delivered: i64 = 0
60 var drops: i64 = 0
61 var tele_err: i64 = 0
62 var tick: i64 = 0
63 var d_sw: i64 = 0 // steady-state delivered (post-warmup)
64 var samples: i64 = 0 // steady-state tick samples
65
66 while delivered < N {
67 if tick >= MAXT { break }
68
69 // 1. ACKs scheduled for now (frames delivered RTT ticks ago) clear in-flight.
70 let a: i64 = ackc[tick]
71 in_flight = in_flight - a
72 acc_total = acc_total + a
73 acc_marked = acc_marked + ackm[tick]
74
75 // 2. DRAIN up to D; each delivered frame schedules its ack at tick+RTT carrying its mark.
76 var dd: i64 = 0
77 while dd < D {
78 if qocc == 0 { break }
79 let mk: i64 = qmark[qhead]
80 qhead = qhead + 1; if qhead >= RS { qhead = 0 }
81 qocc = qocc - 1
82 delivered = delivered + 1
83 if tick >= WARMUP { d_sw = d_sw + 1 }
84 let at: i64 = tick + RTT
85 if at < MAXT { ackc[at] = ackc[at] + 1; ackm[at] = ackm[at] + mk }
86 dd = dd + 1
87 }
88
89 // 3. TELEMETRY: report queue occupancy; independently recount it from head/tail
90 // (NC3 liar-kill -- a fabricated telemetry value would diverge from the recount).
91 var recount: i64 = qtail - qhead
92 if recount < 0 { recount = recount + RS }
93 var terr: i64 = qocc - recount
94 if terr < 0 { terr = 0 - terr }
95 if terr > tele_err { tele_err = terr }
96 if tick >= WARMUP {
97 samples = samples + 1
98 if qocc <= BUFCAP { qhist[qocc] = qhist[qocc] + 1 } else { qhist[BUFCAP] = qhist[BUFCAP] + 1 }
99 }
100
101 // 4. PER-RTT controller update (DCTCP). CC_OPEN never adapts.
102 rtt_timer = rtt_timer + 1
103 if rtt_timer >= RTT {
104 if mode == CC_DCTCP {
105 if acc_total > 0 {
106 let frac: i64 = (acc_marked * CC_SCALE) / acc_total // marked fraction
107 alpha = alpha + (frac - alpha) / 16 // EWMA g=1/16
108 }
109 cwnd = cwnd + 1 // AIMD additive increase EVERY RTT (real DCTCP)
110 if acc_marked > 0 { cwnd = cwnd - (cwnd * alpha) / (2 * CC_SCALE) } // proportional cut on congestion
111 if cwnd < 1 { cwnd = 1 }
112 }
113 if mode == CC_NC1 { cwnd = cwnd + 1 } // marks IGNORED -> only grows -> bloat
114 acc_total = 0; acc_marked = 0; rtt_timer = 0
115 }
116
117 // 5. SEND: the WINDOW (cwnd) governs injection -- a window larger than the BDP
118 // parks the excess in the bottleneck queue (that IS bufferbloat). Lightly
119 // paced to <= 2*D/tick so the queue builds over ticks, not as a tick-0 spike.
120 var ss: i64 = 0
121 while ss < 2 * D {
122 if in_flight >= cwnd { break }
123 if next_new >= N { break }
124 if qocc < BUFCAP {
125 var mk2: i64 = 0
126 if qocc >= K { mk2 = 1 } // ECN mark at enqueue when queue >= K
127 qmark[qtail] = mk2; qtail = qtail + 1; if qtail >= RS { qtail = 0 }; qocc = qocc + 1
128 in_flight = in_flight + 1; next_new = next_new + 1
129 } else {
130 drops = drops + 1; next_new = next_new + 1
131 }
132 ss = ss + 1
133 }
134 tick = tick + 1
135 }
136
137 // queue-depth percentiles across the `tick` samples
138 let t50: i64 = (samples * 50) / 100
139 let t99: i64 = (samples * 99) / 100
140 var cum: i64 = 0
141 var p50: i64 = 0
142 var p99: i64 = 0
143 var g50: i64 = 0
144 var g99: i64 = 0
145 var hh: i64 = 0
146 while hh <= BUFCAP {
147 cum = cum + qhist[hh]
148 if g50 == 0 { if cum > t50 { p50 = hh; g50 = 1 } }
149 if g99 == 0 { if cum > t99 { p99 = hh; g99 = 1 } }
150 if g99 == 1 { break }
151 hh = hh + 1
152 }
153
154 m.q_p50 = p50
155 m.q_p99 = p99
156 m.drops = drops
157 m.tele_max_err = tele_err
158 m.delivered = delivered
159 m.ticks = tick
160 if samples > 0 { m.util_x1000 = (d_sw * 1000) / (D * samples) } else { m.util_x1000 = 0 }
161 return 0
162}
163
164func main() -> i64 { return 0 }