PaperlayerView exact revision on arXiv

Source-linked AI summary

The Age of Information in Networks: Moments, Distributions, and Sampling

Roy D. Yates

arXiv:1806.03487v4cs.IT

TL;DR

Time-average AoI remains challenging to analyze even in simple queues, motivating tools for understanding timeliness in networks. This paper extends stochastic hybrid systems analysis and shows that, in line networks, age can be represented as a sum of independent renewal-process ages.

  • Problem

    Time-average AoI remains challenging to analyze even in simple queues, motivating tools for characterizing AoI in networks.

    Source: §I · p. 1

  • Method

    Using SHS for finite-state continuous-time Markov network models, the paper derives linear differential equations for age moments and the MGF.

    Source: C. Paper Overview · p. 3, §VII · p. 13

  • Results

    At each node in a line, AoI is distributed as a sum of independent renewal-process ages for equilibrium renewal processes with continuous inter-update distributions and stationary age processes.

    Source: §VII · p. 13

  • Takeaways & Limitations

    The distributional characterization extends beyond preemptive memoryless servers to status-sampling networks with general service-time distributions.

    Source: C. Paper Overview · p. 3, §VII · p. 13

Abstract

from arXiv · show

A source provides status updates to monitors through a network with state defined by a continuous-time finite Markov chain. An age of information (AoI) metric is used to characterize timeliness by the vector of ages tracked by the monitors. Based on a stochastic hybrid systems (SHS) approach, first order linear differential equations are derived for the temporal evolution of both the moments and the moment generating function (MGF) of the age vector components. It is shown that the existence of a non-negative fixed point for the first moment is sufficient to guarantee convergence of all higher order moments as well as a region of convergence for the stationary MGF vector of the age. The stationary MGF vector is then found for the age on a line network of preemptive memoryless servers. From this MGF, it is found that the age at a node is identical in distribution to the sum of independent exponential service times. This observation is then generalized to linear status sampling networks in which each node receives samples of the update process at each preceding node according to a renewal point process. For each node in the line, the age is shown to be identical in distribution to a sum of independent renewal process age random variables.

I. INTRODUCTION … C. Paper Overview

The paper extends stochastic hybrid systems (SHS) analysis from average age to higher-order moments and age distributions, then applies it to preemptive-server line networks and renewal-based status sampling networks.

I. INTRODUCTION

  • AoI measures the time since the freshest update received, while maximizing update rate can cause backlogs and throttling can leave monitors without fresh updates.For an update timestamped u, its age at time t is t − u.Source: §I · p. 1

A. AoI Background

  • A renewal source resets the input monitor’s age to zero at each fresh update, and that age grows at unit rate between updates,.This input age is the renewal process’s backward excess; downstream age is reset to an update’s age upon delivery.Source: A. AoI Background · p. 2

B. Prior Work

  • Prior work introduced SHS for AoI analysis, while this paper develops tools that complement the age-optimality results for preemptive LGFS policies.The introduction identifies time-average AoI analysis as challenging even for simple queues and motivates tools for moments and distributions.Source: §I · p. 1, B. Prior Work · p. 3, C. Paper Overview · p. 3

C. Paper Overview

  • The analysis models network update movement as a finite-state continuous-time Markov chain embedded in an SHS with a non-negative real-valued age vector.The network may range from a simple queue to a complex multihop network with interfering traffic.Source: C. Paper Overview · p. 3
  • A non-negative fixed point for first-moment equations guarantees all higher-order age moments and a region of convergence for the stationary MGF.The paper derives first-order linear differential equations for higher-order moments and the age-vector MGF; these equations underpin the later results.Source: C. Paper Overview · p. 3
  • In a line network with preemptive memoryless servers, each node’s stationary age is distributed as a sum of independent exponential random variables.The paper derives the network’s moments, MGF, and stationary age distribution from the SHS results.Source: C. Paper Overview · p. 3
  • In a status sampling network, a node’s stationary age is distributed as the independent sum of its neighbor’s stationary age and the renewal process age.Samples of one node’s update process reach a neighboring node as a point process; the result applies when that process is a renewal process.Source: C. Paper Overview · p. 3

D. Notation · II. A MODEL FOR UPDATES IN NETWORKS

The paper fixes notation for age vectors and probability distributions, then models network ages as continuous states coupled to a finite-state Markov chain. Its AoI stochastic hybrid system uses unit-rate age growth and transition-dependent resets to support moment and MGF analysis.

