Certifying Tail Latency from Finite Traces

Stochastic network calculus is a way of proving statements like "at most one packet in 100,000 will wait longer than 2 ms at this switch." It works by fitting a probabilistic model to measured traffic and then applying exponential tail inequalities, built from the traffic's moment generating function, to bound how often delays exceed a deadline. The bounds are only as trustworthy as the fitted model. In practice that model is estimated from a finite, bursty, autocorrelated trace, and the bound is reported as if its parameters were known exactly. The claimed violation probabilities, often $10^{-5}$ or smaller, describe events the trace may contain a handful of times or never. This is the rare-event problem that biostatisticians call low statistical power. A vaccine trial in a mild season accumulates too few infections to say anything about the live-attenuated vaccine (Gilbert et al.). In the same way, a one-hour packet trace may hold too few large bursts to support a $10^{-6}$ delay guarantee.

We propose to make stochastic network calculus bounds honest about sample size. Each certificate becomes a two-level statement: "delay exceeds $d$ with probability at most $\epsilon$, and this holds with confidence $1-\delta$ given the trace we saw." We also derive the companion quantity that is missing from the literature, which is how much trace is needed before a given $(d, \epsilon)$ guarantee can be certified at all. The core observation is that the tail inequality optimizes a free parameter. For very small $\epsilon$, that optimum moves to exactly the region where the moment generating function is estimated worst. The power limitation is therefore built into the method, not incidental to it.

Core Claim

A standard stochastic network calculus backlog or delay bound has the form

$$\epsilon(d) = \inf_{\theta>0} e^{-\theta d}\, K(\theta),$$

where $\theta$ is the free Chernoff parameter. $K(\theta)$ collects the moment generating functions $M_A(\theta)=\mathbb{E}[e^{\theta A}]$ of the arrival increments $A$ and the corresponding service terms. When $M_A$ is estimated from $n_{\text{eff}}$ effectively independent blocks of trace, the relative standard error of the estimate is roughly

$$\sqrt{\big(M_A(2\theta)/M_A(\theta)^2 - 1\big)/n_{\text{eff}}}.$$

This follows directly from the variance of $e^{\theta A}$. For bursty traffic the ratio $M_A(2\theta)/M_A(\theta)^2$ grows very fast in $\theta$. Small target $\epsilon$ pushes the optimal $\theta$ upward, so a plug-in certificate rests on its least reliable estimate.

Our claim has three parts. First, plug-in certificates computed from realistic trace lengths will fall short of their nominal guarantee measurably often, and the shortfall will be worst for long-range-dependent traffic. Long-range dependence shrinks $n_{\text{eff}}$ well below the packet count. Second, a confidence-qualified bound, which restricts $\theta$ to the range where the moment generating function is estimable and uses an upper confidence limit for $K(\theta)$, restores nominal coverage at a quantifiable cost in tightness. Third, inverting this bound gives a trace-length requirement $n_{\text{eff}}(d,\epsilon,\delta)$. Operators can check that requirement before trusting any certificate.

Relation to Prior Work

Two lines of work supply the machinery we audit.

dMAPAR-HMM builds a rich traffic model and derives its moment generating function in closed form. The model has two parts: a Markovian on-off process for burst timing, and an autoregressive hidden Markov model for packet sizes. Its parameters are fit with online expectation-maximization on MAWI and Huawei traces. The paper shows that Poisson models underestimate delay by orders of magnitude at high load. It treats the fitted parameters as exact, however, and a richer model has more parameters to estimate from the same trace. We reuse its moment generating function and add parameter uncertainty to it.

The stochastic traffic regulator of Boroujeny, Mark and Ephraim adjusts a per-packet burstiness parameter using empirical overshoot ratios. It explicitly assumes stationary, ergodic traffic, so that those ratios converge to the true probabilities. We ask a narrower question it leaves open: how many overshoots must be observed before the ratio is a usable proxy at the target $\epsilon$.

DLPF scheduling learns arrival rates over geometrically growing phases to reach near-optimal deadline-constrained forwarding. It has the same exposure in its short early phases. We treat it as a secondary test case.

Two systems motivate the problem as consumers of the bounds. HOLMES uses deterministic network calculus to keep an ICU model-serving pipeline within 200 ms. LPNS uses deterministic network calculus to bound virtualized NVMe latency below 25 µs on P5800X drives. Both pay for worst-case pessimism. Any move they make to stochastic bounds would inherit exactly the finite-sample question we study.

The clinical papers enter by analogy, not as an application domain. The FLUVACS trial and the small endoleak cohort (Kim et al.) show the failure mode we expect in network certificates: confusing "no violations seen" with "violations are rare." We deliberately do not pursue the file's suggestion of modeling clinical event accumulation with network calculus envelopes. Event-count projection in trials is a solved problem with Poisson and negative-binomial forecasting, and network calculus adds little there.

Research Program

The work has four components.

