Scheduling Frame Deadlines with Predictive Distributions in Cloud Gaming

In mobile cloud gaming, a remote server runs the game and streams video to a phone. Much of the delay a player feels does not come from the network. It comes from the display timing signal, VSync, which releases frames only at fixed ticks, every 16.6 ms at 60 Hz. A frame that arrives 0.5 ms late waits for the next tick, so it costs a whole extra period. The strongest current system, LoopTailor, predicts how long each pipeline stage will take and shifts the tick boundaries to match. It still reports a "butterfly effect": jitter under 2 ms can cascade into missed deadlines (Dissecting and Streamlining the Interactive Loop of Mobile Cloud Gaming). Our diagnosis is that LoopTailor discards information at one specific point. Its latency predictor gives a single number, and the scheduler turns that number into a hard hit-or-miss decision. The penalty for a wrong guess is a step function, so the uncertainty around the guess is exactly what decides the outcome, and the single number throws it away.

We propose to keep that uncertainty. The predictor will output a full distribution of arrival times for each stage. The scheduler will then pick each tick offset to minimize the expected latency after the tick has rounded it, rather than to match a point estimate. The core claim can be put to a colleague in two sentences. Missed deadlines in timing-aligned cloud gaming come less from inaccurate latency prediction than from collapsing a predictive distribution to one value before making a step-shaped decision. Choosing offsets by minimizing expected rounded latency under the full distribution should cut tail latency and miss rate, beyond what either a smoother point predictor or a tuned safety margin achieves.

Core Claim

Consider one alignment decision. A frame's arrival time $L$ at a stage is random. We choose an offset $\theta$ for the next tick. Here $T$ is the tick period (16.6 ms at 60 Hz) and $F$ is the predicted cumulative distribution of $L$ given the current context. If the frame arrives before $\theta$, it waits until $\theta$; otherwise it waits a further period. The expected delay contributed is then approximately

$$C(\theta) = \theta + T\,\bigl(1 - F(\theta)\bigr),$$

and the best offset satisfies $T f(\theta^*) = 1$, where $f$ is the predicted density, at the point where it is falling. Two consequences follow, and both can be tested.

First, the optimal offset is not a fixed quantile. It depends on the shape of the distribution. Contexts with bimodal arrival times, such as Wi-Fi retransmissions or encoder keyframes, call for quite different margins than contexts with tight unimodal ones. Any constant safety margin, and any fixed-quantile rule, is therefore suboptimal whenever the shape varies across contexts.

Second, a point predictor that is more accurate in mean squared error need not reduce misses. What matters is how much probability lies near the boundary, not how smooth the mean forecast is. The second consequence matters because the research file frames this gap as stair-step error in LoopTailor's regression trees. It proposes swapping in continuous piecewise-linear trees such as CLARITree, which fits continuous piecewise-linear regressors instead of piecewise-constant steps. We think that swap targets the wrong discretization. The damaging rounding is the deadline itself, applied downstream of the forecast. We include the CLARITree swap as an ablation precisely so this disagreement can be settled.

The Direction 2 literature supplies the motivation rather than the method. Thresholding continuous scores destroys power and confidence (AutoML Two-Sample Test). Single cutoffs hide multimodal and non-monotonic structure (Anaya et al.). Values near a cutoff get treated as categorically different (Walter et al.). In those settings the fix is to stop dichotomizing. In ours, the dichotomy is imposed by hardware and cannot be removed. The fix is instead to make the decision with the undichotomized distribution in hand.

Research Program

We will build three things.

The first is a probabilistic stage-latency predictor. It is a conditional density model over per-stage times (game render, encode, network transit, decode, client compose). Its inputs are the same features LoopTailor uses: recent stage timings, frame size, and link type. We will try quantile gradient-boosted trees and a small mixture-density network, and prefer the simpler one if the two tie. LoopTailor reconciles per-stage forecasts with MinT, a method that makes per-stage forecasts sum consistently to the end-to-end forecast. We will replace it with sampling from the joint of the stage distributions, because MinT reconciles means and not distribution shapes.

The second is a scheduler for the multi-tick chain. LoopTailor aligns three ticks: VSync1 on the server, VSync4, and VSync5 on the client. A miss at one tick changes the arrival time at the next. We will optimize the offsets jointly by Monte Carlo over sampled stage times, which is cheap enough to run every frame. The first step will be checked against the closed-form condition above.

The third is a counterfactual evaluator. Given a log of true per-stage arrival times, the rounded latency under any offset policy can be computed exactly. This holds as long as shifting a tick does not change when upstream frames arrive. We will test that assumption on the live testbed, measuring how often a shifted VSync1 changes render start times. The evaluator lets us compare many policies on identical traces before running live tests.

