PaperlayerView exact revision on arXiv

Source-linked AI summary

Age of Information in G/G/1/1 Systems: Age Expressions, Bounds, Special Cases, and Optimization

Alkan Soysal, Sennur Ulukus

arXiv:1905.13743v1cs.ITcs.NIeess.SPmath.IT

TL;DR

Age-of-information analysis has largely used well-behaved queueing distributions, while general distributions make the necessary expectations harder to calculate. This paper derives expressions and upper bounds for blocking and preemption systems, finding that bounds can closely track exact age and that optimal arrivals depend on the service setting.

  • Problem

    Age analysis for general interarrival and service distributions is difficult because calculating expected values can involve complex, possibly correlated random quantities.

    Source: §I · pp. 2–3

  • Method

    The paper derives exact age expressions and upper bounds for G/G/1/1 blocking and preemption systems, then gives expressions for M/G/1/1 and G/M/1/1 cases.

    Source: §I · pp. 3–4

  • Results

    Blocking bounds are tight for M/M/1/1 and generally close to exact age; deterministic interarrivals are optimal in G/M/1/1, while non-exponential service makes the optimal arrival distribution depend on relative means.

    Source: §I · pp. 3–4, §V · p. 23

  • Takeaways & Limitations

    Designing systems using the proposed upper bounds yields optimized achievable age values.

    Source: §I · p. 3, §V · p. 23

Abstract

from arXiv · show

We consider the age of information in G/G/1/1 systems under two service discipline models. In the first model, if a new update arrives when the service is busy, it is blocked; in the second model, a new update preempts the current update in service. For the blocking model, we first derive an exact age expression, then we propose two simple to calculate upper bounds for the average age. The first upper bound assumes the interarrival times to have log-concave distribution. The second upper bound assumes both the interarrivals and service times to have log-concave distribution. Both upper bounds are tight in the case of M/M/1/1 systems. We show that deterministic interarrivals and service times are optimum for the blocking service model. In addition, using the age expression for G/G/1/1 systems, we calculate average age expressions for special cases, i.e., M/G/1/1 and G/M/1/1 systems. Next, for the preemption in service model, we first derive an exact average age expression for G/G/1/1 systems. Then, we propose a simple to calculate upper bound for the average age. In addition, similar to blocking discipline, using the age expression for G/G/1/1 systems, we calculate average age expressions for special cases, i.e., M/G/1/1 and G/M/1/1 systems. Average age for G/M/1/1 can be written as a summation of two terms, the first of which depends only on the first and second moments of interarrival times and the second of which depends only on the service rate. In other words, interarrival and service times are decoupled. We show that deterministic interarrivals are optimum for G/M/1/1 systems. On the other hand, we observe for non-exponential service times that the optimal distribution of interarrival times depends on the relative values of the mean interarrival time and the mean service time.

I. INTRODUCTION

The paper extends age-of-information analysis beyond exponential queueing models to general interarrival and service distributions. It analyzes blocking and preemption disciplines, deriving age expressions and bounds for general and special-case systems.

I. INTRODUCTION

  • The paper targets general distributions because exact age calculations can require difficult expectations, especially with non-exponential interarrivals.It derives exact expressions for known service distributions and upper bounds intended to simplify system design.Source: §I · pp. 2–3
  • For blocking, the paper derives an exact age expression, two upper bounds, and special-case formulas, with deterministic times minimizing its first bound.The bounds assume log-concave interarrivals, or log-concave interarrivals and service times; both are tight for M/M/1/1.Source: §I · pp. 3–4, §III · pp. 6–7
  • For preemption, the paper derives an exact expression without infinite sums, a bound without stochastic-ordering restrictions, and formulas for M/G/1/1 and G/M/1/1.Deterministic interarrivals are optimal in G/M/1/1; with non-exponential service, the optimal interarrival distribution depends on the relative means.Source: §I · p. 4

II. SYSTEM MODEL

  • The model assumes independent i.i.d. interarrival and service times with general distributions, transmitting updates through a single server.The arrival and service processes are independent of one another.Source: §II · p. 4

A. Blocking Discipline

  • Under blocking, busy-server arrivals are discarded, and effective interarrival times run between consecutive successful updates.Each effective interarrival time includes service time and the idle wait until the next successful arrival.Source: A. Blocking Discipline · p. 5

B. Preemption in Service Discipline

  • Under preemption, each arrival starts service, replacing any update already in service; only arrivals that finish before the next arrival succeed.The number of arrivals until a successful one is geometric, with success probability Pr(Y1,n > Sn).Source: B. Preemption in Service Discipline · pp. 5–6

