PaperlayerView exact revision on arXiv

Source-linked AI summary

Minimizing the Age of Information through Queues

Ahmed M. Bedewy, Yin Sun, Ness B. Shroff

arXiv:1709.04956v4cs.IT

TL;DR

The paper addresses which queueing discipline minimizes age and the conditions under which minimum age is achievable. It develops LGFS-based scheduling policies and establishes age-optimality for exponential service times, with near-optimality for NBU service times, including replication.

  • Problem

    Prior studies cannot determine which queueing discipline minimizes age or under what conditions the minimum age is achievable.

  • Method

    The paper develops scheduling policies based on LGFS, including policies with replication, for systems where packets may arrive out of generation-time order.

  • Results

    For exponentially distributed service times, the proposed policies achieve age-optimality for any maximum replication degree; for NBU service times, LGFS policies with replication are near age-optimal.

  • Takeaways & Limitations

    The optimality result applies to the age process and any non-decreasing functional of it, while the proposed policies can also achieve throughput and delay optimality.

Abstract

from arXiv · show

In this paper, we investigate scheduling policies that minimize the age of information in single-hop queueing systems. We propose a Last-Generated, First-Serve (LGFS) scheduling policy, in which the packet with the earliest generation time is processed with the highest priority. If the service times are i.i.d. exponentially distributed, the preemptive LGFS policy is proven to be age-optimal in a stochastic ordering sense. If the service times are i.i.d. and satisfy a New-Better-than-Used (NBU) distributional property, the non-preemptive LGFS policy is shown to be within a constant gap from the optimum age performance. These age-optimality results are quite general: (i) They hold for arbitrary packet generation times and arrival times (including out-of-order packet arrivals), (ii) They hold for multi-server packet scheduling with the possibility of replicating a packet over multiple servers, (iii) They hold for minimizing not only the time-average age and mean peak age, but also for minimizing the age stochastic process and any non-decreasing functional of the age stochastic process. If the packet generation time is equal to packet arrival time, the LGFS policies reduce to the Last-Come, First-Serve (LCFS) policies. Hence, the age optimality results of LCFS-type policies are also established.

I. INTRODUCTION

The paper addresses which queueing discipline minimizes information age and when that minimum is achievable. It proposes LGFS and establishes broad optimality or near-optimality results across service distributions, system configurations, and age metrics.

  • Prior studies did not determine which queueing discipline minimizes age or the conditions under which minimum age is achievable.
  • LGFS prioritizes the packet with the earliest generation time.
  • With i.i.d. exponential service times, preemptive LGFS with replication minimizes the age process and every non-decreasing functional of it under arbitrary system parameters.The setting includes arbitrary generation and arrival times, out-of-order arrivals, server counts, replication degrees, and buffer sizes.
  • The results cover time-average age, average peak age, and time-average age-penalty functions, while extending to multi-server systems and packet replication.
  • With i.i.d. NBU service times, non-preemptive LGFS with replication is within a constant gap of optimum average age, independent of the stated system parameters.
  • When generation and arrival orders coincide, LGFS reduces to LCFS, establishing age-optimality or near-optimality results for corresponding LCFS policies.
  • For exponential service times, preemptive LGFS with replication is also throughput- and delay-optimal; without replication and with NBU service, non-preemptive LGFS is optimal among non-preemptive policies.

III. MODEL AND FORMULATION

The paper establishes notation for conditional distributions, vector and stochastic orders, and stochastic-process ordering used in its proofs.

  • A. Notations and Definitions: Conditional notation [Z|A] and E[Z|A] denotes the conditional distribution and expectation of Z given event A.
  • A. Notations and Definitions: Vectors are ordered componentwise, and x[i] denotes the i-th largest component of vector x.
  • A. Notations and Definitions: An upper set contains every vector y satisfying y ≥ x whenever it contains x.
  • A. Notations and Definitions: Univariate and multivariate stochastic orders compare random variables or vectors through probabilities assigned to upper sets.
  • A. Notations and Definitions: A stochastic process X is smaller than Y when every finite-dimensional vector of X is stochastically smaller than the corresponding vector of Y.
  • B. Preliminary Propositions: If independent random vectors satisfy componentwise stochastic orders, an increasing function preserves the resulting stochastic order.
  • B. Preliminary Propositions: Conditional stochastic ordering can be established by comparing conditional distributions for each value of the conditioning variable.
  • B. Preliminary Propositions: The coupling characterization states that process stochastic ordering is equivalent to constructing same-space versions ordered pointwise.

