Certifying Playback-Speed Controllers for Satellite Video Against Every Outage and Every Bitrate Algorithm

Video players on Starlink-style satellite links freeze when the dish switches satellites, which happens roughly every 15 seconds. The best current fix is SARA. It is a thin software layer that wraps an existing bitrate algorithm. When it predicts a switch, it slows playback slightly and feeds the inner algorithm deflated buffer and throughput numbers, so the player banks extra video in advance. SARA works well on average. It gives no guarantee, though, and the outage distribution has a long tail that reaches 31 seconds. This note proposes a way to prove, before deployment, that such a wrapper never lets the buffer run dry. The proof should cover every outage pattern inside a stated envelope, and it should hold whatever bitrate algorithm sits inside the wrapper.

The tool for this comes from programming-language verification. Game semantics models a program fragment as one player in a dialogue with its unknown surroundings. For certain restricted languages, the set of all possible dialogues can be compiled into an automaton, meaning a finite machine whose language can be checked mechanically. The key observation is that a playback-rate wrapper is exactly an open program: code with unresolved pieces. It has two unknowns. One is the network, which decides when outages happen. The other is the inner bitrate algorithm, which the wrapper calls but does not define. Game semantics was built to reason about code whose collaborators are unspecified. We would use it to certify the wrapper once, for all inner algorithms. A cheap filter stage would first discard hopeless controller settings, in the spirit of the necessary-condition filters used to search huge catalogues of geometric objects. The exact but expensive check then runs only on the survivors.

Core Claim

Once buffer level, playback speed and outage duration are quantized into finite types, a wrapper of this kind falls inside language fragments where checking behaviour against all environments is decidable. Rounding is chosen conservatively: buffer rounds down, outage length rounds up, and the application-layer stall multiplier rounds up. With that rounding, a certificate for the quantized model implies a certificate for the real player.

This gives three results that neither simulation nor average-case tuning can give:

  1. The largest outage length $L^*$ a wrapper provably survives, given a minimum spacing $G$ between outages.
  2. A concrete counterexample outage sequence plus inner-algorithm behaviour whenever certification fails.
  3. For the probabilistic variant, the exact stall probability under a quantized outage distribution fitted to measured traces.

The claim is only worth making if these outputs differ from what a back-of-envelope buffer calculation or trace-driven testing would give. The experiments are built to test that directly.

What the Directions Contribute

The application regime (supplies the problem and the data). Toward Robust Live Streaming over LEO Satellite Constellations and its journal version Robust Live Streaming over LEO Satellite Constellations provide three things:

  • SARA itself, which uses particle swarm optimization to pick speeds between 0.95× and 1.03× and to pick the input-scaling factors.
  • 3,755 measured outages, of which 87.33% last under 2 seconds and the longest lasts 31 seconds.
  • The finding that a 1-second physical outage causes about 3.4 seconds of application disruption.

Those papers motivate the work, because they document the heavy tail and supply no guarantee. We do not replace their outage predictor. We certify what happens when its forecast is wrong.

The perceptual constraint. Drop or Stop found that 0.9× playback is statistically indistinguishable from normal speed (differential opinion score 4.8/5). It also found a cliff at 0.7× (opinion score 2.7, the same as a 0.5-second stall), and that ramping gradually at 0.05/s recovers 0.7 points. These results fix the speed alphabet and the allowed slopes in our model. The same paper reports that tolerance depends on content, with dialogue scenes the worst. We therefore also certify under a stricter speed floor.

The group-playback extension. PREPARE controls bitrate switching for several clients with an unverified finite state machine. That makes it a second, already finite-state target.

The core mechanism (supplies the method). Four papers provide the verification machinery:

  • Third-order Idealized Algol with iteration is decidable shows that programs with loops and calls to unknown functions compile to visibly pushdown automata, which are automata whose stack operations are tied to call and return symbols.
  • HOMER implements equivalence checking with counterexample generation on top of that result. - Algorithmic probabilistic game semantics translates open probabilistic programs into probabilistic automata whose equivalence can be decided by linear algebra.

  • APEX implements that translation with state-reduction steps and scales Dining Cryptographers to 800 participants.

