diff options
Diffstat (limited to 'src/ipcpd/unicast/ca/tests')
| -rw-r--r-- | src/ipcpd/unicast/ca/tests/CMakeLists.txt | 34 | ||||
| -rw-r--r-- | src/ipcpd/unicast/ca/tests/mb_ecn_lab_test.c | 1294 | ||||
| -rw-r--r-- | src/ipcpd/unicast/ca/tests/mb_ecn_test.c | 723 |
3 files changed, 1806 insertions, 245 deletions
diff --git a/src/ipcpd/unicast/ca/tests/CMakeLists.txt b/src/ipcpd/unicast/ca/tests/CMakeLists.txt index 6e42163d..20e2349d 100644 --- a/src/ipcpd/unicast/ca/tests/CMakeLists.txt +++ b/src/ipcpd/unicast/ca/tests/CMakeLists.txt @@ -42,3 +42,37 @@ target_link_libraries(${PARENT_DIR}_test PRIVATE ouroboros-common) add_dependencies(build_tests ${PARENT_DIR}_test) ouroboros_register_tests(TARGET ${PARENT_DIR}_test TESTS ${${PARENT_DIR}_tests}) + +# The lab includes mb-ecn.c for its statics, so it needs its own binary +create_test_sourcelist(${PARENT_DIR}_lab_tests test_lab_suite.c + mb_ecn_lab_test.c + ) + +add_executable(${PARENT_DIR}_lab_test ${${PARENT_DIR}_lab_tests} + ${UNICAST_SOURCE_DIR}/cap.c + ) + +target_include_directories(${PARENT_DIR}_lab_test PRIVATE + ${CMAKE_CURRENT_SOURCE_DIR} + ${CMAKE_CURRENT_BINARY_DIR} + ${CURRENT_SOURCE_PARENT_DIR} + ${CURRENT_BINARY_PARENT_DIR} + ${UNICAST_SOURCE_DIR} + ${UNICAST_BINARY_DIR} + ${CMAKE_SOURCE_DIR}/include + ${CMAKE_BINARY_DIR}/include + ${CMAKE_SOURCE_DIR}/src/ipcpd + ${CMAKE_BINARY_DIR}/src/ipcpd +) + +disable_test_logging_for_target(${PARENT_DIR}_lab_test) +target_link_libraries(${PARENT_DIR}_lab_test PRIVATE ouroboros-common) + +if(MB_ECN_LAB_FULL) + target_compile_definitions(${PARENT_DIR}_lab_test PRIVATE MB_ECN_LAB_FULL) +endif() + +add_dependencies(build_tests ${PARENT_DIR}_lab_test) + +ouroboros_register_tests(TARGET ${PARENT_DIR}_lab_test + TESTS ${${PARENT_DIR}_lab_tests}) diff --git a/src/ipcpd/unicast/ca/tests/mb_ecn_lab_test.c b/src/ipcpd/unicast/ca/tests/mb_ecn_lab_test.c new file mode 100644 index 00000000..dac5e8ac --- /dev/null +++ b/src/ipcpd/unicast/ca/tests/mb_ecn_lab_test.c @@ -0,0 +1,1294 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2026 + * + * Shared-bottleneck lab for multi-bit ECN congestion avoidance + * + * Dimitri Staessens <dimitri@ouroboros.rocks> + * Sander Vrijders <sander@ouroboros.rocks> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 as + * published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., http://www.fsf.org/about/contact/. + */ + +#include "mb-ecn.c" +#include <test/test.h> + +#define MS (MILLION) /* one millisecond in ns */ +#define LEN 1000 /* default packet size (bytes) */ + +/* Create a context with the clock zeroed for deterministic time steps. */ +static struct mb_ecn_ctx * mk_ctx(void) +{ + struct mb_ecn_ctx * ctx; + + ctx = mb_ecn_ctx_create(); + if (ctx == NULL) + return NULL; + + ctx->rx_ts = 0; + ctx->rx_win = 0; + ctx->last_ts = 0; + ctx->last_ctrl = 0; + ctx->last_fb = 0; + ctx->last_sig = 0; + ctx->last_loc = 0; + ctx->last_cap = 0; + + ctx->snd_byt = 0; + ctx->snd_win = 0; + ctx->snd_r0 = CA_RATE_INIT; + ctx->snd_rate = CA_RATE_INIT; + ctx->backlogged = true; + ctx->src_limited = false; + ctx->started = false; + ctx->ss_tc = 20 * MS; /* fixed slope for deterministic SS */ + + return ctx; +} + +/* + * ------------------------------------------------------------------ + * Lab: packet-level shared-bottleneck simulator. + * + * Exact-time FIFO link of capacity cap: a packet departs at + * max(enqueue, previous departure) + len / cap. Packets are marked + * at enqueue from the instantaneous byte queue by mb_ecn_calc_ecn, + * the same function the forwarding path calls. Delivered packets + * drive a per-flow receiver estimator (mb_ecn_rcv); every window + * close is fed back to the sender as ece after a one-way lag, + * including the ece 0 release (fa.c). The sender sees its own + * previous packet's mark as the local fallback (fa.c l_ecn) and + * heartbeat pongs keep liveness. Greedy flows send whenever the + * pacer allows; CBR flows follow an absolute schedule. A tick every + * LAB_SAMPLE drains the link between sends, so feedback queued by a + * departure is due on time even while every flow sits idle. With + * cfg.shared every flow runs on one ctx, as a production build does, + * and the flow count follows t0, t1 and the churn period. + * + * The fixpoint tests assert; the sweep always returns success: an + * instrument, not a regression test. + * ------------------------------------------------------------------ + */ + +#define LAB_MAXF 8 /* most flows on one link */ +#define LAB_FIFO 16384 /* bottleneck ring, packets */ +#define LAB_FBQ 64 /* pending feedback ring */ +#define LAB_NONE UINT64_MAX /* no pending event */ +#define LAB_SAMPLE (5 * MS) /* service tick */ + +struct lab_pkt { + uint64_t dep; /* departure time (ns) */ + uint8_t ecn; + uint8_t f; /* flow index */ +}; + +struct lab_fb { + uint64_t t; + uint16_t ece; + uint8_t fcap; +}; + +struct lab_flow { + struct mb_ecn_ctx * snd; + struct mb_ecn_ctx * rcv; + uint64_t t_snd; /* next send attempt (ns) */ + uint64_t last; /* ctx clock high-water (ns) */ + uint64_t ftag; + uint64_t ia; /* app interval, 0 = greedy */ + uint64_t app; /* next app slot (ns) */ + uint64_t lag; /* feedback one-way lag (ns) */ + uint8_t lecn; /* own previous packet's mark */ + struct lab_fb fbq[LAB_FBQ]; + size_t fb_h; + size_t fb_n; + uint64_t hb_t; /* pong due, LAB_NONE = none */ + uint64_t hb_rtt; + /* metrics, accumulated past warmup */ + uint64_t m_t; /* last accounting time */ + uint64_t dlv; /* delivered bytes */ + uint64_t dlv2; /* delivered in score window */ + uint64_t r_int; /* integral of rate dt */ + uint64_t r_lo; + uint64_t r_hi; + uint64_t lead_B; /* lead-term cut volume */ + uint64_t prop_B; /* proportional cut volume */ + uint64_t cuts; /* >45% single-event cuts */ + uint64_t hold_ns; /* time with ai_hold set */ + uint64_t lim_ns; /* time src_limited (latch) */ + uint64_t idl_ns; /* time the backlog test off */ +}; + +struct lab_link { + uint64_t cap; /* bytes/s */ + uint8_t cc; /* stamped capacity code */ + uint64_t t_srv; /* line busy until (ns) */ + uint64_t q; /* queued bytes */ + uint64_t qmax; /* blocking threshold (bytes) */ + struct lab_pkt pk[LAB_FIFO]; + size_t h; + size_t n; + /* metrics */ + uint64_t q_t; /* last q-change time */ + uint64_t q_int; /* integral of q dt */ + uint64_t mk_int; /* integral of ece(q) dt */ + uint64_t e_from; /* empty-dwell start */ + uint64_t e_ns; /* empty time past warmup */ + size_t e_eps; /* empty episodes past warmup */ + uint64_t dlv; /* delivered bytes */ +}; + +struct lab_cfg { + const char * name; + uint64_t cap; /* bytes/s */ + uint64_t dur; /* run length (ns) */ + uint64_t wu; /* warmup excluded (ns) */ + size_t len; /* packet size (bytes) */ + uint64_t qmax; /* bytes */ + size_t n; /* flows, up to LAB_MAXF */ + uint64_t ia[LAB_MAXF]; /* app interval, 0 = greedy */ + uint64_t lag[LAB_MAXF]; /* one-way feedback lag (ns) */ + bool no_loc; /* disable local-mark path */ + uint64_t st_d; /* service stall length (ns) */ + uint64_t st_p; /* stall period, 0 = never */ + unsigned st_f; /* stalled-flow mask, 0 = all */ + uint64_t t0[LAB_MAXF]; /* flow start offsets (ns) */ + uint64_t t1[LAB_MAXF]; /* flow stop, 0 = runs to end */ + uint64_t r0[LAB_MAXF]; /* seed rate, 0 = slow start */ + uint64_t sc_lo; /* score window (ns), as the */ + uint64_t sc_hi; /* integration test scores */ + bool shared; /* one ctx for every flow */ + uint64_t ch_p; /* churn period, 0 = never */ + unsigned ch_f; /* churning flow mask */ +}; + +static struct lab_link lab_lnk; +static struct lab_flow lab_fl[LAB_MAXF]; +static uint64_t lab_sc_lo; +static uint64_t lab_sc_hi; +static size_t lab_len; + +/* + * Does flow i hold the ctx at t? A churning flow holds it for the + * first half of every ch_p and is gone for the second. + */ +static bool lab_up(const struct lab_cfg * c, + size_t i, + uint64_t t) +{ + if (t < c->t0[i]) + return false; + + if (c->t1[i] > 0 && t >= c->t1[i]) + return false; + + if (c->ch_p == 0 || ((c->ch_f >> i) & 1) == 0) + return true; + + return t % c->ch_p < c->ch_p / 2; +} + +/* Flows holding the ctx at t, the count ca_ctx_get refcounts. */ +static size_t lab_live(const struct lab_cfg * c, + uint64_t t) +{ + size_t n = 0; + size_t i; + + for (i = 0; i < c->n; i++) + if (lab_up(c, i, t)) + n++; + + return n > 0 ? n : 1; +} + +/* The bottleneck marks with the production function, nothing else. */ +static uint8_t lab_mark(uint64_t q) +{ + uint8_t e = 0; + + if (q == 0) + return 0; + + mb_ecn_calc_ecn(q, &e, QOS_CUBE_BE, lab_len); + + return e; +} + +/* Track the queue integral, the mark integral and empty dwells. */ +static void lab_q_acct(struct lab_link * l, + uint64_t now, + uint64_t wu) +{ + uint64_t dt = now - l->q_t; + + if (l->q_t >= wu && dt > 0) { + l->q_int += l->q * dt; + l->mk_int += (uint64_t) lab_mark(l->q) * 32 * dt; + } + + if (l->q == 0) { + if (l->e_from == LAB_NONE) + l->e_from = l->q_t; + } else if (l->e_from != LAB_NONE) { + if (now >= wu) { + uint64_t f = l->e_from > wu ? l->e_from : wu; + l->e_ns += l->q_t > f ? l->q_t - f : 0; + l->e_eps++; + } + l->e_from = LAB_NONE; + } + + l->q_t = now; +} + +/* Deliver everything due; receiver estimator feeds the fb ring. */ +static void lab_service(struct lab_link * l, + uint64_t now, + uint64_t wu) +{ + uint16_t ece; + uint8_t fcap; + + while (l->n > 0 && l->pk[l->h].dep <= now) { + struct lab_pkt * p = &l->pk[l->h]; + struct lab_flow * f = &lab_fl[p->f]; + + lab_q_acct(l, p->dep, wu); + l->q -= lab_len; + + if (p->dep >= wu) { + l->dlv += lab_len; + f->dlv += lab_len; + } + + if (p->dep >= lab_sc_lo && p->dep < lab_sc_hi) + f->dlv2 += lab_len; + + if (mb_ecn_rcv(f->rcv, lab_len, p->ecn, l->cc, &ece, &fcap, + p->dep) && + f->fb_n < LAB_FBQ) { + size_t i = (f->fb_h + f->fb_n++) % LAB_FBQ; + f->fbq[i].t = p->dep + f->lag; + f->fbq[i].ece = ece; + f->fbq[i].fcap = fcap; + } + + l->h = (l->h + 1) % LAB_FIFO; + l->n--; + } +} + +/* Integrate rate, regime dwell and extrema between a flow's events. */ +static void lab_f_acct(struct lab_flow * f, + uint64_t now, + uint64_t wu) +{ + struct mb_ecn_ctx * c = f->snd; + uint64_t dt; + uint16_t m; + + if (now < f->m_t) + now = f->m_t; + + dt = now - f->m_t; + if (f->m_t >= wu && dt > 0) { + f->r_int += c->rate * dt; + + if (c->ai_hold) + f->hold_ns += dt; + + if (c->src_limited) + f->lim_ns += dt; + + if (!c->backlogged) + f->idl_ns += dt; + + m = c->tx_ece > 0 ? c->tx_ece + : (uint16_t) (c->tx_loc << CA_SHFT); + + if (m > CA_ECE_MAX) + m = CA_ECE_MAX; + f->prop_B += c->rate / CA_ECE_REF * m * dt / BILLION; + + if (c->rate < f->r_lo) + f->r_lo = c->rate; + + if (c->rate > f->r_hi) + f->r_hi = c->rate; + } + + f->m_t = now; +} + +/* One send attempt; returns false when blocked on a full buffer. */ +static bool lab_send(struct lab_link * l, + struct lab_flow * f, + size_t fi, + size_t nf, + uint64_t wu, + bool no_loc) +{ + uint64_t t = f->t_snd; + uint64_t r0; + uint64_t dep; + uint8_t ecn; + time_t w; + + lab_service(l, t, wu); + + if (l->q + lab_len > l->qmax) { /* blocking write */ + f->t_snd = l->pk[l->h].dep; + return false; + } + + lab_f_acct(f, t, wu); + + ecn = lab_mark(l->q); + + r0 = f->snd->rate; + + mb_ecn_flows(f->snd, nf, t); + + if (!no_loc) + mb_ecn_loc(f->snd, f->lecn, t); + + w = mb_ecn_snd(f->snd, lab_len, t, &f->ftag); + + if (f->snd->rate * 100 < r0 * 55) + f->cuts++; + + f->lecn = ecn; + f->last = t; + + lab_q_acct(l, t, wu); + + dep = (t > l->t_srv ? t : l->t_srv) + lab_len * BILLION / l->cap; + l->t_srv = dep; + l->pk[(l->h + l->n) % LAB_FIFO].dep = dep; + l->pk[(l->h + l->n) % LAB_FIFO].ecn = ecn; + l->pk[(l->h + l->n) % LAB_FIFO].f = (uint8_t) fi; + l->n++; + l->q += lab_len; + + if (mb_ecn_ctx_hb_due(f->snd, t) && f->hb_t == LAB_NONE) { + f->hb_rtt = l->q * BILLION / l->cap + 2 * f->lag; + f->hb_t = t + f->hb_rtt; + } + + if (f->ia == 0) { + f->t_snd = t + (w > 0 ? (uint64_t) w : 1); + } else { + f->app += f->ia; + f->t_snd = f->app > t + (uint64_t) w ? f->app + : t + (uint64_t) w; + } + + return true; +} + +/* Apply one queued feedback to the sender, with lead accounting. */ +static void lab_fb_apply(struct lab_flow * f, + uint64_t wu) +{ + struct lab_fb * fb = &f->fbq[f->fb_h]; + uint64_t t = fb->t > f->last ? fb->t : f->last; + uint64_t r0 = f->snd->rate; + uint16_t step; + bool up; + + lab_f_acct(f, t, wu); + + if (t >= wu) { + up = fb->ece > f->snd->tx_ecp; + step = up ? fb->ece - f->snd->tx_ecp + : f->snd->tx_ecp - fb->ece; + + if (step > CA_ECE_REF) + step = CA_ECE_REF; + + if (up) + f->lead_B += r0 * step + / (CA_ECE_REF * CA_MD_KD_DIV); + } + + mb_ecn_ece(f->snd, fb->ece, fb->fcap, t); + + if (f->snd->rate * 100 < r0 * 55) + f->cuts++; + + f->last = t; + f->fb_h = (f->fb_h + 1) % LAB_FBQ; + f->fb_n--; +} + +static void lab_run(const struct lab_cfg * c) +{ + struct lab_link * l = &lab_lnk; + uint64_t smp = 0; + uint64_t st_t; + uint64_t span; + double secs; + size_t i; + + memset(l, 0, sizeof(*l)); + + l->cap = c->cap; + l->cc = cap_enc(c->cap); + l->qmax = c->qmax; + l->e_from = LAB_NONE; + + memset(lab_fl, 0, sizeof(lab_fl)); + + for (i = 0; i < c->n; i++) { + struct lab_flow * f = &lab_fl[i]; + + /* Production interns one ctx per (peer, qos cube). */ + if (c->shared && i > 0) { + f->snd = lab_fl[0].snd; + f->rcv = lab_fl[0].rcv; + } else { + f->snd = mk_ctx(); + f->rcv = mk_ctx(); + } + + if (f->snd == NULL || f->rcv == NULL) { + printf("lab: no memory.\n"); + goto fail_ctx; + } + + f->ia = c->ia[i]; + f->lag = c->lag[i]; + f->hb_t = LAB_NONE; + f->r_lo = UINT64_MAX; + f->t_snd = c->t0[i]; + f->app = c->t0[i]; + f->m_t = c->t0[i]; + /* Layer-declared RTT seed; pongs then track truth. */ + f->snd->ss_tc = 2 * CA_SS_RTT_DEF * MILLION; + + /* Seeded: start in AIMD, so the sweep probes the + attractor and not the ramp. */ + if (c->r0[i] == 0) + continue; + + f->snd->rate = c->r0[i]; + f->snd->inv_rate = mb_ecn_rate_inv(c->r0[i]); + f->snd->snd_r0 = c->r0[i]; + f->snd->snd_rate = c->r0[i]; + f->snd->tx_cav = true; + } + + lab_len = c->len; + lab_sc_lo = c->sc_lo; + lab_sc_hi = c->sc_hi; + + st_t = c->st_p > 0 ? c->st_p : LAB_NONE; + + while (true) { + uint64_t nxt = LAB_NONE; + int ev = -1; /* flow * 4 + kind */ + + /* + * Sender-side service stall: the scheduler feeding + * the transmit queue pauses for st_d, the queue + * drains clean, and the resume bursts the backlog + * through the marker (dsched untrack/starve model). + * Jitter the period so it cannot phase-lock. + */ + if (st_t != LAB_NONE && smp >= st_t) { + uint64_t end = st_t + c->st_d; + unsigned msk = c->st_f == 0 ? 3 : c->st_f; + + for (i = 0; i < c->n; i++) + if (((msk >> i) & 1) && lab_fl[i].t_snd < end) + lab_fl[i].t_snd = end; + st_t += c->st_p + (st_t / c->st_p % 3) * c->st_p / 5; + } + + for (i = 0; i < c->n; i++) { + struct lab_flow * f = &lab_fl[i]; + + if (c->t1[i] > 0 && f->t_snd >= c->t1[i]) { + f->t_snd = LAB_NONE; + } else if (c->ch_p > 0 && !lab_up(c, i, f->t_snd)) { + /* Gone: the app resumes next period. */ + f->t_snd = (f->t_snd / c->ch_p + 1) * c->ch_p; + f->app = f->t_snd; + } + + if (f->t_snd < nxt) { + nxt = f->t_snd; + ev = (int) i * 4; + } + if (f->fb_n > 0 && f->fbq[f->fb_h].t < nxt) { + nxt = f->fbq[f->fb_h].t; + ev = (int) i * 4 + 1; + } + if (f->hb_t < nxt) { + nxt = f->hb_t; + ev = (int) i * 4 + 2; + } + } + + if (smp < nxt) { + nxt = smp; + ev = -2; + } + + if (nxt >= c->dur) + break; + + if (ev == -2) { + lab_service(l, smp, c->wu); + smp += LAB_SAMPLE; + continue; + } + + i = (size_t) (ev / 4); + switch (ev % 4) { + case 0: + (void) lab_send(l, &lab_fl[i], i, + c->shared ? lab_live(c, nxt) : 1, + c->wu, c->no_loc); + break; + case 1: + lab_fb_apply(&lab_fl[i], c->wu); + break; + default: + lab_f_acct(&lab_fl[i], lab_fl[i].hb_t, c->wu); + if (lab_fl[i].hb_t > lab_fl[i].last) + lab_fl[i].last = lab_fl[i].hb_t; + mb_ecn_ctx_rtt(lab_fl[i].snd, lab_fl[i].last, + lab_fl[i].hb_rtt); + lab_fl[i].hb_t = LAB_NONE; + break; + } + } + + lab_service(l, c->dur, c->wu); + lab_q_acct(l, c->dur, c->wu); + + span = c->dur - c->wu; + secs = (double) span / BILLION; + + printf("%-14s C %5.2f MB/s n %zu | util %5.1f%% " + "q %6.1f pkt mk %5.1f e%% %4.1f eps %3zu\n", + c->name, (double) c->cap / MILLION, c->n, + 100.0 * (double) l->dlv / ((double) c->cap * secs), + (double) l->q_int / ((double) span * c->len), + (double) l->mk_int / (double) span, + 100.0 * (double) l->e_ns / (double) span, + l->e_eps); + + for (i = 0; i < c->n; i++) { + struct lab_flow * f = &lab_fl[i]; + struct mb_ecn_ctx * s = f->snd; + + lab_f_acct(f, c->dur, c->wu); + + if (c->sc_hi > c->sc_lo) + printf(" f%zu score %.3f Mb/s in [%llu,%llu)s\n", + i, 8.0 * (double) f->dlv2 / + ((double) (c->sc_hi - c->sc_lo) / BILLION + * MILLION), + (unsigned long long) (c->sc_lo / BILLION), + (unsigned long long) (c->sc_hi / BILLION)); + printf(" f%zu %s dlv %5.3f Mb/s rate mean %8.0f " + "lo %8" PRIu64 " hi %8" PRIu64 "\n" + " lead %8" PRIu64 " prop %8" PRIu64 + " cuts %4" PRIu64 " hold %4.1f%% lim %4.1f%%" + " idl %4.1f%% loss %" PRIu64 "\n", + i, f->ia == 0 ? "gdy" : "cbr", + 8.0 * (double) f->dlv / ((double) secs * MILLION), + (double) f->r_int / (double) span, + f->r_lo == UINT64_MAX ? 0 : f->r_lo, f->r_hi, + f->lead_B, f->prop_B, f->cuts, + 100.0 * (double) f->hold_ns / (double) span, + 100.0 * (double) f->lim_ns / (double) span, + 100.0 * (double) f->idl_ns / (double) span, + s->n_loss); + + if (c->shared && i > 0) + continue; + + mb_ecn_ctx_destroy(f->snd); + mb_ecn_ctx_destroy(f->rcv); + } + + return; + fail_ctx: + for (i = 0; i < c->n; i++) { + if (c->shared && i > 0) + break; + + mb_ecn_ctx_destroy(lab_fl[i].snd); + mb_ecn_ctx_destroy(lab_fl[i].rcv); + } +} + +/* + * Faithful test_cbr_protection / test_single_flow_slow_link protocol: + * 3-node chain, bottleneck one hop past the sender (no local mark), + * ~2 ms feedback path, CBR from t = 0, greedy joining at 300 ms, + * scored over the integration test's own window (slow start and + * convergence included, as the real assertion sees them). + */ +static void lab_cfg_std(struct lab_cfg * c, + const char * name, + uint64_t cap, + size_t n) +{ + size_t i; + + memset(c, 0, sizeof(*c)); + + c->name = name; + c->cap = cap; + c->n = n; + c->len = LEN; + /* 1024 = SSM_RBUFF_SIZE (cmake/config/lib/ssm.cmake). */ + c->qmax = 1024 * c->len; + c->no_loc = true; + + for (i = 0; i < n; i++) + c->lag[i] = 2 * MS; + + if (n == 2) { /* cbr_protection */ + c->ia[1] = c->len * BILLION / 375000; + c->t0[0] = 300 * MS; + c->dur = 35ULL * BILLION; + c->wu = 30ULL * BILLION; + c->sc_lo = 5ULL * BILLION; + c->sc_hi = 30ULL * BILLION; + } else { /* single_flow_slow_link */ + c->dur = 95ULL * BILLION; + c->wu = 55ULL * BILLION; + c->sc_lo = 20ULL * BILLION; + c->sc_hi = 50ULL * BILLION; + } +} + +/* Spread the seeds may end on and still count as one attractor. */ +#define LAB_FIX_TOL 0.10 + +/* + * Two flows on one bottleneck reach the same split whatever they start + * from: the difference mode contracts, so the seed cannot survive in + * the answer. A second attractor shows as seeds that disagree, a bias + * as agreement away from 1. + */ +static int test_mb_ecn_lab_fixpoint(uint64_t cap, + uint64_t lag) +{ + static struct lab_cfg c; + static const unsigned num[] = { 1, 1, 4 }; + static const unsigned den[] = { 4, 1, 1 }; + uint64_t kb = cap * 8 / 1000; + uint64_t ms = lag / MS; + double r[3]; + double lo; + double hi; + size_t i; + + TEST_START("(%" PRIu64 " kb/s, lag %" PRIu64 " ms)", kb, ms); + + for (i = 0; i < 3; i++) { + lab_cfg_std(&c, "fixpoint", cap, 2); + + /* 10 Gb/s carries 9000 B frames; below 1 Gb/s, 1000 B. */ + c.len = cap >= 125000000 ? 9000 : LEN; + c.qmax = 1024 * c.len; + + c.ia[1] = 0; /* both greedy */ + c.t0[0] = 0; + c.lag[0] = lag; + c.lag[1] = lag; + c.dur = 60ULL * BILLION; + c.wu = 30ULL * BILLION; + c.sc_lo = 30ULL * BILLION; + c.sc_hi = 60ULL * BILLION; + c.r0[0] = cap * num[i] / (num[i] + den[i]); + c.r0[1] = cap * den[i] / (num[i] + den[i]); + + lab_run(&c); + + if (lab_fl[1].dlv2 == 0) { + printf("seed %u:%u starved a flow.\n", num[i], den[i]); + goto fail; + } + + r[i] = (double) lab_fl[0].dlv2 / (double) lab_fl[1].dlv2; + } + + lo = hi = r[0]; + + for (i = 1; i < 3; i++) { + if (r[i] < lo) + lo = r[i]; + + if (r[i] > hi) + hi = r[i]; + } + + if (hi > lo * (1.0 + LAB_FIX_TOL)) { + printf("seeds disagree: %.3f %.3f %.3f.\n", r[0], r[1], r[2]); + goto fail; + } + + if (lo < 1.0 - LAB_FIX_TOL || hi > 1.0 + LAB_FIX_TOL) { + printf("split %.3f..%.3f is not fair.\n", lo, hi); + goto fail; + } + + TEST_SUCCESS("(%" PRIu64 " kb/s, lag %" PRIu64 " ms)", kb, ms); + + return TEST_RC_SUCCESS; + fail: + TEST_FAIL("(%" PRIu64 " kb/s, lag %" PRIu64 " ms)", kb, ms); + return TEST_RC_FAIL; +} + +static int test_mb_ecn_lab_fixpoint_all(void) +{ +#ifdef MB_ECN_LAB_FULL + static const uint64_t cap[] = { 1250000000, 12500000, + 1250000, 62500 }; +#else + static const uint64_t cap[] = { 1250000, 62500 }; +#endif + static const uint64_t lag[] = { 2 * MS, 42 * MS }; + int ret = 0; + size_t i; + size_t j; + + for (i = 0; i < sizeof(cap) / sizeof(cap[0]); i++) + for (j = 0; j < sizeof(lag) / sizeof(lag[0]); j++) + ret |= test_mb_ecn_lab_fixpoint(cap[i], lag[j]); + + return ret; +} + +/* Seed weights: even, graded, and graded reversed. */ +static const unsigned lab_n8_w[3][LAB_MAXF] = { + { 1, 1, 1, 1, 1, 1, 1, 1 }, + { 1, 2, 3, 4, 5, 6, 7, 8 }, + { 8, 7, 6, 5, 4, 3, 2, 1 } +}; + +/* Spread across eight flows that still counts as one even split. */ +#define LAB_N8_TOL 0.10 + +/* + * Below this, packet-size quantisation dominates the spread, so the + * split is not scored here; starvation (lo == 0) and the utilisation + * gate still apply, so the exemption is narrow. + */ +#define LAB_N8_FAIR 125000 /* bytes/s, 1 Mb/s */ + +/* Aggregate the link has to carry for a run to say anything at all. */ +#define LAB_N8_UTIL 2 /* divisor: half of capacity */ + +/* + * Eight flows on one bottleneck. The additive increase is per flow, so + * both the aggregate probe and the contraction rate scale with the flow + * count, and this is where that scaling shows. + */ +static int test_mb_ecn_lab_fixpoint_n8(uint64_t cap, + uint64_t lag) +{ + static struct lab_cfg c; + uint64_t kb = cap * 8 / 1000; + uint64_t ms = lag / MS; + double worst = 1.0; + uint64_t want; + uint64_t tot; + uint64_t sum; + uint64_t lo; + uint64_t hi; + size_t i; + size_t j; + + TEST_START("(%" PRIu64 " kb/s, lag %" PRIu64 " ms)", kb, ms); + + for (i = 0; i < 3; i++) { + lab_cfg_std(&c, "fixpoint-n8", cap, LAB_MAXF); + + /* 10 Gb/s carries 9000 B frames; below 1 Gb/s, 1000 B. */ + c.len = cap >= 125000000 ? 9000 : LEN; + c.qmax = 1024 * c.len; + + sum = 0; + + for (j = 0; j < LAB_MAXF; j++) + sum += lab_n8_w[i][j]; + + for (j = 0; j < LAB_MAXF; j++) { + c.ia[j] = 0; /* all greedy */ + c.t0[j] = 0; + c.lag[j] = lag; + c.r0[j] = cap * lab_n8_w[i][j] / sum; + } + + c.dur = 400ULL * BILLION; + c.wu = 200ULL * BILLION; + c.sc_lo = 200ULL * BILLION; + c.sc_hi = 400ULL * BILLION; + + lab_run(&c); + + tot = 0; + lo = lab_fl[0].dlv2; + hi = lab_fl[0].dlv2; + + for (j = 0; j < LAB_MAXF; j++) { + tot += lab_fl[j].dlv2; + if (lab_fl[j].dlv2 < lo) + lo = lab_fl[j].dlv2; + + if (lab_fl[j].dlv2 > hi) + hi = lab_fl[j].dlv2; + } + + if (lo == 0) { + printf("seed %zu wedged a flow.\n", i); + goto fail; + } + + want = cap * ((c.sc_hi - c.sc_lo) / BILLION); + if (tot < want / LAB_N8_UTIL) { + printf("seed %zu carried %" PRIu64 " of %" PRIu64 + " bytes.\n", i, tot, want); + goto fail; + } + + if ((double) hi / (double) lo > worst) + worst = (double) hi / (double) lo; + } + + if (cap >= LAB_N8_FAIR && worst > 1.0 + LAB_N8_TOL) { + printf("widest split %.3f across eight flows.\n", worst); + goto fail; + } + + TEST_SUCCESS("(%" PRIu64 " kb/s, lag %" PRIu64 " ms)", kb, ms); + + return TEST_RC_SUCCESS; + fail: + TEST_FAIL("(%" PRIu64 " kb/s, lag %" PRIu64 " ms)", kb, ms); + return TEST_RC_FAIL; +} + +static int test_mb_ecn_lab_fixpoint_n8_all(void) +{ +#ifdef MB_ECN_LAB_FULL + static const uint64_t cap[] = { 1250000000, 12500000, + 1250000, 62500 }; +#else + static const uint64_t cap[] = { 1250000, 62500 }; +#endif + static const uint64_t lag[] = { 2 * MS, 42 * MS }; + int ret = 0; + size_t i; + size_t j; + + for (i = 0; i < sizeof(cap) / sizeof(cap[0]); i++) + for (j = 0; j < sizeof(lag) / sizeof(lag[0]); j++) + ret |= test_mb_ecn_lab_fixpoint_n8(cap[i], lag[j]); + + return ret; +} + +/* Jain's fairness index over the score bytes of flows [lo, hi). */ +static double lab_jain(size_t lo, + size_t hi) +{ + double s = 0.0; + double s2 = 0.0; + double x; + size_t i; + + for (i = lo; i < hi; i++) { + x = (double) lab_fl[i].dlv2; + s += x; + s2 += x * x; + } + + if (s2 == 0.0) + return 0.0; + + return s * s / ((double) (hi - lo) * s2); +} + +/* Greedy flows on one ctx, all from t = 0, short feedback path. */ +static void lab_cfg_shared(struct lab_cfg * c, + const char * name, + uint64_t cap, + size_t n) +{ + size_t i; + + lab_cfg_std(c, name, cap, n); + + c->shared = true; + + for (i = 0; i < n; i++) { + c->ia[i] = 0; + c->t0[i] = 0; + c->lag[i] = 2 * MS; + } +} + +/* + * ------------------------------------------------------------------ + * Shared context: n flows, one struct mb_ecn_ctx, one ftag each. + * + * This is what a production build runs: ca_ctx_get interns one ctx + * per (peer, qos cube), so rate, vt and the mark are shared and the + * start tag is all a flow owns. The pacer then admits n * rate, so + * the attractor for rate is C / n, and the offered load the ctx + * measures is n flows' bytes against one flow's rate. + * ------------------------------------------------------------------ + */ + +/* + * Spread the shared attractor may sit in and still count as a + * per-flow share. The flows share one virtual clock, so the pacer + * fires them in one burst per tick; where that burst is a large part + * of the bandwidth-delay product the quarter-log2 mark prices it as + * a queue and the loop settles into a deep sawtooth, down to ~0.55 + * of C / n around 10 Mb/s at 1 kB packets. The band carries that and + * is still an order of magnitude under the path rate C. + */ +#define LAB_SHR_LO 0.45 +#define LAB_SHR_HI 1.10 + +/* Peak of the same sawtooth, over the settled window. */ +#define LAB_SHR_PK 1.35 + +/* One even split across the flows sharing the ctx. */ +#define LAB_SHR_JN 0.98 + +/* + * Greedy flows on one ctx, optionally with half of them joining and + * leaving again mid-run. Scores the epoch after the last change. + */ +static int test_mb_ecn_lab_shared(uint64_t cap, + size_t n, + bool churn) +{ + static struct lab_cfg c; + uint64_t kb = cap * 8 / 1000; + uint64_t tc = 20ULL * BILLION; + uint64_t fair; + uint64_t mean; + double jain; + size_t nl; + size_t i; + + TEST_START("(%" PRIu64 " kb/s, %zu flows%s)", kb, n, + churn ? ", churn" : ""); + + lab_cfg_shared(&c, churn ? "shr-churn" : "shr-gdy", cap, n); + + nl = churn ? n / 2 : n; + /* Half the flows join at tc and are gone again at 2 * tc. */ + for (i = nl; i < n; i++) { + c.t0[i] = tc; + c.t1[i] = 2 * tc; + } + + fair = cap / nl; + + /* + * Warmup ends at the last change, so r_hi is the peak of the + * epoch that has to settle back to the new share. + */ + c.dur = 2 * tc + 60ULL * BILLION; + c.wu = churn ? 2 * tc : 40ULL * BILLION; + c.sc_lo = c.wu + 20ULL * BILLION; + c.sc_hi = c.dur; + + lab_run(&c); + + mean = lab_fl[0].r_int / (c.dur - c.wu); + jain = lab_jain(0, nl); + + if (mean < (uint64_t) (LAB_SHR_LO * (double) fair) + || mean > (uint64_t) (LAB_SHR_HI * (double) fair)) { + printf("rate %" PRIu64 " is not a %" PRIu64 " share.\n", + mean, fair); + goto fail; + } + + if (lab_fl[0].r_hi > (uint64_t) (LAB_SHR_PK * (double) fair)) { + printf("rate peaked at %.2f of the share.\n", + (double) lab_fl[0].r_hi / (double) fair); + goto fail; + } + + if (jain < LAB_SHR_JN) { + printf("fairness %.4f across %zu flows.\n", jain, nl); + goto fail; + } + + TEST_SUCCESS("(%" PRIu64 " kb/s, %zu flows%s)", kb, n, + churn ? ", churn" : ""); + + return TEST_RC_SUCCESS; + fail: + TEST_FAIL("(%" PRIu64 " kb/s, %zu flows%s)", kb, n, + churn ? ", churn" : ""); + return TEST_RC_FAIL; +} + +/* + * Offered load per flow, as a divisor of the fair share. Low enough + * that the aggregate never fills the link, so nothing marks and the + * offered-load path is the only thing bounding the rate. + */ +#define LAB_SRC_DIV 4 + +/* + * mb_ecn_ceiling admits twice the load ONE flow offers. The slack + * covers the additive increase banked between two window closes and + * the truncation in sharing the offered bytes out. Reading the whole + * ctx's load as one flow's puts the bound n times higher, so a wide + * slack still separates the two. + */ +#define LAB_SRC_CEIL 2.5 + +/* Churn half-period; below CA_SND_WIN no window would ever close. */ +#define LAB_SRC_CHP (100 * MS) + +/* + * Source-limited flows on one ctx. Each offers a fixed rate well + * under its share, so mb_ecn_ceiling and the backlog level are all + * that bound the rate, and both read the offered load. With churn, + * the flows above n / 4 come and go every LAB_SRC_CHP, so a window + * that does not restart on the count change never measures one + * population. + */ +static int test_mb_ecn_lab_shared_load(uint64_t cap, + size_t n, + bool churn) +{ + static struct lab_cfg c; + uint64_t kb = cap * 8 / 1000; + uint64_t off = cap / (LAB_SRC_DIV * n); + uint64_t hi; + double jain; + size_t ns; + size_t i; + + TEST_START("(%" PRIu64 " kb/s, %zu flows%s)", kb, n, + churn ? ", churn" : ""); + + lab_cfg_shared(&c, churn ? "src-churn" : "src-cbr", cap, n); + + for (i = 0; i < n; i++) + c.ia[i] = c.len * BILLION / off; + + if (churn) { + c.ch_p = 2 * LAB_SRC_CHP; + c.ch_f = ~0u << (n / 4); + } + + c.dur = 120ULL * BILLION; + c.wu = 60ULL * BILLION; + c.sc_lo = 60ULL * BILLION; + c.sc_hi = 120ULL * BILLION; + + lab_run(&c); + + hi = lab_fl[0].r_hi; + + /* Score the flows that shared the ctx over the same epochs. */ + ns = churn ? n / 4 : 0; + jain = lab_jain(ns, n); + + if (hi > (uint64_t) (LAB_SRC_CEIL * (double) off)) { + printf("rate peaked at %.2f of the %" PRIu64 " offered, " + "%.2f of the %" PRIu64 " path.\n", + (double) hi / (double) off, off, + (double) hi / (double) cap, cap); + goto fail; + } + + if (jain < LAB_SHR_JN) { + printf("fairness %.4f across %zu flows.\n", jain, n - ns); + goto fail; + } + + TEST_SUCCESS("(%" PRIu64 " kb/s, %zu flows%s)", kb, n, + churn ? ", churn" : ""); + + return TEST_RC_SUCCESS; + fail: + TEST_FAIL("(%" PRIu64 " kb/s, %zu flows%s)", kb, n, + churn ? ", churn" : ""); + return TEST_RC_FAIL; +} + +static int test_mb_ecn_lab(void) +{ + static const uint64_t gc_cap[] = { 625000, 1250000, 12500000 }; + static const char * gc_nm[] = { "gc-5M", "gc-10M", "gc-100M" }; + static const uint64_t sf_cap[] = { 62500, 125000, 1250000 }; + static const char * sf_nm[] = { "sf-500k", "sf-1M", "sf-10M" }; + static const uint64_t g2_cap[] = { + 1250000, 1250000, 1250000, 62500, 62500, 62500 + }; + static const uint64_t g2_lag[] = { + 2 * MS, 20 * MS, 42 * MS, 2 * MS, 20 * MS, 42 * MS + }; + static const char * g2_nm[] = { + "g2-10M-2", "g2-10M-20", "g2-10M-42", + "g2-500k-2", "g2-500k-20", "g2-500k-42" + }; + static const uint64_t ul_lag[] = { 20 * MS, 42 * MS }; + static const char * ul_nm[] = { "g2-ul20", "g2-ul42" }; + static struct lab_cfg c; + size_t i; + + TEST_START(); + + /* + * cbr_protection over capacity: a 3 Mb/s CBR flow shares the + * link with a greedy flow joining at 300 ms, so the share the + * CBR has to hold runs 60%, 30% and 3% of the link. + */ + for (i = 0; i < 3; i++) { + lab_cfg_std(&c, gc_nm[i], gc_cap[i], 2); + lab_run(&c); + } + + /* + * single_flow_slow_link over capacity: one greedy flow alone. + * The marking quantum is fixed in bytes, so capacity alone + * decides how much queueing delay one ecn step prices. + */ + for (i = 0; i < 3; i++) { + lab_cfg_std(&c, sf_nm[i], sf_cap[i], 1); + lab_run(&c); + } + + /* + * Two greedy flows over capacity and equal feedback lag: the + * split they settle on and how a long loop degrades it. + */ + for (i = 0; i < 6; i++) { + lab_cfg_std(&c, g2_nm[i], g2_cap[i], 2); + + c.ia[1] = 0; + c.lag[0] = g2_lag[i]; + c.lag[1] = g2_lag[i]; + c.dur = 65ULL * BILLION; + c.wu = 35ULL * BILLION; + + lab_run(&c); + } + + /* Unequal lag: flow 0 keeps 2 ms, flow 1 reacts slower. */ + for (i = 0; i < 2; i++) { + lab_cfg_std(&c, ul_nm[i], 1250000, 2); + + c.ia[1] = 0; + c.lag[1] = ul_lag[i]; + c.dur = 65ULL * BILLION; + c.wu = 35ULL * BILLION; + + lab_run(&c); + } + + /* + * Service stalls: the scheduler feeding the transmit queue + * pauses, the queue drains clean and the resume bursts the + * backlog through the marker. + */ + lab_cfg_std(&c, "st-gc", 1250000, 2); + + c.st_d = 60 * MS; + c.st_p = 400 * MS; + + lab_run(&c); + + lab_cfg_std(&c, "st-sf", 125000, 1); + + c.st_d = 200 * MS; + c.st_p = BILLION; + + lab_run(&c); + + /* Per-flow starvation: only the sparse CBR flow stalls. */ + lab_cfg_std(&c, "st-pf", 1250000, 2); + + c.st_d = 100 * MS; + c.st_p = 300 * MS; + c.st_f = 2; + + lab_run(&c); + + /* + * Greedy joins 10 s in, once the CBR flow has settled: a step + * into contention rather than a shared ramp. + */ + lab_cfg_std(&c, "gc-late", 1250000, 2); + + c.t0[0] = 10ULL * BILLION; + c.dur = 45ULL * BILLION; + c.wu = 40ULL * BILLION; + c.sc_lo = 15ULL * BILLION; + c.sc_hi = 40ULL * BILLION; + + lab_run(&c); + + /* + * Second greedy flow joins 5 s in: the incumbent has to give + * back half to a newcomer that is still in slow start. + */ + lab_cfg_std(&c, "g2-stag", 1250000, 2); + + c.ia[1] = 0; + c.t0[0] = 0; + c.t0[1] = 5ULL * BILLION; + c.dur = 65ULL * BILLION; + c.wu = 35ULL * BILLION; + + lab_run(&c); + + TEST_SUCCESS(); + + return TEST_RC_SUCCESS; +} + +int mb_ecn_lab_test(int argc, + char ** argv) +{ + int ret = 0; + + (void) argc; + (void) argv; + + ret |= test_mb_ecn_lab_shared(1250000, 5, false); + ret |= test_mb_ecn_lab_shared(1250000, 8, false); + ret |= test_mb_ecn_lab_shared(1250000, 8, true); + ret |= test_mb_ecn_lab_shared_load(1250000, 5, false); + ret |= test_mb_ecn_lab_shared_load(1250000, 8, false); + ret |= test_mb_ecn_lab_shared_load(1250000, 5, true); + ret |= test_mb_ecn_lab_shared_load(1250000, 8, true); + ret |= test_mb_ecn_lab_fixpoint_all(); + ret |= test_mb_ecn_lab_fixpoint_n8_all(); + ret |= test_mb_ecn_lab(); + + return ret; +} diff --git a/src/ipcpd/unicast/ca/tests/mb_ecn_test.c b/src/ipcpd/unicast/ca/tests/mb_ecn_test.c index 4bbc12aa..7186d3af 100644 --- a/src/ipcpd/unicast/ca/tests/mb_ecn_test.c +++ b/src/ipcpd/unicast/ca/tests/mb_ecn_test.c @@ -21,6 +21,7 @@ */ #include "mb-ecn.c" + #include <test/test.h> #define MS (MILLION) /* one millisecond in ns */ @@ -121,109 +122,140 @@ static int test_mb_ecn_ctx_create_destroy(void) return TEST_RC_FAIL; } -static int test_mb_ecn_calc_ecn(void) +/* The pricing window derives from the declared RTT. */ +static int test_mb_ecn_init_window(void) { - uint8_t ecn; - TEST_START(); - /* A queue below one ECN quantum marks nothing. */ - ecn = 0; - mb_ecn_calc_ecn(CA_MARK_Q - 1, &ecn, QOS_CUBE_BE, 0); - if (ecn != 0) { - printf("Sub-quantum queue marked %u.\n", ecn); - goto fail; - } + /* A fabric RTT lands on the floor, not below it. */ + mb_ecn_init(1); - /* Queue depth maps to ecn = queued / CA_MARK_Q. */ - ecn = 0; - mb_ecn_calc_ecn(5 * CA_MARK_Q, &ecn, QOS_CUBE_BE, 0); - if (ecn != 5) { - printf("Expected ecn 5, got %u.\n", ecn); + if (mb_ecn_tw != CA_TW_MIN) { + printf("fabric window %" PRIu64 ".\n", mb_ecn_tw); goto fail; } - /* MAX keeps the larger value; a smaller mark cannot raise it. */ - ecn = 0x80; - mb_ecn_calc_ecn(CA_MARK_Q, &ecn, QOS_CUBE_BE, 0); - if (ecn != 0x80) { - printf("Expected ecn 0x80, got 0x%x.\n", ecn); - goto fail; - } + /* A WAN RTT caps the window. */ + mb_ecn_init(200); - ecn = 3; - mb_ecn_calc_ecn(4 * CA_MARK_Q, &ecn, QOS_CUBE_BE, 0); - if (ecn != 4) { - printf("Expected ecn 4, got %u.\n", ecn); + if (mb_ecn_tw != CA_TW) { + printf("wan window %" PRIu64 ".\n", mb_ecn_tw); goto fail; } - /* A queue past 255 quanta saturates, it does not wrap to a low mark. */ - ecn = 0; - mb_ecn_calc_ecn(256 * CA_MARK_Q, &ecn, QOS_CUBE_BE, 0); - if (ecn != 255) { - printf("Deep queue wrapped: exp 255, got %u.\n", ecn); + /* An unspecified RTT takes the default and caps the window. */ + mb_ecn_init(0); + + if (mb_ecn_tw != CA_TW) { + printf("default window %" PRIu64 ".\n", mb_ecn_tw); goto fail; } + mb_ecn_init(CA_SS_RTT_DEF); + TEST_SUCCESS(); return TEST_RC_SUCCESS; fail: + mb_ecn_init(CA_SS_RTT_DEF); TEST_FAIL(); return TEST_RC_FAIL; } -/* The first mark after idle emits the raw value with zero latency. */ -static int test_mb_ecn_rcv_onset_immediate(void) +/* Queue depth (packets) that reads as full congestion. */ +#define FULL_PKTS (CA_MARK_KNEE << ((CA_ECE_REF >> CA_SHFT) / 4)) + +static int test_mb_ecn_calc_ecn(void) { - struct mb_ecn_ctx * ctx; - uint16_t ece; - uint8_t fcap; + uint8_t ecn; TEST_START(); - ctx = mk_ctx(); - if (ctx == NULL) { - printf("Failed to create context.\n"); + /* One packet in the queue is the floor: it marks nothing. */ + ecn = 0; + + mb_ecn_calc_ecn(1400, &ecn, QOS_CUBE_BE, 1400); + + if (ecn != 0) { + printf("Single packet marked %u.\n", ecn); goto fail; } - if (!mb_ecn_rcv(ctx, LEN, 4, 0, &ece, &fcap, MS)) { - printf("Onset did not update.\n"); - goto fail_ctx; + /* An unknown mean packet size cannot mark. */ + ecn = 0; + + mb_ecn_calc_ecn(1400, &ecn, QOS_CUBE_BE, 0); + + if (ecn != 0) { + printf("Unknown mean marked %u.\n", ecn); + goto fail; } - if (ece != 4 << CA_SHFT) { - printf("Onset ece: exp %u, got %u.\n", 4 << CA_SHFT, ece); - goto fail_ctx; + /* Each doubling of the queue adds 4. */ + ecn = 0; + + mb_ecn_calc_ecn(2 * 1400, &ecn, QOS_CUBE_BE, 1400); + + if (ecn != 4) { + printf("Expected ecn 4 at 2 packets, got %u.\n", ecn); + goto fail; } - if (mb_ecn_rcv(ctx, LEN, 4, 0, &ece, &fcap, 2 * MS)) { - printf("Mid-window packet updated.\n"); - goto fail_ctx; + /* FULL_PKTS packets is full congestion. */ + ecn = 0; + + mb_ecn_calc_ecn(FULL_PKTS * 1400, &ecn, QOS_CUBE_BE, 1400); + + if (ecn != (CA_ECE_REF >> CA_SHFT)) { + printf("Expected ecn %u at full, got %u.\n", + CA_ECE_REF >> CA_SHFT, ecn); + goto fail; } - mb_ecn_ctx_destroy(ctx); + /* The same packet count marks the same at any packet size. */ + ecn = 0; + + mb_ecn_calc_ecn(FULL_PKTS * 200, &ecn, QOS_CUBE_BE, 200); + + if (ecn != (CA_ECE_REF >> CA_SHFT)) { + printf("Size dependence: exp %u, got %u.\n", + CA_ECE_REF >> CA_SHFT, ecn); + goto fail; + } + + /* MAX keeps the larger value; a smaller mark cannot lower it. */ + ecn = 0x80; + + mb_ecn_calc_ecn(2 * 1400, &ecn, QOS_CUBE_BE, 1400); + + if (ecn != 0x80) { + printf("Expected ecn 0x80, got 0x%x.\n", ecn); + goto fail; + } + + ecn = 3; + + mb_ecn_calc_ecn(4 * 1400, &ecn, QOS_CUBE_BE, 1400); + + if (ecn != 8) { + printf("Expected ecn 8, got %u.\n", ecn); + goto fail; + } TEST_SUCCESS(); return TEST_RC_SUCCESS; - fail_ctx: - mb_ecn_ctx_destroy(ctx); fail: TEST_FAIL(); return TEST_RC_FAIL; } -/* A 50% duty mark square wave emits the time mean, not the last peak. */ -static int test_mb_ecn_rcv_window_mean(void) +/* The first mark after idle emits the raw value with zero latency. */ +static int test_mb_ecn_rcv_onset_immediate(void) { struct mb_ecn_ctx * ctx; uint16_t ece; uint8_t fcap; - size_t upd; - size_t i; TEST_START(); @@ -233,24 +265,18 @@ static int test_mb_ecn_rcv_window_mean(void) goto fail; } - mb_ecn_rcv(ctx, LEN, 8, 0, &ece, &fcap, MS); - - /* The byte trigger closes every ~32 packets: two windows. */ - upd = 0; - for (i = 1; i <= 68; i++) { - time_t ecn = (i & 1) ? 8 : 0; - time_t t = MS + i * MS; - if (mb_ecn_rcv(ctx, LEN, ecn, 0, &ece, &fcap, t)) - upd++; + if (!mb_ecn_rcv(ctx, LEN, 4, 0, &ece, &fcap, MS)) { + printf("Onset did not update.\n"); + goto fail_ctx; } - if (upd != 2) { - printf("%zu updates in two windows.\n", upd); + if (ece != 4 << CA_SHFT) { + printf("Onset ece: exp %u, got %u.\n", 4 << CA_SHFT, ece); goto fail_ctx; } - if (ece < 120 || ece > 136) { - printf("window mean: exp ~128, got %u.\n", ece); + if (mb_ecn_rcv(ctx, LEN, 4, 0, &ece, &fcap, 2 * MS)) { + printf("Mid-window packet updated.\n"); goto fail_ctx; } @@ -466,7 +492,7 @@ static int test_mb_ecn_rcv_gap_restart(void) mb_ecn_rcv(ctx, LEN, 6, 0, &ece, &fcap, MS); mb_ecn_rcv(ctx, LEN, 6, 0, &ece, &fcap, 2 * MS); - t = 2 * MS + 10 * CA_TW_INIT; + t = 2 * MS + 10 * CA_TW; if (!mb_ecn_rcv(ctx, LEN, 5, 0, &ece, &fcap, t)) { printf("gap restart did not update.\n"); goto fail_ctx; @@ -477,7 +503,7 @@ static int test_mb_ecn_rcv_gap_restart(void) goto fail_ctx; } - t += 10 * CA_TW_INIT; + t += 10 * CA_TW; if (!mb_ecn_rcv(ctx, LEN, 0, 0, &ece, &fcap, t) || ece != 0) { printf("gap with clean packet did not end: %u.\n", ece); goto fail_ctx; @@ -500,8 +526,14 @@ static int test_mb_ecn_rcv_gap_restart(void) return TEST_RC_FAIL; } -/* Max marks at max gaps: exact ceiling, no overflow past the edge. */ -static int test_mb_ecn_rcv_accum_bounds(void) +/* + * At a floored layer RTT, rx_tw sits at CA_TW_MIN, so 4 * rx_tw is + * well under CA_ECE_TTL. A gap in that band must still close the + * window as a diluted average, not restart fresh: a fresh restart + * always emits the raw undiluted mark (ecn << CA_SHFT), so an ece + * that low pins the CA_ECE_TTL floor in mb_ecn_rcv_fresh. + */ +static int test_mb_ecn_rcv_gap_floor(void) { struct mb_ecn_ctx * ctx; uint16_t ece; @@ -510,33 +542,39 @@ static int test_mb_ecn_rcv_accum_bounds(void) TEST_START(); + mb_ecn_init(2); + ctx = mk_ctx(); if (ctx == NULL) { printf("Failed to create context.\n"); goto fail; } - mb_ecn_rcv(ctx, LEN, 15, 0, &ece, &fcap, MS); - - /* Two packets at dt just under CA_TW_INIT straddle the boundary. */ - t = MS + CA_TW_INIT - 1; - if (mb_ecn_rcv(ctx, LEN, 15, 0, &ece, &fcap, t)) { - printf("update before the window closed.\n"); + if (ctx->rx_tw != CA_TW_MIN) { + printf("window not floored: %" PRIu64 ".\n", ctx->rx_tw); goto fail_ctx; } - t += CA_TW_INIT - 1; - if (!mb_ecn_rcv(ctx, LEN, 15, 0, &ece, &fcap, t)) { - printf("no update at the window boundary.\n"); + /* Onset, then a second packet inside the window: mark banked. */ + mb_ecn_rcv(ctx, LEN, 8, 0, &ece, &fcap, MS); + mb_ecn_rcv(ctx, LEN, 8, 0, &ece, &fcap, 2 * MS); + + /* 20 ms gap: past 4 * rx_tw (16 ms), well under CA_ECE_TTL. */ + + t = 2 * MS + 20 * MS; + if (!mb_ecn_rcv(ctx, LEN, 8, 0, &ece, &fcap, t)) { + printf("window did not close.\n"); goto fail_ctx; } - if (ece != 15 << CA_SHFT) { - printf("ceiling: exp %u, got %u.\n", 15 << CA_SHFT, ece); + /* A fresh restart would emit the raw mark 8 << CA_SHFT, undiluted. */ + if (ece >= (8 << CA_SHFT)) { + printf("gap read as a fresh onset: ece %u.\n", ece); goto fail_ctx; } mb_ecn_ctx_destroy(ctx); + mb_ecn_init(CA_SS_RTT_DEF); TEST_SUCCESS(); @@ -544,78 +582,49 @@ static int test_mb_ecn_rcv_accum_bounds(void) fail_ctx: mb_ecn_ctx_destroy(ctx); fail: + mb_ecn_init(CA_SS_RTT_DEF); TEST_FAIL(); return TEST_RC_FAIL; } -/* Scale-free density: the window holds ~CA_N_TARGET packets at any rate. */ -static int test_mb_ecn_rcv_window_holds_target(void) +/* Max marks at max gaps: exact ceiling, no overflow past the edge. */ +static int test_mb_ecn_rcv_accum_bounds(void) { struct mb_ecn_ctx * ctx; uint16_t ece; uint8_t fcap; - uint16_t last_ece; - uint64_t rates[4]; - uint64_t ia; uint64_t t; - size_t closes; - size_t since; - size_t count; - size_t ri; TEST_START(); - rates[0] = 5000000; - rates[1] = 10000000; - rates[2] = 50000000; - rates[3] = 100000000; - - ctx = NULL; - for (ri = 0; ri < 4; ri++) { - ia = 8000ULL * BILLION / rates[ri]; - t = 0; - closes = 0; - since = 0; - count = 0; - last_ece = 0; - - ctx = mk_ctx(); - if (ctx == NULL) { - printf("Failed to create context.\n"); - goto fail; - } + ctx = mk_ctx(); + if (ctx == NULL) { + printf("Failed to create context.\n"); + goto fail; + } - /* Warm past the ramp from CA_TW_INIT, then time one gap. */ - while (closes < 42) { - t += ia; - since++; - if (!mb_ecn_rcv(ctx, LEN, 8, 0, &ece, &fcap, t)) - continue; - closes++; - if (closes == 41) { - since = 0; - } else if (closes == 42) { - count = since - 1; - last_ece = ece; - } - } + mb_ecn_rcv(ctx, LEN, 15, 0, &ece, &fcap, MS); - if (count < 8 || count > 32) { - printf("rate %" PRIu64 ": %zu pkts/window.\n", - rates[ri], count); - goto fail_ctx; - } + /* Two packets at dt just under CA_TW straddle the boundary. */ + t = MS + CA_TW - 1; + if (mb_ecn_rcv(ctx, LEN, 15, 0, &ece, &fcap, t)) { + printf("update before the window closed.\n"); + goto fail_ctx; + } - if (last_ece < 224 || last_ece > 288) { - printf("rate %" PRIu64 ": ece %u ~256.\n", - rates[ri], last_ece); - goto fail_ctx; - } + t += CA_TW - 1; + if (!mb_ecn_rcv(ctx, LEN, 15, 0, &ece, &fcap, t)) { + printf("no update at the window boundary.\n"); + goto fail_ctx; + } - mb_ecn_ctx_destroy(ctx); - ctx = NULL; + if (ece != 15 << CA_SHFT) { + printf("ceiling: exp %u, got %u.\n", 15 << CA_SHFT, ece); + goto fail_ctx; } + mb_ecn_ctx_destroy(ctx); + TEST_SUCCESS(); return TEST_RC_SUCCESS; @@ -627,7 +636,7 @@ static int test_mb_ecn_rcv_window_holds_target(void) } /* - * The window floors at CA_TW_MIN, tracks the rate below the old knee, + * The window floors at CA_TW, tracks the rate below the knee, * and only a pathological fold hits the CA_TW_ABSMAX ceiling. */ static int test_mb_ecn_rcv_window_clip_bounds(void) @@ -641,7 +650,7 @@ static int test_mb_ecn_rcv_window_clip_bounds(void) TEST_START(); - /* 1 GbE is above the high knee: the window floors at CA_TW_MIN. */ + /* 1 GbE is above the high knee: the window floors at CA_TW. */ ctx = mk_ctx(); if (ctx == NULL) { printf("Failed to create context.\n"); @@ -657,15 +666,15 @@ static int test_mb_ecn_rcv_window_clip_bounds(void) closes++; } - if (ctx->rx_tw != CA_TW_MIN) { + if (ctx->rx_tw != CA_TW) { printf("high-rate window: exp %" PRIu64 ", got %" PRIu64 - ".\n", (uint64_t) CA_TW_MIN, ctx->rx_tw); + ".\n", (uint64_t) CA_TW, ctx->rx_tw); goto fail_ctx; } mb_ecn_ctx_destroy(ctx); - /* 1 Mbps: past the old knee, ~16 pkts = 16 * 8 ms = 131 ms. */ + /* 1 Mbps: below the knee, ~16 pkts = 16 * 8 ms = 131 ms. */ ctx = mk_ctx(); if (ctx == NULL) { printf("Failed to create context.\n"); @@ -697,7 +706,7 @@ static int test_mb_ecn_rcv_window_clip_bounds(void) } mb_ecn_rcv(ctx, 10, 8, 0, &ece, &fcap, MS); - mb_ecn_rcv(ctx, 10, 8, 0, &ece, &fcap, MS + CA_TW_INIT); + mb_ecn_rcv(ctx, 10, 8, 0, &ece, &fcap, MS + CA_TW); if (ctx->rx_tw != CA_TW_ABSMAX) { printf("window ceiling breached: %" PRIu64 ".\n", @@ -782,9 +791,9 @@ static int test_mb_ecn_rcv_no_overflow_highrate(void) /* Open a window, then inject a maximal byte count and span. */ mb_ecn_rcv(ctx, LEN, 15, 0, &ece, &fcap, 0); ctx->rx_byt = CA_RATE_MAX / 8; - ctx->rx_ts = 2 * CA_TW_INIT - 2; + ctx->rx_ts = 2 * CA_TW - 2; - ok = mb_ecn_rcv(ctx, LEN, 15, 0, &ece, &fcap, 2 * CA_TW_INIT - 1); + ok = mb_ecn_rcv(ctx, LEN, 15, 0, &ece, &fcap, 2 * CA_TW - 1); if (!ok) { printf("max-window close did not fire.\n"); @@ -797,7 +806,7 @@ static int test_mb_ecn_rcv_no_overflow_highrate(void) } /* A wrapped numerator drives rx_tw to MAX; it must descend. */ - if (ctx->rx_tw >= CA_TW_INIT || ctx->rx_tw < CA_TW_MIN) { + if (ctx->rx_tw > CA_TW || ctx->rx_tw < CA_TW) { printf("window %" PRIu64 " did not descend.\n", ctx->rx_tw); goto fail_ctx; } @@ -816,7 +825,7 @@ static int test_mb_ecn_rcv_no_overflow_highrate(void) /* * The sender holds a mark across the full inter-feedback gap (TTL > - * 2 * CA_TW_INIT); a repeated mark adds only the proportional cut. + * 2 * CA_TW); a repeated mark adds only the proportional cut. */ static int test_mb_ecn_ece_ttl_covers_cadence(void) { @@ -840,10 +849,10 @@ static int test_mb_ecn_ece_ttl_covers_cadence(void) mb_ecn_ece(ctx, 100, 0, MS); mb_ecn_snd(ctx, LEN, MS, &ftag); - /* Sends between feedbacks spaced 2 * CA_TW_INIT + 5 ms apart. */ + /* Sends between feedbacks spaced 2 * CA_TW + 5 ms apart. */ t = MS; for (i = 0; i < 4; i++) { - t += (2 * CA_TW_INIT + 5 * MS) / 4; + t += (2 * CA_TW + 5 * MS) / 4; mb_ecn_snd(ctx, LEN, t, &ftag); if (ctx->tx_ece == 0) { printf("mark cleared inside the feedback gap.\n"); @@ -949,10 +958,8 @@ static int test_mb_ecn_dt_scaling_invariant(void) mb_ecn_ece(b, 0, 0, 0); a->rate = (uint64_t) 10 << 20; b->rate = (uint64_t) 10 << 20; - a->r_bkt = a->rate; - b->r_bkt = b->rate; - /* a: one 30 ms step (under one washout bucket, so it stays out). */ + /* a: one 30 ms step. */ mb_ecn_snd(a, LEN, 30 * MS, &fta); /* b: thirty 1 ms steps over the same 30 ms. */ @@ -1036,6 +1043,66 @@ static int test_mb_ecn_multiplicative_decrease(void) return TEST_RC_FAIL; } +/* The hold releases on any unsaturated mark, including above REF. */ +static int test_mb_ecn_ai_hold_release(void) +{ + struct mb_ecn_ctx * ctx; + uint64_t r0 = (uint64_t) 100 << 20; + + TEST_START(); + + ctx = mk_ctx(); + if (ctx == NULL) { + printf("Failed to create context.\n"); + goto fail; + } + + /* A saturated mark keeps the hold: the queue has not drained. */ + ctx->ai_hold = true; + + mb_ecn_ece(ctx, CA_ECE_MAX, 0, MS); + + if (!ctx->ai_hold) { + printf("saturated feedback released the hold.\n"); + goto fail_ctx; + } + + /* A standing mark of 20 flows is unsaturated: release. */ + ctx->ai_hold = true; + + mb_ecn_ece(ctx, 22 << CA_SHFT, 0, 2 * MS); + + if (ctx->ai_hold) { + printf("unsaturated feedback held the increase.\n"); + goto fail_ctx; + } + + /* The decrease still scales with the mark saturated at CA_ECE_MAX. */ + ctx->rate = r0; + ctx->tx_cav = true; + ctx->tx_ece = CA_ECE_MAX; + ctx->tx_ecp = CA_ECE_MAX; + ctx->dec_acc = 0; + + mb_ecn_decrease(ctx, MILLION); + + if (ctx->rate > r0 - r0 / 700) { + printf("clamped decrease too weak: %" PRIu64 ".\n", ctx->rate); + goto fail_ctx; + } + + mb_ecn_ctx_destroy(ctx); + + TEST_SUCCESS(); + + return TEST_RC_SUCCESS; + fail_ctx: + mb_ecn_ctx_destroy(ctx); + fail: + TEST_FAIL(); + return TEST_RC_FAIL; +} + static int test_mb_ecn_rate_floor(void) { struct mb_ecn_ctx * ctx; @@ -1119,17 +1186,15 @@ static int test_mb_ecn_fixed_point(void) return TEST_RC_FAIL; } -/* - * A rising ECE mark takes a one-sided lead cut on top of the - * proportional term; a flat or falling mark takes only the small - * proportional cut. - */ -static int test_mb_ecn_lead_cut(void) +/* The lead is two-sided: it cuts on a rise and gives back on a fall. */ +static int test_mb_ecn_lead_symmetric(void) { struct mb_ecn_ctx * ctx; - uint64_t prev; + uint64_t r0 = (uint64_t) 100 << 20; + uint64_t net; uint64_t drop; - uint64_t ftag = 0; + uint64_t gain; + uint64_t kd2; TEST_START(); @@ -1139,36 +1204,81 @@ static int test_mb_ecn_lead_cut(void) goto fail; } - ctx->rate = (uint64_t) 100 << 20; ctx->tx_cav = true; - /* Rise 0 -> 256: the lead term cuts hard (~rate/8). */ - prev = ctx->rate; - mb_ecn_ece(ctx, 256, 0, MS); - mb_ecn_snd(ctx, LEN, MS, &ftag); - drop = prev - ctx->rate; - if (drop < prev / 16) { - printf("rising mark under-cut: %" PRIu64 ".\n", drop); + /* Rise of one reference: cut rate / CA_MD_KD_DIV, no more. */ + ctx->rate = r0; + ctx->tx_ece = CA_ECE_REF; + ctx->tx_ecp = 0; + ctx->dec_acc = 0; + + mb_ecn_decrease(ctx, 0); + + drop = r0 - ctx->rate; + if (drop != r0 / CA_MD_KD_DIV) { + printf("rise cut %" PRIu64 ", want %" PRIu64 ".\n", + drop, r0 / CA_MD_KD_DIV); goto fail_ctx; } - /* Flat mark: no rise, only the proportional cut. */ - prev = ctx->rate; - mb_ecn_ece(ctx, 256, 0, 2 * MS); - mb_ecn_snd(ctx, LEN, 2 * MS, &ftag); - drop = prev - ctx->rate; - if (drop > prev / 100) { - printf("flat mark over-cut: dropped %" PRIu64 ".\n", drop); + /* Fall of one reference: give the same fraction back. */ + ctx->rate = r0; + ctx->tx_ece = 1; + ctx->tx_ecp = CA_ECE_REF + 1; + ctx->dec_acc = 0; + + mb_ecn_decrease(ctx, 0); + + gain = ctx->rate - r0; + if (gain != r0 / CA_MD_KD_DIV) { + printf("fall boost %" PRIu64 ", want %" PRIu64 ".\n", + gain, r0 / CA_MD_KD_DIV); goto fail_ctx; } - /* Falling mark: no rise, no lead beyond the proportional term. */ - prev = ctx->rate; - mb_ecn_ece(ctx, 64, 0, 3 * MS); - mb_ecn_snd(ctx, LEN, 3 * MS, &ftag); - drop = prev > ctx->rate ? prev - ctx->rate : 0; - if (drop > prev / 100) { - printf("falling mark cut: dropped %" PRIu64 ".\n", drop); + /* A collapse from deep saturation is clamped to the same. */ + ctx->rate = r0; + ctx->tx_ece = 1; + ctx->tx_ecp = 255 << CA_SHFT; + ctx->dec_acc = 0; + + mb_ecn_decrease(ctx, 0); + + gain = ctx->rate - r0; + if (gain != r0 / CA_MD_KD_DIV) { + printf("unclamped fall boost %" PRIu64 ".\n", gain); + goto fail_ctx; + } + + /* A cycle that stays marked nets out: no standing bias. */ + ctx->rate = r0; + ctx->tx_ecp = 4 << CA_SHFT; + ctx->tx_ece = 12 << CA_SHFT; + ctx->dec_acc = 0; + + mb_ecn_decrease(ctx, 0); + + ctx->tx_ece = 4 << CA_SHFT; + ctx->dec_acc = 0; + + mb_ecn_decrease(ctx, 0); + + net = ctx->rate > r0 ? ctx->rate - r0 : r0 - ctx->rate; + /* + * The two lead steps compound to (1 - x)(1 + x), x = 1 / + * (2 * CA_MD_KD_DIV), so net ~= r0 / (4 * CA_MD_KD_DIV^2). + * Band it a factor of 2 either side so a materially weaker + * gain (e.g. KD off by a factor of 4) fails the floor. + */ + kd2 = (uint64_t) CA_MD_KD_DIV * CA_MD_KD_DIV; + if (net > r0 / (2 * kd2)) { + printf("cycle bias %" PRIu64 " of %" PRIu64 ".\n", net, r0); + goto fail_ctx; + } + + if (net < r0 / (8 * kd2)) { + printf("lead gain weaker than expected: net %" PRIu64 + " of %" PRIu64 ".\n", net, r0); goto fail_ctx; } @@ -1722,8 +1832,6 @@ static int test_mb_ecn_probe_scale_invariant(void) mb_ecn_ece(b, 0, 0, 0); a->rate = (uint64_t) 10 << 20; b->rate = (uint64_t) 1000 << 20; - a->r_bkt = a->rate; - b->r_bkt = b->rate; a->backlogged = true; b->backlogged = true; ra0 = a->rate; @@ -1787,8 +1895,8 @@ static int test_mb_ecn_probe_time_constant(void) /* Clean path, out of slow start, backlogged, below the ceiling. */ mb_ecn_ece(ctx, 0, 0, 0); + ctx->rate = (uint64_t) 1 << 30; - ctx->r_bkt = ctx->rate; ctx->backlogged = true; r0 = ctx->rate; @@ -1799,11 +1907,10 @@ static int test_mb_ecn_probe_time_constant(void) mb_ecn_ece(ctx, 0, 0, t); } - /* Washout damps the probe to ~4/3 TC, so 8 s -> ~2.12x. */ + /* Undamped probe: 8 s at TC 8 s is one full e-fold, ~2.72x. */ ratio = (double) ctx->rate / r0; - if (ratio < 2.0 || ratio > 2.25) { - printf("probe TC off: exp ~2.12, got %.3fx over 8 s.\n", - ratio); + if (ratio < 2.6 || ratio > 2.85) { + printf("probe TC off: exp ~2.72, got %.3fx over 8 s.\n", ratio); goto fail_ctx; } @@ -1851,7 +1958,7 @@ static int test_mb_ecn_rcv_cap_window_min(void) mb_ecn_rcv(ctx, LEN, 8, 40, &ece, &fcap, 2 * MS); mb_ecn_rcv(ctx, LEN, 8, 36, &ece, &fcap, 3 * MS); - t = 3 * MS + CA_TW_INIT; + t = 3 * MS + CA_TW; if (!mb_ecn_rcv(ctx, LEN, 8, 0, &ece, &fcap, t)) { printf("Window did not close.\n"); goto fail_ctx; @@ -1865,7 +1972,7 @@ static int test_mb_ecn_rcv_cap_window_min(void) /* The next window starts unknown; follow the adapted rx_tw. */ upd = false; for (i = 0; i < 128 && !upd; i++) { - t += CA_TW_INIT; + t += CA_TW; upd = mb_ecn_rcv(ctx, LEN, 8, 0, &ece, &fcap, t); } @@ -1920,7 +2027,7 @@ static int test_mb_ecn_rcv_cap_onset_fresh(void) mb_ecn_rcv(ctx, LEN, 4, 50, &ece, &fcap, 2 * MS); /* A gap restart must not fold in the stale window min. */ - t = 2 * MS + 5 * CA_TW_INIT; + t = 2 * MS + 5 * CA_TW; if (!mb_ecn_rcv(ctx, LEN, 4, 90, &ece, &fcap, t)) { printf("Gap restart did not update.\n"); goto fail_ctx; @@ -1970,7 +2077,7 @@ static int test_mb_ecn_ece_cap_derives_rates(void) goto fail_ctx; } - if (ctx->ai_rate != ctx->rate_min) { + if (ctx->ai_rate != 2 * ctx->rate_min) { printf("AI slope did not track the floor.\n"); goto fail_ctx; } @@ -2162,8 +2269,8 @@ static int test_mb_ecn_ctrl_per_ctx_ai(void) /* Leave slow start; raise the slope as capacity would. */ mb_ecn_ece(ctx, 0, 0, 0); + ctx->rate = (uint64_t) 10 << 20; - ctx->r_bkt = ctx->rate; ctx->ai_rate = 16 * CA_AI_RATE; want = ctx->rate + ctx->ai_rate * (30 * MS) / BILLION; @@ -2407,15 +2514,15 @@ static int test_mb_ecn_backlogged_paced(void) } /* - * A source-limited flow is capped to the next quarter-log2 headroom - * above the offered estimate, and NOT re-floored to a high capacity - * rate_min. + * A source-limited flow is capped to the backlog level above the + * offered estimate, and NOT re-floored to a high capacity rate_min. */ static int test_mb_ecn_source_limited_ceiling(void) { struct mb_ecn_ctx * ctx; uint64_t ftag = 0; uint64_t t = 10 * MS; + uint64_t expect; TEST_START(); @@ -2439,9 +2546,10 @@ static int test_mb_ecn_source_limited_ceiling(void) mb_ecn_snd(ctx, LEN, t + 2 * MS, &ftag); - if (ctx->rate != ((uint64_t) 2 << 20)) { + expect = 1398101; /* (1 << 20) * 4 / 3, truncated */ + if (ctx->rate != expect) { printf("ceiling: exp %" PRIu64 ", got %" PRIu64 ".\n", - (uint64_t) 2 << 20, ctx->rate); + expect, ctx->rate); goto fail_ctx; } @@ -2452,6 +2560,37 @@ static int test_mb_ecn_source_limited_ceiling(void) mb_ecn_ctx_destroy(ctx); + /* Non-power-of-two case: verify the exact level, not a step. */ + + ctx = mk_ctx(); + if (ctx == NULL) { + printf("Failed to create context.\n"); + goto fail; + } + + ctx->tx_cav = true; + ctx->started = true; + ctx->backlogged = false; + ctx->rate = (uint64_t) 100 << 20; + ctx->inv_rate = mb_ecn_rate_inv(ctx->rate); + ctx->rate_min = (uint64_t) 50 << 20; + ctx->snd_rate = (uint64_t) 303 << 12; + ctx->snd_r0 = ctx->rate; + ctx->snd_win = t; + ctx->last_ts = t; + ctx->last_ctrl = t; + + mb_ecn_snd(ctx, LEN, t + 2 * MS, &ftag); + + expect = 1654784; /* (303 << 12) * 4 / 3, exact */ + if (ctx->rate != expect) { + printf("exact ceiling: exp %" PRIu64 ", got %" PRIu64 + ".\n", expect, ctx->rate); + goto fail_ctx; + } + + mb_ecn_ctx_destroy(ctx); + TEST_SUCCESS(); return TEST_RC_SUCCESS; @@ -2526,6 +2665,7 @@ static int test_mb_ecn_idle_clears_backlogged(void) ctx->started = true; ctx->backlogged = true; + ctx->rate = snd_rate; ctx->snd_rate = snd_rate; ctx->snd_win = t; ctx->last_ts = t; @@ -2638,7 +2778,7 @@ static void shared_link_run(struct mb_ecn_ctx * a, tgt = (k + 1) * TF_STEP; ecn = 0; - mb_ecn_calc_ecn(q / LEN, &ecn, QOS_CUBE_BE, LEN); + mb_ecn_calc_ecn(q, &ecn, QOS_CUBE_BE, LEN); hist[k % TF_HIST] = (uint16_t) (ecn << CA_SHFT); ea = k < lag_a ? 0 : hist[(k - lag_a) % TF_HIST]; @@ -2775,16 +2915,14 @@ static int test_mb_ecn_ramp_overshoot_grows_with_rtt(void) } /* - * Washout damps a fixed 1/4 of the rate change once per wall-clock - * bucket: a sub-bucket step banks time only, a full bucket removes a - * quarter of the gap either way without crossing the snapshot, and a - * sparse step (> CA_DT_CAP) resets it so a starved sender keeps its cut. + * Flows sharing a context offer bytes together but each may send at + * rate, so the window must be shared out before the backlog level is + * read. Four flows offering two thirds of a share each stay below it. */ -static int test_mb_ecn_washout_bucket(void) +static int test_mb_ecn_shared_ctx_offered_per_flow(void) { struct mb_ecn_ctx * ctx; - uint64_t r0 = (uint64_t) 100 << 20; - uint64_t gap; + uint64_t rate = 1000000; TEST_START(); @@ -2794,56 +2932,148 @@ static int test_mb_ecn_washout_bucket(void) goto fail; } - gap = r0 >> 4; + ctx->rate = rate; + ctx->snd_flows = 4; + ctx->snd_r0 = rate; + ctx->snd_win = 0; + ctx->snd_byt = 4 * rate * 2 / 3; - /* Sub-bucket: time banks, the rate does not move. */ - ctx->rate = r0; - ctx->r_bkt = r0 - gap; - ctx->wash_acc = 0; - mb_ecn_washout(ctx, MS, MS); - if (ctx->rate != r0 || ctx->wash_acc != MS) { - printf("sub-bucket washout moved the rate: %" PRIu64 ".\n", - ctx->rate); + mb_ecn_win(ctx, BILLION); + + if (ctx->backlogged) { + printf("aggregate load read as one flow's backlog.\n"); goto fail_ctx; } - /* Full bucket, rate leads: cut a quarter of the gap, no crossing. */ - ctx->rate = r0; - ctx->r_bkt = r0 - gap; - ctx->wash_acc = 0; - mb_ecn_washout(ctx, MS, CA_WASH_BKT); - if (ctx->rate != r0 - (gap >> CA_WASH_SHFT)) { - printf("bucket down: got %" PRIu64 ".\n", ctx->rate); + /* The close left a fresh window; a full share each clears it. */ + ctx->snd_byt = 4 * rate; + + mb_ecn_win(ctx, 2 * BILLION); + + if (!ctx->backlogged) { + printf("per-flow share did not read as backlogged.\n"); + goto fail_ctx; + } + + mb_ecn_ctx_destroy(ctx); + + TEST_SUCCESS(); + + return TEST_RC_SUCCESS; + fail_ctx: + mb_ecn_ctx_destroy(ctx); + fail: + TEST_FAIL(); + return TEST_RC_FAIL; +} + +/* + * A join or a leave opens a fresh window, so none divides the bytes + * one population offered by the count of another. An unchanged count + * leaves the running window alone. + */ +static int test_mb_ecn_flow_count_restarts_window(void) +{ + struct mb_ecn_ctx * ctx; + uint64_t rate = 1000000; + + TEST_START(); + + ctx = mk_ctx(); + if (ctx == NULL) { + printf("Failed to create context.\n"); + goto fail; + } + + ctx->rate = rate; + ctx->snd_flows = 2; + ctx->snd_win = MS; + ctx->snd_byt = 12345; + ctx->snd_r0 = 7; + + mb_ecn_flows(ctx, 5, 8 * MS); + + if (ctx->snd_flows != 5 || ctx->snd_byt != 0 + || ctx->snd_win != 8 * MS || ctx->snd_r0 != rate) { + printf("count change left a stale window: flows=%zu " + "byt=%" PRIu64 " win=%" PRIu64 " r0=%" PRIu64 + ".\n", ctx->snd_flows, ctx->snd_byt, + ctx->snd_win, ctx->snd_r0); goto fail_ctx; } - if (ctx->rate <= r0 - gap) { - printf("washout reversed a ramp: %" PRIu64 ".\n", ctx->rate); + ctx->snd_byt = 999; + + mb_ecn_flows(ctx, 5, 20 * MS); + + if (ctx->snd_byt != 999 || ctx->snd_win != 8 * MS) { + printf("unchanged count restarted the window.\n"); goto fail_ctx; } - if (ctx->r_bkt != ctx->rate || ctx->wash_acc != 0) { - printf("washout did not reset the bucket.\n"); + /* An empty context still measures a single sender. */ + mb_ecn_flows(ctx, 0, 30 * MS); + + if (ctx->snd_flows != 1) { + printf("zero flows did not floor at one: %zu.\n", + ctx->snd_flows); goto fail_ctx; } - /* Full bucket, rate trails: add a quarter of the gap (symmetric). */ - ctx->rate = r0; - ctx->r_bkt = r0 + gap; - ctx->wash_acc = 0; - mb_ecn_washout(ctx, MS, CA_WASH_BKT); - if (ctx->rate != r0 + (gap >> CA_WASH_SHFT)) { - printf("bucket up: got %" PRIu64 ".\n", ctx->rate); + mb_ecn_ctx_destroy(ctx); + + TEST_SUCCESS(); + + return TEST_RC_SUCCESS; + fail_ctx: + mb_ecn_ctx_destroy(ctx); + fail: + TEST_FAIL(); + return TEST_RC_FAIL; +} + +/* + * The ceiling must land where a window of the delivered rate reads + * backlogged again: a context clamped above that level can never + * leave the clamp, and loses its capacity floor with it. + */ +static int test_mb_ecn_ceiling_clears_backlog(void) +{ + struct mb_ecn_ctx * ctx; + uint64_t x = 1 << 20; + + TEST_START(); + + ctx = mk_ctx(); + if (ctx == NULL) { + printf("Failed to create context.\n"); + goto fail; + } + + ctx->backlogged = false; + ctx->snd_rate = x; + ctx->rate = 100 * x; + ctx->rate_min = CA_RATE_MIN; + + mb_ecn_ceiling(ctx); + + if (ctx->rate >= 100 * x) { + printf("ceiling did not bind: %" PRIu64 ".\n", ctx->rate); goto fail_ctx; } - /* Sparse step: reset to the current rate, keep the cut. */ - ctx->rate = r0; - ctx->r_bkt = r0 - gap; - ctx->wash_acc = CA_WASH_BKT / 2; - mb_ecn_washout(ctx, CA_DT_CAP + 1, MS); - if (ctx->rate != r0 || ctx->r_bkt != r0 || ctx->wash_acc != 0) { - printf("sparse step did not reset the bucket.\n"); + /* One window delivering x, with the pacer deferring nothing. */ + ctx->snd_r0 = ctx->rate; + ctx->snd_flows = 1; + ctx->snd_win = 0; + ctx->snd_byt = x; + ctx->snd_pac = 0; + + mb_ecn_win(ctx, BILLION); + + if (!ctx->backlogged) { + printf("clamped at %" PRIu64 " cannot clear on %" PRIu64 + ".\n", ctx->snd_r0, x); goto fail_ctx; } @@ -2868,15 +3098,15 @@ int mb_ecn_test(int argc, (void) argv; ret |= test_mb_ecn_ctx_create_destroy(); + ret |= test_mb_ecn_init_window(); ret |= test_mb_ecn_calc_ecn(); ret |= test_mb_ecn_rcv_onset_immediate(); - ret |= test_mb_ecn_rcv_window_mean(); ret |= test_mb_ecn_rcv_rate_independent(); ret |= test_mb_ecn_rcv_size_fair(); ret |= test_mb_ecn_rcv_release_exact_zero(); ret |= test_mb_ecn_rcv_gap_restart(); + ret |= test_mb_ecn_rcv_gap_floor(); ret |= test_mb_ecn_rcv_accum_bounds(); - ret |= test_mb_ecn_rcv_window_holds_target(); ret |= test_mb_ecn_rcv_window_clip_bounds(); ret |= test_mb_ecn_rcv_slow_window(); ret |= test_mb_ecn_rcv_no_overflow_highrate(); @@ -2885,8 +3115,9 @@ int mb_ecn_test(int argc, ret |= test_mb_ecn_dt_scaling_invariant(); ret |= test_mb_ecn_probe_scale_invariant(); ret |= test_mb_ecn_multiplicative_decrease(); + ret |= test_mb_ecn_ai_hold_release(); ret |= test_mb_ecn_fixed_point(); - ret |= test_mb_ecn_lead_cut(); + ret |= test_mb_ecn_lead_symmetric(); ret |= test_mb_ecn_slow_start_local_brake(); ret |= test_mb_ecn_slow_start_clean_ramp(); ret |= test_mb_ecn_starved_decrease_escape(); @@ -2917,7 +3148,9 @@ int mb_ecn_test(int argc, ret |= test_mb_ecn_first_send_warmup(); ret |= test_mb_ecn_two_flow_converge(); ret |= test_mb_ecn_ramp_overshoot_grows_with_rtt(); - ret |= test_mb_ecn_washout_bucket(); + ret |= test_mb_ecn_shared_ctx_offered_per_flow(); + ret |= test_mb_ecn_flow_count_restarts_window(); + ret |= test_mb_ecn_ceiling_clears_backlog(); return ret; } |