PaperlayerView exact revision on arXiv

Source-linked AI summary

The Age of Information: Real-Time Status Updating by Multiple Sources

Roy D. Yates, Sanjit K. Kaul

arXiv:1608.08622v2cs.IT

TL;DR

The paper addresses how to evaluate and control the timeliness of updates from multiple independent sources sharing queueing systems. It formulates AoI, derives multi-source results for FCFS and LCFS systems, and introduces an SHS-based evaluation method. The results characterize feasible status-age regions and show gains from coordinated sharing, while identifying excessive offered load as a risk under lossy LCFS.

  • Problem

    Timely status updating by multiple sources is not well understood, while AoI lacks a consistent analytic methodology for evaluating shared service systems.

  • Method

    The paper derives general AoI results, analyzes Poisson-arrival M/M/1 FCFS and LCFS systems, and develops a simplified stochastic-hybrid-systems procedure for finite-state queues.

  • Results

    The paper characterizes feasible status-age regions and finds nontrivial trunking-efficiency gains when multiple sources share capacity with coordinated load balancing.

  • Takeaways & Limitations

    Shared updating capacity can be used efficiently through coordinated source load balancing, but queueing and packet discarding create different offered-load pressures in FCFS and lossy LCFS systems.

Abstract

from arXiv · show

We examine multiple independent sources providing status updates to a monitor through simple queues. We formulate an Age of Information (AoI) timeliness metric and derive a general result for the AoI that is applicable to a wide variety of multiple source service systems. For first-come first-served and two types of last-come first-served systems with Poisson arrivals and exponential service times, we find the region of feasible average status ages for multiple updating sources. We then use these results to characterize how a service facility can be shared among multiple updating sources. A new simplified technique for evaluating the AoI in finite-state continuous-time queueing systems is also derived. Based on stochastic hybrid systems, this method makes AoI evaluation to be comparable in complexity to finding the stationary distribution of a finite-state Markov chain.

I. INTRODUCTION

The paper develops Age of Information (AoI) as an application-independent metric for evaluating timely status updates from multiple sources sharing communication queues. It analyzes how update rates and queueing disciplines affect status age under constrained network resources.

  • Applications and system setting: A vehicle-network example illustrates how multiple sensors generate packets that queue for wireless service, with service times affected by channel access, retransmissions, and backoff.Sensors may send separate updates or aggregate measurements into one status message.
  • Metric and motivation: AoI provides a consistent, application-independent basis for evaluating network performance across status-updating systems.The metric separates network evaluation from application-specific measures that may be too complex for network design.
  • Metric and motivation: AoI measures the elapsed time since the monitor’s most recently received status update was generated.For update timestamp u(t), age is ∆(t) = t − u(t), and smaller average age indicates timelier updating.
  • Metric and motivation: Timely updating differs from maximizing throughput, utilization, or minimizing packet delay because excessive update rates can create backlog and increase received-update age.The paper therefore considers optimizing source updating rates in response to available system resources.
  • Queueing disciplines: Replacing outdated queued packets with newer ones motivates lossy LCFS disciplines, which discard preempted updates and can reduce monitor status age.Under the stated Markov-state assumption, transmitting the youngest update makes older packets unnecessary.
  • Scope and prior work: The paper extends AoI analysis to multiple-source FCFS and LCFS queues while relating the metric to prior freshness and status-update studies.The introduction identifies applications including caches, real-time databases, ad hoc networks, and vehicular systems.

B. Paper Overview

The paper studies multiple Poisson status sources sharing M/M/1 service systems and derives analytical AoI results for FCFS and two preemptive LCFS disciplines. It also introduces a stochastic-hybrid-systems method for systematically evaluating AoI in finite-state queues.

  • General AoI analysis: Theorem 3 expresses each source’s AoI using stationary properties of interarrival times and system times for delivered updates.The result provides the general basis for subsequent FCFS and LCFS analyses.
  • Queueing results: For multiple Poisson sources with exponential service, the paper derives feasible average-age regions for FCFS and LCFS-S and LCFS-W queues.LCFS-S preempts the packet in service, whereas LCFS-W replaces only an older waiting packet.
  • Queueing results: The analysis assumes source-agnostic preemption, leaving prioritized preemption policies beyond the scope of the work.A packet from one source may therefore preempt a packet from another source.
  • SHS method: Theorem 4 gives a systematic procedure for calculating AoI in finite-state queues with memoryless service using simplified stochastic hybrid systems.The method represents queue states discretely and age variables continuously, with linear reset mappings at transitions.
  • SHS method: The paper applies the SHS procedure to derive FCFS and LCFS results through state-space reduction, continuous-state embeddings, and fake updates.These derivations are described as simpler than earlier analyses of the LCFS systems.
  • Resource sharing: Coordinated load balancing allows nontrivial trunking-efficiency gains when multiple sources share system capacity.High FCFS offered load raises AoI through queueing delays, while lossy LCFS can mitigate this but may encourage excessively high offered loads.