D. Notation

  • Vectors are row vectors, [x]j denotes a component, and X ⊕ Y denotes the sum under the product of their distributions.For a random vector x, E[esx] is its MGF vector.Source: D. Notation · p. 4

II. A MODEL FOR UPDATES IN NETWORKS

  • The model couples an age vector x(t), tracking monitors at network observation posts, with a finite-state continuous-time Markov chain q(t) describing update-packet movement.Observation posts may be nodes, links, queue positions, or servers.Source: §II · p. 4
  • Between transitions, every monitor age grows at unit rate; when a transition delivers a fresher update, the affected age jumps downward, producing sawtooth processes.A monitor observing a fresh update resets to zero.Source: §II · pp. 4–5
  • Each transition applies a binary age-assignment matrix x′ = xAl, whose columns select the age copied to each monitor or reset it to zero.The assignment matrices depend on queue discipline, routing, and update indexing.Source: §II · pp. 4–5
  • The resulting AoI SHS framework underpins the paper’s later analysis of stationary moments and MGF, preemptive-server line networks, and networks where nodes sample neighbors’ ages.The paper identifies Lemma 1’s differential equations as the foundation for these analyses.Source: §II · pp. 5–6
  • State-partitioned conditional expectations provide bookkeeping for age moments and the MGF, which are recovered by summing their weighted contributions across Markov states.The conditional first moments and state probabilities evolve through first-order linear differential equations, with higher moments computed successively.Source: §II · p. 5

III. STATIONARY MOMENTS AND THE STATIONARY MGF

Under an ergodic discrete-state chain, the section derives stationary age moments from first-moment equations. It states that a nonnegative solution to the first-moment system guarantees convergence of higher moments and of the stationary MGF for s < s0.

III. STATIONARY MOMENTS AND THE STATIONARY MGF

  • Assuming an ergodic chain with stationary state probabilities, the first-moment equations form a system whose stability depends on the reset maps; when stable, its stationary solution gives the average age.Source: §III · p. 6
  • If each reset map leaves x1 unchanged, then x1(t) tracks elapsed time and grows without bound in every discrete state.Source: §III · p. 6
  • With an ergodic chain, positive stationary state probabilities, and a nonnegative solution to (15), the age moment vectors converge to their stationary values.Theorem 1 states this convergence for the mth moment age vector.Source: §III · p. 6
  • Under the same conditions, there is an s0 > 0 such that the MGF vector converges to its stationary vector for s < s0.Source: §III · p. 6

A. Example: The M/M/1/1 queue with abandonment

The section analyzes destination age in an M/M/1/1 queue with abandonment, finding a stationary MGF and an average-age benefit from abandonment when λ/µ is sufficiently large.

A. Example: The M/M/1/1 queue with abandonment

B. Matrix Formulation of the Age Moments

The section recasts age-moment dynamics and fixed points in matrix form, extending the small-state treatment and supporting analysis of larger systems. It establishes that, under stated conditions, a non-negative stationary first-moment solution guarantees convergence of higher moments.

B. Matrix Formulation of the Age Moments

  • The matrix formulation represents age-moment dynamics and fixed points with long row vectors, and supports matrix versions of the moment and MGF theorems.This representation facilitates proofs and computational methods for larger systems than the small-state examples addressed directly by Theorem 1.Source: B. Matrix Formulation of the Age Moments · p. 7
  • If the stationary probability vector is strictly positive and the first-moment equation has a non-negative solution, the matrix governing first-moment dynamics is stable.Its eigenvalues have strictly negative real parts, so the first-moment dynamics converge to the stationary solution.Source: B. Matrix Formulation of the Age Moments · pp. 7–8
  • For an ergodic Markov chain with strictly positive stationary probabilities, a non-negative solution for the stationary first moment ensures convergence of all higher age moments.The limiting moments are the stationary mth moments.Source: B. Matrix Formulation of the Age Moments · p. 8

C. Matrix Formulation of the Age MGF

This section formulates the age MGF evolution in matrix form and shows that a stationary first moment guarantees convergence to a stationary MGF vector near s = 0. Successive derivatives of that MGF recover the stationary age moments.

C. Matrix Formulation of the Age MGF

  • The MGF derivation follows Theorem 1(b) to express the age evolution in vector form using the transition-set substitutions and relations in (29), (37), and (38).Source: C. Matrix Formulation of the Age MGF · p. 8
  • An ergodic chain with positive stationary state probabilities and a nonnegative stationary first moment satisfying (34) guarantees convergence to the stationary MGF vector for all s < s0, for some s0 > 0.The first moment is pivotal: its existence guarantees existence of, and convergence to, the stationary age MGF vector.Source: C. Matrix Formulation of the Age MGF · p. 8
  • Successive derivatives of the stationary MGF equation yield the stationary higher-order moments and corresponding age moments E[x^m] for m > 1.The stationary MGF also rederives the stationary moments of Theorem 2.Source: C. Matrix Formulation of the Age MGF · p. 8