C. Queueing System Model

The model is a multi-server update queue with arbitrary generation and arrival times, finite or infinite buffering, and optional packet replication. Age is evaluated through stochastic and penalty-based criteria.

  • A packet may be replicated on at most r of m servers, and the first completed replica is valid while remaining replicas are cancelled.
  • Generation and arrival sequences are arbitrary, so packets may reach the queue out of generation order.
  • Each packet has generation time s_i, arrival time a_i, and delivery time c_i, with s_i ≤ a_i ≤ c_i.
  • The buffer size B may be infinite, finite, or zero; packets arriving to a full finite buffer may be dropped or replace queued packets.
  • Service times are i.i.d. across servers and assigned packets, while policy decisions determine delivery times but not packet generation or arrival sequences.
  • The policy class Π_r includes causal and non-causal policies and expands with the allowed replication degree.
  • Preemptive policies may interrupt service, whereas non-preemptive policies continue processing until completion or cancellation.
  • Age is represented by the process Δ(t), and non-decreasing functionals include time-average age, average peak age, and age-penalty functions.

IV. AGE-OPTIMALITY RESULTS OF LGFS POLICIES

The paper defines LGFS scheduling and develops its replicated preemptive implementation. Under exponential service, the policy achieves broad age optimality, including across replication levels and several LCFS special cases.

  • LGFS serves the packet with the largest generation time first, whereas LCFS orders packets by arrival time.
  • The paper proposes preemptive Last-Generated, First-Serve with replication, or prmp-LGFS-R.
  • With replication, prmp-LGFS-R prioritizes fresher packets and distributes replicas across available servers subject to maximum degree r.
  • The policy is causal: scheduling decisions use system history and current state rather than future information.
  • The ordering result minimizes every non-decreasing functional of age, including time-average age, average peak age, and age-penalty functions.
  • For exponential service times, prmp-LGFS-R achieves age-process optimality within Π_r for arbitrary packet generation and arrival processes.
  • When r = m, prmp-LGFS-R is age-optimal against policies with any maximum replication degree, and its age performance is unchanged for B ≥ 0.
  • With ordered arrivals and no replication, the policy reduces to LCFS-S, which is age-optimal; ordered-arrival LGFS and LCFS have identical age performance.

1) Simulation Results:

Simulations compare age performance across traffic intensities, queue sizes, server counts, and replication degrees. They report advantages for prmp-LGFS-R and illustrate queue-size effects on competing policies.

  • The simulations use exponential service times with mean 1/μ = 1, Erlang-2 inter-generation times with mean 1/λ, and traffic intensity ρ = λ/mμ.
  • For m = 1, Figure 3 plots time-average age versus traffic intensity ρ across queue sizes B.
  • With ordered arrivals, prmp-LGFS-R achieves lower age than the cited FCFS policy and non-preemptive LGFS with B = 1.
  • Across the simulated replication settings, prmp-LGFS-R performs better than other policies in Π_r; at r = 2 it also outperforms plotted policies with r = 1 and r = 2.
  • Prmp-LGFS-R age performance remains unchanged with queue size B, whereas non-preemptive LGFS-R and FCFS vary with B.
  • FCFS with B = ∞ has average peak age that blows up at high traffic intensity, while FCFS with B = 10 remains high but bounded.

B. NBU Service Time Distributions

For NBU service times, the paper introduces non-preemptive LGFS with replication and establishes near age-optimality under broad queueing settings. The policy prioritizes fresh packets, uses bounded replication, and supports causal scheduling.

  • Policy: Non-prmp-LGFS-R extends LGFS to replicated multi-server queues without allowing packet preemption.Fresh packets can replace the stalest queued packet when a full buffer requires a drop decision.
  • Policy: The policy replicates packets across available idle servers, subject to maximum replication degree r, and cancels remaining copies after delivery.When servers become available, it prioritizes the queued packet with the largest generation time for replication.
  • Analysis: Non-prmp-LGFS-R is causal: its scheduling decisions use the system history and current state rather than future arrivals or generation times.The analysis compares its age with a lower bound based on packet assignment times instead of completion times.
  • Age guarantees: Under NBU service times, non-prmp-LGFS-R is within a constant age gap of the optimum average age for arbitrary generation and arrival sequences, server counts, replication degrees, and buffer sizes.The result applies across policies in Πm and remains near age-optimal compared with policies using any maximum replication degree.
  • Age guarantees: When packets arrive in generation order, replication is disallowed, and B = 1, LCFS-W and M/M/1/2* are near age-optimal under Theorem 12 conditions.This is the single-source reduction of the non-preemptive LGFS policy.