As a secondary extension, we will treat variable-refresh-rate client displays, which LoopTailor cannot control. In that setting the client tick becomes a continuous choice with its own cost. We will evaluate this only where the hardware allows the scheduler to observe its timing.

The data come from a testbed we build, since X-MCG is commercial and not accessible to us. It will consist of an Android-emulator cloud gaming server with frame interception, in the spirit of LoopTailor's Game Frame Interceptor, plus a set of phones on Ethernet, Wi-Fi and LTE. Following A Measurement Study on Achieving Imperceptible Latency in Mobile Cloud Gaming, we will measure end-to-end latency with a hardware probe. We will log per-stage timestamps for every frame. We will also replay network delay traces with emulated jitter. If the Tencent START production traces used by Pudica are obtainable, we will replay their delay processes. Otherwise we will collect our own and say so plainly.

Baselines

The naive reference point is stock Android VSync with no alignment: frames simply wait for the next fixed tick at every stage. It shows how large the timing tax is on our testbed. LoopTailor found the existing platforms it measured at 112–403 ms interactive latency (Dissecting and Streamlining).

The strongest existing method is LoopTailor's Remote VSync Coordinator. It uses regression-tree latency prediction with MinT reconciliation and aligns VSync1, VSync4 and VSync5 to the point forecasts. LoopTailor reports 91 ms mean and 95 ms 99th-percentile interactive latency on X-MCG, and 76 ms mean non-network latency. Those numbers come from a platform we cannot reproduce. We will therefore reimplement the coordinator on our testbed, using the same features, the same training logs and the same hyperparameter search budget as our predictor, and compare on our own measurements. Beating it means lower 99th-percentile interactive latency and lower deadline-miss rate on the same traces, with mean latency no worse. We will use paired comparisons across sessions and pre-register the jitter regimes we test.

Three ablations isolate the key ingredient. The first replaces the regression trees with CLARITree-style continuous piecewise-linear trees, keeping point-forecast alignment. It tests the "stair-step error" explanation. The second applies a constant safety margin to LoopTailor's point forecast, with the margin tuned on held-out traces. It tests whether uncertainty matters at all. The third aligns to a single tuned quantile of our predictive distribution. It tests whether shape-dependent offsets beat a uniform quantile. The full method beats these only if it wins specifically in the high-jitter and multimodal regimes and roughly ties elsewhere, which is what the cost function predicts.

Why not just…?

Why not just use a smoother regression model, as the gap analysis suggests? Swapping in CLARITree would remove step artifacts in the forecast. But a perfect mean forecast still misses deadlines about half the time whenever the frame's arrival is symmetric around that forecast, because the deadline is set at the predicted mean. Our first ablation measures this directly. If the smoother point model closes most of the gap to our method, our central claim is wrong and we will report that.

Why not just add a tuned safety margin? This is the real threat. If arrival-time distributions have nearly the same shape across contexts, a constant margin or a fixed quantile approximates the optimum and our method adds complexity for little gain. The cost function says the gap should appear only when the shape varies, for example bimodal Wi-Fi delays against tight Ethernet delays. Our second and third ablations, stratified by link type and jitter level, will show whether such variation exists in practice. If it does not, the honest contribution narrows to "use a tuned quantile," which is still a cheap, useful finding.

Why not just use faster displays or edge servers? Higher refresh shrinks $T$ but keeps the step. The measurement study found 120 Hz, front-buffer rendering and 5G together saved only about 20 ms (Measurement Study). OpenRTiST found a roughly 100 ms device floor and persistent LTE jitter even with edge servers at 23 ms end-to-end. We will run every condition at both 60 and 120 Hz to show how much of the gain survives faster ticks.

Why not just fix the network with low-queuing congestion control? Pudica cuts frame delay and stalls by keeping queues near empty. That narrows the arrival distribution but does not remove decode and compositor variance. We treat it as complementary: we will run our scheduler both on top of a low-queuing sender and without one.

Decisive Checks

The first test is offline. On logged traces, the counterfactual evaluator must show our policy lowering expected rounded latency and miss rate relative to all three ablations in multimodal contexts. If it cannot do that offline, the live system will not either.

The second is a sanity check: measured miss rates should track the predicted values of $1 - F(\theta)$. This shows that the predictive distributions are calibrated, which the method depends on.

The third is live. On the testbed, with paired sessions across Ethernet, Wi-Fi and LTE under replayed jitter, we compare 99th-percentile interactive latency and miss rate against the reimplemented LoopTailor coordinator. Success means a statistically clear reduction in the high-jitter Wi-Fi and LTE strata, without mean regression. A null result in those strata would falsify the claim that discarding predictive uncertainty, rather than forecast resolution, drives the remaining misses.