IV. PREEMPTIVE LINE NETWORKS

An initial SHS analysis found average age additive hop to hop in the preemptive line network [97]; fake updates provide an equivalent age-process model that avoids tracking each node’s idle/busy state.

IV. PREEMPTIVE LINE NETWORKS

  • The network sends Poisson updates from source 0 through preemptive µi·/M/1/1 servers, where arrivals enter service immediately and preempted updates are discarded.There is no queueing; each server is idle or serving an update.Source: §IV · p. 8
  • Actual-network updates can be lost, arrive aged and correlated with their interarrival times, and reach the monitor with survivor bias.Departures from nodes i > 0 are not memoryless because preempted updates are discarded.Source: §IV · p. 8
  • The initial SHS analysis found average age additive hop to hop in the preemptive line network [97].The analysis used fake updates to avoid the combinatorial explosion from tracking each node’s idle/busy state.Source: §IV · p. 9
  • Fake updates preserve the age-vector evolution by replacing each departing update with a same-timestamp update that can be preempted without delaying arrivals.A fake update that completes service proceeds to the next node with the age of the update it preempts.Source: §IV · p. 9
  • The fake-update model treats each node as perpetually busy and equivalent in age evolution to a model forwarding its current update to the next node at rate µi.In the alternate interpretation, forwarding is an instantaneous delivery at a Poisson point process.Source: §IV · p. 9

A. Age Moments on the Line Network · B. Age MGF on the Line Network

For the n-node line network, the paper derives stationary age moments and an age MGF; the stationary age at each node is distributed as a sum of independent exponential service times.

A. Age Moments on the Line Network

  • The fake-update method depends on preemptive service and fails for ·/M/1/1 servers with abandonment, where idle/busy server states must be tracked.Source: A. Age Moments on the Line Network · p. 9
  • A fresh update resets node 1's age to zero, while transmission from node l to node l + 1 resets the receiving node's age to the age at node l.Other age components remain unchanged during these transitions.Source: A. Age Moments on the Line Network · p. 9
  • Theorem 4 establishes a stationary mth-moment age vector for the n-node line network.Its displayed vector has entries involving reciprocal service rates.Source: A. Age Moments on the Line Network · p. 9

B. Age MGF on the Line Network

V. SAMPLING STATIONARY AGE PROCESSES · A. Status Sampling Renewal Processes

A non-negative first moment yields exponential convergence to a stationary MGF and age distributions; under independent equilibrium renewal sampling, downstream ages are sums of the input age and renewal-process age.

V. SAMPLING STATIONARY AGE PROCESSES

  • A non-negative first moment implies exponential convergence of the MGF vector to its fixed point, and each age component converges to a stationary distribution.The stationary age process is considered once the Markov chain has stationary probabilities and the MGF vector has converged.Source: §V · p. 10
  • In the Poisson line network, rate-µ updates reset the downstream age to the upstream age, while that age grows at unit rate between updates.The sampling inter-update times are iid exponential(µ) random variables.Source: §V · p. 10

A. Status Sampling Renewal Processes

  • Under independent equilibrium renewal sampling, X_j is stationary and identical in distribution to X_i ⊕ Z, where Z is the renewal-process age.The renewal process has inter-update times distributed as Y, and Z is its stationary backward age.Source: A. Status Sampling Renewal Processes · pp. 10–11
  • Renewal sampling generalizes the line network: each node samples the preceding node’s update process, and exponential inter-renewal times recover the preemptive-server line’s age distributions.This is a status-sampling network, not a queueing network with easily defined customer service times.Source: §V · p. 10, A. Status Sampling Renewal Processes · p. 11
  • At node k of the line network, stationary age is distributed as the sum of the independent renewal-process age variables Z_i, starting from source age zero.The recursion is X_{i+1} ∼ X_i ⊕ Z_i.Source: A. Status Sampling Renewal Processes · pp. 10–11
  • Under stationarity, E[X_k]=kb/3 and Var[X_k]=kb^2/18; for n=3, 4, and 5, Gaussian PDFs with matching mean and variance reasonably fit the sample histograms.Sample-path histograms of X_1 and X_2 correspond to their PDFs; X_n is skewed leftward relative to the corresponding Gaussian.Source: A. Status Sampling Renewal Processes · p. 11