1) Simulation Results:

Simulations examine how traffic intensity, service-time variability, replication, and preemption affect average age in multi-server update systems. They show that replication can help under high variability, whereas preemption can become harmful for non-memoryless service times.

  • Preemption versus non-preemption: At high traffic intensity, the average age of preemptive LGFS with replication grows without bound under non-memoryless gamma service times.Frequent preemption replaces packets whose remaining service may be shorter than a new service time, reducing delivery frequency.
  • Age guarantees: At ρ = 1.8, the non-prmp-LGFS-R curves remain within E[X] = 1/µ = .5 of the age lower bound for r = 1 and r = 4.This matches the constant-gap guarantee in Theorem 12.
  • Replication: With gamma service times, non-prmp-LGFS-R using r = 4 outperforms r = 1 when the shape parameter K ≤12.5.The paper attributes this improvement to exploiting four-server diversity when service-time variability is high.
  • Preemption versus non-preemption: For K = 1, prmp-LGFS-R with r = 4 achieves the best plotted age performance.K = 1 is exponential and memoryless, a setting in which preemption is beneficial.
  • Preemption versus non-preemption: As K increases, decreasing gamma variability reduces replication benefits, while preemption further worsens age performance and can cause average age to blow up.The paper links this behavior to reduced service-time variability and loss of memorylessness when K ≠ 1.

C. Discussion

The discussion contrasts preemption and replication across service-time distributions. Exponential memorylessness supports preemption and exact age optimality, while NBU distributions favor non-preemptive LGFS policies and replication can improve age despite delay-throughput trade-offs.

  • Preemption versus non-preemption: For exponential service times, preemption preserves the service-time distribution after interruption, enabling age-optimal preemptive LGFS policies for any traffic intensity.The paper notes this remains true even when ρ > 1 and the system is unstable.
  • Preemption versus non-preemption: For NBU service times, the paper recommends non-preemptive LGFS because preemption can replace a packet with a new service that is probably longer than its remaining service.For gamma distributions with K > 1, preemptive LGFS age grows to infinity at high traffic intensity.
  • NBU guarantees: Non-prmp-LGFS-R remains within a small constant gap of optimum age for all NBU service-time distributions considered, including gamma distributions.This extends the discussion beyond the narrower settings of earlier studies.
  • Replication: For NBU service times, replicating a packet across all servers can provide lower service rate than avoiding replication, explaining its possible delay-throughput cost.The discussion contrasts this cost with replication’s age benefit under variable service times.
  • Replication: Replication improves age by exploiting diversity across servers, although replication can worsen delay and throughput under NBU service times.Age prioritizes delivering the freshest packet, whereas delay and throughput account for broader system service effects.

V. THROUGHPUT-DELAY ANALYSIS

The throughput-delay analysis asks whether age-oriented policies can also optimize delivery and delay, especially when applications need both fresh and historical updates. It shows exact optimality in exponential settings and non-preemptive no-replication optimality for NBU settings.

  • Motivation and metrics: The analysis considers applications where users need both current updates and past information, motivating simultaneous study of age, throughput, and delay.Examples include news, social updates, stock quotes, and sensor information.
  • Exponential service times: Under exponential service times with B = ∞, prmp-LGFS-R is throughput-optimal and delay-optimal among all policies in Πm.The proof couples server departure processes with arbitrary work-conserving policies.
  • Work conservation: Preemptive LGFS-R has the same throughput and mean-delay performance as any work-conserving policy.The argument tracks distinct packets in the system and distinct delivered packets, excluding replicas.
  • Work conservation: Non-work-conserving policies have worse throughput and delay because idling servers postpones packet delivery.This conclusion uses i.i.d. service times across servers and packets assigned to the same server.
  • Replication: Replication does not affect throughput or delay for replicative preemptive policies with i.i.d. exponential service times.Memorylessness makes new copies and remaining cancelled copies identically distributed after one replica completes.

APPENDIX A PROOF OF THEOREM 6