The hard limit (constrains the method). These same papers restrict decidability to finite ground types and first-order probabilistic types. This is the tension the file calls out: real buffers are continuous. Our contribution sits exactly at that boundary. We build a sound abstraction, one whose guarantees are guaranteed to transfer to the real system. We do not attempt a fully abstract one.

The search pattern. From combinatorial candidate screening we borrow the idea of cheap necessary conditions before expensive exact checks. Necessary conditions on Calabi-Yau manifolds for large volume vacua and New large volume Calabi-Yau threefolds use this pattern to cut a catalogue of 473,800,776 objects down to a small set that can be checked exactly. Our candidate space is smaller: all combinations of speed tiers, ramp slopes, buffer thresholds and scaling factors. Each exact check, however, is costly.

Crossing matchings (a calibration testbed only). Perfect Matchings with Crossings asks whether a point set has a perfect matching with exactly $k$ crossings. It shows the answer is always yes for small $k$, but beyond about $n^2/64$ there can be gaps, including a 30-point set with a 105-crossing matching and none with 103 or 104. We use exact-$k$ existence on the small point sets from the order-type database as a problem with known answers. Running the same screening pipeline there tests whether our filters ever wrongly discard a feasible candidate. We make no claim to advance the geometry.

Research Program

The model. The wrapper is written in a finitary Idealized-Algol-style language with three parts:

  • a main loop over 100 ms ticks;
  • a local buffer counter in tokens, capped at a bounded size;
  • a speed register over tiers such as 0.90, 0.95, 1.00 and 1.03.

Fractional drain is tracked with bounded residue counters, so 0.95× drains 19 tokens per 20 ticks. The model has two free identifiers:

  • net, which the environment answers each tick with "delivering" or "outage";
  • abr(buffer, throughput), which the environment answers with one of the four bitrates used in the SARA benchmark.

Because abr is left unspecified, the automaton quantifies over every inner algorithm, including adversarial ones. This makes the certificate stronger than one for BBA or Pensieve alone.

The outage envelope. Outage patterns are constrained by a small observer automaton with three parameters: maximum outage length $L$, minimum spacing $G$, and an application multiplier $m$. Here $m$ is set to 3.4 from the measurements, and conservatively higher in sensitivity runs.

The checks. The safety question is whether the product of the wrapper and the envelope can reach the stall move. HOMER-style complementation and emptiness checking decide this and return a witness trace when the answer is yes. For the probabilistic question, the envelope becomes a quantized fit to the measured duration histogram, and the check follows the APEX approach.

The screening stage. The first filter is a fluid-buffer necessary condition. Banking during a slowdown of length $T$ at speed $\beta$ yields $(1-\beta)T$ seconds of extra buffer. So a candidate can only survive outage length $L$ if

$$B_{\min} + (1-\beta)T \ge mL,$$

where $B_{\min}$ is the lowest buffer the candidate's thresholds permit before an outage. Two further filters are monotonicity invariants: raising $G$ or lowering $L$ never breaks a certificate. Together these let bisection over $L$ replace exhaustive checking. The pipeline outputs, for each candidate, the certified $L^*(G)$ and a Pareto frontier of certified outage tolerance against modelled bitrate.

Baselines

The naive reference: plain bitrate algorithms. BBA, RobustMPC, BOLA and Pensieve run with no speed control on the SARA benchmark: Big Buck Bunny at 1000/2500/5000/8000 kbps with 500 ms segments, replayed over the Starlink outage traces. This sets the floor for rebuffering and bitrate. Each is also run through our checker with abr fixed to that algorithm, to report its certified $L^*$. We expect that value to be near the starting buffer.

The strongest existing method: SARA. SARA wraps the same six inner algorithms. The SARA paper reports a 39.41% reduction in average rebuffering time and a 21.41% reduction in rebuffering frequency across those algorithms, at a 0.13% bitrate cost. We re-run SARA's particle swarm tuning on the same traces with the same wall-clock budget our screening pipeline uses.