The first is the confidence-qualified bound. We split the trace into blocks whose length is chosen from the estimated autocorrelation or Hurst exponent. We then form upper confidence limits on $\log M_A(\theta)$, uniformly over a grid of $\theta$ values. For the empirical moment generating function we use a union bound over the grid. For parametric models such as dMAPAR-HMM we propagate profile-likelihood intervals through the closed-form expression. Finally we take the infimum only over $\theta$ values whose estimated relative error stays below a tolerance. Under the stated block-independence approximation, the result is a certificate valid with probability $1-\delta$.

The second is the trace-length law. We invert the bound to predict the $n_{\text{eff}}$ needed for a given $(d,\epsilon,\delta)$. We then check that prediction against the empirical trace length at which coverage reaches nominal.

The third is a power-aware regulator. We replace the regulator's raw overshoot ratio with an anytime-valid upper confidence sequence on the overshoot probability. This lets the regulator tell "within target" apart from "not enough evidence yet."

The fourth is a non-stationarity probe. We inject level shifts and burst-regime changes. This tells us whether the confidence machinery fails gracefully, by widening, or silently, by staying confident.

Baselines

The naive reference point is the plug-in certificate. It is the same tail inequality computed with point-estimated parameters, using the dMAPAR-HMM fit from dMAPAR-HMM and, separately, a Poisson/MAP fit. This is current practice, and every method gets the same trace prefix. It is "beaten" if its coverage falls clearly below $1-\epsilon$ while ours does not.

The strongest competitor on the coverage question is the moving-block bootstrap of the entire fit-and-bound pipeline. It is generic and needs no derivation, and it handles dependence if the block length is right. We run it with the same block length, the same trace, and a compute budget matched to ours in wall-clock time. It is beaten only if we achieve equal or better coverage with tighter or comparably tight bounds at lower cost. Alternatively, it is beaten if it under-covers at small $\epsilon$, because resampling cannot produce bursts larger than those observed.

The model-free reference is a Clopper-Pearson upper bound on the empirical exceedance frequency of simulated delay. It is valid but cannot certify anything below roughly $3/n_{\text{eff}}$.

The pessimistic reference is deterministic network calculus applied to the trace's observed maximum envelope, as LPNS and HOLMES do. We report how much capacity it requires relative to our certificate.

The key-ingredient ablation keeps the confidence limits but removes the restriction on $\theta$. This isolates whether the gain comes from refusing to extrapolate where the moment generating function is unestimable.

On reported numbers: the file gives qualitative fidelity claims for dMAPAR-HMM and the Poisson underestimation, with no numerical bound errors. There is no reported result found on Lacuna for coverage or confidence of any stochastic network calculus certificate. The concrete reported bound we can anchor capacity comparisons to is LPNS's under 25 µs (P5800X) and under 90 µs (PM1735) under FIO workloads.

Why not just…?

Why not just bootstrap the existing pipeline? This is the real threat. It may be enough for moderate $\epsilon$. Its known weakness is that resampled traces never contain bursts beyond the observed maximum. That suggests it will under-cover exactly in the extrapolation regime that stochastic network calculus exists for. The head-to-head coverage curves across $\epsilon$ from $10^{-2}$ to $10^{-6}$ will settle this. If the bootstrap matches us throughout, the contribution narrows to the trace-length law and the diagnostic restriction on $\theta$, and we will say so.

Why not just measure the empirical delay tail and skip the model? Model-free binomial bounds are always valid, but they are vacuous below about $1/n_{\text{eff}}$. Certifying $10^{-6}$ that way would need millions of effectively independent blocks, far more than long-range-dependent traces supply. The Clopper-Pearson baseline will show where it stops being informative.

Why not just use extreme value theory on delays directly? Peaks-over-threshold fitting extrapolates tails too, and it has its own estimation-power problem. It also gives no compositional handle across hops or regulators. We include it as an additional baseline, reported for single-node delay only. The file contains no evidence on it either way.

Why not just add a safety margin or use deterministic calculus? A fixed margin has no principled size. Deterministic calculus is the over-provisioning that stochastic calculus was built to avoid. The capacity-ratio comparison above quantifies the cost.

Proposed Experiments

Ground truth requires knowing the true violation probability, so the core study uses long synthetic traces generated from dMAPAR-HMM processes fit to MAWI traces. On those traces, discrete-event simulation over $10^9$ or more packets gives near-exact tail probabilities. We then draw short prefixes, from minutes to hours, compute every certificate, and repeat over hundreds of prefixes. The metrics are coverage (the fraction of prefixes whose certified $\epsilon$ is at least the true one), tightness (certified over true $\epsilon$), and capacity needed to meet a $(d,\epsilon)$ target.

We repeat the analysis on raw MAWI segments, using a held-out multi-day trace as approximate ground truth, and on FIU storage server traces replayed through a single queue with LPNS-like service rates. The Huawei campus traces are internal and probably unavailable. The regulator and DLPF studies use the same synthetic generators with injected regime shifts.

The decisive checks are three. If plug-in certificates already achieve nominal coverage at realistic trace lengths, the premise is wrong and the project stops at a negative result. If our bound covers but is so loose that it needs as much capacity as deterministic calculus, the restriction on $\theta$ is too conservative and must be redesigned. If the predicted trace-length law tracks the empirical coverage threshold within a small factor across traffic types, operators gain a usable pre-deployment check. That outcome is the main deliverable.