Turning delay variance from a liability into a strategic advantage for information freshness in real-time networks.
"Lazy is timely" has been the mantra for Age of Information (AoI). But when network delays have heavy tails, waiting passively for a packet to arrive can be disastrous.
Existing non-preemptive policies suffer from Head-of-Line blocking. Once a packet enters service, the system is stuck waiting, even if the delay becomes excessively long (common in Pareto or Log-Normal distributions).
We introduce TAILOR (TAIL-aware Optimal pReemption). By intelligently preempting stale updates, we cut the heavy tail, achieving up to a 30x reduction in average AoI cost.
We model a continuous-time status update system as an impulse-controlled Piecewise-Deterministic Markov Process (PDMP). The controller has two levers:
Deciding when to submit a fresh update when the channel is free. Usually involves waiting ("Lazy").
Deciding when to abort an ongoing transmission to restart with a fresher packet, based on the current service age.
Source
Destination
Try following the optimal policy: Wait if AoI is low, Sample when prompted, and Preempt if service takes too long.
We formulated the system as an impulse-controlled PDMP and solved it using coupled integral average-cost optimality equations (ACOE).
Treats AoI as a drifting state. Sampling and Preemption are instantaneous "impulses" with associated costs ($\kappa_s, \kappa_p$).
A key invariance collapses busy-phase dynamics. Preemption reduces to an Optimal Stopping Problem against the random completion time.
We developed a specialized algorithm with "Heavy-Tail Acceleration" (hybrid grid + far-field linear closure) to solve for the optimal policy numerically.
Simulations under Pareto and Log-Normal service times.
Lower is better. Note the massive gap for Log-Normal $L_2$.
| Service Dist. | TAILOR | AoI-NP [7] | Zero-Wait |
|---|---|---|---|
| Pareto II | 2.06 | 3.73 | 6.35 |
| Log-Normal ($L_1$) | 1.99 | 16.0 | 56.8 |
| Log-Normal ($L_2$) | 1.77 | 53.5 | 524 |
Usually, high variance hurts performance. However, with preemption, higher variance (Tail $L_2$ vs $L_1$) actually reduced the cost for TAILOR (1.99 $\to$ 1.77). Preemption "clips" the heavy tail, exploiting the variability to find short service times.