C. Notation

The paper defines AoI through the monitor’s status-age process and derives a general time-average identity using delivered-update interarrival and system times. This identity applies broadly across lossless FCFS and lossy, preemptive LCFS systems, without assumptions about other queue traffic.

  • Age calculation: The area decomposition separates boundary, trapezoidal, and triangular contributions before taking the long-run limit.The boundary contribution is finite with probability 1 and vanishes after normalization as T grows.
  • Age process: AoI is the long-run time average of a source’s monitor age, whose graph rises between deliveries and resets when an update is received.The average is computed as the area under the age graph divided by the observation interval.
  • General identity: The general AoI identity uses Y, the interarrival time between delivered updates, and T, the system time of a delivered update.The result is formulated for stationary ergodic status-updating systems.
  • Scope: Theorem 3 applies to both lossless FCFS systems and lossy LCFS systems with updates preempted and discarded.It also makes no specific assumptions about other traffic sharing the queue.
  • Age calculation: For preemptive LCFS, delivered packets are indexed by completions, while arbitrarily many intervening arrivals may be preempted and discarded.Thus Y measures time between delivered packets rather than all source arrivals.

A. M/M/1 First-Come First-Served

The paper extends average-age analysis to a multi-source M/M/1 FCFS queue and generalizes the single-source load optimization to N sources. It evaluates AoI using delivered-update interarrival and system-time moments.

  • A. M/M/1 First-Come First-Served: The single-source M/M/1 average age is minimized at offered load ρ*≈0.53, motivating its extension to an N-source system.The multi-source setting retains Poisson arrivals and exponential service assumptions.
  • A. M/M/1 First-Come First-Served: In FCFS, source-i delivered updates have iid exponential interarrival times Y_j, while T_j denotes their packet system times.The system time decomposes as T=W+S, with W waiting time and S service time.
  • A. M/M/1 First-Come First-Served: The AoI calculation requires E[Y], E[Y^2], and E[YT], with E[YT] involving the negatively correlated interarrival and waiting times.A long interarrival can allow the queue to empty, producing a small waiting time.
  • A. M/M/1 First-Come First-Served: Theorem 1 reduces to the single-source result when ρ_i=ρ and ρ_-i=0.This establishes consistency with the previously analyzed single-source M/M/1 FCFS case.
  • A. M/M/1 First-Come First-Served: For LCFS with preemption in service, arrivals preempt the packet currently in service, and only one packet can be in the system’s service position.The interval between departures may contain multiple idle and busy blocks, including completions and preemptions from other sources.

III. STOCHASTIC HYBRID SYSTEMS FOR AOI ANALYSIS

The paper develops a piecewise-linear stochastic hybrid-system framework for AoI in finite-state continuous-time queueing systems. Its moment equations reduce AoI computation to a task practically comparable to finding the queue’s stationary probabilities.

  • III. STOCHASTIC HYBRID SYSTEMS FOR AOI ANALYSIS: The piecewise-linear SHS derives first-order differential equations for first moments of the continuous state.These equations track expectations and correlations between age variables and discrete Markov states.
  • III. STOCHASTIC HYBRID SYSTEMS FOR AOI ANALYSIS: For finite-state queueing systems, the resulting AoI methodology is practically as simple as calculating the queue’s stationary probabilities.The approach targets general finite-state queue descriptions by continuous-time Markov chains.
  • III. STOCHASTIC HYBRID SYSTEMS FOR AOI ANALYSIS: The SHS separates a discrete continuous-time Markov state q(t) from a continuous state x(t) evolving through flows and transition resets.Transitions may have state-dependent intensities and map (q,x) to (q′,x′).
  • III. STOCHASTIC HYBRID SYSTEMS FOR AOI ANALYSIS: The framework assumes the discrete Markov chain is finite-state and ergodic, so its state probabilities converge to a unique stationary vector.Age-moment stability is a separate condition that depends on the reset maps.
  • III. STOCHASTIC HYBRID SYSTEMS FOR AOI ANALYSIS: Lemma 2 provides coupled first-order ordinary differential equations for discrete-state probabilities and age-related moment processes.The equations support both temporal evolution and limiting average-age calculations.