Beating it has two parts:

  • The certified wrapper must match SARA's average rebuffering on real traces within its trace-to-trace variance.
  • It must provably survive a strictly larger $L^*$, and SARA's own tuned setting must yield checker counterexamples that actually stall when replayed in the trace simulator.

If our certified wrapper loses more than a few percent of bitrate relative to SARA, we report the cost of certification rather than claim a win.

The fluid-bound heuristic. This controller is tuned only with the one-line inequality above. It is the natural "no automata needed" competitor.

The ablation that isolates open-program reasoning. We compare certifying the wrapper once over the unspecified abr with certifying it separately for each fixed inner algorithm. The first shows whether a single certificate generalizes. The second shows how much conservatism the universal quantifier costs.

The probabilistic baseline. For stall-probability estimates, the baseline is Monte Carlo simulation with matched compute. No reported result exists on Lacuna for exact stall probabilities or formal certificates of any bitrate controller, so our numbers there have no published comparison point.

Why not just…?

Why not just replay the traces, or stress-test with synthetic long outages? Testing only covers the sequences someone thought to generate. The dangerous cases combine a long outage with an inner algorithm that picked a high bitrate just before it. That combination is a joint choice of two unknowns, and random traces rarely hit it. Experiment E2 settles this. We count how many checker-found counterexamples appear in 10,000 random stress traces with matched compute. If random testing finds nearly all of them, the verification layer is not earning its cost, and we would say so.

Why not just use the fluid-buffer inequality as the guarantee? This is the most serious threat. For a wrapper with a single slowdown and no bitrate interaction, the inequality may be essentially exact. Where we expect it to fail is in:

  • repeated outages every 15 seconds, before the buffer refills;
  • losses from 500 ms segment boundaries;
  • the inner algorithm reacting to deflated inputs by switching bitrate mid-bank.

E3 reports the gap between $L^*$ from the fluid bound and from the checker across the candidate grid. If the gap stays within one quantization step, we narrow the claim to the probabilistic and counterexample outputs.

Why not just train a reinforcement-learning controller with a stall penalty? Q-learning and actor-learner methods do help with search. For example, Generating Triangulations and Fibrations with Reinforcement Learning needed 33,148 steps against 41,902 for a random walk. A learned policy still offers no bound on tail outages. It can be treated as one more inner abr, and our universal certificate covers it without retraining. We include a Pensieve-wrapped run to show this.

Proposed Experiments

E1: scalability. We measure checker time and automaton size as the buffer cap grows from 2 to 20 seconds at 100 ms resolution. The target is certifying a realistic 10-second cap on one workstation, which is comparable to the scale APEX reached.

E2: auditing SARA. We certify the published SARA settings, extract counterexamples, and replay them in the trace simulator. The decisive outcome is at least one confirmed stall with an outage length inside the measured distribution.

E3: screening and the certified frontier. We screen the parameter grid, report what fraction of candidates each filter prunes, and compare the certified frontier against SARA and the fluid-bound controller on the Starlink traces. Speed floors are 0.90 (imperceptible), and 0.95 for dialogue-heavy content, following Drop or Stop.

E4: exact stall probability. We compare exact stall probability under the fitted outage histogram with Monte Carlo estimates. Agreement validates the abstraction, and the exact value should resolve rare-event tails that Monte Carlo cannot.

E5: PREPARE. We certify PREPARE's state machine against an adversarial two-client bandwidth split, to test whether the method carries over to multi-client control.

E6: calibration of the screening filters. We run the screen-then-exact-check pipeline on exact-$k$ crossing matchings for all order types with $n \le 10$, where brute force gives ground truth. The filters must never discard a feasible $(point set, k)$ pair, and the pipeline must reproduce the reported case where a wheel configuration beats convex position at $k=6$. A false prune here would show our filter design is unsound, and we would revisit the analogous filters in E3.