PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimizing Age-of-Information in a Multi-class Queueing System

Longbo Huang, Eytan Modiano

arXiv:1504.05103v1math.OCcs.PF

TL;DR

The paper asks how to optimize information freshness when heterogeneous status-update streams share a queue, since both generation intervals and delivery delays affect age. It derives exact PAoI profiles for multi-class M/G/1 and M/G/1/1 systems and formulates update-rate selection as a PAoI-based optimization problem. The M/G/1/1 problem is quasi-convex with structural properties of its optimum, while the general M/G/1 problem is non-convex and is treated approximately.

  • Problem

    The paper addresses age-of-information optimization for heterogeneous status-update streams sharing queueing resources, where freshness reflects both update-generation and delivery delays.

  • Method

    The paper derives exact PAoI expressions for multi-class M/G/1 and M/G/1/1 queues and optimizes update rates using PAoI-based quasiconvex formulations.

  • Results

    The M/G/1/1 optimization is a quasi-convex program with structural properties of the optimal solution, whereas general M/G/1 optimization is non-convex and approximated.

  • Takeaways & Limitations

    PAoI provides a tractable basis for optimizing system cost as a function of update intervals in heterogeneous queueing systems.

Abstract

from arXiv · show

We consider the age-of-information in a multi-class $M/G/1$ queueing system, where each class generates packets containing status information. Age of information is a relatively new metric that measures the amount of time that elapsed between status updates, thus accounting for both the queueing delay and the delay between packet generation. This gives rise to a tradeoff between frequency of status updates, and queueing delay. In this paper, we study this tradeoff in a system with heterogenous users modeled as a multi-class $M/G/1$ queue. To this end, we derive the exact peak age-of-Information (PAoI) profile of the system, which measures the "freshness" of the status information. We then seek to optimize the age of information, by formulating the problem using quasiconvex optimization, and obtain structural properties of the optimal solution.

I. INTRODUCTION

The paper studies freshness of status information in heterogeneous multi-class M/G/1 systems, where shared queueing and update generation delays jointly affect performance. It derives PAoI expressions and formulates update-rate optimization using quasiconvex analysis, with approximation required for the general M/G/1 case.

  • Motivation: Realtime status information supports control and decision-making in sensor, autonomous-vehicle, and wireless-network systems.The relevant concern is how accurately received updates describe the observed physical phenomenon, rather than delivery speed alone.
  • System model: The system models heterogeneous entities whose status packets have different service-time distributions in a multi-class M/G/1 queue.Packets share a single server, so the model captures both resource sharing and queueing during delivery.
  • Contributions: The paper derives exact peak age-of-information values for each entity in both M/G/1 and M/G/1/1 systems.M/G/1 queues packets when the server is busy, whereas M/G/1/1 discards new packets under that condition.
  • Optimization: Update-rate control minimizes a quasiconvex PAoI-based cost in M/G/1/1, while the general M/G/1 formulation is non-convex and receives an approximate solution.The optimization controls update arrival rates, equivalently the sampling rates of the observed physical processes.
  • Optimization: PAoI minimization is equivalent to minimizing the sum of update interval and update packet delay, making the optimization problem non-convex.The paper emphasizes PAoI because it is more tractable than average AoI and therefore facilitates optimization.

B. Age-of-Information

This section defines status age and introduces peak age-of-information as a tractable alternative to average age-of-information. It then connects PAoI to entity costs and distinguishes the queueing and packet-discarding models used for analysis.

  • Status age: Status age Δn(t) is the elapsed time since entity n’s latest received update packet was generated.Receiving a packet resets the age to the current time minus that packet’s generation time.
  • Peak age-of-information: PAoI An(λ) is the average of the peak values Ank reached by entity n’s status-age process before new updates arrive.The metric captures maximum information age and is more tractable than average AoI for optimization.
  • Cost formulation: The system minimizes the maximum entity cost Cn(An), where each cost is quasiconvex, non-decreasing, and satisfies Cn(0) = 0.The optimization chooses a feasible update-rate vector λ to minimize Csys(A(λ)).
  • Queue models: M/G/1 queues new packets when the server is busy, whereas M/G/1/1 discards them.This packet-management distinction determines the two queueing models analyzed for PAoI.