VI. STOCHASTIC HYBRID SYSTEMS FOR AOI ANALYSIS · A. AoI tracking as an SHS

The paper embeds AoI tracking in a general SHS framework, then specializes that model to show how discrete-state transitions govern age evolution and resets. This formulation supports the Dynkin-based results developed later.

VI. STOCHASTIC HYBRID SYSTEMS FOR AOI ANALYSIS

  • AoI tracking is a special case of the general SHS model in, whose formalism provides the basis for subsequent analysis.The paper notes that this formalization uses cumbersome notation but may enable extensions of the age-tracking SHS.Source: §VI · p. 12
  • Applying Dynkin’s formula to the age-tracking SHS yields Lemma 1, which underpins Theorems 1, 2, and 3.Source: §VI · p. 12
  • The general SHS framework partitions the state into a discrete process q(t) and a continuous vector x(t), with dynamics, transition/reset maps, and transition intensities.The model also specifies a vector of independent Brownian motion processes.Source: §VI · p. 12
  • In a discrete state, the continuous state evolves according to its dynamics; at a discrete transition, it can jump according to the reset map.A counting process tracks each transition, whose probability over (t, t + dt] is its intensity times dt.Source: §VI · p. 12

A. AoI tracking as an SHS

  • The AoI-tracking system is a simple time-invariant SHS, with continuous age evolution ˙x(t) = 1 in each discrete state.Source: A. AoI tracking as an SHS · p. 12
  • Its discrete state is a continuous-time finite-state Markov chain with directed transitions of fixed rates, and each transition applies the linear reset x′ = xA_l.Source: A. AoI tracking as an SHS · p. 12

B. SHS test functions · VII. CONCLUSION

The section explains how SHS test functions and their extended generator yield moment and MGF evolution equations, then summarizes stationary age characterizations and their generalization through renewal-process sampling.

B. SHS test functions

  • Because direct SHS process characterization can be complicated, applying the extended generator and Dynkin’s formula to each test function yields differential equations for its expected value.Source: B. SHS test functions · pp. 12–13
  • Time-invariant test-function families track each age component’s moments and MGF in each SHS state, with expected values given by weighted conditional expectations.Source: B. SHS test functions · pp. 12–13

VII. CONCLUSION

  • For finite-state continuous-time Markov-chain networks, SHS yields linear ODEs for age-vector moments and the MGF; their fixed point gives all stationary moments and the age MGF.Source: §VII · p. 13
  • The resulting MGF-vector results are described as the first explicit age-distribution results for updates traversing multihop network routes.Source: §VII · p. 13
  • Extending prior SHS analysis [97], line-network age at a node is distributed as a sum of independent renewal-process age variables, which are exponential for preemptive memoryless servers.Source: §VII · p. 13
  • The sum representation extends to equilibrium renewal processes with continuous inter-update distributions and stationary age processes; sampling an update process is key to the generalization.Source: §VII · p. 13
  • These observations suggest considerable progress remains in characterizing age of information in systems and networks.Source: §VII · p. 13

APPENDIX

The appendix proves the moment-evolution lemmas and convergence theorem, then uses these results to establish the line-network theorems. Its arguments derive the lemma equations, bound eigenvalues, and apply the results to specified transition matrices.

Lemma 1 proof

  • The proof of Lemma 1 gathers the derived equations into vector and row-vector forms to obtain (12a), (12b), and (12c).The final derivations use the reset-map cases and the definition of ˆAl in (11).Source: APPENDIX · pp. 13–14

Lemma 2 proof

  • Lemma 2 proves that if the first-moment fixed point exists, every eigenvalue of R − D has negative real part.The proof uses a nonnegative dominant eigenvalue and eigenvector of σI + R − D to show σ − r(σ) > 0.Source: APPENDIX · p. 14

Theorem 2 proof

  • Theorem 2’s induction shows that a first-moment fixed point implies convergence of the first moment, with higher-order convergence following from the induction hypothesis.The base case uses Lemma 2 to establish stability of R − D and convergence of the first-moment differential equation.Source: APPENDIX · p. 15

Theorem 4 proof

  • With shorthand βj = d0 − µj, (29a) can be used, then a result follows from (45), and the proof concludes that the claim follows from Theorem 2.Source: APPENDIX · p. 15

Theorem 5 proof

  • Theorem 5’s proof specifies the transition and rate matrices, defines µ̄i = µi − s, and concludes the claim from that definition.Source: APPENDIX · p. 15
Loading 1806.03487v4…