C. An SHS for AoI

The paper specializes SHS to AoI by representing ages as constant-slope processes with queue-discipline-specific linear resets. This representation can simplify the discrete state space while yielding average age from stationary moment equations.

  • C. An SHS for AoI: Careful continuous-state definitions can reduce the size of the discrete state space in LCFS-S analysis.The paper explicitly notes considerable flexibility in choosing x(t).
  • C. An SHS for AoI: An AoI SHS uses binary unit-rate flows for relevant age components and binary linear reset maps determined by the queue discipline.The discrete state is a continuous-time Markov chain, and transitions apply x′=xA_l.
  • C. An SHS for AoI: Irrelevant variables are set to zero in states where they do not affect future age evolution, while relevant source-1 ages grow at unit rate.Variables are irrelevant when their queue positions contain other sources or no corresponding updates.
  • C. An SHS for AoI: When the moment differential equation is stable, the average age is obtained from limiting state-conditioned age moments and the stationary state probabilities.Theorem 4 provides a sufficient condition using an ergodic discrete chain and a non-negative solution for the limiting moments.
  • C. An SHS for AoI: For non-negative reset maps, stability is equivalent to an eigenvalue constraint on a non-negative matrix.The theorem’s closed-form equations are also rewritten in matrix form for numerical evaluation.

IV. LCFS AGE: SHS ANALYSIS

The LCFS-S system is modeled with an SHS whose discrete state tracks server occupancy and serving source, while continuous variables encode current and post-delivery source age. Transition-specific reset maps and stationary moment equations yield the average age.

  • SHS model: The discrete state q(t) ∈ {0, 1, 2} denotes an idle server or a source 1 or source 2 update in service.The continuous state is x(t) = [x0(t) x1(t)], where x0 is the current source 1 age and x1 is the age after delivering the update in service.
  • Transition maps: The SHS uses transition rates and binary reset matrices to translate each arrival, completion, and preemption into continuous-state updates.For each transition, the x → x′ mapping determines a matrix A_l with x′ = xA_l, and v_qA_l is included for the moment equations.
  • Transition maps: Source 1 arrivals reset the in-service age variable to zero, while source 1 delivery resets the monitor age to the delivered update’s age.Source 2 service events leave source 1’s current age unchanged, and variables irrelevant to the current state are set to zero.
  • Stationary analysis: The resulting stationary moment equations provide the average source 1 age through the SHS theorem.The derivation establishes the required nonnegative stationary moments and uses them to obtain the average age.
  • Stationary analysis: Irrelevant continuous variables have zero stationary moments, allowing the moment equations to be reduced to relevant variables before solving for average age.In particular, x1 is irrelevant in states 0 and 2, so v01 and v21 are zero.

B. LCFS-S: A simpler SHS analysis

A simpler LCFS-S SHS omits the serving source from the discrete state and preserves source-specific age information through transition reset maps. Solving the reduced moment equations again recovers the average-age result.

  • Model simplification: The simplified LCFS-S model tracks only whether the server is idle or busy, rather than which source’s update is in service.Source-specific effects are encoded in reset maps that depend on the arriving update’s source.
  • Transition maps: The simplified SHS has one busy-state Markov representation with transition rates and reset maps listed for five links.Its transition structure is shown in Figure 5 and its transition table is identified as Table II.
  • Continuous state: The continuous state retains the current source 1 age and the age that would result if the update in service were delivered.Both variables grow at unit rate while busy; the prospective age is irrelevant when the server is idle.
  • Result: Solving the reduced stationary equations yields nonnegative moments and reproduces Theorem 2(a) for source 1.The average age is obtained from the relevant moments after normalization by the service rate.

C. LCFS-S: An even simpler SHS analysis with fake updates