A. A general result for G/G/1 queues

The paper develops a general G/G/1 characterization of peak age-of-information (PAoI) and relates it to time-average age-of-information (AoI). PAoI combines update intervals with packet delays and can approximate or upper-bound AoI.

  • G/G/1 PAoI characterization: PAoI equals the inter-arrival time plus the next update packet’s waiting and service delay in a G/G/1 queue.This follows from measuring the time between an update’s generation and the completion of the next update.
  • Relationship to AoI: PAoI samples age at peak moments, whereas AoI computes the time average of instantaneous age.Consequently, PAoI provides an approximate upper bound for AoI.
  • Relationship to AoI: For multi-class G/G/1 queues, the paper compares the PAoI expression with the corresponding AoI expression.The comparison provides a way to assess how close the two metrics are.
  • Periodic arrivals: When inter-arrival times are constant, corresponding to periodic arrivals, the comparison between PAoI and AoI specializes accordingly.The paper uses this case to examine the relationship between the two metrics.
  • G/G/1 PAoI characterization: The paper states a general G/G/1 proposition for PAoI and identifies the result as related to G/G/1 queues.The proposition is supported by a proof referenced in the appendix.

B. PAoI for multi-class M/G/1 queue

The paper specializes the general age analysis to a multi-class M/G/1 queue and derives the PAoI for each class. It also establishes stability requirements, comparisons with AoI, and conservation properties.

  • Multi-class M/G/1 PAoI: The paper derives the PAoI for a multi-class M/G/1 system using the waiting-time expression for the queue.The M/G/1 waiting time is computed using the Pollaczek–Khinchine formula.
  • Stability: The queue must satisfy ρ = Σ_j λ_j x_j < 1 for stability and finite PAoI.Here λ_j is the class-j arrival rate and x_j is its mean service time.
  • Comparison with AoI: For an M/M/1 specialization, the paper compares the resulting PAoI with the previously derived AoI expression.This comparison evaluates the relationship between the two metrics in the single-class exponential-service case.
  • Comparison with AoI: PAoI is described as a close upper bound of AoI for M/M/1 queues and as more tractable.The paper uses this tractability to motivate PAoI as an analyzable metric.
  • Conservation properties: The multi-class M/G/1 expression yields conservation formulas for PAoI and class-pair relationships determined by update rates.The paper presents conservation results after deriving the class-specific PAoI expression.

C. PAoI for M/G/1/1 queue

The M/G/1/1 model derives the PAoI for each class when incoming packets are discarded rather than queued. The resulting expression decomposes peak age into processing, waiting-for-arrival, and service-completion components, while packet dropping can reduce PAoI by eliminating queueing delay.

  • The M/G/1/1 server performs packet management by not queuing incoming update packets.This setting is used to derive the multi-class PAoI expression.
  • Peak age comprises the current packet’s processing time, the expected time until the next arrival, and the completion time of the next class-n update.Arrivals during busy periods are dropped, so the next-arrival interval contributes directly to the decomposition.
  • The PAoI expression does not require the second service-time moment because discarded packets do not remain in the buffer.The absence of buffered packets removes the residual-service-time contribution from the calculation.
  • For N = 1, the M/G/1/1 expression recovers the known M/M/1/1 result, and packet discard permits violating the usual ρ < 1 constraint.These observations follow directly from the derived PAoI formula.
  • When update rates are large and ρ is close to 1, packet dropping may reduce PAoI by reducing queueing delay.The M/G/1/1 PAoI can then be much smaller than the corresponding M/G/1 value.

IV. PAOI OPTIMIZATION

