Preemptive Scheduling for Age of Information Minimization

154 concepts79 papers1 proposal

Traditional queuing theory optimizes for throughput (maximizing packets delivered per second) or delay (minimizing the time a packet spends in the system). However, in real-time monitoring applications—such as autonomous driving, sensor networks, or cloud-based tracking—the critical metric is data freshness. This is formalized as the Age of Information (AoI), defined as the time elapsed since the most recently received status update was generated.

Optimizing for AoI requires a fundamental paradigm shift. In standard networks, queues act as buffers to prevent packet loss. But for information freshness, a packet waiting in a queue is actively aging. By the time it is delivered, it may already be obsolete. To solve this, researchers have developed age-based scheduling and preemption strategies that prioritize the newest data, often by intentionally discarding older packets.

The Intuition of Discarding and Zero-Buffer Queues

Why would a network intentionally drop data? In traditional systems, dropping a packet wastes resources and lowers throughput. However, Huang et al. demonstrated that buffer-limited discarding mechanisms—which drop incoming packets if the server is busy—often achieve significantly better information freshness than traditional First-In-First-Out (FIFO) queues.

When a queue is allowed to grow, packets stall behind one another, accumulating queuing delay. By the time the server finishes processing the backlog, every update delivered is already stale. As Maatouk et al. show, a zero-buffer policy (such as an M/M/1/1 queue) ensures that the system never wastes time on a backlog; it either processes an update immediately or waits for a fresher one. Even in multi-class systems with prioritized streams, Maatouk et al. proved that at high arrival rates, discarding preempted lower-priority packets rather than buffering them yields superior overall freshness.

Preemption and the Memoryless Property

If a new, fresher packet arrives while the server is currently transmitting an older one, should the system preempt the current transmission or finish it? This is the preemption-completion trade-off.

The answer depends heavily on the nature of the service time distribution. Bedewy et al. proved that when service times are exponential (memoryless), a preemptive policy that always switches to the most recently generated packet is stochastically optimal for minimizing information age. Because the distribution is memoryless, the remaining time required to finish the current stale packet is identical to the time required to start and finish a brand-new packet. Since both choices take the same expected time to complete, it is always optimal to spend that time delivering the fresher data.

Conversely, if service times are near-deterministic, preemption can backfire. Najm et al. showed that in stable, deterministic environments, high update rates combined with preemption can cause a cascade of interruptions. The server repeatedly abandons tasks that are nearly finished, preventing any update from successfully reaching the destination. Thus, the optimal decision boundary depends on how much progress has been made and the packet size, a concept formalized by Wang et al. through the sequential preemption property.

Scaling to Multi-Source and Multi-Hop Networks

When a single channel or relay must serve multiple independent data sources, scheduling becomes a question of resource allocation. How do we choose which source to update?

The optimal strategy is often a greedy, age-based priority rule. Bedewy et al. demonstrated that prioritizing the source with the highest current age (Maximum Age First) minimizes both average and peak AoI across the system. For symmetric wireless networks, Duan proved that this greedy index policy is optimal, removing the need for complex centralized optimization.

In multi-hop networks, where updates must traverse several nodes to reach a destination, managing out-of-order arrivals due to network jitter becomes critical. Bedewy et al. showed that a local Last-Generated First-Served (LGFS) policy is globally optimal. By tracking generation timestamps rather than arrival times, independent nodes can immediately drop stale packets that arrive out of order, ensuring that network resources are exclusively preserved for propagating the freshest information end-to-end (Bedewy et al.).

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 79 papers
  2. Version 1 · 2026-10-04 · 98 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_maximum_age_first_scheduling_e6cba495,
  title = {maximum age first scheduling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/maximum-age-first-scheduling/rdr_e6cba49566054bee844b50a0a5e1dc27},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_maximum_age_first_scheduling_e6cba495_v2,
  title = {maximum age first scheduling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/maximum-age-first-scheduling/rdr_e6cba49566054bee844b50a0a5e1dc27/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake