Source-linked AI summary
Status Updates in a multi-stream M/G/1/1 preemptive queue
Elie Najm, Emre Telatar
TL;DR
The paper studies how multiple Poisson update streams share a single-slot M/G/1/1 queue with preemption and general service times. Using detour flow graphs, it derives closed-form average and peak ages for each stream. Increasing one stream’s generation rate prioritizes it, whereas equal rates minimize total age.
Problem
The paper addresses average and peak age in a multi-stream M/G/1/1 preemptive queue with general service times.
Method
The paper uses the detour flow graph method to derive closed-form age expressions for each stream.
Results
Increasing a stream’s generation rate decreases its average and peak age relative to other streams.
Takeaways & Limitations
With fixed total generation rate, equal generation rates across streams minimize total average age and total average peak age.
Abstract
from arXiv · showhide
We consider a source that collects a multiplicity of streams of updates and sends them through a network to a monitor. However, only a single update can be in the system at a time. Therefore, the transmitter always preempts the packet being served when a new update is generated. We consider Poisson arrivals for each stream and a common general service time, and refer to this system as the multi-stream M/G/1/1 queue with preemption. Using the detour flow graph method, we compute a closed form expression for the average age and the average peak age of each stream. Moreover, we deduce that although all streams are treated equally from a transmission point of view (they all preempt each other), one can still prioritize a stream from an age point of view by simply increasing its generation rate. However, this will increase the sum of the ages which is minimized when all streams have the same update rate.
I. INTRODUCTION
The paper studies freshness for multiple Poisson update streams in a preemptive M/G/1/1 system and derives average-age and peak-age results. It shows that increasing one stream’s generation rate can prioritize that stream, while equal rates minimize total age.
- Motivation: Prior work evaluates update freshness using Age of Information, especially the time average age for Poisson-generated updates.The instantaneous age increases linearly between successful receptions, producing a sawtooth trajectory.
- Problem setting: The model has one source observing M streams, with each generated update selecting a stream probabilistically and preempting any update already in service.The queue has no buffer and uses a general service-time distribution.
- Contribution: The paper derives closed-form expressions for each stream’s average age and average peak age using the detour flow graph method.The work generalizes prior single-stream and exponential-service analyses.
- Findings: Increasing stream i’s update rate decreases its age relative to other streams when the total update rate is fixed.This increase requires reducing the update rates assigned to other streams.
- Findings: Equal update rates minimize the sum of stream ages under a fixed total generation rate.The paper therefore identifies fairness as the age-sum-optimal allocation.
II. SYSTEM MODEL
The system models M update streams sharing a single-slot preemptive queue. Stream selection is equivalent to independent Poisson arrivals, and successful deliveries, interarrival times, service times, and system times define the analysis variables.
- Arrival model: A source generates updates at total rate λ, selecting stream i independently with probability p_i.The stream probabilities satisfy Σp_i = 1.
- Arrival model: The selected-stream model is equivalent to M independent Poisson sources with rates λ_i = λp_i.The total rate satisfies λ = λ_1 + ··· + λ_M.
- Queue discipline: The M/G/1/1 queue permits only one update at a time, so updates from different streams and the same stream preempt one another.Service time S has a general distribution shared across streams.
- Successful delivery: Only updates that avoid preemption and reach the receiver are counted as successfully received updates.Dropped updates remain part of the arrival process but not the received-update sequence.
- Analysis variables: The analysis defines interdeparture time Y_j, stream-i interarrival time X^(i), service time S, and successful-packet system time T_j.Service times are independent of interarrival times across and within streams.
III. AGE OF A MULTI-STREAM M/G/1/1 PREEMPTIVE QUEUE
The section derives closed-form age expressions for each stream in the preemptive multi-stream M/G/1/1 queue. It models interdeparture times through a semi-Markov chain and detour flow graph, then relates stream-level age to update system and interdeparture times.
- Interdeparture-time model: The queue’s interdeparture time is represented by a semi-Markov chain whose states track whether stream 1 or another stream is being served.Arrivals from any stream can preempt the update in service, while successful completion returns the system to an idle state.
- Interdeparture-time model: The detour flow graph enumerates paths and their clock-occurrence combinations to obtain the moment generating function of the interdeparture time.The relevant clock variables are mutually independent, and the path probability includes the number of paths with each occurrence combination.
- Age expressions: Theorem 1 gives closed-form expressions for the average age and average peak age of stream i under general service time S and total arrival rate λ.The result applies to independent Poisson stream rates λ_i with λ = λ_1 + ··· + λ_M.
- Age expressions: The average peak age of stream 1 is the sum of its average system time and average interdeparture time.The section states Δ_peak,1 = E(T) + E(Y).
- Age trade-offs: Increasing a stream’s selection probability can reduce that stream’s average age and average peak age relative to the other streams.With a fixed total generation rate, prioritizing one stream requires increasing its choice probability.
- Age trade-offs: For fixed total generation rate, the total average age and total average peak age are minimized by the fair strategy giving every stream the same generation rate.Thus, prioritizing one stream and minimizing total age are contradictory objectives.
IV. CONCLUSION
The paper derives closed-form average and average peak ages for a multi-stream M/G/1/1 preemptive system and examines prioritization under a fixed total generation rate.
- The detour flow graph method yields closed-form expressions for the average age and average peak age of each stream.
- A stream can receive lower average and average peak age by being assigned a higher generation rate than other streams.
- Minimizing total age requires generating all streams at the same rate, so prioritizing one stream conflicts with total-age optimization.