The proof couples the prmp-LGFS-R policy with an arbitrary policy and inductively compares their system states. Under i.i.d. exponential service times, this establishes stochastic age optimality, including policies that idle servers.

  • State representation: The system state records the destination’s largest delivered generation time and each server’s packet generation time, with idle servers assigned that destination value.Replicated packets may appear multiple times among the server-state coordinates.
  • Coupling: The proof couples delivery events under prmp-LGFS-R and an arbitrary work-conserving policy using exponential service-time memorylessness.Both policies share the same packet generation and arrival times.
  • Age comparison: The coupled state comparison implies that prmp-LGFS-R’s age process is stochastically no larger than that of every work-conserving policy.The resulting ordering holds for all times and all replication degrees allowed by the policy space.
  • All policies: Because idling only increases packet waiting time under exponential service, the same stochastic age ordering extends to non-work-conserving policies.Thus the policy minimizes any non-decreasing functional of the age process.

APPENDIX B PROOF OF LEMMA 11

The proof of Lemma 11 compares packet completion opportunities under an arbitrary policy with those under non-preemptive LGFS-R. NBU residual-service ordering makes the LGFS-R opportunity stochastically earlier, including replicated service.

  • Comparison quantities: Lemma 11 tracks each packet’s earliest assignment time Γi and completion time Di, which determine the relevant delivery-order comparison.The age process is an increasing function of the resulting completion-time vector D.
  • Replication: For replicated packet j, policy π starts service at the earliest replica assignment and completes it at the earliest replica completion.These times are vj(π)=minw τw and cj(π)=minw αw.
  • NBU comparison: NBU service times allow the remaining service on each server under LGFS-R to be compared with a fresh replica’s service time under π.Independence across servers then supports comparison of the earliest server-availability times.
  • Availability cases: At least one LGFS-R server becomes available at a time stochastically smaller than π’s replicated-packet completion time.The proof denotes this availability time by θ(P) and handles whether a newer or older packet is assigned next.
  • Conclusion: Applying the comparison recursively yields the completion-time inequality needed for Lemma 11, including cases where a newer packet completes before packet j.The argument preserves the required ordering for arbitrary queue size and packet-generation order.

APPENDIX C PROOF OF THEOREM 12

The proof bounds non-preemptive LGFS-R’s average age by decomposing its gap above a lower-bound age process. Replication improves the bound through the minimum of r service times.

  • Gap decomposition: The proof represents the gap between LGFS-R’s age and a lower-bound age process as geometric areas associated with generated packets.Figure 11 illustrates the decomposition into parallelograms Gi.
  • Single-server bound: Independence between service times and inter-generation times bounds the expected service contribution by E[X].The conditional expectation argument uses E[di|τ,N(T)]=E[di]≤E[X].
  • Single-server bound: ∆P is no larger than E[X], while the lower-bound process accounts for the remaining age component.This establishes the constant-gap comparison for the non-replicated case.
  • Replication bound: With replication degree r, a packet’s delivery delay is bounded by the minimum service time among its r replicas.The proof uses Di(P)−Γi(P)≤minl∈Sk Xl.
  • Replication bound: ∆P is no larger than E[minl=1,...,r Xl], yielding a smaller constant gap when replicas use multiple independent servers.This bound is combined with the lower-bound age process.

APPENDIX D PROOF OF THEOREM 14

The proof compares prmp-LGFS-R with arbitrary work-conserving policies through a coupled system state tracking distinct packets and delivered packets. With infinite buffer, the coupling gives identical throughput and delay distributions, while idling worsens both.

  • Coupling: With B=∞, packet delivery events can be coupled across prmp-LGFS-R and any work-conserving policy because exponential service times are memoryless.Replicated copies are cancelled after one copy completes.
  • State representation: The coupled state Hπ(t) consists of the number of distinct packets in the system and the number of distinct packets delivered by time t.The state is defined for arbitrary policies and is assumed right-continuous.
  • Distributional equality: The coupled state processes have the same distribution for every work-conserving policy with the same initial state.This is the content of Lemma 20.
  • Performance: Prmp-LGFS-R has the same throughput and delay performance as every work-conserving policy under infinite buffer.The proof derives these equalities from the coupled delivered-packet and in-system-packet processes.
  • Optimality: Because service idling increases packet waiting time, prmp-LGFS-R is throughput-optimal and delay-optimal among policies in Πm.Non-work-conserving policies have worse throughput and delay performance in this setting.
Loading 1709.04956v4…