An even simpler LCFS-S representation keeps the server perpetually busy by inserting fake updates after real deliveries. This one-state SHS still yields the source-age result, but the trick does not extend to LCFS-W.

  • Fake-update construction: The fake-update method models multi-source LCFS-S with a one-state SHS in which the server is always busy.The discrete state no longer records whether the server is idle or which source is being served.
  • Fake-update construction: A fake update duplicates the previously delivered update’s timestamp, so its completion leaves the monitor age unchanged.A newly submitted true update immediately preempts any fake update that is keeping the server busy.
  • SHS dynamics: The one-state continuous state records current age and post-delivery age, with both components increasing at unit rate.Delivery resets the current age to the prospective age while retaining that prospective value, corresponding to a duplicate fake update.
  • Result: Solving the one-state moment equations again yields Theorem 2(a) for source 1.The discrete chain has stationary probability π0 = 1, and the average age is the first stationary moment v00.
  • LCFS-W extension: For LCFS-W, the discrete state tracks the number of updates, while continuous variables encode current, in-service, and waiting-update ages.The model uses three states and makes variables irrelevant when the corresponding service or waiting position is absent.
  • LCFS-W extension: The LCFS-W reset maps account for how service completion transfers a waiting update into service and how preemption modifies waiting-age variables.In particular, transitions l = 5 and l = 8 require less straightforward reset maps for the waiting update.
  • LCFS-W extension: The fake-update simplification fails for LCFS-W because real and fake in-service updates have different preemption behavior.The discrete state must therefore distinguish whether the update in service is real or fake.

V. SHS MATRIX REFORMULATION

The SHS moment equations are reformulated as a matrix differential system and a stationary linear system. A nonnegative stationary solution certifies stability and convergence of expected age.

  • Matrix formulation: The SHS differential and stationary moment equations are written in vectorized matrix form using block transition matrices and block-diagonal rate matrices.The long vector v(t) collects state-conditioned moments, while R, B, and D encode resets, drifts, and departure rates.
  • Stability criterion: A nonnegative stationary solution provides a fixed point for the relevant moment dynamics.The reformulation starts from the fixed-point condition obtained by setting the moment derivative to zero.
  • Reduced system: Irrelevant variables can be removed because they remain zero and contribute zero rows and columns to the relevant matrix system.Stability depends only on the remaining relevant variables.
  • Stability criterion: Nonnegative reset matrices and a dominant-eigenvalue argument establish stability of the relevant differential equations.The proof uses the nonnegative structure of the reset matrices and bounds the dominant real eigenvalue.
  • Stability criterion: Stability implies that E[x0(t)] converges to the average age, completing the proof of the general SHS result.The argument concludes by transferring stability from the relevant reduced system to the full moment dynamics.
  • Applications: The matrix result supports analysis of achievable AoI regions and resource sharing for multiple updating sources, including sensor-based systems.The paper connects these applications to embedded and IoT systems with independently generating sensors and exponential transmission times.

A. M/M/1 FCFS: Two Sources

For two sources sharing an M/M/1 queue, achievable age pairs depend on both total load and how that load is allocated. Equal allocation minimizes sum age under FCFS, while LCFS policy performance depends on load and source proportions.

  • FCFS: The feasible age pairs are the union of contours obtained by varying total load and source-load allocations.For fixed total load ρ, the contours arise from ρ1 + ρ2 = ρ.
  • FCFS: ρ1 = ρ2 = 0.306 minimizes sum age, yielding ∆1 = ∆2 = 5.30.With a shared rate µ = 2 server, each source instead obtains average age 2.65.
  • FCFS: A shared service facility provides trunking efficiency: two sources sharing rate µ = 2 achieve lower age than separately partitioned rate µ = 1 servers.With separate servers and optimal load ρ1 = 0.531, Equation (8) yields ∆1 = 3.48.
  • FCFS: The FCFS Pareto frontier depends on allocation: ρ = 0.612 is optimal near equal loads, while ρ = 0.53 reduces ∆1 as ρ2 → 0.Thus, the optimal total load varies along the Pareto frontier.
  • LCFS: For two sources, LCFS-W outperforms LCFS-S at low arrival rates but is somewhat worse at high arrival rates.The paper speculates that LCFS-W benefits at low rates by avoiding preemption of an update already in service.
  • LCFS: At total load ρ = 0.612, both LCFS policies produce better age contours than FCFS, and LCFS-S minimizes sum age when all loads are selectable.Policy regions nevertheless vary with total load and source-load proportions.
  • Multiple sources: For equal offered loads, sum age is minimized by ρi = ρ/N, and each user’s age decreases monotonically with total load.These conclusions extend to N-source resource allocation.
  • Multiple sources: For fixed ρ, LCFS-W outperforms LCFS-S when the number of sources N is large, while all three systems become equivalent as N becomes large.The paper also argues that FCFS is more efficient than either LCFS discipline for large symmetric systems.

D. Non-cooperative Rate Adaptation