III. G/G/1/1 WITH BLOCKING

  • For blocking, average age equals the renewal age of effective interarrivals plus mean service time.The exact expression depends on effective-interarrival moments, which can be difficult to calculate for general distributions.Source: §III · pp. 6–7

A. Age for General Interarrival and Service Times

For blocking G/G/1/1 systems, the paper derives an exact average-age expression and examines its calculation and behavior. For G/M/1/1, it gives a closed-form expression and finds deterministic interarrivals minimize age for a fixed mean.

A. Age for General Interarrival and Service Times

  • The exact blocking G/G/1/1 average age is expressed using interarrival and service distributions, including an infinite sum of service-tail probabilities at accumulated interarrival times.The expression has terms depending only on interarrival times, only on service times, and on both distributions.Source: A. Age for General Interarrival and… · pp. 7–8
  • With E[S] = E[Y ], the summation calculation error is below 0.5% after five terms; age decreases with either gamma rate and increases with either shape parameter.The number of terms needed for convergence depends on the ratio of expected service time to expected interarrival time.Source: A. Age for General Interarrival and… · p. 8, Figure 3 · p. 8

B. Age for General Interarrival and Exponential Service Times

  • For blocking G/M/1/1, the average-age expression is a sum of three terms, with the middle term requiring no summation and depending on both interarrival and service parameters.The expression provides a relatively direct calculation for a given interarrival distribution.Source: B. Age for General Interarrival and… · pp. 9–10
  • In G/M/1/1, age decreases as either the interarrival rate or service rate increases; among the plotted interarrival shapes, smaller αY yields lower age.For the service-rate comparison, the lowest age occurs when the mean interarrival time is smallest.Source: B. Age for General Interarrival and… · p. 10, Figure 5 · p. 11
  • For a fixed mean interarrival time in blocking G/M/1/1, deterministic interarrivals minimize age, while exponential interarrivals are worst among log-concave distributions.Gamma interarrivals with α < 1 are not log-concave.Source: B. Age for General Interarrival and… · p. 11, Figure 6 · p. 11

C. Age for Exponential Interarrival and General Service Times

For blocking G/G/1/1 systems, the paper develops exact age analysis and tractable upper bounds, then applies these results to exponential and log-concave cases. The bounds and special-case results expose how interarrival and service-time assumptions affect age and its optimization.

C. Age for Exponential Interarrival and General Service Times

  • For exponential interarrivals, the M/G/1/1 derivation uses the fact that the wait after service completion is exponential, so the gap is G = Y + S.The paper presents this as an alternative proof of a previously known result.Source: C. Age for Exponential Interarrival… · p. 12
  • For M/G/1/1 blocking, the paper gives an alternative derivation of the age expression from its general G/G/1/1 result, revisiting a result previously derived in.The derivation uses exponential interarrivals and general service times.Source: C. Age for Exponential Interarrival… · p. 12

D. Age for Log-Concave Interarrival and General Service Times

  • For LC/G/1/1 blocking, the paper gives an upper bound that applies to log-concave interarrivals and general service times, with calculation facilitated when E[K] is easy to obtain.The bound closely follows the exact age in the reported gamma-distribution examples.Source: D. Age for Log-Concave Interarrival… · pp. 13–14
  • A second LC/G/1/1 bound uses only the first two moments of interarrival and service times, decoupling their contributions.The interarrival terms depend on the first and second moments of interarrivals; the service terms depend on the first and second moments of service times.Source: D. Age for Log-Concave Interarrival… · p. 14
  • In the gamma examples, Theorem 4’s bound is nearly the exact age, while the Corollary 3 bound has an almost constant gap across many parameter values.The log-concavity condition on interarrivals matters: the expression is not an upper bound when the gamma interarrival shape αY is below 1.Source: D. Age for Log-Concave Interarrival… · pp. 14–15
  • With fixed means, deterministic interarrivals and service times minimize the second bound, while exponential interarrivals maximize it.The authors also note a similar conclusion for exact age in Fig. 6.Source: D. Age for Log-Concave Interarrival… · pp. 15–16

E. Age for Log-Concave Interarrival and Log-Concave Service Times

The paper considers a blocking system with log-concave interarrival and service-time distributions and proposes an upper bound. In the gamma examples, the bound tightens relative to another bound in specified parameter regimes, but the comparison does not apply when interarrival shape is below one.

