When to Preempt? Age of Information Minimization under Link Capacity Constraint

Boyu Wang, Songtao Feng, Jing Yang

Abstract

In this paper, we consider a scenario where a source continuously monitors an object and sends time-stamped status updates to a destination through a rate-limited link. We assume updates arrive randomly at the source according to a Bernoulli process. Due to the link capacity constraint, it takes multiple time slots for the source to complete the transmission of an update. Therefore, when a new update arrives at the source during the transmission of another update, the source needs to decide whether to skip the new arrival or to switch to it, in order to minimize the expected average age of information (AoI) at the destination. We start with the setting where all updates are of the same size, and prove that within a broadly defined class of online policies, the optimal policy should be a renewal policy, and has a sequential switching property. We then show that the optimal decision of the source in any time slot has threshold structures, and only depends on the age of the update being transmitted and the AoI at the destination. We then consider the setting where updates are of different sizes, and show that the optimal Markovian policy also has a multiple-threshold structure. For each of the settings, we explicitly identify the thresholds by formulating the problem as a Markov Decision Process (MDP), and solve it through value iteration. Special structural properties of the corresponding optimal policy are utilized to reduce the computational complexity of the value iteration algorithm.

Introduction

In real-time monitoring systems, such as power grids or autonomous vehicles, data freshness is paramount. The Age of Information (AoI) metric quantifies this freshness by measuring the time elapsed since the generation of the most recently received update. While many models assume instantaneous transmission, real-world links are often rate-limited, requiring multiple time slots to deliver a single update.

The evolution of Age of Information (AoI) over time, illustrating the impact of update arrivals and transmission delays.

This constraint introduces a fundamental dilemma: if a new update arrives while a previous one is still being transmitted, should the system finish the current transmission or preempt it for the fresher data? Preemption promises a fresher update later but risks wasting the work already done on the current packet.

Methodology

The researchers modeled the problem as a Markov Decision Process (MDP). They analyzed two primary scenarios: uniform update sizes, where every packet takes exactly $d$ time slots to send, and non-uniform update sizes, where packets have varying transmission times following a known distribution.

To find the optimal policy, the authors utilized Value Iteration. By proving that the optimal policy follows a specific threshold structure—for instance, deciding not to switch if a current packet is nearly finished—they developed a "Structured Value Iteration" algorithm. This approach significantly reduces computational complexity compared to standard methods by narrowing the search space for optimal decisions.

Key Insights and Structural Properties

The study reveals several critical properties of optimal status update policies:

  • Sequential Switching Property: For uniform update sizes, the authors proved that if the optimal decision is to skip a new arrival, the source should skip all subsequent arrivals until the current transmission is finished. You don't "change your mind" halfway through a skip.
  • Dynamic Thresholds: The decision to switch is not static; it depends on both the current AoI at the destination and the remaining transmission time (or age) of the active update.
  • Size Bias: In the non-uniform case, the source is more likely to switch to smaller packets. A smaller packet can be delivered faster, resetting the AoI clock sooner even if it is not significantly younger than the current one.
  • The Danger of "Always Switch": A preemptive "Always Switch" policy, while often optimal in simpler queueing models, performs poorly here. At high arrival rates, it causes the transmitter to constantly restart, leading to a "starvation" effect where no updates ever reach the destination.

Performance Results

Numerical simulations demonstrate that the proposed optimal threshold policy consistently outperforms common baselines, such as "Always Skip" (finishing every packet started) and "Always Switch."

Performance comparison of the optimal policy against "Always Skip" and "Always Switch" strategies across different arrival probabilities.

As illustrated in the figure, the advantage of the optimal policy is most pronounced at moderate arrival rates. When arrivals are rare, choices are infrequent. Conversely, at very high arrival rates, the "Always Skip" policy becomes nearly optimal because a fresh packet is almost guaranteed to be available immediately after the current transmission completes. Notably, the "Always Switch" policy's performance degrades significantly as arrival probability increases due to the aforementioned starvation effect.

Conclusion

This research provides a rigorous framework for minimizing AoI under link capacity constraints. By identifying the threshold-based structure of the optimal policy, the authors offer a practical and efficient solution for managing status updates in rate-limited environments. Future work may explore the impact of source buffers or multi-hop network configurations to further enhance data freshness in complex systems.

Summary updated

Abstract

In this paper, we consider a scenario where a source continuously monitors an object and sends time-stamped status updates to a destination through a rate-limited link. We assume updates arrive randomly at the source according to a Bernoulli process. Due to the link capacity constraint, it takes multiple time slots for the source to complete the transmission of an update. Therefore, when a new update arrives at the source during the transmission of another update, the source needs to decide whether to skip the new arrival or to switch to it, in order to minimize the expected average age of information (AoI) at the destination. We start with the setting where all updates are of the same size, and prove that within a broadly defined class of online policies, the optimal policy should be a renewal policy, and has a sequential switching property. We then show that the optimal decision of the source in any time slot has threshold structures, and only depends on the age of the update being transmitted and the AoI at the destination. We then consider the setting where updates are of different sizes, and show that the optimal Markovian policy also has a multiple-threshold structure. For each of the settings, we explicitly identify the thresholds by formulating the problem as a Markov Decision Process (MDP), and solve it through value iteration. Special structural properties of the corresponding optimal policy are utilized to reduce the computational complexity of the value iteration algorithm.
BibTeX
@article{wang2019when,
  author = {Boyu Wang and Songtao Feng and Jing Yang},
  title = {{When to Preempt? Age of Information Minimization under Link Capacity Constraint}},
  journal = {J. Commun. Networks},
  year = {2019},
  url = {https://openreview.net/forum?id=XCeKkzf6fu},
}
Figure