After deriving PAoI for the queueing cases, the paper optimizes update rates to minimize the system cost and provide differentiated service across applications.

  • The update-rate optimization minimizes Csys(λ) to provide differentiated service to different applications.

A. M/G/1/1 optimization

For M/G/1/1, the PAoI optimization is formulated as a quasiconvex program and solved efficiently by bisection, with structural properties for optimal rates.

  • The M/G/1/1 optimization problem is a quasiconvex program over the feasible rate set Λ.Quasiconvexity follows from the linear-fractional age expressions, quasiconvex nondecreasing class costs, and the max operator.
  • The problem can be solved by bisection over a feasibility condition equivalent to Csys(λ) ≤ t.Each iteration tests feasibility and updates the lower or upper threshold.
  • An optimal rate vector can be enlarged entrywise until at least one rate reaches λmax without changing Csys.The construction proportionally increases all rates while preserving their ratios.
  • When all entities are identical, setting λn = λmax for every entity is optimal.

B. M/G/1 optimization

For general M/G/1, the optimization loses quasiconvexity, so the paper replaces the exact age with a quasiconvex approximation that can still be minimized by bisection.

  • In M/G/1, the constraint contains a sum of two linear-fractional functions and may no longer be quasiconvex.
  • The paper approximates An(λ) with Bn(λ) and solves the resulting problem instead of the exact formulation.
  • The approximation is useful because Bn(λ) is quasiconvex in λ, making Csys(B(λ)) efficiently minimizable by bisection.
  • The approximation’s performance is characterized using βn, the maximum increasing slope of each class cost function.For linear costs Cn(A) = wnA, the bound parameter satisfies βn = wn.
  • Lemma 4 compares the optimal solution of the original M/G/1 problem with the optimal solution of the approximation program.

V. NUMERICAL RESULTS

The numerical examples compare cost optimization in M/G/1/1 and M/G/1 queues, including an approximate solution for the general queue.

  • M/G/1/1 example: λ1 = 10 and λ2 = 6 minimize Csys(λ) in the M/G/1/1 example, yielding PAoI vector A = (3.9, 7.83).The resulting costs are C1 = 60.84 and Csys(λ) = C2 = 61.36.
  • M/G/1 example: The M/G/1 example requires ρ < 1 for finite PAoI and attains its minimum at λ = (0.29, 0.125), with A = (6.56, 13.11).Rates violating ρ < 1 are assigned a constant PAoI value, producing the flat region.
  • Approximation: The approximation approach produces λ∗B = (0.285, 0.17), PAoI vector A = (8.94, 13.31), and cost vector (C1, C2) = (319.69, 177.16).

VI. CONCLUSION

The paper studies age-of-information in heterogeneous multi-class M/G/1 systems, capturing both update-generation and queueing delays. It derives exact PAoI expressions for M/G/1 and M/G/1/1 systems and optimizes system cost through update-rate selection.

  • The study extends age-of-information analysis to heterogeneous service-time distributions in a multi-class M/G/1 queue.
  • Exact peak-age-of-information expressions are derived for both M/G/1 and M/G/1/1 systems.
  • PAoI enables system-cost optimization by choosing the update interval.

APPENDIX A – PROOF OF LEMMA 1

The appendix proves a lemma by relating waiting time to queue-clearing time and inter-arrival time, then applies these relations to establish bounds and cost comparisons.

  • Waiting time is represented as W = (TQ − I)+, where TQ clears existing queued packets and I is the next inter-arrival time.The proof uses independence between I and TQ, and between service time X and I.
  • The inequality (TQ − I)+ + I ≥ TQ provides the key lower-bound step in the lemma proof.The resulting integral relation is substituted into the preceding equations to obtain the bound.
  • The Lemma 4 proof bounds the system cost under the approximation between costs evaluated at B(λ∗) and 2A(λ∗).The proof takes the maximum over entities and combines the resulting inequalities to establish the stated bound.
Loading 1504.05103v1…