E. Age for Log-Concave Interarrival and Log-Concave Service Times

  • The second blocking upper bound assumes both interarrival and service times are log-concave, and depends only on their first and second moments.The theorem compares the LC/LC system with an M/LC system formed by replacing interarrivals with exponential ones of the same mean.Source: E. Age for Log-Concave Interarrival… · p. 16
  • When the interarrival rate is large or shape is small, the Theorem 5 upper bound is tighter than Corollary 3’s; the M/LC/1/1 age converges to the LC/LC/1/1 age as λ increases.Source: E. Age for Log-Concave Interarrival… · p. 16
  • For gamma interarrivals with αY < 1, the stated upper-bound comparison does not hold because the interarrival distribution is no longer log-concave.This boundary concerns interarrivals; the text says the analogous expression remains an upper bound when service shape αS < 1.Source: E. Age for Log-Concave Interarrival… · p. 17

IV. G/G/1/1 WITH PREEMPTION IN SERVICE

Under preemption in service, the paper derives an exact G/G/1/1 age expression and a simpler upper bound, then examines how distribution choices affect age. Unlike blocking, preemption can make age nonmonotone and change which interarrival distribution is optimal.

A. Age for General Interarrival and Service Times

  • The exact G/G/1/1 age expression is the sum of the age of the effective interarrival process and the update’s time in service, which differs from the server’s mean service time.The expression depends on the general interarrival and service distributions and avoids the infinite sums required in the blocking model.Source: §IV · p. 17, A. Age for General Interarrival and… · p. 18
  • The proposed upper bound is close to the exact age in simulations, with a small, bounded gap that depends on the interarrival and service distributions.The bound is tight when K is independent of Yk; the paper gives the multicast model as an example.Source: A. Age for General Interarrival and… · p. 19
  • For G/G/1/1 with preemption in service, evidence suggests the age-minimizing distribution is not deterministic; at very large λ, log-concave service times (αS > 1) overload the system and increase age.Source: A. Age for General Interarrival and… · p. 20
  • The minimum age over the rate parameter is lower under blocking than preemption for G/G/1/1, whereas the ordering is reversed for M/M/1/1,.Source: A. Age for General Interarrival and… · p. 20
  • With gamma service shape αS = 2 and rate µ = 2, deterministic interarrivals are optimal above a mean-interarrival threshold, while exponential interarrivals are optimal below it among log-concave distributions.For gamma service shape αS = 0.5 and rate µ = 2, deterministic interarrivals are optimal irrespective of the mean interarrival time.Source: A. Age for General Interarrival and… · pp. 20–21

B. Age for General Interarrival and Exponential Service Times

For preemptive G/M/1/1, the paper derives an age expression that separates interarrival and service effects, and establishes optimality results for interarrival distributions. It also gives an alternative proof of the previously derived M/G/1/1 result and concludes that upper bounds are generally close to exact ages.

B. Age for General Interarrival and Exponential Service Times

  • For G/M/1/1 with preemption, average age is the sum of the interarrival-process age and 1/µ, depending on the first two interarrival moments and service rate separately.The conditional service time ˜S disappears from the expression.Source: B. Age for General Interarrival and… · p. 21
  • Given a mean interarrival time, deterministic interarrivals minimize age in G/M/1/1, while exponential interarrivals give the worst age among log-concave distributions.Source: B. Age for General Interarrival and… · p. 21
  • For gamma interarrivals with exponential service, age decreases with both rate parameters; smaller αY lowers age when λ varies, and the lowest age occurs at the smallest mean interarrival time when µ varies.Source: B. Age for General Interarrival and… · p. 22, Figure 12 · p. 22

C. Age for Exponential Interarrival and General Service Times

V. CONCLUSIONS

  • The conclusion reports that the proposed upper bounds are generally close to exact average ages and says optimizing systems against them yields optimized achievable age values.Source: §V · p. 23

VI. APPENDIX

The appendix proves the blocking-model results by expressing effective interarrival moments through the stopping count K and using Wald’s equation. For exponential service, it identifies K as geometric and substitutes the resulting expectations into the age expression.

A. Proof of Theorem 1

  • The proof uses that K is a stopping time and that the indicator for continuing through k arrivals is determined by earlier interarrivals, making it independent of Yk.Source: A. Proof of Theorem 1 · p. 24
  • Wald’s equation gives E[G] = E[K]E[Y], and the proof proceeds to derive the second moment E[G^2] using indicators for whether the process has not stopped.Source: A. Proof of Theorem 1 · p. 24

C. Proof of Theorem 2

  • For exponential service with rate µ, K is geometric with mean 1/(1 − E[e^-µY]), which is inserted with the derived numerator into the blocking age expression.Source: C. Proof of Theorem 2 · pp. 26–27

D. Proof of Corollary 1

