Source-linked AI summary
Status updates through M/G/1/1 queues with HARQ
Elie Najm, Roy D. Yates, Emina Soljanin
TL;DR
The paper studies how to manage updates when an M/G/1/1 system can serve only one update without buffering. It derives average-age results for general service times and applies them to IIR and FR HARQ over erasure channels. Across the studied HARQ settings, not preempting the current update is better, and IIR provides better age performance than FR.
Problem
The paper asks whether preemption is optimal in M/G/1/1 systems with general service times, beyond cases where exponential service favors preemption.
Method
The paper derives average-age expressions for blocking and preemptive M/G/1/1 models, then applies them to IIR and FR HARQ over symbol erasure channels.
Results
For both HARQ protocols, the M/G/1/1 blocking system performs better than the preemptive system, while IIR performs better than FR from an age perspective.
Takeaways & Limitations
The supported strategy is to prioritize the update currently being transmitted rather than preempt it; reliable delivery using large FR codewords does not achieve optimal average age.
Abstract
from arXiv · showhide
We consider a system where randomly generated updates are to be transmitted to a monitor, but only a single update can be in the transmission service at a time. Therefore, the source has to prioritize between the two possible transmission policies: preempting the current update or discarding the new one. We consider Poisson arrivals and general service time, and refer to this system as the M/G/1/1 queue. We start by studying the average status update age and the optimal update arrival rate for these two schemes under general service time distribution. We then apply these results on two practical scenarios in which updates are sent through an erasure channel using (a) an infinite incremental redundancy (IIR) HARQ system and (b) a fixed redundancy (FR) HARQ system. We show that in both schemes the best strategy would be not to preempt. Moreover, we also prove that, from an age point of view, IIR is better than FR.
I. INTRODUCTION
The paper studies freshness in an M/G/1/1 system where Poisson updates compete for a single transmission service without buffering. It compares preemption with discarding new arrivals and applies the analysis to IIR and FR HARQ over erasure channels.
- Age metric: Age of Information measures the freshness of updates using the time average of the instantaneous age at the monitor.The instantaneous age increases linearly until a successful reception produces a sawtooth age trajectory.
- System model: The M/G/1/1 system admits one update in service and must choose whether to preempt it or discard a newly generated update when busy.Updates arrive according to a Poisson process, and service times are generally distributed.
- Research question: The study addresses whether preemption remains preferable beyond exponential service times, since gamma-distributed service may favor another policy.Prior work found preemption best for exponential service times, while other results questioned its optimality for gamma service.
- HARQ setting: The paper analyzes IIR and FR HARQ protocols for updates sent through a symbol erasure channel.IIR uses rateless coding until K unerased symbols arrive, whereas FR divides each update into packets protected by MDS codes.
- Paper roadmap: The analysis derives average-age expressions for blocking and preemptive models and compares their performance across the two HARQ protocols.The paper also studies the existence of an optimal FR codeword length for fixed arrival rate.
- Main findings: In both HARQ settings, prioritizing the update already in service outperforms preempting it.The paper’s conclusion also reports that IIR has better age performance than FR.
A. Average age calculation
This section derives the average age of the M/G/1/1 blocking system using renewal periods and geometric areas under the instantaneous-age curve. The resulting expression is stated in terms of the service-time distribution and traffic parameters.
- Renewal representation: The successful-update process forms a renewal process because residual interarrival times are exponential and independent of preceding renewal intervals.Memoryless interarrival times make the renewal intervals identically distributed.
- Average-age formula: Theorem 1 gives the average age for an M/G/1/1 blocking system in terms of service-time moments and traffic-related quantities.The expression introduces the service-time variability measure C_S and parameters ρ and β.
- Age calculation: Average age is computed as the long-run sum of geometric areas under the instantaneous-age curve.The calculation uses the renewal interval and the associated trapezoidal area.
B. Finding the optimal arrival rate
This section identifies the update arrival rate that minimizes average age in the blocking model. The optimizer depends on service-time variability, while some distributions make age decrease continually as the arrival rate grows.
- Optimization objective: The arrival rate λ can be controlled to seek the minimum average age.The optimization is performed using the average-age expression for the blocking system.
- Optimal rate: Theorem 2 specifies an optimal arrival-rate condition for the M/G/1/1 blocking system.The condition is obtained by setting the derivative of the average age with respect to the relevant traffic parameter to zero.
- Service-time variability: When service-time variability satisfies C_S ≤ 1, average age strictly decreases with λ and its minimum is attained as λ →∞.In this regime there is no finite minimizing arrival rate.
- HARQ application: For IIR and FR blocking systems, the paper applies the general optimization results to erasure-channel HARQ models.The two protocols are evaluated under symbol erasures with rate δ.
A. Infinite Incremental Redundancy
The IIR-HARQ model treats service as the channel uses required to collect enough unerased symbols for decoding. The blocking average age and its limiting optimum are then obtained from the general M/G/1/1 result.
- IIR service model: IIR transmission ends after the monitor receives k_s unerased symbols, so its service time is negative binomial with success probability 1−δ.Updates arriving while the system is busy are discarded.
- Optimal arrival rate: For the IIR blocking model, the minimum average age is achieved as λ →∞.The limiting value follows by applying the general optimal-rate result to the IIR service distribution.
B. Fixed Redundancy
The fixed-redundancy HARQ scheme uses packet- and physical-layer coding, with updates decoded after enough packets succeed. Its blocking-queue age is minimized as the update arrival rate grows without bound.
- Fixed Redundancy: FR-HARQ applies packet-level rateless coding and physical-layer MDS coding to each update.An update contains k_p packets, each carrying k_s information symbols and encoded into n_s symbols; at least k_s unerased symbols are needed to decode a packet.
- Fixed Redundancy: Theorem 4 gives the average age of the M/G/1/1 FR-HARQ blocking system.
- Fixed Redundancy: The minimum average age is achieved as λ →∞, with its limiting value obtained from the FR age expression.
- Fixed Redundancy: The FR service time is S = n_sM, where M is negative binomial with k_p successes and success probability 1 − ϵ_p.The mean and variance of S follow from the distribution of M.
V. M/G/1/1 WITH PREEMPTION
The preemptive M/G/1/1 model gives newly generated updates priority over updates in service. Its queue is represented by a two-state semi-Markov chain, and its average age depends on the service-time Laplace transform.
- M/G/1/1 with Preemption: Preemption replaces the packet in service whenever a new packet arrives, giving priority to the newly generated update.The queue has no more than one packet in service, and the preemptive and blocking models assign priority to opposite updates.
- M/G/1/1 with Preemption: The queue is modeled as a two-state semi-Markov chain: state 0 is empty, while state 1 serves one packet.From state 1, service completion returns the process to state 0; a new arrival leaves it in state 1 under preemption.
- M/G/1/1 with Preemption: The transition from the serving state to the empty state occurs with probability p = P(S < X), where X is an independent exponential interarrival time.The service-time distribution determines the probability that service completes before the next arrival.
- M/G/1/1 with Preemption: The average age is derived from the system time T and interdeparture time Y using the instantaneous-age process.The derivation obtains moments of T and Y, including the moment-generating function of Y.
- M/G/1/1 with Preemption: For preemption, the average age depends on the Laplace transform of the service-time distribution.Theorem 5 provides the average-age expression, and the paper states this dependence explicitly.
VI. M/G/1/1 WITH PREEMPTION AND HARQ
This section studies how IIR and FR HARQ affect average age in a preemptive M/G/1/1 queue over a symbol-erasure channel.
- M/G/1/1 with Preemption and HARQ: The preemptive HARQ analysis assumes a symbol-erasure channel with erasure rate δ and considers IIR and FR protocols.
A. Infinite Incremental Redundancy
Under preemption, IIR service ends when either enough unerased symbols arrive or a new update is generated. The section derives its average age and the arrival-rate condition for minimizing it.
- Infinite Incremental Redundancy: Under IIR preemption, transmission ends when k_s symbols are successfully received or a new update arrives, whichever occurs first.
- Infinite Incremental Redundancy: Theorem 6 gives the average age of a preemptive M/G/1/1 system using IIR.
- Infinite Incremental Redundancy: The IIR average age has a minimizing arrival rate λ* that satisfies the condition stated in the section.The condition is obtained by differentiating the average-age expression with respect to λ.
- Infinite Incremental Redundancy: The IIR service time follows a negative-binomial distribution with parameters k_s and 1 − δ.Its support is {k_s, k_s + 1, …}, reflecting the number of transmissions needed to collect k_s unerased symbols.
- Infinite Incremental Redundancy: The minimizing IIR arrival rate generally requires solving an equation without a simple closed form, so a small-λ approximation is also provided.The approximation uses e^λ* ≈ 1 + λ* to reduce the optimization equation.
B. Fixed Redundancy
The FR policy's average age is derived for the preemptive M/G/1/1 system, together with conditions characterizing its minimizing arrival rate and supporting approximations.
- Theorem 7 gives the average information age for an M/G/1/1 system with preemption using the FR policy.
- The minimizing arrival rate λ* for ΔPFR must satisfy the stated condition obtained from the age expression.
- The FR service time is modeled as S = nsM, where M is negative binomial with kp successes and success probability 1 − ϵp.
- For kp ≤ 1, the lower bound in (44) is a tight approximation for typical values of kp.
VII. NUMERICAL RESULTS
The numerical results compare FR packetization, packet length, HARQ policies, and queue management, showing optimal packet lengths and better age performance for IIR and blocking.
- Preemption: With optimal ns, FR average age increases as the number of packets per update increases, while IIR outperforms FR across choices of ks and ns.
- Preemption: For preemption, ΔPIIR and ΔPFR attain minima at small λ values, and FR has an optimal packet length ns.
- Preemption: For fixed λ, FR packet length should be neither too small nor too large, and the optimal ns increases as erasure rate δ increases.
- Blocking: In the blocking system, average age decreases with λ, increases with the number of packets per update, and has an optimal packet length ns.
- Queue-management comparison: Across all λ values, the M/G/1/1 blocking system performs better than the preemptive counterpart for both HARQ policies.
VIII. CONCLUSION
The paper derives average-age results for preemptive and blocking M/G/1/1 systems and applies them to IIR and FR HARQ over erasure channels. The conclusion favors blocking and IIR from an age perspective, while noting that highly reliable FR packets are not optimal.
- The paper derives general average-age expressions for preemptive and blocking M/G/1/1 systems and applies them to IIR and FR HARQ.
- The numerical comparisons include FR-HARQ under preemption and blocking, as well as comparisons between IIR and FR.
- For FR, ensuring reliable delivery of every update packet with large codeword length ns does not achieve the optimal average age.