The paper examines how independently adapting sources share service capacity under AoI objectives. It finds that simple adaptation can be unstable or inefficient, while coordinated load balancing and target-age policies offer more controlled sharing across queueing systems.

  • FCFS adaptation: For FCFS, each source can adapt its load as a best response to the aggregate load of the other sources.The adaptation is essentially the best-response normalized load that minimizes the source’s average age.
  • FCFS adaptation: Using half the residual capacity, ρ̂_i = 0.5(1 − ρ_−i), provides a good linear approximation because the age minimum is broad and nearly flat.This rule is reported as a practical approximation for FCFS rate adaptation.
  • Iterative adaptation: For N = 2, the synchronous iterative algorithm converges to ρ_1 = ρ_2 = 0.342 and corresponding ages Δ_1 = Δ_2 = 5.4390.The cited two-user iteration was shown to work reasonably well.
  • Iterative adaptation: The same iteration is unstable for N > 2, although allocating each source a fraction ω_N of residual capacity can be stable.The paper notes that directly sending each source its appropriate load ρ_i may be equivalent to sending the residual-capacity fraction.
  • LCFS adaptation: In both LCFS systems, sources have incentives to increase updating rates, so under maximum-load constraints the Nash equilibrium sets every source at its maximum load.The resulting age depends on each source’s maximum load and the total updating load, and may be undesirable when offered load carries a cost.
  • Shared capacity: The paper also derives feasible status-age regions and finds nontrivial trunking-efficiency gains when multiple sources share capacity with coordinated load balancing.FCFS can incur high AoI through queueing delays, whereas lossy LCFS can mitigate this but may encourage excessively high offered loads.
  • SHS evaluation: Stochastic hybrid systems provide closed-form or straightforward numerical AoI evaluation for finite-state queues and extend analysis toward more realistic service facilities.The approach covers priority differences, heterogeneous facilities, state-dependent policies, and time-varying arrival or service rates, though age-system stability remains incompletely understood.

APPENDIX A

This appendix derives waiting-time components for source i packets in a shared FCFS queue by partitioning interarrival times according to whether the preceding packet remains in the system. It uses exponential-service and Poisson-arrival properties to characterize the resulting conditional workloads and waiting times.

  • Interarrival partition: The proof partitions source i interarrival periods into brief and long events according to whether the preceding packet remains in the system.B_j denotes a brief interarrival period, while L_j is the complementary long event.
  • Queueing model: Identical exponential service times make the combined queue an M/M/1 system with offered load ρ = ρ_i + ρ_-i.This reduction provides the steady-state queueing model used in the appendix.
  • Brief interarrivals: For brief interarrivals, waiting includes the preceding packet’s residual system time and workloads from other-source arrivals during the interarrival period.The number of such arrivals is Poisson conditional on the interarrival duration, and their service requirements are independent exponential variables.
  • Brief interarrivals: The expected workload from other-source arrivals during an interarrival period of length y is ρ_-i y^2.This follows from E[M|Y_j = y] = λ_-i y and E[S_k|Y_j = y] = 1/µ.
  • Long interarrivals: For long interarrivals, the preceding packet has departed before packet j arrives, so waiting depends on other-source packets present at that arrival.The number present is characterized through the preceding packet’s system time and a geometric distribution.
  • Combining cases: The appendix combines the conditional calculations, including P[B_j] = ρ_i/(1 − ρ_-i), to obtain the waiting-time result.The brief-event probability follows from independence between the preceding system time and the subsequent interarrival.

APPENDIX B

This appendix analyzes packet service and interdeparture intervals using memoryless arrival and service processes, then applies their moments to the AoI expression and derives differential equations for piecewise-linear stochastic hybrid systems.

  • Service time: The service time T is exponentially distributed with rate λ + µ, giving E[T] = 1/(λ + µ).T is the service-completion time conditioned on service completing before the next packet arrival.
  • Interdeparture intervals: The interdeparture interval D is represented as a random sum of block lengths B_k ending with a departure of a source i update.Each block comprises an idle period and a busy period.
  • Busy periods: During a busy period, the service rate remains µ even when packets are preempted, and the busy period is memoryless.The busy period is independent of the number of arrivals preempted and of the source whose packet departs at its end.
  • Block structure: The memoryless arrival and service processes imply that each block B_k is independent of the number L of blocks.The idle and busy periods forming each block are also mutually independent.
  • AoI result: Applying the moments E[T], E[D], and E[D^2] to the AoI equation yields Theorem 2(a).The theorem follows after the service and interdeparture moments are evaluated.
  • SHS analysis: For the piecewise-linear SHS, the appendix derives first-order differential equations for the first moments of the continuous state.The derivation gathers state-specific equations and rewrites them in row form.
Loading 1608.08622v2…