The proofs for exponential service rewrite terms in the blocking age expression using conditional expectations and event probabilities. For exponential interarrivals, the proof then evaluates terms using the Erlang distribution of sums of interarrivals.

D. Proof of Corollary 1

E. Proof of Theorem 3

  • For exponential interarrivals, Ak is Erlang distributed because it is a sum of k exponential variables, enabling evaluation of the relevant term in the age expression.Source: E. Proof of Theorem 3 · p. 28

F. Proof of Theorem 4

The proofs establish an upper bound under log-concave interarrivals and develop a log-concavity argument used to bound age in the preemption setting.

F. Proof of Theorem 4

  • For log-concave interarrivals, the proof establishes the bound in (13) by proving an inequality with Laplace transforms.It uses the k-fold convolution density of the interarrival time and the unit step function.Source: F. Proof of Theorem 4 · p. 29

G. Proof of Theorem 5

  • If S and the i.i.d. interarrival times Y_k are log-concave and independent, then their random-sum aggregate G has a log-concave density.The proof establishes this through total-positivity properties of the convolution and mixture densities.Source: G. Proof of Theorem 5 · p. 30
  • For the preemption bound, W given S=s is a residual-life variable of G, and log-concavity makes its mean residual life non-increasing.This supports the proof's conclusion that Cov(W,S) ≤ 0 and its ensuing age bound.Source: G. Proof of Theorem 5 · pp. 31–32
  • The proof compares W plus an independent service time with exponential benchmarks, then uses the resulting order to bound the age by the M/G/1/1 expression.It uses convex and harmonic mean residual life orders, with the final comparison applied to the square function.Source: G. Proof of Theorem 5 · p. 32

H. Proof of Theorem 6

The proof expresses the average age through moments of the effective interarrival time, which is a geometric sum of ordinary interarrivals.

H. Proof of Theorem 6

  • The effective interarrival time G is a random sum of interarrivals with geometric count K, and E[G] = E[K]E[Y].The proof then derives E[G^2] using indicator events and the preemption condition Y_j < S for j < k.Source: H. Proof of Theorem 6 · pp. 32–33
  • Bayes’ rule gives the probability of surviving service beyond an interarrival y as Pr(S > y) = F̄_S(y).This probability is used in the average-age calculation.Source: H. Proof of Theorem 6 · pp. 33–34
  • The average-age expression uses E[Y], E[Y F̄_S(Y)], the geometric-count moments, and the expected service-time quantity ẼS.K is geometric with p = 1 − E[F̄_S(Y)].Source: H. Proof of Theorem 6 · p. 34

I. Proof of Theorem 7

The proofs simplify the age expression under exponential service or exponential interarrivals by exploiting the corresponding distributional properties.

I. Proof of Theorem 7

  • Decomposing E[S] across S<Y and S>Y lets the proof rewrite the age expression using conditional service-time terms.Substitution yields an expression involving E[S − Y | S > Y] and Pr(S > Y).Source: §I · p. 34
  • For exponential S, memorylessness makes E[S] = E[S − Y | S > Y], reducing the expression to (118).The resulting expression includes Pr(S < Y).Source: §I · p. 34

J. Proof of Theorem 8

  • For exponential Y, the proof evaluates Pr(S < Y) as E[e^−λS] and substitutes this and E[S | S < Y] into (120) to obtain (24).The passage identifies the exponential interarrival rate as λ.Source: J. Proof of Theorem 8 · p. 35

K. Total Positivity and Stochastic Ordering

This section collects distributional properties and stochastic orders used in the paper’s bounds, including links between log-concavity and total positivity.

K. Total Positivity and Stochastic Ordering

  • For a probability density on the non-negative real line, log-concavity, PF2, and TP2 are equivalent properties.The section defines TP2 and PF2 and states their connection to log-concavity.Source: K. Total Positivity and Stochastic… · pp. 35–36
  • Residual life is the conditional distribution of a variable’s remaining lifetime given survival up to a specified time.The section defines this distribution for times at which the survival probability is positive.Source: K. Total Positivity and Stochastic… · p. 36
  • Log-concavity implies DMRL, and DMRL implies NBUE.The section introduces DMRL through decreasing mean residual life and NBUE through a bound on mean residual life.Source: K. Total Positivity and Stochastic… · pp. 36–37
  • The paper uses convex and harmonic mean residual life orders to compare random variables, including with exponential variables of the same mean.The section states that NBUE variables are smaller than equal-mean exponential variables in convex order and gives order properties used in the bounds.Source: K. Total Positivity and Stochastic… · p. 37
Loading 1905.13743v1…